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