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

/*** Copyright 1989 Norbert Schlenker.  All rights reserved.

 *** This software is distributed subject to the following provisions:
 ***    - this notice may not be removed;
 ***    - you may modify the source code, as long as redistributed
 ***      versions have their modifications clearly marked;
 ***    - no charge, other than a nominal copying fee, may be made
 ***      when providing copies of this source code to others;
 ***    - if this source code is used as part of a product which is
 ***      distributed only as a binary, a copy of this source code
 ***      must be included in the distribution.
 ***
 *** Unlike the GNU GPL, use of this code does not obligate you to
 *** disclose your own proprietary source code.

 *** The author of this software provides no warranty, express or
 *** implied, as to its utility or correctness.  That said, reports
 *** of bugs or compatibility problems will be gladly received by
 *** nfs@princeton.edu, and fixes will be attempted.
 ***/


/*** index.c - routines to manipulate index lists */

/*** Definition:  An "index list" is an ascending sequence of positive
 ***              integers that can be operated upon as follows:
 ***
 ***                 make_index_list - makes an index list of consecutive
 ***                    integers from some lower bound through an upper bound.
 ***                 choose_index - given a number "k", removes the integer
 ***                    in the k'th position in the index list and returns it.
 ***                    Requests for positions less than 1 or greater than
 ***                    the current list length return zero.
 ***                 remove_index - removes a specified integer from the
 ***                    index list.  Requests to remove integers not in the
 ***                    list are ignored, except that they reduce the list's
 ***                    "pseudo_size" (see below).
 ***                 index_size - returns the number of integers in the
 ***                    index list.
 ***                 pseudo_size - returns the number of integers in the
 ***                    index list, less the number for which remove_index
 ***                    failed due to a request to remove a non-existent one.
 ***                    (Note that this is here solely to support an apparent
 ***                    bug in the original definition of the NETGEN program.)

 *** Two simple methods of accomplishing these functions are:
 ***   - allocating an array of flags that indicate whether a particular
 ***     integer is valid, and searching the array during the choose_index
 ***     operation for the k'th valid integer.
 ***   - allocating a linked list for the indices and updating the list
 ***     during both the choose_index and remove_index operations.
 ***
 *** For small index lists, the first of these methods is quite efficient
 *** and is, in fact, implemented in the following code.  Unfortunately,
 *** for the uses we have in mind (i.e. NETGEN), the typical access pattern
 *** to index lists involves a large list, with both choose_index and
 *** remove_index operations occurring at random positions in the list.
 ***
 *** As a result, the code has been extended for the case of large lists.
 *** The enclosed implementation makes use of a binary interval tree, which
 *** records information regarding the valid intervals from which indices
 *** may be chosen.  At a cost of a substantial increase in space requirements,
 *** and under rather generous assumptions regarding the randomness of the
 *** positions supplied to choose_index, running time becomes logarithmic
 *** per choose_index and remove_index operation.
 ***/

#include "netgen.h"

/*** Useful constants */
#define FLAG_LIMIT 100          /* upper limit for simple implementation */


/*** Internally useful types */
typedef unsigned char FLAG;

typedef struct index_header {
  INDEX original_size;          /* original size of index */
  INDEX index_size;             /* number of indices in the index */
  INDEX pseudo_size;            /* almost the number of indices in the index */
  union {
    INDEX index_base;           /* base of index list - small case */
    INDEX index_nodes;          /* number of nodes in the interval tree - large case */
  } i;
  union {
    FLAG* flag;                 /* pointer to flag array - small */
    struct interval_node* first_node; /* pointer to root of interval tree - large */
  } p;
} HEADER;

typedef struct interval_node {
  INDEX base;                   /* smallest integer in this subtree */
  INDEX count;                  /* count of indices in this subtree */
  struct interval_node* left_child; /* pointers down the tree */
} INODE;


/*** Static storage */

static INDEX_LIST active_handles = 0;
static HEADER* index_headers = NULL;


/*** Make a new index list with a specified range.  Returns an integer handle
 *** to identify the list, or -1 if an error occurs.
 ***/
INDEX_LIST make_index_list(from, to)
INDEX from;                     /* lower limit of index list */
INDEX to;                       /* upper limit of index list */
{
  INDEX_LIST handle = 0;
  HEADER* hp;
  INODE* np;

  if (from <= 0 || from > to)   /* sanity check */
    return -1;

/*** Find an inactive list header or allocate a new one. */
  for (hp = index_headers; handle < active_handles; hp++, handle++) {
    if (hp->original_size == 0)
      break;
  }
  if (handle == active_handles) {
    ++active_handles;
    if (handle == 0)
      index_headers = (HEADER*) malloc(active_handles * sizeof(HEADER));
    else
      index_headers = (HEADER*) realloc(index_headers, active_handles * sizeof(HEADER));
  }
  if (index_headers == NULL)
    return -1;


/*** Fill in the list header and allocate space for the list. */
  hp = &index_headers[handle];
  hp->pseudo_size = hp->index_size = hp->original_size = to - from + 1;
  if (hp->original_size <= FLAG_LIMIT) { /* SMALL */
    hp->i.index_base = from;
    hp->p.flag = (FLAG*) malloc(hp->original_size * sizeof(FLAG));
    if (hp->p.flag == NULL)
      return -1;
    (void)memset((void *)hp->p.flag, 0, hp->original_size * sizeof(FLAG));
  } else {                      /* LARGE */
    hp->i.index_nodes = 1;
    np = (INODE*) malloc(hp->original_size * sizeof(INODE));
    if (np == NULL)
      return -1;
    hp->p.first_node = np;
    np->base = from;
    np->count = hp->original_size;
    np->left_child = NULL;
  }
  return handle;
}


/*** Free an existing index list.  The header is zeroed afterwards
 *** to indicate that it can be reused.
 ***/
void free_index_list(handle)
INDEX_LIST handle;
{
  HEADER* hp;

  if (handle < 0 || handle >= active_handles)   /* sanity check */
    return;

  hp = &index_headers[handle];
  if (hp->p.flag)
    free((void *)hp->p.flag);
  (void)memset((void *)hp, 0, sizeof(HEADER));
}

/*** Choose the integer at a certain position in an index list.  The
 *** integer is then removed from the list so that it won't be chosen
 *** again.  Choose_index returns 0 if the position is invalid.
 ***/
INDEX choose_index(handle, position)
INDEX_LIST handle;
INDEX position;
{
  HEADER* hp;
  FLAG* cp;
  INODE* np;
  INODE* npl;
  INODE* npr;
  INDEX index;

  if (handle < 0 || handle >= active_handles)   /* sanity checks */
    return 0;
  hp = &index_headers[handle];
  if (hp->p.flag == NULL)
    return 0;
  if (position < 1 || position > hp->index_size)
    return 0;

/*** Adjust counts of remaining indices. */
  hp->index_size--;
  hp->pseudo_size--;


/*** Find the index we want and remove it from the list. */
  if (hp->original_size <= FLAG_LIMIT) { /* SMALL */
    for (cp = hp->p.flag; position > 0; cp++)
      if (!*cp)
        position--;
    *(--cp) = 1;
    return hp->i.index_base + (INDEX)(cp - hp->p.flag);
  } else {                      /* LARGE */
    np = hp->p.first_node;
    while (np->left_child) {
      np->count--;
      np = np->left_child;
      if (position > np->count) {
        position -= np->count;
        np++;
      }
    }
    np->count--;
    if (position == 1) {        /* beginning of interval */
      index = np->base++;
    }
    else
    if (position > np->count) { /* end of interval */
      index = np->base + np->count;
    }
    else                        /* middle of interval - split it */
    {
      index = np->base + position - 1;
      npl = np->left_child = hp->p.first_node + hp->i.index_nodes;
      npr = npl + 1;
      hp->i.index_nodes += 2;
      npl->base = np->base;
      npl->count = position - 1;
      npl->left_child = NULL;
      npr->base = index + 1;
      npr->count = np->count - npl->count;
      npr->left_child = NULL;
    }
    return index;
  }
}

/*** Remove a particular integer from an index list.  If the integer
 *** does not exist in the list, we reduce the list's pseudo-size,
 *** but return no error indication.
 ***/
void remove_index(handle, index)
INDEX_LIST handle;
INDEX index;
{
  HEADER* hp;
  FLAG* cp;
  INODE* np;
  INODE* npl;
  INODE* npr;

  if (handle < 0 || handle >= active_handles)   /* sanity checks */
    return;
  hp = &index_headers[handle];
  if (hp->p.flag == NULL)
    return;

/*** Adjust the pseudo-size before looking for the index. */
  hp->pseudo_size--;

/*** Remove the index from the index list. */
  if (hp->original_size <= FLAG_LIMIT) { /* SMALL */
    if (index < hp->i.index_base || index >= hp->i.index_base + hp->original_size)
      return;
    cp = hp->p.flag + (index - hp->i.index_base);
    if (!*cp) {
      *cp = 1;
      hp->index_size--;
    }
    return;
  } else {                      /* LARGE */
    np = hp->p.first_node;
    while (np->left_child) {
      np->count--;
      np = np->left_child + 1;
      if (index < np->base)
        np--;
    }
    if (index < np->base || index >= np->base + np->count) { /* mistake - back out */
      np = hp->p.first_node;
      while (np->left_child) {
        np->count++;
        np = np->left_child + 1;
        if (index < np->base)
          np--;
      }
      return;
    }
    np->count--;
    if (index == np->base) {                    /* beginning of interval */
      np->base++;
    }
    else
    if (index == np->base + np->count) {        /* end of interval */
    }
    else                                        /* middle of interval - split it */
    {
      npl = np->left_child = hp->p.first_node + hp->i.index_nodes;
      npr = npl + 1;
      hp->i.index_nodes += 2;
      npl->base = np->base;
      npl->count = index - np->base;
      npl->left_child = NULL;
      npr->base = index + 1;
      npr->count = np->count - npl->count;
      npr->left_child = NULL;
    }
    hp->index_size--;
    return;
  }
}


/*** Return actual number of remaining entries in the index list.
 ***/
INDEX index_size(handle)
INDEX_LIST handle;
{
  if (handle < 0 || handle >= active_handles)   /* sanity check */
    return 0;

  return index_headers[handle].index_size;
}


/*** Return a peculiar number, vaguely related to the number of
 *** remaining entries in the index list.  Required by NETGEN.
 ***/
INDEX pseudo_size(handle)
INDEX_LIST handle;
{
  if (handle < 0 || handle >= active_handles)   /* sanity check */
    return 0;

  return index_headers[handle].pseudo_size;
}