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 | } |
---|