1 /*-----------------------------------------------------------------------
2
3 File : clb_pqueues.c
4
5 Author: Stephan Schulz
6
7 Contents
8
9 LIFO-Lists of pointers and (long) integers.
10
11 Copyright 1998, 1999 by the author.
12 This code is released under the GNU General Public Licence and
13 the GNU Lesser General Public License.
14 See the file COPYING in the main E directory for details..
15 Run "eprover -h" for contact information.
16
17 Changes
18
19 <1> Tue Jun 30 17:34:19 MET DST 1998
20 New
21
22 -----------------------------------------------------------------------*/
23
24 #include "clb_pqueue.h"
25
26
27
28 /*---------------------------------------------------------------------*/
29 /* Global Variables */
30 /*---------------------------------------------------------------------*/
31
32
33 /*---------------------------------------------------------------------*/
34 /* Forward Declarations */
35 /*---------------------------------------------------------------------*/
36
37
38 /*---------------------------------------------------------------------*/
39 /* Internal Functions */
40 /*---------------------------------------------------------------------*/
41
42
43 /*---------------------------------------------------------------------*/
44 /* Exported Functions */
45 /*---------------------------------------------------------------------*/
46
47 /*-----------------------------------------------------------------------
48 //
49 // Function: PQueueGrow()
50 //
51 // Increase the size of queue.
52 //
53 // Global Variables: -
54 //
55 // Side Effects : Memory operations.
56 //
57 /----------------------------------------------------------------------*/
58
PQueueGrow(PQueue_p queue)59 void PQueueGrow(PQueue_p queue)
60 {
61 long new_size, i;
62 IntOrP *new_mem;
63
64 new_size = queue->size*2;
65 new_mem = SizeMalloc(new_size*sizeof(IntOrP));
66
67 for(i=0; i<queue->head; i++)
68 {
69 new_mem[i] = queue->queue[i];
70 }
71 for(i=queue->head; i<queue->size; i++)
72 {
73 new_mem[i+queue->size] = queue->queue[i];
74 }
75 queue->tail+= queue->size;
76 SizeFree(queue->queue, queue->size*sizeof(IntOrP));
77 queue->queue = new_mem;
78 queue->size = new_size;
79 }
80
81
82 /*-----------------------------------------------------------------------
83 //
84 // Function: PQueueCardinality()
85 //
86 // Return the number of elements in the queue.
87 //
88 // Global Variables: -
89 //
90 // Side Effects : -
91 /
92 /----------------------------------------------------------------------*/
93
PQueueCardinality(PQueue_p queue)94 long PQueueCardinality(PQueue_p queue)
95 {
96 long res;
97 if(queue->head>=queue->tail)
98 {
99 res = queue->head-queue->tail;
100 }
101 else
102 {
103 res = queue->tail+(queue->size-queue->head);
104 }
105 /* printf("Card(%ld, %ld) = %ld\n", queue->head, queue->tail,
106 res); */
107 return res;
108 }
109
110
111 /*-----------------------------------------------------------------------
112 //
113 // Function: PQueueElement()
114 //
115 // Retutn the entry at absolute index index.
116 //
117 // Global Variables: -
118 //
119 // Side Effects : -
120 //
121 /----------------------------------------------------------------------*/
122
PQueueElement(PQueue_p queue,long index)123 IntOrP PQueueElement(PQueue_p queue, long index)
124 {
125 return queue->queue[index];
126 }
127
128
129 /*-----------------------------------------------------------------------
130 //
131 // Function: PQueueTailIndex()
132 //
133 // Return the index of the tail (oldest, last) element (or -1 if the
134 // queue is empty).
135 //
136 // Global Variables:
137 //
138 // Side Effects :
139 //
140 /----------------------------------------------------------------------*/
141
PQueueTailIndex(PQueue_p queue)142 long PQueueTailIndex(PQueue_p queue)
143 {
144 if(PQueueEmpty(queue))
145 {
146 return -1;
147 }
148 return queue->tail;
149 }
150
151 /*-----------------------------------------------------------------------
152 //
153 // Function: PQueueIncIndex()
154 //
155 // Given an index to a (used) element in the queue, return a similar
156 // index to to next element (or -1 if there is no next element).
157 //
158 // Global Variables: -
159 //
160 // Side Effects : -
161 //
162 /----------------------------------------------------------------------*/
163
PQueueIncIndex(PQueue_p queue,long index)164 long PQueueIncIndex(PQueue_p queue, long index)
165 {
166 index = (index+1) % queue->size;
167 if(index == queue->head)
168 {
169 return -1;
170 }
171 return index;
172 }
173
174
175
176 /*---------------------------------------------------------------------*/
177 /* End of File */
178 /*---------------------------------------------------------------------*/
179
180
181