Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso/unix/volume14/bsd-dyna-link/assoc.c

C/C++ Source or Header | 1988-05-08 | 17KB | 744 lines

#include <ctype.h>
#include <stdio.h>


#define PANIC_FILE stderr

#include "assoc.h"

int* H_getmem();
int* assoc_lookup();


#define LOWER(ch) (isupper(ch)? tolower(ch) : (ch))

/************************************************************************\
**************************************************************************
**                                    **
**  This package uses hash tables to implement an associative memory,    **
**  or "name table".  See also "assoc.h" and "assoc_internals.h".    **
**                                    **
**  The user may associate names, also called "index strings" with    **
**  packets of memory, called "mem_cell"s, which come in fixed sizes.    **
**  Then if you know the name, you can look up the mem_cell or vice    **
**  versa.                                **
**                                    **
**  The collision recovery mechanism is a nifty little scheme           **
**  of my own invention, which I call "linear-congruential rehash",    **
**  which means "add one and multiply by three".            **
**                                    **
**  The orbit of the rehash function touches exactly half the entries    **
**  in the table, and the table is never allowed to be over half full,  **
**  so there will always be an empty slot for a new entry.        **
**  Removing entries is a little bit tricky. Since the lookup mechanism **
**  stops and reports failure when it comes to an empty slot in the     **
**  rehash orbit for the value searched for, when an entry is removed,    **
**  the values in the same orbit which are there as a result of a     **
**  collision must be backed up to fill the evacuated slot.          **
**  The entry number is also there for removing entries.  It provides a **
**  reference back to the slot which points to the entry.        **
**                                                                      **
**  We assume that our machine uses two's complement arithmetic.    **
**************************************************************************
\************************************************************************/

/**************************************************************************
**
**  An entry looks like this:
**
**
**  [pointers]      [pointees]
**
**          ------------------
**  mem         -> |  entry number  |  index of entry into hash table.
**          ------------------
**  mem_cell ->    |             |
**  (slot)    |         |
**        | user's goodies |  of size table->value_size
**            |         |
**        ------------------
**  string   -> |         |
**        |  index string  |
**        |         |
**        |         |
**        ------------------
**
**
**  See string_from_cell(), cell_from_string(), mem_from_cell(), and
**  cell_from_mem().. all macros.
**
\*************************************************************************/







/* N.B. The routine assoc() depends on the fact that if a table is less
** than half full, the rehash orbit will always find an empty slot.
** This rehash will hit exactly half the slots before it repeats, provided
** that the table length is a power of two.
*/
#define REHASH(hash,table) (((hash+1)*3) & table -> mask)




/**** factory-procedure, makes new tables. ****/

assoc_mem
new_assoc_mem(value_size)
  int value_size; /* storage size of values to be in assoc mem */
{
  register assoc_mem table;

  table = (assoc_mem) H_getmem(sizeof (struct assoc_mem_rec));

  table->value_size = value_size;
  table->entries = 0;
  table->size = INIT_TABLE_SIZE;
  table->size_div_2 = table->size / 2;
  table->mask = table->size -1;
  table->array = (hash_table *)H_getmem(table->size * (sizeof (mem_cell)));

  return table;
}



/* Associates a name with a new mem_cell, or return pointers to previously
** associated cell.  Initializes new cells to all zero, so you may determine
** whether or not a cell is new by smudging a "virgin-bit" when you
** first obtain a new cell.  If you get a cell from assoc() with a
** fresh new virgin bit, then the cell must be a new one.
*/


mem_cell
assoc( string, table)
  register char* string;
  register assoc_mem table;
{ /* assoc */

  int length;
  int hashval;

  register int   rehash;
  register entry assoc_value;

  /* This is essential.  See assoc_internals.h */
  if (table->entries >= table->size_div_2 - 1)
    H_expand_table(table);

  hash(string, table->mask, &length, &hashval);
  rehash = hashval;

 look_at_slot:
  {  register entry * slot = &((*(table->array))[rehash]);

     assoc_value = *slot;

     if ( (assoc_value) == 0)
       /* Nothing else has hashed to this slot.
      We will put our string here. */
       {
     *slot =  cell_from_mem(
            (entry) H_getmem(table->value_size + length + sizeof('\0')
                     + sizeof(entry*)));

     *(mem_from_cell(*slot)) = rehash;
     assoc_value = *slot;
     strcpy(string_from_cell(assoc_value, table), string);
     table->entries++;
     return assoc_value;        /* <=========== */
       }

     if (strcmp( string_from_cell(assoc_value,table), string) != 0)
       {                /* Oops.. collision. */
     rehash = REHASH(rehash,table);
     goto look_at_slot;        /* <=========== */
       }
     else return assoc_value;        /* <=========== */

   }





}                    /* end assoc */

/* Like assoc, except for non-null-terminated strings */
mem_cell
assocn( string, length, table)
  register char* string;
  register assoc_mem table;
  register int length;
{ /* assocn */

  int hashval;

  register int   rehash;
  register entry assoc_value;

  /* This is essential.  See assoc_internals.h */
  if (table->entries >= table->size_div_2 - 1)
    H_expand_table(table);

  hashn(string, table->mask, length, &hashval);
  rehash = hashval;

 look_at_slot:
  {  register entry * slot = &((*(table->array))[rehash]);

     assoc_value = *slot;

     if ( (assoc_value) == 0)
       /* Nothing else has hashed to this slot.
      We will put our string here. */
       {
     *slot =  cell_from_mem(
            (entry) H_getmem(table->value_size + length + sizeof('\0')
                     + sizeof(entry*)));

     *(mem_from_cell(*slot)) = rehash;
     assoc_value = *slot;
     strncpy(string_from_cell(assoc_value, table), string, length);
     table->entries++;
     return assoc_value;        /* <=========== */
       }

     if (lstrncmp( string_from_cell(assoc_value,table), string, length) != 0)
       {                /* Oops.. collision. */
     rehash = REHASH(rehash,table);
     goto look_at_slot;        /* <=========== */
       }
     else return assoc_value;        /* <=========== */

   }


}                    /* end assocn */
/* Like assoc, except for non-null-terminated strings, and folds cases. */
mem_cell
assocnf( string, length, table)
  register char* string;
  register assoc_mem table;
  register int length;
{ /* assocn */

  int hashval;

  register int   rehash;
  register entry assoc_value;

  /* This is essential.  See assoc_internals.h */
  if (table->entries >= table->size_div_2 - 1)
    H_expand_table(table);

  hashnf(string, table->mask, length, &hashval);
  rehash = hashval;

 look_at_slot:
  {  register entry * slot = &((*(table->array))[rehash]);

     assoc_value = *slot;

     if ( (assoc_value) == 0)
       /* Nothing else has hashed to this slot.
      We will put our string here. */
       {
     *slot =  cell_from_mem(
            (entry) H_getmem(table->value_size + length + sizeof('\0')
                     + sizeof(entry*)));

     *(mem_from_cell(*slot)) = rehash;
     assoc_value = *slot;
     strncpy(string_from_cell(assoc_value, table), string, length);
     table->entries++;
     return assoc_value;        /* <=========== */
       }

     if (lstrncmpf( string_from_cell(assoc_value,table), string, length) != 0)
       {                /* Oops.. collision. */
     rehash = REHASH(rehash,table);
     goto look_at_slot;        /* <=========== */
       }
     else return assoc_value;        /* <=========== */

   }

}                    /* end assocnf */

/* returns 0 iff a null-terminated string and counted string compare */
static
lstrncmp(nullterm, counted, len)
  char* nullterm;
  char* counted;
{

  while( *nullterm && len && *nullterm++ == *counted++)
    len--;
  return !(len == 0 && *nullterm == 0);
}

/* returns 0 iff a null-terminated string and counted string compare */
/* folds cases */
static
lstrncmpf(nullterm, counted, len)
  char* nullterm;
  char* counted;
{

  while( *nullterm && len && LOWER(*nullterm) == LOWER(*counted))
    {
      len--;
      nullterm++; counted++;
    }
  return !(len == 0 && *nullterm == 0);
}



/* Look up the mem_cell associated with a given name. */
/* Returns NULL if not found.                  */

mem_cell
assoc_lookup( string, table)
  register char* string;
  register assoc_mem table;
{
  register entry retval;
  int length;
  int hashval;

  hash(string, table->mask, &length, &hashval);

  { register int  rehash = hashval;
    register int * assoc_value = 0;

    look_at_slot:
    {  entry * slot = &((*(table->array))[rehash]);

       assoc_value = *slot;

       if ( (assoc_value) == 0)
        /* Nothing has hashed to this slot.
           Lookup has come to a sorry end. */
        {
           return assoc_value;  /* <=========== */
        }

       if (strcmp( string_from_cell(assoc_value,table), string) == 0)
        /*  An identical string was previously put in this slot.
        **  We found it!
        */
            {
           return assoc_value;  /* <=========== */
        }

       /* collision... try next slot in the rehash orbit */
       rehash = REHASH(rehash,table);
       goto look_at_slot;        /* <=========== */
    }

  }


} /* end assoc_lookup */


mem_cell
assocn_lookup( string, length, table)
  register char* string;
  register assoc_mem table;
{
  register entry retval;
  int hashval;

  hashn(string, table->mask, length, &hashval);

  { register int  rehash = hashval;
    register int * assoc_value = 0;

  look_at_slot:
    {  entry * slot = &((*(table->array))[rehash]);

       assoc_value = *slot;

       if ( (assoc_value) == 0)
     /* Nothing has hashed to this slot.
        Lookup has come to a sorry end. */
     {
       return assoc_value;  /* <=========== */
     }

       if (lstrncmp( string_from_cell(assoc_value,table), string, length) == 0)
     /*  An identical string was previously put in this slot.
     **  We found it!
     */
     {
       return assoc_value;  /* <=========== */
     }

       /* collision... try next slot in the rehash orbit */
       rehash = REHASH(rehash,table);
       goto look_at_slot;        /* <=========== */

     }

  }


} /* end assocn_lookup */


mem_cell
assocnf_lookup( string, length, table)
  register char* string;
  register assoc_mem table;
{
  register entry retval;
  int hashval;

  hashnf(string, table->mask, length, &hashval);

  { register int  rehash = hashval;
    register int * assoc_value = 0;

  look_at_slot:
    {  entry * slot = &((*(table->array))[rehash]);

       assoc_value = *slot;

       if ( (assoc_value) == 0)
     /* Nothing has hashed to this slot.
        Lookup has come to a sorry end. */
     {
       return assoc_value;  /* <=========== */
     }

       if (lstrncmpf( string_from_cell(assoc_value,table), string, length) == 0)
     /*  An identical string was previously put in this slot.
     **  We found it!
     */
     {
       return assoc_value;  /* <=========== */
     }

       /* collision... try next slot in the rehash orbit */
       rehash = REHASH(rehash,table);
       goto look_at_slot;        /* <=========== */

     }

  }


} /* end assocnf_lookup */




/* This routine hashes a string and counts the number of chars in it.   */
/* The hash value is a function of the table size.             */

static
hash(string, mask, lenp, hashp)
  char* string;
  int mask;     /* Is table size minus one. */
  int *lenp;
  int *hashp;

{
  register int len = 0;
  register int hash = 0;
  register char* cursor = string;

  len = 0;
  hash = 0;

  while (*cursor)
    { len++;
      hash += ((hash << 1) + *cursor++);
    }
  *hashp = hash & mask;
  *lenp = len;


} /* hash */

/* Like hash, except for counted (not null-terminated) strings */
static
hashn(string, mask, len, hashp)
  char* string;
  int mask;     /* Is table size minus one. */
  int len;
  int *hashp;

{
  register int hash = 0;
  register char* cursor = string;

  hash = 0;

  while (len--)
    {
      hash += ((hash << 1) + *cursor++);
    }

  *hashp = hash & mask;

} /* hashn*/
/* Like hash, except for counted (not null-terminated) strings */
/* Folds cases. */
static
hashnf(string, mask, len, hashp)
  char* string;
  int mask;     /* Is table size minus one. */
  int len;
  int *hashp;

{
  register int hash = 0;
  register char* cursor = string;

  hash = 0;

  while (len--)
    {
      hash += ((hash << 1) + LOWER(*cursor));
      cursor++;
    }

  *hashp = hash & mask;

} /* hashn*/




/* "Safe" memory allocation routine... zeros out memory obtained. */

static int*
H_getmem(size)
  int size;
{
  int * retval = (int*)calloc(size, sizeof(char));
  if (retval == (int*)0)
    {
    fprintf(PANIC_FILE, "RESOURCE FAILURE: Assoc out of memory. (%d)\n",
        size);
    exit(1);
    }
  else return retval;

}






/* When a table becomes half full, we double its size.  (The
** orbit of the rehash function touches exactly half the slots.)
**
*/

static
H_expand_table(table)
  register assoc_mem table;
{
  register hash_table * old_table = table->array;
  register int old_size = table->size;

  table->size_div_2 = table->size;
  table->size = table->size * 2;
  table->mask = table->size -1;

  table->array = (hash_table *)H_getmem(table->size * (sizeof (mem_cell)));

  /* Move the members from the old small table to be new big one. */
  { register int recno;

    for (recno = 0; recno < old_size; recno++)
      if ( (*old_table)[recno] != (entry)0)
        H_reassoc( (*old_table)[recno], table );
  }

  cfree (old_table);
}





/* This routine is a little like assoc. It is used by expand_table() to
** put entries which were in table which overflowed into the new larger one.
** Used by assoc_free() to put entries back into the table which might
** have originally been bumped down the rehash orbit by the entry being
** removed.
*/

static
H_reassoc( rec, table)
  register entry rec;
  register assoc_mem table;
{
  register entry retval;
  register char* string = string_from_cell(rec, table);
  int length;
  int hashval;

  hash(string, table->mask, &length, &hashval);

  { register int  rehash = hashval;

    look_at_slot:
    {  register entry * slot = &((*(table->array))[rehash]);

       if ( (*slot) == 0)
        {
          *slot = rec;
          *(mem_from_cell(*slot)) = rehash;

          return;        /* <========= */
        }

       rehash = REHASH(rehash,table);
       goto look_at_slot;      /* <========= */
    }

  }


} /* H_reassoc */




/* This is a sequencer for a table.  You give it a pointer to an
** integer variable which you have initialized to zero, and it gives
** you a member of the table and modifies the variable.  Call it
** again without changing the variable and it gives you the next one, etc...
**
**    { int handle = 0;
**      mem_cell member;
**
**      do { member = assoc_seq(table, &handle);
**           if (member != NULL) process(member);
**         }
**      while (member != NULL);
**    }
**
**
** DO NOT ADD OR DELETE MEMBERS BETWEEN RELATED CALLS TO assoc_seq().
** To do so will wreak non-determinancy if the assoc() caused the
** table to expand, or if the assoc_free() caused a member to be
** moved back up the rehash chain.  You might very easily miss some
** members.
**
*/

mem_cell
assoc_seq(table, num)
  register assoc_mem table;
  register int *num;
{
  register hash_table * hash_tab = table->array;
  register int size = table->size;

  /* Standard linear search algorithm looks for next non-empty slot
  ** at index *num or further down.
  */
  for (; (*num) < size; (*num)++)
    if ( (*hash_tab)[*num] != (entry)0)
    { mem_cell retval = (*hash_tab)[*num];
      (*num)++;
      return retval;
    }

  return 0;

}



/*
** This procedure removes a member from a table.
*/

assoc_free(cell, table)
  mem_cell cell;
  assoc_mem table;
{
  /* Invariant: next_slot_num and next_slot point to entries in the rehash
  ** orbit of the cell being removed.  They start out pointing to the
  ** slot of the condemned cell itself:
  */
  register next_slot_num = *(mem_from_cell(cell));
  register entry *next_slot = &((*(table->array))[next_slot_num]);

  /* Remove the condemned cell. */
  free(mem_from_cell(*next_slot));
  *next_slot = 0; /* Splat! got it. */
  table->entries -= 1;

  /* The entry we just removed might have caused some other entries
  ** to be "bumped down the rehash orbit" when they were installed in
  ** the table.  If that was the case, they can not now be found unless
  ** they are moved to their (now) proper position in the table.
  */
   while(
      next_slot_num = REHASH(next_slot_num,table),
      next_slot = &((*(table->array))[next_slot_num]),
      (*next_slot != 0)
    )
     { entry mover = *next_slot;
       *next_slot = 0;
       H_reassoc(mover, table);
     }

}/* assoc_free */



/* Deletes a table and returns 0 if the table is empty.
** Does not delete table, but returns number of entries remaining if
** table is not empty.
*/

int
assoc_mem_free(table)
  assoc_mem table;
{
  if (table->entries == 0)
    {  free(table->array);
       free(table);
       return 0;
    }
  else return table->entries;

}

/* Deletes all members in a table, then removes the table. */

assoc_mem_remove(table)
  assoc_mem table;
{ register int num = 0;
  register hash_table * hash_tab = table->array;
  register int size = table->size;

  for (; (num) < size; (num)++)
    if ( (*hash_tab)[num] != (entry)0)
    {
          free(mem_from_cell((*hash_tab)[num]));
    }


  free(table->array);
  free(table);

}