home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / lib / xp / xp_hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  14.7 KB  |  576 lines
  1. /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
  2.  *
  3.  * The contents of this file are subject to the Netscape Public License
  4.  * Version 1.0 (the "NPL"); you may not use this file except in
  5.  * compliance with the NPL.  You may obtain a copy of the NPL at
  6.  * http://www.mozilla.org/NPL/
  7.  *
  8.  * Software distributed under the NPL is distributed on an "AS IS" basis,
  9.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the NPL
  10.  * for the specific language governing rights and limitations under the
  11.  * NPL.
  12.  *
  13.  * The Initial Developer of this code under the NPL is Netscape
  14.  * Communications Corporation.  Portions created by Netscape are
  15.  * Copyright (C) 1998 Netscape Communications Corporation.  All Rights
  16.  * Reserved.
  17.  */
  18.  
  19.  
  20. #include "xp_hash.h"
  21. #include "xp.h"
  22.  
  23. #ifdef PROFILE
  24. #pragma profile on
  25. #endif
  26.  
  27. /*
  28.  * XP_StringHash() is from:
  29.  * Aho, Sethi, and Ullman, "Compilers - Principles, Techniques, and Tools",
  30.  * (the Dragon book), p436, hashpjw() by Peter J. Weinberger.
  31.  * Permission has been kindly granted by Mr Weinberger to release this
  32.  * function as part of the Mozilla public release.
  33.  */
  34. PUBLIC uint32
  35. XP_StringHash (const void *xv)
  36. { 
  37.   register uint32 h = 0;
  38.   register uint32 g;
  39.   register unsigned const char *x = (unsigned const char *) xv;
  40.  
  41.   assert(xv);
  42.  
  43.   if (!x) return 0;
  44.  
  45.   while (*x != 0)
  46.   {
  47.     h = (h << 4) + *x++;
  48.     if ((g = h & 0xf0000000) != 0)
  49.       h = (h ^ (g >> 24)) ^ g;
  50.   }
  51.  
  52.   return h;
  53. }
  54.  
  55. /*    phong's linear congruential hash  */
  56. uint32
  57. XP_StringHash2 (const char *ubuf)
  58. {
  59.     unsigned char * buf = (unsigned char*) ubuf;
  60.     uint32 h=1;
  61.     while(*buf)
  62.     {
  63.         h = 0x63c63cd9*h + 0x9c39c33d + (int32)*buf;
  64.         buf++;
  65.     }
  66.     return h;
  67. }
  68.  
  69.  
  70.  
  71. /* Hash tables.  For sure this time.
  72.  
  73.    These tables consist of a fixed number of buckets containing linked lists.
  74.    The number of buckets is forced to be prime.  Links in the buckets are
  75.    in no particular order.
  76.  
  77.    Since each link in the bucket is a seperate malloc'ed block, that incurs
  78.    nontrivial overhead; a more memory efficient model would have us avoid
  79.    colisions and enlarge and rehash the table when it got tight, but that
  80.    requires the table cells to be contiguous in memory, andw ith large
  81.    tables, that could get to be a problem, because of memory fragmentation.
  82.    So it's probably better to use many small mallocs.
  83.  
  84.    In hash tables, comparison function is used only as an equality test, not
  85.    an ordering test.  Hash lists use the order, but I don't see a benefit to
  86.    keeping links in the buckets ordered.
  87.  */
  88.  
  89. struct xp_HashTable
  90. {
  91.   XP_HashingFunction  hash_fn;
  92.   XP_HashCompFunction compare_fn;
  93.   uint32 size;
  94.   struct xp_HashBucket **buckets;
  95. };
  96.  
  97. struct xp_HashBucket
  98. {
  99.   const void *key;
  100.   void *value;
  101.   struct xp_HashBucket *next;
  102. };
  103.  
  104.  
  105. static const uint32 primes[] = {
  106.   /* 3, 7, 11, 13, 29, 37, 47, */ 59, 71, 89, 107, 131, 163, 197, 239, 293,
  107.   353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371,
  108.   4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023, 25229,
  109.   30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
  110.   187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403,
  111.   968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249 };
  112.  
  113.  
  114. static uint32
  115. toprime (uint32 size)
  116. {
  117.   register unsigned int i;
  118.   static unsigned int s = (sizeof (primes) / sizeof (*primes)) - 1;
  119.   for (i = 0; i < s; i++)
  120.     /* Return the smallest prime larger than SIZE, but don't return a
  121.        prime such that allocating an array of that many pointers will
  122.        allocate a block larger than 64k.  The toy computers can't do it,
  123.        and all platforms will assert().
  124.      */
  125.     if (size <= primes[i] ||
  126.         ((primes[i+1] * sizeof(void *)) >= 64000))
  127.       return primes[i];
  128.   return primes[s-1];
  129. }
  130.  
  131.  
  132. /* Create a new, empty hash table object.
  133.  */
  134. PUBLIC XP_HashTable
  135. XP_HashTableNew (uint32 size, 
  136.                  XP_HashingFunction  hash_fn, 
  137.                  XP_HashCompFunction compare_fn)
  138. {
  139.   struct xp_HashTable *table = XP_NEW (struct xp_HashTable);
  140.   if (!table) return 0;
  141.   table->hash_fn = hash_fn;
  142.   table->compare_fn = compare_fn;
  143.  
  144.   table->size = toprime (size);
  145.   table->buckets = (struct xp_HashBucket **)
  146.     XP_CALLOC (table->size, sizeof (struct xp_HashBucket *));
  147.   if (!table->buckets)
  148.     {
  149.       XP_FREE (table);
  150.       return 0;
  151.     }
  152.   return table;
  153. }
  154.  
  155. /* Remove all entries from the hash table.
  156.  */
  157. PUBLIC void
  158. XP_Clrhash (XP_HashTable table)
  159. {
  160.   XP_ASSERT (table);
  161.   if (!table)
  162.     return;
  163.  
  164.   XP_ASSERT (table->buckets);
  165.   if (table->buckets)
  166.     {
  167.       uint32 i;
  168.       struct xp_HashBucket *bucket, *next;
  169.       for (i = 0; i < table->size; i++)
  170.         for (bucket = table->buckets[i], next = bucket ? bucket->next : 0;
  171.              bucket;
  172.              bucket = next, next = bucket ? bucket->next : 0)
  173.           XP_FREE (bucket);
  174.       XP_MEMSET (table->buckets, 0, table->size * sizeof (*table->buckets));
  175.     }
  176. }
  177.  
  178.  
  179. /* Clear and free the hash table.
  180.  */
  181. PUBLIC void
  182. XP_HashTableDestroy (XP_HashTable table)
  183. {
  184.   XP_ASSERT (table);
  185.   if (!table)
  186.     return;
  187.   XP_Clrhash (table);
  188.   XP_ASSERT (table->buckets);
  189.   if (table->buckets)
  190.     XP_FREE (table->buckets);
  191.   XP_FREE (table);
  192. }
  193.  
  194. /* Add an association between KEY and VALUE to the hash table.
  195.    An existing association will be replaced.
  196.    (Note that 0 is a legal value.)
  197.    This can only fail if we run out of memory.
  198.  */
  199. PUBLIC int
  200. XP_Puthash (XP_HashTable table, const void *key, void *value)
  201. {
  202.   register uint32 bucket_num;
  203.   register struct xp_HashBucket *bucket, *prev;
  204.   XP_ASSERT (table);
  205.   if (! table) return -1;
  206.  
  207.   bucket_num = ((*table->hash_fn) (key)) % table->size;
  208.  
  209.   /* Iterate over all entries in this bucket.
  210.    */
  211.   for (prev = 0, bucket = table->buckets [bucket_num];
  212.        bucket;
  213.        prev = bucket, bucket = bucket->next)
  214.  
  215.     if (key == bucket->key ||
  216.         0 == (*table->compare_fn) (key, bucket->key))  /* We have a winner! */
  217.       {
  218.         bucket->value = value;
  219.         return 0;
  220.       }
  221.  
  222.   /* If we get here, there was no entry for this key in the table.
  223.    */
  224.   bucket = XP_NEW (struct xp_HashBucket);
  225.   if (! bucket)
  226.     return -1;
  227.  
  228.   bucket->key = key;
  229.   bucket->value = value;
  230.   bucket->next = 0;
  231.  
  232.   if (prev)
  233.     /* If prev has a value, it is the last bucket entry in the chain. */
  234.     prev->next = bucket;
  235.   else
  236.     table->buckets [bucket_num] = bucket;
  237.  
  238.   return 0;
  239. }
  240.  
  241. /* Remove the for KEY in the table, if it exists.
  242.    Returns FALSE if the key wasn't in the table.
  243.  */
  244. PUBLIC XP_Bool
  245. XP_Remhash (XP_HashTable table, const void *key)
  246. {
  247.   register uint32 bucket_num;
  248.   register struct xp_HashBucket *bucket, *prev;
  249.   XP_ASSERT (table);
  250.   if (! table) return -1;
  251.  
  252.   bucket_num = ((*table->hash_fn) (key)) % table->size;
  253.  
  254.   /* Iterate over all entries in this bucket.
  255.    */
  256.   for (prev = 0, bucket = table->buckets [bucket_num];
  257.        bucket;
  258.        prev = bucket, bucket = bucket->next)
  259.  
  260.     if (key == bucket->key ||
  261.         0 == (*table->compare_fn) (key, bucket->key))  /* We have a winner! */
  262.       {
  263.         if (prev)
  264.           prev->next = bucket->next;
  265.         else
  266.           table->buckets [bucket_num] = bucket->next;
  267.         XP_FREE (bucket);
  268.         return TRUE;
  269.       }
  270.  
  271.   return FALSE;
  272. }
  273.  
  274.  
  275. /* Looks up KEY in the table and returns the corresponding value.
  276.    If KEY is not in the table, `default_value' will be returned instead.
  277.    (This is necessary since 0 is a valid value with which a key can be
  278.    associated.)
  279.  */
  280. PUBLIC void *
  281. XP_Gethash (XP_HashTable table, const void *key, void *default_value)
  282. {
  283.   register uint32 bucket_num;
  284.   register struct xp_HashBucket *bucket;
  285.   XP_ASSERT (table);
  286.   if (! table) return default_value;
  287.  
  288.   bucket_num = ((*table->hash_fn) (key)) % table->size;
  289.   for (bucket = table->buckets [bucket_num]; bucket; bucket = bucket->next)
  290.     if (key == bucket->key ||
  291.         0 == (*table->compare_fn) (key, bucket->key))  /* We have a winner! */
  292.       return bucket->value;
  293.  
  294.   return default_value;
  295. }
  296.  
  297.  
  298. static void
  299. xp_maphash (XP_HashTable table, XP_HashTableMapper mapper, void *closure,
  300.             XP_Bool remhash_p)
  301. {
  302.   struct xp_HashBucket *bucket, *next;
  303.   uint32 i;
  304.   XP_ASSERT (table);
  305.   XP_ASSERT (mapper);
  306.   if (!table || !mapper) return;
  307.   /* map over buckets. */
  308.   for (i = 0; i < table->size; i++)
  309.     /* map over bucket entries.  Remember the "next" pointer in case
  310.        remhash is called. */
  311.     for (bucket = table->buckets[i], next = bucket ? bucket->next :0;
  312.          bucket;
  313.          bucket = next, next = bucket ? bucket->next : 0)
  314.       {
  315.         /* Call the mapper, and terminate early if it returns FALSE.
  316.            After calling the mapper, but before returning, free and
  317.            unlink the bucket if we're in remhash-mode.
  318.          */
  319.         XP_Bool status = (*mapper) (table, bucket->key, bucket->value,closure);
  320.         if (remhash_p)
  321.           {
  322.             XP_FREE (bucket);
  323.             /* It always becomes the top of the list, since we've freed
  324.                the others. */
  325.             table->buckets [i] = next;
  326.           }
  327.         if (status == FALSE)
  328.           return;
  329.       }
  330. }
  331.  
  332.  
  333. /* Apply a function to each pair of elements in the hash table.
  334.    If that function returns FALSE, then the mapping stops prematurely.
  335.    The mapping function may call XP_Remhash() on the *current* key, but
  336.    not on any other key in this table.  It also may not clear or destroy
  337.    the table.
  338.  */
  339. PUBLIC void
  340. XP_Maphash (XP_HashTable table, XP_HashTableMapper mapper, void *closure)
  341. {
  342.   xp_maphash (table, mapper, closure, FALSE);
  343. }
  344.  
  345. /* Apply a function to each pair of elements in the hash table.
  346.    After calling the function, that pair will be removed from the table.
  347.    If the function returns FALSE, then the mapping stops prematurely.
  348.    Any items which were not mapped over will still remain in the table,
  349.    but those items which were mapped over will have been freed.
  350.  
  351.    This could also be done by having the mapper function unconditionally
  352.    call XP_Remhash(), but using this function will be slightly more efficient.
  353.  */
  354. PUBLIC void
  355. XP_MapRemhash (XP_HashTable table, XP_HashTableMapper mapper, void *closure)
  356. {
  357.   xp_maphash (table, mapper, closure, TRUE);
  358. }
  359.  
  360.  
  361.  
  362. /* create a hash list, which isn't really a table.
  363.  */
  364. PUBLIC XP_HashList *
  365. XP_HashListNew (int size, 
  366.                   XP_HashingFunction  hash_func, 
  367.                   XP_HashCompFunction comp_func)
  368. {
  369.     XP_HashList * hash_struct = XP_NEW(XP_HashList);
  370.     XP_List **hash_list;
  371.     int new_size;
  372.  
  373.     if(!hash_struct)
  374.         return(NULL);
  375.  
  376.     new_size = toprime (size);
  377.     XP_ASSERT (new_size >= size);
  378.  
  379.     hash_list = (XP_List **) XP_ALLOC(sizeof(XP_List *) * new_size);
  380.  
  381.     if(!hash_list)
  382.       {
  383.         XP_FREE(hash_struct);
  384.         return(NULL);
  385.       }
  386.  
  387.     /* zero out the list
  388.      */
  389.     XP_MEMSET(hash_list, 0, sizeof(XP_List *) * new_size);
  390.  
  391.     hash_struct->list          = hash_list;
  392.     hash_struct->size          = new_size;
  393.     hash_struct->hash_func     = hash_func;
  394.     hash_struct->comp_func     = comp_func;
  395.     
  396.     return(hash_struct);
  397. }
  398.  
  399. /* free a hash list, which isn't really a table.
  400.  */
  401. PUBLIC void
  402. XP_HashListDestroy (XP_HashList * hash_struct)
  403. {
  404.     if(!hash_struct)
  405.        return;
  406.  
  407.     XP_FREE(hash_struct->list);
  408.     XP_FREE(hash_struct);
  409. }
  410.  
  411. /* add an element to a hash list, which isn't really a table.
  412.  *
  413.  * returns positive on success and negative on failure
  414.  *
  415.  * ERROR return codes
  416.  *
  417.  *  XP_HASH_DUPLICATE_OBJECT
  418.  */
  419. PUBLIC int
  420. XP_HashListAddObject (XP_HashList * hash_struct, void * new_ele)
  421. {
  422.     uint32   bucket_num;
  423.     int      result;
  424.     XP_List * list_ptr;
  425.     void   * obj_ptr;
  426.  
  427.     if(!hash_struct)
  428.        return -1;
  429.  
  430.     /* get an integer from the hashing function 
  431.      */
  432.     bucket_num = (*hash_struct->hash_func)(new_ele);
  433.  
  434.     /* adjust the integer to the size of the hash table
  435.      */
  436.     bucket_num = bucket_num % hash_struct->size;
  437.  
  438.     list_ptr = hash_struct->list[bucket_num];
  439.  
  440.     if(!list_ptr)
  441.       {
  442.         list_ptr = XP_ListNew();
  443.     
  444.         if(!list_ptr)
  445.             return -1;
  446.  
  447.         hash_struct->list[bucket_num] = list_ptr;
  448.       }
  449.  
  450.     /* run through the list and find an object that returns
  451.      * greater than 0 when compared
  452.      */
  453.     while((obj_ptr = XP_ListNextObject(list_ptr)) != 0)
  454.       {
  455.         result = (*hash_struct->comp_func)(obj_ptr, new_ele);
  456.         if(result > -1)
  457.            break;
  458.       }
  459.  
  460.     if(obj_ptr && result == 0)
  461.       {
  462.         /* the objects are the same!
  463.          */
  464.         return(XP_HASH_DUPLICATE_OBJECT);
  465.       }
  466.  
  467.     if(obj_ptr)
  468.       {
  469.         /* insert right before the obj_ptr 
  470.          */
  471.         XP_ListInsertObject(hash_struct->list[bucket_num], obj_ptr, new_ele);
  472.       }
  473.     else
  474.       {
  475.         /* it's either the first element to go into the list
  476.          * or it is the last by comparison
  477.          */
  478.         XP_ListAddObjectToEnd(hash_struct->list[bucket_num], new_ele);
  479.       }
  480.  
  481.     return 0; /* #### what should return value be? */
  482. }
  483.  
  484. /* finds an object by name in the hash list, which isn't really a table.
  485.  */
  486. PUBLIC void *
  487. XP_HashListFindObject (XP_HashList * hash_struct, void * ele)
  488. {
  489.     uint32   bucket_num;
  490.     int      result;
  491.     XP_List * list_ptr;
  492.     void   * obj_ptr;
  493.  
  494.     if(!hash_struct)
  495.        return(NULL);
  496.  
  497.     /* get an integer from the hashing function
  498.      */
  499.     bucket_num = (*hash_struct->hash_func)(ele);
  500.  
  501.     /* adjust the integer to the size of the hash table
  502.      */
  503.     bucket_num = bucket_num % hash_struct->size;
  504.  
  505.     list_ptr = hash_struct->list[bucket_num];
  506.  
  507.     /* run through the list and find the object
  508.      */
  509.     while((obj_ptr = XP_ListNextObject(list_ptr)) != 0)
  510.       {
  511.         result = (*hash_struct->comp_func)(obj_ptr, ele);
  512.  
  513.         if(result == 0)
  514.            return(obj_ptr);
  515.  
  516.         if(result > 0)
  517.            return(NULL);
  518.  
  519.       }
  520.  
  521.     return(NULL);
  522. }
  523.  
  524. /* removes an object by name from the hash list, which isn't really a table,
  525.  * and returns the object if found
  526.  */
  527. PUBLIC void *
  528. XP_HashListRemoveObject (XP_HashList * hash_struct, void * ele)
  529. {
  530.     uint32   bucket_num;
  531.     int      result;
  532.     XP_List * list_ptr;
  533.     void   * obj_ptr;
  534.  
  535.     if(!hash_struct || !ele)
  536.        return(NULL);
  537.  
  538.     /* get an integer from the hashing function
  539.      */
  540.     bucket_num = (*hash_struct->hash_func)(ele);
  541.  
  542.     /* adjust the integer to the size of the hash table
  543.      */
  544.     bucket_num = bucket_num % hash_struct->size;
  545.  
  546.     list_ptr = hash_struct->list[bucket_num];
  547.  
  548.     /* run through the list and find the object
  549.      */
  550.     while((obj_ptr = XP_ListNextObject(list_ptr)) != 0)
  551.       {
  552.         result = (*hash_struct->comp_func)(obj_ptr, ele);
  553.  
  554.         if(result == 0)
  555.           {
  556.             XP_ListRemoveObject(hash_struct->list[bucket_num], obj_ptr);
  557.  
  558. /* ALEKS. Bucket needs to be freed here if there are no more objects in it*/
  559.             if (hash_struct->list[bucket_num]->next == NULL)
  560.             {
  561.                 XP_ListDestroy(hash_struct->list[bucket_num]);
  562.                 hash_struct->list[bucket_num] = NULL;
  563.             }
  564.             return(obj_ptr);
  565.           }
  566.         
  567.         if(result > 0)
  568.            return(NULL);
  569.       }
  570.     return(NULL);
  571. }
  572.  
  573. #ifdef PROFILE
  574. #pragma profile on
  575. #endif
  576.