1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/generators/netgen/index.c Fri Nov 26 19:23:47 2010 +0100
1.3 @@ -0,0 +1,342 @@
1.4 +/*** Copyright 1989 Norbert Schlenker. All rights reserved.
1.5 +
1.6 + *** This software is distributed subject to the following provisions:
1.7 + *** - this notice may not be removed;
1.8 + *** - you may modify the source code, as long as redistributed
1.9 + *** versions have their modifications clearly marked;
1.10 + *** - no charge, other than a nominal copying fee, may be made
1.11 + *** when providing copies of this source code to others;
1.12 + *** - if this source code is used as part of a product which is
1.13 + *** distributed only as a binary, a copy of this source code
1.14 + *** must be included in the distribution.
1.15 + ***
1.16 + *** Unlike the GNU GPL, use of this code does not obligate you to
1.17 + *** disclose your own proprietary source code.
1.18 +
1.19 + *** The author of this software provides no warranty, express or
1.20 + *** implied, as to its utility or correctness. That said, reports
1.21 + *** of bugs or compatibility problems will be gladly received by
1.22 + *** nfs@princeton.edu, and fixes will be attempted.
1.23 + ***/
1.24 +
1.25 +
1.26 +/*** index.c - routines to manipulate index lists */
1.27 +
1.28 +/*** Definition: An "index list" is an ascending sequence of positive
1.29 + *** integers that can be operated upon as follows:
1.30 + ***
1.31 + *** make_index_list - makes an index list of consecutive
1.32 + *** integers from some lower bound through an upper bound.
1.33 + *** choose_index - given a number "k", removes the integer
1.34 + *** in the k'th position in the index list and returns it.
1.35 + *** Requests for positions less than 1 or greater than
1.36 + *** the current list length return zero.
1.37 + *** remove_index - removes a specified integer from the
1.38 + *** index list. Requests to remove integers not in the
1.39 + *** list are ignored, except that they reduce the list's
1.40 + *** "pseudo_size" (see below).
1.41 + *** index_size - returns the number of integers in the
1.42 + *** index list.
1.43 + *** pseudo_size - returns the number of integers in the
1.44 + *** index list, less the number for which remove_index
1.45 + *** failed due to a request to remove a non-existent one.
1.46 + *** (Note that this is here solely to support an apparent
1.47 + *** bug in the original definition of the NETGEN program.)
1.48 +
1.49 + *** Two simple methods of accomplishing these functions are:
1.50 + *** - allocating an array of flags that indicate whether a particular
1.51 + *** integer is valid, and searching the array during the choose_index
1.52 + *** operation for the k'th valid integer.
1.53 + *** - allocating a linked list for the indices and updating the list
1.54 + *** during both the choose_index and remove_index operations.
1.55 + ***
1.56 + *** For small index lists, the first of these methods is quite efficient
1.57 + *** and is, in fact, implemented in the following code. Unfortunately,
1.58 + *** for the uses we have in mind (i.e. NETGEN), the typical access pattern
1.59 + *** to index lists involves a large list, with both choose_index and
1.60 + *** remove_index operations occurring at random positions in the list.
1.61 + ***
1.62 + *** As a result, the code has been extended for the case of large lists.
1.63 + *** The enclosed implementation makes use of a binary interval tree, which
1.64 + *** records information regarding the valid intervals from which indices
1.65 + *** may be chosen. At a cost of a substantial increase in space requirements,
1.66 + *** and under rather generous assumptions regarding the randomness of the
1.67 + *** positions supplied to choose_index, running time becomes logarithmic
1.68 + *** per choose_index and remove_index operation.
1.69 + ***/
1.70 +
1.71 +#include "netgen.h"
1.72 +
1.73 +/*** Useful constants */
1.74 +#define FLAG_LIMIT 100 /* upper limit for simple implementation */
1.75 +
1.76 +
1.77 +/*** Internally useful types */
1.78 +typedef unsigned char FLAG;
1.79 +
1.80 +typedef struct index_header {
1.81 + INDEX original_size; /* original size of index */
1.82 + INDEX index_size; /* number of indices in the index */
1.83 + INDEX pseudo_size; /* almost the number of indices in the index */
1.84 + union {
1.85 + INDEX index_base; /* base of index list - small case */
1.86 + INDEX index_nodes; /* number of nodes in the interval tree - large case */
1.87 + } i;
1.88 + union {
1.89 + FLAG* flag; /* pointer to flag array - small */
1.90 + struct interval_node* first_node; /* pointer to root of interval tree - large */
1.91 + } p;
1.92 +} HEADER;
1.93 +
1.94 +typedef struct interval_node {
1.95 + INDEX base; /* smallest integer in this subtree */
1.96 + INDEX count; /* count of indices in this subtree */
1.97 + struct interval_node* left_child; /* pointers down the tree */
1.98 +} INODE;
1.99 +
1.100 +
1.101 +/*** Static storage */
1.102 +
1.103 +static INDEX_LIST active_handles = 0;
1.104 +static HEADER* index_headers = NULL;
1.105 +
1.106 +
1.107 +/*** Make a new index list with a specified range. Returns an integer handle
1.108 + *** to identify the list, or -1 if an error occurs.
1.109 + ***/
1.110 +INDEX_LIST make_index_list(from, to)
1.111 +INDEX from; /* lower limit of index list */
1.112 +INDEX to; /* upper limit of index list */
1.113 +{
1.114 + INDEX_LIST handle = 0;
1.115 + HEADER* hp;
1.116 + INODE* np;
1.117 +
1.118 + if (from <= 0 || from > to) /* sanity check */
1.119 + return -1;
1.120 +
1.121 +/*** Find an inactive list header or allocate a new one. */
1.122 + for (hp = index_headers; handle < active_handles; hp++, handle++) {
1.123 + if (hp->original_size == 0)
1.124 + break;
1.125 + }
1.126 + if (handle == active_handles) {
1.127 + ++active_handles;
1.128 + if (handle == 0)
1.129 + index_headers = (HEADER*) malloc(active_handles * sizeof(HEADER));
1.130 + else
1.131 + index_headers = (HEADER*) realloc(index_headers, active_handles * sizeof(HEADER));
1.132 + }
1.133 + if (index_headers == NULL)
1.134 + return -1;
1.135 +
1.136 +
1.137 +/*** Fill in the list header and allocate space for the list. */
1.138 + hp = &index_headers[handle];
1.139 + hp->pseudo_size = hp->index_size = hp->original_size = to - from + 1;
1.140 + if (hp->original_size <= FLAG_LIMIT) { /* SMALL */
1.141 + hp->i.index_base = from;
1.142 + hp->p.flag = (FLAG*) malloc(hp->original_size * sizeof(FLAG));
1.143 + if (hp->p.flag == NULL)
1.144 + return -1;
1.145 + (void)memset((void *)hp->p.flag, 0, hp->original_size * sizeof(FLAG));
1.146 + } else { /* LARGE */
1.147 + hp->i.index_nodes = 1;
1.148 + np = (INODE*) malloc(hp->original_size * sizeof(INODE));
1.149 + if (np == NULL)
1.150 + return -1;
1.151 + hp->p.first_node = np;
1.152 + np->base = from;
1.153 + np->count = hp->original_size;
1.154 + np->left_child = NULL;
1.155 + }
1.156 + return handle;
1.157 +}
1.158 +
1.159 +
1.160 +/*** Free an existing index list. The header is zeroed afterwards
1.161 + *** to indicate that it can be reused.
1.162 + ***/
1.163 +void free_index_list(handle)
1.164 +INDEX_LIST handle;
1.165 +{
1.166 + HEADER* hp;
1.167 +
1.168 + if (handle < 0 || handle >= active_handles) /* sanity check */
1.169 + return;
1.170 +
1.171 + hp = &index_headers[handle];
1.172 + if (hp->p.flag)
1.173 + free((void *)hp->p.flag);
1.174 + (void)memset((void *)hp, 0, sizeof(HEADER));
1.175 +}
1.176 +
1.177 +/*** Choose the integer at a certain position in an index list. The
1.178 + *** integer is then removed from the list so that it won't be chosen
1.179 + *** again. Choose_index returns 0 if the position is invalid.
1.180 + ***/
1.181 +INDEX choose_index(handle, position)
1.182 +INDEX_LIST handle;
1.183 +INDEX position;
1.184 +{
1.185 + HEADER* hp;
1.186 + FLAG* cp;
1.187 + INODE* np;
1.188 + INODE* npl;
1.189 + INODE* npr;
1.190 + INDEX index;
1.191 +
1.192 + if (handle < 0 || handle >= active_handles) /* sanity checks */
1.193 + return 0;
1.194 + hp = &index_headers[handle];
1.195 + if (hp->p.flag == NULL)
1.196 + return 0;
1.197 + if (position < 1 || position > hp->index_size)
1.198 + return 0;
1.199 +
1.200 +/*** Adjust counts of remaining indices. */
1.201 + hp->index_size--;
1.202 + hp->pseudo_size--;
1.203 +
1.204 +
1.205 +/*** Find the index we want and remove it from the list. */
1.206 + if (hp->original_size <= FLAG_LIMIT) { /* SMALL */
1.207 + for (cp = hp->p.flag; position > 0; cp++)
1.208 + if (!*cp)
1.209 + position--;
1.210 + *(--cp) = 1;
1.211 + return hp->i.index_base + (INDEX)(cp - hp->p.flag);
1.212 + } else { /* LARGE */
1.213 + np = hp->p.first_node;
1.214 + while (np->left_child) {
1.215 + np->count--;
1.216 + np = np->left_child;
1.217 + if (position > np->count) {
1.218 + position -= np->count;
1.219 + np++;
1.220 + }
1.221 + }
1.222 + np->count--;
1.223 + if (position == 1) { /* beginning of interval */
1.224 + index = np->base++;
1.225 + }
1.226 + else
1.227 + if (position > np->count) { /* end of interval */
1.228 + index = np->base + np->count;
1.229 + }
1.230 + else /* middle of interval - split it */
1.231 + {
1.232 + index = np->base + position - 1;
1.233 + npl = np->left_child = hp->p.first_node + hp->i.index_nodes;
1.234 + npr = npl + 1;
1.235 + hp->i.index_nodes += 2;
1.236 + npl->base = np->base;
1.237 + npl->count = position - 1;
1.238 + npl->left_child = NULL;
1.239 + npr->base = index + 1;
1.240 + npr->count = np->count - npl->count;
1.241 + npr->left_child = NULL;
1.242 + }
1.243 + return index;
1.244 + }
1.245 +}
1.246 +
1.247 +/*** Remove a particular integer from an index list. If the integer
1.248 + *** does not exist in the list, we reduce the list's pseudo-size,
1.249 + *** but return no error indication.
1.250 + ***/
1.251 +void remove_index(handle, index)
1.252 +INDEX_LIST handle;
1.253 +INDEX index;
1.254 +{
1.255 + HEADER* hp;
1.256 + FLAG* cp;
1.257 + INODE* np;
1.258 + INODE* npl;
1.259 + INODE* npr;
1.260 +
1.261 + if (handle < 0 || handle >= active_handles) /* sanity checks */
1.262 + return;
1.263 + hp = &index_headers[handle];
1.264 + if (hp->p.flag == NULL)
1.265 + return;
1.266 +
1.267 +/*** Adjust the pseudo-size before looking for the index. */
1.268 + hp->pseudo_size--;
1.269 +
1.270 +/*** Remove the index from the index list. */
1.271 + if (hp->original_size <= FLAG_LIMIT) { /* SMALL */
1.272 + if (index < hp->i.index_base || index >= hp->i.index_base + hp->original_size)
1.273 + return;
1.274 + cp = hp->p.flag + (index - hp->i.index_base);
1.275 + if (!*cp) {
1.276 + *cp = 1;
1.277 + hp->index_size--;
1.278 + }
1.279 + return;
1.280 + } else { /* LARGE */
1.281 + np = hp->p.first_node;
1.282 + while (np->left_child) {
1.283 + np->count--;
1.284 + np = np->left_child + 1;
1.285 + if (index < np->base)
1.286 + np--;
1.287 + }
1.288 + if (index < np->base || index >= np->base + np->count) { /* mistake - back out */
1.289 + np = hp->p.first_node;
1.290 + while (np->left_child) {
1.291 + np->count++;
1.292 + np = np->left_child + 1;
1.293 + if (index < np->base)
1.294 + np--;
1.295 + }
1.296 + return;
1.297 + }
1.298 + np->count--;
1.299 + if (index == np->base) { /* beginning of interval */
1.300 + np->base++;
1.301 + }
1.302 + else
1.303 + if (index == np->base + np->count) { /* end of interval */
1.304 + }
1.305 + else /* middle of interval - split it */
1.306 + {
1.307 + npl = np->left_child = hp->p.first_node + hp->i.index_nodes;
1.308 + npr = npl + 1;
1.309 + hp->i.index_nodes += 2;
1.310 + npl->base = np->base;
1.311 + npl->count = index - np->base;
1.312 + npl->left_child = NULL;
1.313 + npr->base = index + 1;
1.314 + npr->count = np->count - npl->count;
1.315 + npr->left_child = NULL;
1.316 + }
1.317 + hp->index_size--;
1.318 + return;
1.319 + }
1.320 +}
1.321 +
1.322 +
1.323 +/*** Return actual number of remaining entries in the index list.
1.324 + ***/
1.325 +INDEX index_size(handle)
1.326 +INDEX_LIST handle;
1.327 +{
1.328 + if (handle < 0 || handle >= active_handles) /* sanity check */
1.329 + return 0;
1.330 +
1.331 + return index_headers[handle].index_size;
1.332 +}
1.333 +
1.334 +
1.335 +/*** Return a peculiar number, vaguely related to the number of
1.336 + *** remaining entries in the index list. Required by NETGEN.
1.337 + ***/
1.338 +INDEX pseudo_size(handle)
1.339 +INDEX_LIST handle;
1.340 +{
1.341 + if (handle < 0 || handle >= active_handles) /* sanity check */
1.342 + return 0;
1.343 +
1.344 + return index_headers[handle].pseudo_size;
1.345 +}