|
1 /*** Copyright 1989 Norbert Schlenker. All rights reserved. |
|
2 |
|
3 *** This software is distributed subject to the following provisions: |
|
4 *** - this notice may not be removed; |
|
5 *** - you may modify the source code, as long as redistributed |
|
6 *** versions have their modifications clearly marked; |
|
7 *** - no charge, other than a nominal copying fee, may be made |
|
8 *** when providing copies of this source code to others; |
|
9 *** - if this source code is used as part of a product which is |
|
10 *** distributed only as a binary, a copy of this source code |
|
11 *** must be included in the distribution. |
|
12 *** |
|
13 *** Unlike the GNU GPL, use of this code does not obligate you to |
|
14 *** disclose your own proprietary source code. |
|
15 |
|
16 *** The author of this software provides no warranty, express or |
|
17 *** implied, as to its utility or correctness. That said, reports |
|
18 *** of bugs or compatibility problems will be gladly received by |
|
19 *** nfs@princeton.edu, and fixes will be attempted. |
|
20 ***/ |
|
21 |
|
22 |
|
23 /*** index.c - routines to manipulate index lists */ |
|
24 |
|
25 /*** Definition: An "index list" is an ascending sequence of positive |
|
26 *** integers that can be operated upon as follows: |
|
27 *** |
|
28 *** make_index_list - makes an index list of consecutive |
|
29 *** integers from some lower bound through an upper bound. |
|
30 *** choose_index - given a number "k", removes the integer |
|
31 *** in the k'th position in the index list and returns it. |
|
32 *** Requests for positions less than 1 or greater than |
|
33 *** the current list length return zero. |
|
34 *** remove_index - removes a specified integer from the |
|
35 *** index list. Requests to remove integers not in the |
|
36 *** list are ignored, except that they reduce the list's |
|
37 *** "pseudo_size" (see below). |
|
38 *** index_size - returns the number of integers in the |
|
39 *** index list. |
|
40 *** pseudo_size - returns the number of integers in the |
|
41 *** index list, less the number for which remove_index |
|
42 *** failed due to a request to remove a non-existent one. |
|
43 *** (Note that this is here solely to support an apparent |
|
44 *** bug in the original definition of the NETGEN program.) |
|
45 |
|
46 *** Two simple methods of accomplishing these functions are: |
|
47 *** - allocating an array of flags that indicate whether a particular |
|
48 *** integer is valid, and searching the array during the choose_index |
|
49 *** operation for the k'th valid integer. |
|
50 *** - allocating a linked list for the indices and updating the list |
|
51 *** during both the choose_index and remove_index operations. |
|
52 *** |
|
53 *** For small index lists, the first of these methods is quite efficient |
|
54 *** and is, in fact, implemented in the following code. Unfortunately, |
|
55 *** for the uses we have in mind (i.e. NETGEN), the typical access pattern |
|
56 *** to index lists involves a large list, with both choose_index and |
|
57 *** remove_index operations occurring at random positions in the list. |
|
58 *** |
|
59 *** As a result, the code has been extended for the case of large lists. |
|
60 *** The enclosed implementation makes use of a binary interval tree, which |
|
61 *** records information regarding the valid intervals from which indices |
|
62 *** may be chosen. At a cost of a substantial increase in space requirements, |
|
63 *** and under rather generous assumptions regarding the randomness of the |
|
64 *** positions supplied to choose_index, running time becomes logarithmic |
|
65 *** per choose_index and remove_index operation. |
|
66 ***/ |
|
67 |
|
68 #include "netgen.h" |
|
69 |
|
70 /*** Useful constants */ |
|
71 #define FLAG_LIMIT 100 /* upper limit for simple implementation */ |
|
72 |
|
73 |
|
74 /*** Internally useful types */ |
|
75 typedef unsigned char FLAG; |
|
76 |
|
77 typedef struct index_header { |
|
78 INDEX original_size; /* original size of index */ |
|
79 INDEX index_size; /* number of indices in the index */ |
|
80 INDEX pseudo_size; /* almost the number of indices in the index */ |
|
81 union { |
|
82 INDEX index_base; /* base of index list - small case */ |
|
83 INDEX index_nodes; /* number of nodes in the interval tree - large case */ |
|
84 } i; |
|
85 union { |
|
86 FLAG* flag; /* pointer to flag array - small */ |
|
87 struct interval_node* first_node; /* pointer to root of interval tree - large */ |
|
88 } p; |
|
89 } HEADER; |
|
90 |
|
91 typedef struct interval_node { |
|
92 INDEX base; /* smallest integer in this subtree */ |
|
93 INDEX count; /* count of indices in this subtree */ |
|
94 struct interval_node* left_child; /* pointers down the tree */ |
|
95 } INODE; |
|
96 |
|
97 |
|
98 /*** Static storage */ |
|
99 |
|
100 static INDEX_LIST active_handles = 0; |
|
101 static HEADER* index_headers = NULL; |
|
102 |
|
103 |
|
104 /*** Make a new index list with a specified range. Returns an integer handle |
|
105 *** to identify the list, or -1 if an error occurs. |
|
106 ***/ |
|
107 INDEX_LIST make_index_list(from, to) |
|
108 INDEX from; /* lower limit of index list */ |
|
109 INDEX to; /* upper limit of index list */ |
|
110 { |
|
111 INDEX_LIST handle = 0; |
|
112 HEADER* hp; |
|
113 INODE* np; |
|
114 |
|
115 if (from <= 0 || from > to) /* sanity check */ |
|
116 return -1; |
|
117 |
|
118 /*** Find an inactive list header or allocate a new one. */ |
|
119 for (hp = index_headers; handle < active_handles; hp++, handle++) { |
|
120 if (hp->original_size == 0) |
|
121 break; |
|
122 } |
|
123 if (handle == active_handles) { |
|
124 ++active_handles; |
|
125 if (handle == 0) |
|
126 index_headers = (HEADER*) malloc(active_handles * sizeof(HEADER)); |
|
127 else |
|
128 index_headers = (HEADER*) realloc(index_headers, active_handles * sizeof(HEADER)); |
|
129 } |
|
130 if (index_headers == NULL) |
|
131 return -1; |
|
132 |
|
133 |
|
134 /*** Fill in the list header and allocate space for the list. */ |
|
135 hp = &index_headers[handle]; |
|
136 hp->pseudo_size = hp->index_size = hp->original_size = to - from + 1; |
|
137 if (hp->original_size <= FLAG_LIMIT) { /* SMALL */ |
|
138 hp->i.index_base = from; |
|
139 hp->p.flag = (FLAG*) malloc(hp->original_size * sizeof(FLAG)); |
|
140 if (hp->p.flag == NULL) |
|
141 return -1; |
|
142 (void)memset((void *)hp->p.flag, 0, hp->original_size * sizeof(FLAG)); |
|
143 } else { /* LARGE */ |
|
144 hp->i.index_nodes = 1; |
|
145 np = (INODE*) malloc(hp->original_size * sizeof(INODE)); |
|
146 if (np == NULL) |
|
147 return -1; |
|
148 hp->p.first_node = np; |
|
149 np->base = from; |
|
150 np->count = hp->original_size; |
|
151 np->left_child = NULL; |
|
152 } |
|
153 return handle; |
|
154 } |
|
155 |
|
156 |
|
157 /*** Free an existing index list. The header is zeroed afterwards |
|
158 *** to indicate that it can be reused. |
|
159 ***/ |
|
160 void free_index_list(handle) |
|
161 INDEX_LIST handle; |
|
162 { |
|
163 HEADER* hp; |
|
164 |
|
165 if (handle < 0 || handle >= active_handles) /* sanity check */ |
|
166 return; |
|
167 |
|
168 hp = &index_headers[handle]; |
|
169 if (hp->p.flag) |
|
170 free((void *)hp->p.flag); |
|
171 (void)memset((void *)hp, 0, sizeof(HEADER)); |
|
172 } |
|
173 |
|
174 /*** Choose the integer at a certain position in an index list. The |
|
175 *** integer is then removed from the list so that it won't be chosen |
|
176 *** again. Choose_index returns 0 if the position is invalid. |
|
177 ***/ |
|
178 INDEX choose_index(handle, position) |
|
179 INDEX_LIST handle; |
|
180 INDEX position; |
|
181 { |
|
182 HEADER* hp; |
|
183 FLAG* cp; |
|
184 INODE* np; |
|
185 INODE* npl; |
|
186 INODE* npr; |
|
187 INDEX index; |
|
188 |
|
189 if (handle < 0 || handle >= active_handles) /* sanity checks */ |
|
190 return 0; |
|
191 hp = &index_headers[handle]; |
|
192 if (hp->p.flag == NULL) |
|
193 return 0; |
|
194 if (position < 1 || position > hp->index_size) |
|
195 return 0; |
|
196 |
|
197 /*** Adjust counts of remaining indices. */ |
|
198 hp->index_size--; |
|
199 hp->pseudo_size--; |
|
200 |
|
201 |
|
202 /*** Find the index we want and remove it from the list. */ |
|
203 if (hp->original_size <= FLAG_LIMIT) { /* SMALL */ |
|
204 for (cp = hp->p.flag; position > 0; cp++) |
|
205 if (!*cp) |
|
206 position--; |
|
207 *(--cp) = 1; |
|
208 return hp->i.index_base + (INDEX)(cp - hp->p.flag); |
|
209 } else { /* LARGE */ |
|
210 np = hp->p.first_node; |
|
211 while (np->left_child) { |
|
212 np->count--; |
|
213 np = np->left_child; |
|
214 if (position > np->count) { |
|
215 position -= np->count; |
|
216 np++; |
|
217 } |
|
218 } |
|
219 np->count--; |
|
220 if (position == 1) { /* beginning of interval */ |
|
221 index = np->base++; |
|
222 } |
|
223 else |
|
224 if (position > np->count) { /* end of interval */ |
|
225 index = np->base + np->count; |
|
226 } |
|
227 else /* middle of interval - split it */ |
|
228 { |
|
229 index = np->base + position - 1; |
|
230 npl = np->left_child = hp->p.first_node + hp->i.index_nodes; |
|
231 npr = npl + 1; |
|
232 hp->i.index_nodes += 2; |
|
233 npl->base = np->base; |
|
234 npl->count = position - 1; |
|
235 npl->left_child = NULL; |
|
236 npr->base = index + 1; |
|
237 npr->count = np->count - npl->count; |
|
238 npr->left_child = NULL; |
|
239 } |
|
240 return index; |
|
241 } |
|
242 } |
|
243 |
|
244 /*** Remove a particular integer from an index list. If the integer |
|
245 *** does not exist in the list, we reduce the list's pseudo-size, |
|
246 *** but return no error indication. |
|
247 ***/ |
|
248 void remove_index(handle, index) |
|
249 INDEX_LIST handle; |
|
250 INDEX index; |
|
251 { |
|
252 HEADER* hp; |
|
253 FLAG* cp; |
|
254 INODE* np; |
|
255 INODE* npl; |
|
256 INODE* npr; |
|
257 |
|
258 if (handle < 0 || handle >= active_handles) /* sanity checks */ |
|
259 return; |
|
260 hp = &index_headers[handle]; |
|
261 if (hp->p.flag == NULL) |
|
262 return; |
|
263 |
|
264 /*** Adjust the pseudo-size before looking for the index. */ |
|
265 hp->pseudo_size--; |
|
266 |
|
267 /*** Remove the index from the index list. */ |
|
268 if (hp->original_size <= FLAG_LIMIT) { /* SMALL */ |
|
269 if (index < hp->i.index_base || index >= hp->i.index_base + hp->original_size) |
|
270 return; |
|
271 cp = hp->p.flag + (index - hp->i.index_base); |
|
272 if (!*cp) { |
|
273 *cp = 1; |
|
274 hp->index_size--; |
|
275 } |
|
276 return; |
|
277 } else { /* LARGE */ |
|
278 np = hp->p.first_node; |
|
279 while (np->left_child) { |
|
280 np->count--; |
|
281 np = np->left_child + 1; |
|
282 if (index < np->base) |
|
283 np--; |
|
284 } |
|
285 if (index < np->base || index >= np->base + np->count) { /* mistake - back out */ |
|
286 np = hp->p.first_node; |
|
287 while (np->left_child) { |
|
288 np->count++; |
|
289 np = np->left_child + 1; |
|
290 if (index < np->base) |
|
291 np--; |
|
292 } |
|
293 return; |
|
294 } |
|
295 np->count--; |
|
296 if (index == np->base) { /* beginning of interval */ |
|
297 np->base++; |
|
298 } |
|
299 else |
|
300 if (index == np->base + np->count) { /* end of interval */ |
|
301 } |
|
302 else /* middle of interval - split it */ |
|
303 { |
|
304 npl = np->left_child = hp->p.first_node + hp->i.index_nodes; |
|
305 npr = npl + 1; |
|
306 hp->i.index_nodes += 2; |
|
307 npl->base = np->base; |
|
308 npl->count = index - np->base; |
|
309 npl->left_child = NULL; |
|
310 npr->base = index + 1; |
|
311 npr->count = np->count - npl->count; |
|
312 npr->left_child = NULL; |
|
313 } |
|
314 hp->index_size--; |
|
315 return; |
|
316 } |
|
317 } |
|
318 |
|
319 |
|
320 /*** Return actual number of remaining entries in the index list. |
|
321 ***/ |
|
322 INDEX index_size(handle) |
|
323 INDEX_LIST handle; |
|
324 { |
|
325 if (handle < 0 || handle >= active_handles) /* sanity check */ |
|
326 return 0; |
|
327 |
|
328 return index_headers[handle].index_size; |
|
329 } |
|
330 |
|
331 |
|
332 /*** Return a peculiar number, vaguely related to the number of |
|
333 *** remaining entries in the index list. Required by NETGEN. |
|
334 ***/ |
|
335 INDEX pseudo_size(handle) |
|
336 INDEX_LIST handle; |
|
337 { |
|
338 if (handle < 0 || handle >= active_handles) /* sanity check */ |
|
339 return 0; |
|
340 |
|
341 return index_headers[handle].pseudo_size; |
|
342 } |