COIN-OR::LEMON - Graph Library

source: lemon-benchmark/generators/netgen/index.c @ 6:a3ef33a8694a

Last change on this file since 6:a3ef33a8694a was 6:a3ef33a8694a, checked in by Alpar Juttner <alpar@…>, 14 years ago

Add netgen generator

File size: 10.6 KB
Line 
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 */
75typedef unsigned char FLAG;
76
77typedef 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
91typedef 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
100static INDEX_LIST active_handles = 0;
101static 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 ***/
107INDEX_LIST make_index_list(from, to)
108INDEX from;                     /* lower limit of index list */
109INDEX 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 ***/
160void free_index_list(handle)
161INDEX_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 ***/
178INDEX choose_index(handle, position)
179INDEX_LIST handle;
180INDEX 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 ***/
248void remove_index(handle, index)
249INDEX_LIST handle;
250INDEX 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 ***/
322INDEX index_size(handle)
323INDEX_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 ***/
335INDEX pseudo_size(handle)
336INDEX_LIST handle;
337{
338  if (handle < 0 || handle >= active_handles)   /* sanity check */
339    return 0;
340
341  return index_headers[handle].pseudo_size;
342}
Note: See TracBrowser for help on using the repository browser.