alpar@6: /*** Copyright 1989 Norbert Schlenker.  All rights reserved.
alpar@6: 
alpar@6:  *** This software is distributed subject to the following provisions:
alpar@6:  ***    - this notice may not be removed;
alpar@6:  ***    - you may modify the source code, as long as redistributed
alpar@6:  ***      versions have their modifications clearly marked;
alpar@6:  ***    - no charge, other than a nominal copying fee, may be made
alpar@6:  ***      when providing copies of this source code to others;
alpar@6:  ***    - if this source code is used as part of a product which is
alpar@6:  ***      distributed only as a binary, a copy of this source code
alpar@6:  ***      must be included in the distribution.
alpar@6:  ***
alpar@6:  *** Unlike the GNU GPL, use of this code does not obligate you to
alpar@6:  *** disclose your own proprietary source code.
alpar@6: 
alpar@6:  *** The author of this software provides no warranty, express or
alpar@6:  *** implied, as to its utility or correctness.  That said, reports
alpar@6:  *** of bugs or compatibility problems will be gladly received by
alpar@6:  *** nfs@princeton.edu, and fixes will be attempted.
alpar@6:  ***/
alpar@6: 
alpar@6: 
alpar@6: /*** index.c - routines to manipulate index lists */
alpar@6: 
alpar@6: /*** Definition:  An "index list" is an ascending sequence of positive
alpar@6:  ***              integers that can be operated upon as follows:
alpar@6:  ***
alpar@6:  ***                 make_index_list - makes an index list of consecutive
alpar@6:  ***                    integers from some lower bound through an upper bound.
alpar@6:  ***                 choose_index - given a number "k", removes the integer
alpar@6:  ***                    in the k'th position in the index list and returns it.
alpar@6:  ***                    Requests for positions less than 1 or greater than
alpar@6:  ***                    the current list length return zero.
alpar@6:  ***                 remove_index - removes a specified integer from the
alpar@6:  ***                    index list.  Requests to remove integers not in the
alpar@6:  ***                    list are ignored, except that they reduce the list's
alpar@6:  ***                    "pseudo_size" (see below).
alpar@6:  ***                 index_size - returns the number of integers in the
alpar@6:  ***                    index list.
alpar@6:  ***                 pseudo_size - returns the number of integers in the
alpar@6:  ***                    index list, less the number for which remove_index
alpar@6:  ***                    failed due to a request to remove a non-existent one.
alpar@6:  ***			(Note that this is here solely to support an apparent
alpar@6:  ***			bug in the original definition of the NETGEN program.)
alpar@6: 
alpar@6:  *** Two simple methods of accomplishing these functions are:
alpar@6:  ***   - allocating an array of flags that indicate whether a particular
alpar@6:  ***     integer is valid, and searching the array during the choose_index
alpar@6:  ***     operation for the k'th valid integer.
alpar@6:  ***   - allocating a linked list for the indices and updating the list
alpar@6:  ***     during both the choose_index and remove_index operations.
alpar@6:  ***
alpar@6:  *** For small index lists, the first of these methods is quite efficient
alpar@6:  *** and is, in fact, implemented in the following code.  Unfortunately,
alpar@6:  *** for the uses we have in mind (i.e. NETGEN), the typical access pattern
alpar@6:  *** to index lists involves a large list, with both choose_index and
alpar@6:  *** remove_index operations occurring at random positions in the list.
alpar@6:  ***
alpar@6:  *** As a result, the code has been extended for the case of large lists.
alpar@6:  *** The enclosed implementation makes use of a binary interval tree, which
alpar@6:  *** records information regarding the valid intervals from which indices
alpar@6:  *** may be chosen.  At a cost of a substantial increase in space requirements,
alpar@6:  *** and under rather generous assumptions regarding the randomness of the
alpar@6:  *** positions supplied to choose_index, running time becomes logarithmic
alpar@6:  *** per choose_index and remove_index operation.
alpar@6:  ***/
alpar@6: 
alpar@6: #include "netgen.h"
alpar@6: 
alpar@6: /*** Useful constants */
alpar@6: #define FLAG_LIMIT 100		/* upper limit for simple implementation */
alpar@6: 
alpar@6: 
alpar@6: /*** Internally useful types */
alpar@6: typedef unsigned char FLAG;
alpar@6: 
alpar@6: typedef struct index_header {
alpar@6:   INDEX original_size;		/* original size of index */
alpar@6:   INDEX index_size;		/* number of indices in the index */
alpar@6:   INDEX pseudo_size;		/* almost the number of indices in the index */
alpar@6:   union {
alpar@6:     INDEX index_base;		/* base of index list - small case */
alpar@6:     INDEX index_nodes;		/* number of nodes in the interval tree - large case */
alpar@6:   } i;
alpar@6:   union {
alpar@6:     FLAG* flag;			/* pointer to flag array - small */
alpar@6:     struct interval_node* first_node; /* pointer to root of interval tree - large */
alpar@6:   } p;
alpar@6: } HEADER;
alpar@6: 
alpar@6: typedef struct interval_node {
alpar@6:   INDEX base;			/* smallest integer in this subtree */
alpar@6:   INDEX count;			/* count of indices in this subtree */
alpar@6:   struct interval_node* left_child; /* pointers down the tree */
alpar@6: } INODE;
alpar@6: 
alpar@6: 
alpar@6: /*** Static storage */
alpar@6: 
alpar@6: static INDEX_LIST active_handles = 0;
alpar@6: static HEADER* index_headers = NULL;
alpar@6: 
alpar@6: 
alpar@6: /*** Make a new index list with a specified range.  Returns an integer handle
alpar@6:  *** to identify the list, or -1 if an error occurs.
alpar@6:  ***/
alpar@6: INDEX_LIST make_index_list(from, to)
alpar@6: INDEX from;			/* lower limit of index list */
alpar@6: INDEX to;			/* upper limit of index list */
alpar@6: {
alpar@6:   INDEX_LIST handle = 0;
alpar@6:   HEADER* hp;
alpar@6:   INODE* np;
alpar@6: 
alpar@6:   if (from <= 0 || from > to)	/* sanity check */
alpar@6:     return -1;
alpar@6: 
alpar@6: /*** Find an inactive list header or allocate a new one. */
alpar@6:   for (hp = index_headers; handle < active_handles; hp++, handle++) {
alpar@6:     if (hp->original_size == 0)
alpar@6:       break;
alpar@6:   }
alpar@6:   if (handle == active_handles) {
alpar@6:     ++active_handles;
alpar@6:     if (handle == 0)
alpar@6:       index_headers = (HEADER*) malloc(active_handles * sizeof(HEADER));
alpar@6:     else
alpar@6:       index_headers = (HEADER*) realloc(index_headers, active_handles * sizeof(HEADER));
alpar@6:   }
alpar@6:   if (index_headers == NULL)
alpar@6:     return -1;
alpar@6: 
alpar@6: 
alpar@6: /*** Fill in the list header and allocate space for the list. */
alpar@6:   hp = &index_headers[handle];
alpar@6:   hp->pseudo_size = hp->index_size = hp->original_size = to - from + 1;
alpar@6:   if (hp->original_size <= FLAG_LIMIT) { /* SMALL */
alpar@6:     hp->i.index_base = from;
alpar@6:     hp->p.flag = (FLAG*) malloc(hp->original_size * sizeof(FLAG));
alpar@6:     if (hp->p.flag == NULL)
alpar@6:       return -1;
alpar@6:     (void)memset((void *)hp->p.flag, 0, hp->original_size * sizeof(FLAG));
alpar@6:   } else {			/* LARGE */
alpar@6:     hp->i.index_nodes = 1;
alpar@6:     np = (INODE*) malloc(hp->original_size * sizeof(INODE));
alpar@6:     if (np == NULL)
alpar@6:       return -1;
alpar@6:     hp->p.first_node = np;
alpar@6:     np->base = from;
alpar@6:     np->count = hp->original_size;
alpar@6:     np->left_child = NULL;
alpar@6:   }
alpar@6:   return handle;
alpar@6: }
alpar@6: 
alpar@6: 
alpar@6: /*** Free an existing index list.  The header is zeroed afterwards
alpar@6:  *** to indicate that it can be reused.
alpar@6:  ***/
alpar@6: void free_index_list(handle)
alpar@6: INDEX_LIST handle;
alpar@6: {
alpar@6:   HEADER* hp;
alpar@6: 
alpar@6:   if (handle < 0 || handle >= active_handles)	/* sanity check */
alpar@6:     return;
alpar@6: 
alpar@6:   hp = &index_headers[handle];
alpar@6:   if (hp->p.flag)
alpar@6:     free((void *)hp->p.flag);
alpar@6:   (void)memset((void *)hp, 0, sizeof(HEADER));
alpar@6: }
alpar@6: 
alpar@6: /*** Choose the integer at a certain position in an index list.  The
alpar@6:  *** integer is then removed from the list so that it won't be chosen
alpar@6:  *** again.  Choose_index returns 0 if the position is invalid.
alpar@6:  ***/
alpar@6: INDEX choose_index(handle, position)
alpar@6: INDEX_LIST handle;
alpar@6: INDEX position;
alpar@6: {
alpar@6:   HEADER* hp;
alpar@6:   FLAG* cp;
alpar@6:   INODE* np;
alpar@6:   INODE* npl;
alpar@6:   INODE* npr;
alpar@6:   INDEX index;
alpar@6: 
alpar@6:   if (handle < 0 || handle >= active_handles)	/* sanity checks */
alpar@6:     return 0;
alpar@6:   hp = &index_headers[handle];
alpar@6:   if (hp->p.flag == NULL)
alpar@6:     return 0;
alpar@6:   if (position < 1 || position > hp->index_size)
alpar@6:     return 0;
alpar@6: 
alpar@6: /*** Adjust counts of remaining indices. */
alpar@6:   hp->index_size--;
alpar@6:   hp->pseudo_size--;
alpar@6: 
alpar@6: 
alpar@6: /*** Find the index we want and remove it from the list. */
alpar@6:   if (hp->original_size <= FLAG_LIMIT) { /* SMALL */
alpar@6:     for (cp = hp->p.flag; position > 0; cp++)
alpar@6:       if (!*cp)
alpar@6: 	position--;
alpar@6:     *(--cp) = 1;
alpar@6:     return hp->i.index_base + (INDEX)(cp - hp->p.flag);
alpar@6:   } else {			/* LARGE */
alpar@6:     np = hp->p.first_node;
alpar@6:     while (np->left_child) {
alpar@6:       np->count--;
alpar@6:       np = np->left_child;
alpar@6:       if (position > np->count) {
alpar@6: 	position -= np->count;
alpar@6: 	np++;
alpar@6:       }
alpar@6:     }
alpar@6:     np->count--;
alpar@6:     if (position == 1) {	/* beginning of interval */
alpar@6:       index = np->base++;
alpar@6:     }
alpar@6:     else
alpar@6:     if (position > np->count) {	/* end of interval */
alpar@6:       index = np->base + np->count;
alpar@6:     }
alpar@6:     else			/* middle of interval - split it */
alpar@6:     {
alpar@6:       index = np->base + position - 1;
alpar@6:       npl = np->left_child = hp->p.first_node + hp->i.index_nodes;
alpar@6:       npr = npl + 1;
alpar@6:       hp->i.index_nodes += 2;
alpar@6:       npl->base = np->base;
alpar@6:       npl->count = position - 1;
alpar@6:       npl->left_child = NULL;
alpar@6:       npr->base = index + 1;
alpar@6:       npr->count = np->count - npl->count;
alpar@6:       npr->left_child = NULL;
alpar@6:     }
alpar@6:     return index;
alpar@6:   }
alpar@6: }
alpar@6: 
alpar@6: /*** Remove a particular integer from an index list.  If the integer
alpar@6:  *** does not exist in the list, we reduce the list's pseudo-size,
alpar@6:  *** but return no error indication.
alpar@6:  ***/
alpar@6: void remove_index(handle, index)
alpar@6: INDEX_LIST handle;
alpar@6: INDEX index;
alpar@6: {
alpar@6:   HEADER* hp;
alpar@6:   FLAG* cp;
alpar@6:   INODE* np;
alpar@6:   INODE* npl;
alpar@6:   INODE* npr;
alpar@6: 
alpar@6:   if (handle < 0 || handle >= active_handles)	/* sanity checks */
alpar@6:     return;
alpar@6:   hp = &index_headers[handle];
alpar@6:   if (hp->p.flag == NULL)
alpar@6:     return;
alpar@6: 
alpar@6: /*** Adjust the pseudo-size before looking for the index. */
alpar@6:   hp->pseudo_size--;
alpar@6: 
alpar@6: /*** Remove the index from the index list. */
alpar@6:   if (hp->original_size <= FLAG_LIMIT) { /* SMALL */
alpar@6:     if (index < hp->i.index_base || index >= hp->i.index_base + hp->original_size)
alpar@6:       return;
alpar@6:     cp = hp->p.flag + (index - hp->i.index_base);
alpar@6:     if (!*cp) {
alpar@6:       *cp = 1;
alpar@6:       hp->index_size--;
alpar@6:     }
alpar@6:     return;
alpar@6:   } else {			/* LARGE */
alpar@6:     np = hp->p.first_node;
alpar@6:     while (np->left_child) {
alpar@6:       np->count--;
alpar@6:       np = np->left_child + 1;
alpar@6:       if (index < np->base)
alpar@6: 	np--;
alpar@6:     }
alpar@6:     if (index < np->base || index >= np->base + np->count) { /* mistake - back out */
alpar@6:       np = hp->p.first_node;
alpar@6:       while (np->left_child) {
alpar@6:         np->count++;
alpar@6: 	np = np->left_child + 1;
alpar@6: 	if (index < np->base)
alpar@6: 	  np--;
alpar@6:       }
alpar@6:       return;
alpar@6:     }
alpar@6:     np->count--;
alpar@6:     if (index == np->base) {			/* beginning of interval */
alpar@6:       np->base++;
alpar@6:     }
alpar@6:     else
alpar@6:     if (index == np->base + np->count) {	/* end of interval */
alpar@6:     }
alpar@6:     else    	    	    			/* middle of interval - split it */
alpar@6:     {
alpar@6:       npl = np->left_child = hp->p.first_node + hp->i.index_nodes;
alpar@6:       npr = npl + 1;
alpar@6:       hp->i.index_nodes += 2;
alpar@6:       npl->base = np->base;
alpar@6:       npl->count = index - np->base;
alpar@6:       npl->left_child = NULL;
alpar@6:       npr->base = index + 1;
alpar@6:       npr->count = np->count - npl->count;
alpar@6:       npr->left_child = NULL;
alpar@6:     }
alpar@6:     hp->index_size--;
alpar@6:     return;
alpar@6:   }
alpar@6: }
alpar@6: 
alpar@6: 
alpar@6: /*** Return actual number of remaining entries in the index list.
alpar@6:  ***/
alpar@6: INDEX index_size(handle)
alpar@6: INDEX_LIST handle;
alpar@6: {
alpar@6:   if (handle < 0 || handle >= active_handles)	/* sanity check */
alpar@6:     return 0;
alpar@6: 
alpar@6:   return index_headers[handle].index_size;
alpar@6: }
alpar@6: 
alpar@6: 
alpar@6: /*** Return a peculiar number, vaguely related to the number of
alpar@6:  *** remaining entries in the index list.  Required by NETGEN.
alpar@6:  ***/
alpar@6: INDEX pseudo_size(handle)
alpar@6: INDEX_LIST handle;
alpar@6: {
alpar@6:   if (handle < 0 || handle >= active_handles)	/* sanity check */
alpar@6:     return 0;
alpar@6: 
alpar@6:   return index_headers[handle].pseudo_size;
alpar@6: }