home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / historic / v941.tgz / icon.v941src.tar / icon.v941src / src / xpm / hashtable.c < prev    next >
C/C++ Source or Header  |  2000-07-29  |  5KB  |  206 lines
  1. /* Copyright 1990-92 GROUPE BULL -- See license conditions in file COPYRIGHT */
  2. /*****************************************************************************\
  3. * hashtable.c:                                                                *
  4. *                                                                             *
  5. *  XPM library                                                                *
  6. *                                                                             *
  7. *  Developed by Arnaud Le Hors                                                *
  8. *  this originaly comes from Colas Nahaboo as a part of Wool                  *
  9. *                                                                             *
  10. \*****************************************************************************/
  11.  
  12. #include "xpmP.h"
  13.  
  14. LFUNC(AtomMake, xpmHashAtom, (char *name, void *data));
  15. LFUNC(HashTableGrows, int, (xpmHashTable *table));
  16.  
  17. static xpmHashAtom
  18. AtomMake(name, data)            /* makes an atom */
  19.     char *name;                /* WARNING: is just pointed to */
  20.     void *data;
  21. {
  22.     xpmHashAtom object = (xpmHashAtom) malloc(sizeof(struct _xpmHashAtom));
  23.     if (object) {
  24.     object->name = name;
  25.     object->data = data;
  26.     }
  27.     return object;
  28. }
  29.  
  30. /************************\
  31. *              *
  32. *  hash table routines      *
  33. *              *
  34. \************************/
  35.  
  36. /*
  37.  * Hash function definition:
  38.  * HASH_FUNCTION: hash function, hash = hashcode, hp = pointer on char,
  39.  *                 hash2 = temporary for hashcode.
  40.  * INITIAL_TABLE_SIZE in slots
  41.  * HASH_TABLE_GROWS how hash table grows.
  42.  */
  43.  
  44. /* Mock lisp function */
  45. #define HASH_FUNCTION       hash = (hash << 5) - hash + *hp++;
  46. /* #define INITIAL_HASH_SIZE 2017 */
  47. #define INITIAL_HASH_SIZE 256        /* should be enough for colors */
  48. #define HASH_TABLE_GROWS  size = size * 2;
  49.  
  50. /* aho-sethi-ullman's HPJ (sizes should be primes)*/
  51. #ifdef notdef
  52. #define HASH_FUNCTION    hash <<= 4; hash += *hp++; \
  53.     if(hash2 = hash & 0xf0000000) hash ^= (hash2 >> 24) ^ hash2;
  54. #define INITIAL_HASH_SIZE 4095        /* should be 2^n - 1 */
  55. #define HASH_TABLE_GROWS  size = size << 1 + 1;
  56. #endif
  57.  
  58. /* GNU emacs function */
  59. /*
  60. #define HASH_FUNCTION       hash = (hash << 3) + (hash >> 28) + *hp++;
  61. #define INITIAL_HASH_SIZE 2017
  62. #define HASH_TABLE_GROWS  size = size * 2;
  63. */
  64.  
  65. /* end of hash functions */
  66.  
  67. /*
  68.  * The hash table is used to store atoms via their NAME:
  69.  *
  70.  * NAME --hash--> ATOM |--name--> "foo"
  71.  *               |--data--> any value which has to be stored
  72.  *
  73.  */
  74.  
  75. /*
  76.  * xpmHashSlot gives the slot (pointer to xpmHashAtom) of a name
  77.  * (slot points to NULL if it is not defined)
  78.  *
  79.  */
  80.  
  81. xpmHashAtom *
  82. xpmHashSlot(table, s)
  83.     xpmHashTable *table;
  84.     char *s;
  85. {
  86.     xpmHashAtom *atomTable = table->atomTable;
  87.     unsigned int hash, hash2;
  88.     xpmHashAtom *p;
  89.     char *hp = s;
  90.     char *ns;
  91.  
  92.     hash = 0;
  93.     while (*hp) {            /* computes hash function */
  94.     HASH_FUNCTION
  95.     }
  96.     p = atomTable + hash % table->size;
  97.     while (*p) {
  98.     ns = (*p)->name;
  99.     if (ns[0] == s[0] && strcmp(ns, s) == 0)
  100.         break;
  101.     p--;
  102.     if (p < atomTable)
  103.         p = atomTable + table->size - 1;
  104.     }
  105.     return p;
  106. }
  107.  
  108. static int
  109. HashTableGrows(table)
  110.     xpmHashTable *table;
  111. {
  112.     xpmHashAtom *atomTable = table->atomTable;
  113.     int size = table->size;
  114.     xpmHashAtom *t, *p;
  115.     int i;
  116.     int oldSize = size;
  117.  
  118.     t = atomTable;
  119.     HASH_TABLE_GROWS
  120.     table->size = size;
  121.     table->limit = size / 3;
  122.     atomTable = (xpmHashAtom *) malloc(size * sizeof(*atomTable));
  123.     if (!atomTable)
  124.     return (XpmNoMemory);
  125.     table->atomTable = atomTable;
  126.     for (p = atomTable + size; p > atomTable;)
  127.     *--p = NULL;
  128.     for (i = 0, p = t; i < oldSize; i++, p++)
  129.     if (*p) {
  130.         xpmHashAtom *ps = xpmHashSlot(table, (*p)->name);
  131.         *ps = *p;
  132.     }
  133.     free(t);
  134.     return (XpmSuccess);
  135. }
  136.  
  137. /*
  138.  * xpmHashIntern(table, name, data)
  139.  * an xpmHashAtom is created if name doesn't exist, with the given data.
  140.  */
  141.  
  142. int
  143. xpmHashIntern(table, tag, data)
  144.     xpmHashTable *table;
  145.     char *tag;
  146.     void *data;
  147. {
  148.     xpmHashAtom *slot;
  149.  
  150.     if (!*(slot = xpmHashSlot(table, tag))) {
  151.     /* undefined, make a new atom with the given data */
  152.     if (!(*slot = AtomMake(tag, data)))
  153.         return (XpmNoMemory);
  154.     if (table->used >= table->limit) {
  155.         int ErrorStatus;
  156.         xpmHashAtom new = *slot;
  157.         if ((ErrorStatus = HashTableGrows(table)) != XpmSuccess)
  158.         return(ErrorStatus);
  159.         table->used++;
  160.         return (XpmSuccess);
  161.     }
  162.     table->used++;
  163.     }
  164.     return (XpmSuccess);
  165. }
  166.  
  167. /*
  168.  *  must be called before allocating any atom
  169.  */
  170.  
  171. int
  172. xpmHashTableInit(table)
  173.     xpmHashTable *table;
  174. {
  175.     xpmHashAtom *p;
  176.     xpmHashAtom *atomTable;
  177.  
  178.     table->size = INITIAL_HASH_SIZE;
  179.     table->limit = table->size / 3;
  180.     table->used = 0;
  181.     atomTable = (xpmHashAtom *) malloc(table->size * sizeof(*atomTable));
  182.     if (!atomTable)
  183.     return (XpmNoMemory);
  184.     for (p = atomTable + table->size; p > atomTable;)
  185.     *--p = NULL;
  186.     table->atomTable = atomTable;
  187.     return (XpmSuccess);
  188. }
  189.  
  190. /*
  191.  *   frees a hashtable and all the stored atoms
  192.  */
  193.  
  194. void
  195. xpmHashTableFree(table)
  196.     xpmHashTable *table;
  197. {
  198.     xpmHashAtom *p;
  199.     xpmHashAtom *atomTable = table->atomTable;
  200.     for (p = atomTable + table->size; p > atomTable;)
  201.     if (*--p)
  202.         free(*p);
  203.     free(atomTable);
  204.     table->atomTable = NULL;
  205. }
  206.