home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 4 / FreshFish_May-June1994.bin / bsd / src / make / make-amiga / hash.c < prev    next >
C/C++ Source or Header  |  1993-09-23  |  11KB  |  419 lines
  1. /*
  2.  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
  3.  * Copyright (c) 1988, 1989 by Adam de Boor
  4.  * Copyright (c) 1989 by Berkeley Softworks
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Adam de Boor.
  9.  *
  10.  * Redistribution and use in source and binary forms, with or without
  11.  * modification, are permitted provided that the following conditions
  12.  * are met:
  13.  * 1. Redistributions of source code must retain the above copyright
  14.  *    notice, this list of conditions and the following disclaimer.
  15.  * 2. Redistributions in binary form must reproduce the above copyright
  16.  *    notice, this list of conditions and the following disclaimer in the
  17.  *    documentation and/or other materials provided with the distribution.
  18.  * 3. All advertising materials mentioning features or use of this software
  19.  *    must display the following acknowledgement:
  20.  *    This product includes software developed by the University of
  21.  *    California, Berkeley and its contributors.
  22.  * 4. Neither the name of the University nor the names of its contributors
  23.  *    may be used to endorse or promote products derived from this software
  24.  *    without specific prior written permission.
  25.  *
  26.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36.  * SUCH DAMAGE.
  37.  */
  38.  
  39. #ifndef lint
  40. static char sccsid[] = "@(#)hash.c    5.5 (Berkeley) 12/28/90";
  41. #endif /* not lint */
  42.  
  43. /* hash.c --
  44.  *
  45.  *     This module contains routines to manipulate a hash table.
  46.  *     See hash.h for a definition of the structure of the hash
  47.  *     table.  Hash tables grow automatically as the amount of
  48.  *     information increases.
  49.  */
  50.  
  51. #include "sprite.h"
  52. #include "hash.h"
  53.  
  54. /*
  55.  * Forward references to local procedures that are used before they're
  56.  * defined:
  57.  */
  58.  
  59. static void        RebuildTable();
  60.  
  61. /* 
  62.  * The following defines the ratio of # entries to # buckets
  63.  * at which we rebuild the table to make it larger.
  64.  */
  65.  
  66. #define rebuildLimit 8
  67.  
  68. /*
  69.  *---------------------------------------------------------
  70.  * 
  71.  * Hash_InitTable --
  72.  *
  73.  *    This routine just sets up the hash table.
  74.  *
  75.  * Results:    
  76.  *    None.
  77.  *
  78.  * Side Effects:
  79.  *    Memory is allocated for the initial bucket area.
  80.  *
  81.  *---------------------------------------------------------
  82.  */
  83.  
  84. void
  85. Hash_InitTable(t, numBuckets)
  86.     register Hash_Table *t;    /* Structure to use to hold table. */
  87.     int numBuckets;        /* How many buckets to create for starters.
  88.                  * This number is rounded up to a power of
  89.                  * two.   If <= 0, a reasonable default is
  90.                  * chosen. The table will grow in size later
  91.                  * as needed. */
  92. {
  93.     register int i;
  94.     register struct Hash_Entry **hp;
  95.  
  96.     /*
  97.      * Round up the size to a power of two. 
  98.      */
  99.     if (numBuckets <= 0)
  100.         i = 16;
  101.     else {
  102.         for (i = 2; i < numBuckets; i <<= 1)
  103.              /* void */ ;
  104.     }
  105.     t->numEntries = 0;
  106.     t->size = i;
  107.     t->mask = i - 1;
  108.     t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i);
  109.     while (--i >= 0)
  110.         *hp++ = NULL;
  111. }
  112.  
  113. /*
  114.  *---------------------------------------------------------
  115.  *
  116.  * Hash_DeleteTable --
  117.  *
  118.  *    This routine removes everything from a hash table
  119.  *    and frees up the memory space it occupied (except for
  120.  *    the space in the Hash_Table structure).
  121.  *
  122.  * Results:    
  123.  *    None.
  124.  *
  125.  * Side Effects:
  126.  *    Lots of memory is freed up.
  127.  *
  128.  *---------------------------------------------------------
  129.  */
  130.  
  131. void
  132. Hash_DeleteTable(t)
  133.     Hash_Table *t;
  134. {
  135.     register struct Hash_Entry **hp, *h, *nexth;
  136.     register int i;
  137.  
  138.     for (hp = t->bucketPtr, i = t->size; --i >= 0;) {
  139.         for (h = *hp++; h != NULL; h = nexth) {
  140.             nexth = h->next;
  141.             free((char *)h);
  142.         }
  143.     }
  144.     free((char *)t->bucketPtr);
  145.  
  146.     /*
  147.      * Set up the hash table to cause memory faults on any future access
  148.      * attempts until re-initialization. 
  149.      */
  150.     t->bucketPtr = NULL;
  151. }
  152.  
  153. /*
  154.  *---------------------------------------------------------
  155.  *
  156.  * Hash_FindEntry --
  157.  *
  158.  *     Searches a hash table for an entry corresponding to key.
  159.  *
  160.  * Results:
  161.  *    The return value is a pointer to the entry for key,
  162.  *    if key was present in the table.  If key was not
  163.  *    present, NULL is returned.
  164.  *
  165.  * Side Effects:
  166.  *    None.
  167.  *
  168.  *---------------------------------------------------------
  169.  */
  170.  
  171. Hash_Entry *
  172. Hash_FindEntry(t, key)
  173.     Hash_Table *t;        /* Hash table to search. */
  174.     char *key;        /* A hash key. */
  175. {
  176.     register Hash_Entry *e;
  177.     register unsigned h;
  178.     register char *p;
  179.  
  180.     for (h = 0, p = key; *p;)
  181.         h = (h << 5) - h + *p++;
  182.     p = key;
  183.     for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next)
  184.         if (e->namehash == h && strcmp(e->name, p) == 0)
  185.             return (e);
  186.     return (NULL);
  187. }
  188.  
  189. /*
  190.  *---------------------------------------------------------
  191.  *
  192.  * Hash_CreateEntry --
  193.  *
  194.  *    Searches a hash table for an entry corresponding to
  195.  *    key.  If no entry is found, then one is created.
  196.  *
  197.  * Results:
  198.  *    The return value is a pointer to the entry.  If *newPtr
  199.  *    isn't NULL, then *newPtr is filled in with TRUE if a
  200.  *    new entry was created, and FALSE if an entry already existed
  201.  *    with the given key.
  202.  *
  203.  * Side Effects:
  204.  *    Memory may be allocated, and the hash buckets may be modified.
  205.  *---------------------------------------------------------
  206.  */
  207.  
  208. Hash_Entry *
  209. Hash_CreateEntry(t, key, newPtr)
  210.     register Hash_Table *t;    /* Hash table to search. */
  211.     char *key;        /* A hash key. */
  212.     Boolean *newPtr;    /* Filled in with TRUE if new entry created,
  213.                  * FALSE otherwise. */
  214. {
  215.     register Hash_Entry *e;
  216.     register unsigned h;
  217.     register char *p;
  218.     int keylen;
  219.     struct Hash_Entry **hp;
  220.  
  221.     /*
  222.      * Hash the key.  As a side effect, save the length (strlen) of the
  223.      * key in case we need to create the entry.
  224.      */
  225.     for (h = 0, p = key; *p;)
  226.         h = (h << 5) - h + *p++;
  227.     keylen = p - key;
  228.     p = key;
  229.     for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) {
  230.         if (e->namehash == h && strcmp(e->name, p) == 0) {
  231.             if (newPtr != NULL)
  232.                 *newPtr = FALSE;
  233.             return (e);
  234.         }
  235.     }
  236.  
  237.     /*
  238.      * The desired entry isn't there.  Before allocating a new entry,
  239.      * expand the table if necessary (and this changes the resulting
  240.      * bucket chain). 
  241.      */
  242.     if (t->numEntries >= rebuildLimit * t->size)
  243.         RebuildTable(t);
  244.     e = (Hash_Entry *) emalloc(sizeof(*e) + keylen);
  245.     hp = &t->bucketPtr[h & t->mask];
  246.     e->next = *hp;
  247.     *hp = e;
  248.     e->clientData = NULL;
  249.     e->namehash = h;
  250.     (void) strcpy(e->name, p);
  251.     t->numEntries++;
  252.  
  253.     if (newPtr != NULL)
  254.         *newPtr = TRUE;
  255.     return (e);
  256. }
  257.  
  258. /*
  259.  *---------------------------------------------------------
  260.  *
  261.  * Hash_DeleteEntry --
  262.  *
  263.  *     Delete the given hash table entry and free memory associated with
  264.  *    it.
  265.  *
  266.  * Results:
  267.  *    None.
  268.  *
  269.  * Side Effects:
  270.  *    Hash chain that entry lives in is modified and memory is freed.
  271.  *
  272.  *---------------------------------------------------------
  273.  */
  274.  
  275. void
  276. Hash_DeleteEntry(t, e)
  277.     Hash_Table *t;
  278.     Hash_Entry *e;
  279. {
  280.     register Hash_Entry **hp, *p;
  281.  
  282.     if (e == NULL)
  283.         return;
  284.     for (hp = &t->bucketPtr[e->namehash & t->mask];
  285.          (p = *hp) != NULL; hp = &p->next) {
  286.         if (p == e) {
  287.             *hp = p->next;
  288.             free((char *)p);
  289.             t->numEntries--;
  290.             return;
  291.         }
  292.     }
  293.     (void) write(2, "bad call to Hash_DeleteEntry\n", 29);
  294.     abort();
  295. }
  296.  
  297. /*
  298.  *---------------------------------------------------------
  299.  *
  300.  * Hash_EnumFirst --
  301.  *    This procedure sets things up for a complete search
  302.  *    of all entries recorded in the hash table.
  303.  *
  304.  * Results:    
  305.  *    The return value is the address of the first entry in
  306.  *    the hash table, or NULL if the table is empty.
  307.  *
  308.  * Side Effects:
  309.  *    The information in searchPtr is initialized so that successive
  310.  *    calls to Hash_Next will return successive HashEntry's
  311.  *    from the table.
  312.  *
  313.  *