src/xpm/hashtab.c

   1 /*
   2  * Copyright (C) 1989-95 GROUPE BULL
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a copy
   5  * of this software and associated documentation files (the "Software"), to
   6  * deal in the Software without restriction, including without limitation the
   7  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
   8  * sell copies of the Software, and to permit persons to whom the Software is
   9  * furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  17  * GROUPE BULL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  18  * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  19  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  20  *
  21  * Except as contained in this notice, the name of GROUPE BULL shall not be
  22  * used in advertising or otherwise to promote the sale, use or other dealings
  23  * in this Software without prior written authorization from GROUPE BULL.
  24  */
  25
  26 /*****************************************************************************\
  27 * hashtab.c:                                                                  *
  28 *                                                                             *
  29 *  XPM library                                                                *
  30 *                                                                             *
  31 *  Developed by Arnaud Le Hors                                                *
  32 *  this originaly comes from Colas Nahaboo as a part of Wool                  *
  33 *                                                                             *
  34 \*****************************************************************************/
  35
  36 #include "XpmI.h"
  37
  38 LFUNC(AtomMake, xpmHashAtom, (char *name, void *data));
  39 LFUNC(HashTableGrows, int, (xpmHashTable * table));
  40
  41 static xpmHashAtom
  42 AtomMake(name, data)                    /* makes an atom */
  43     char *name;                         /* WARNING: is just pointed to */
  44     void *data;
  45 {
  46     xpmHashAtom object = (xpmHashAtom) XpmMalloc(sizeof(struct _xpmHashAtom));
  47
  48     if (object) {
  49         object->name = name;
  50         object->data = data;
  51     }
  52     return object;
  53 }
  54
  55 /************************\
  56 *                        *
  57 *  hash table routines   *
  58 *                        *
  59 \************************/
  60
  61 /*
  62  * Hash function definition:
  63  * HASH_FUNCTION: hash function, hash = hashcode, hp = pointer on char,
  64  *                               hash2 = temporary for hashcode.
  65  * INITIAL_TABLE_SIZE in slots
  66  * HASH_TABLE_GROWS how hash table grows.
  67  */
  68
  69 /* Mock lisp function */
  70 #define HASH_FUNCTION     hash = (hash << 5) - hash + *hp++;
  71 /* #define INITIAL_HASH_SIZE 2017 */
  72 #define INITIAL_HASH_SIZE 256           /* should be enough for colors */
  73 #define HASH_TABLE_GROWS  size = size * 2;
  74
  75 /* aho-sethi-ullman's HPJ (sizes should be primes)*/
  76 #ifdef notdef
  77 #define HASH_FUNCTION   hash <<= 4; hash += *hp++; \
  78     if(hash2 = hash & 0xf0000000) hash ^= (hash2 >> 24) ^ hash2;
  79 #define INITIAL_HASH_SIZE 4095          /* should be 2^n - 1 */
  80 #define HASH_TABLE_GROWS  size = size << 1 + 1;
  81 #endif
  82
  83 /* GNU emacs function */
  84 /*
  85 #define HASH_FUNCTION     hash = (hash << 3) + (hash >> 28) + *hp++;
  86 #define INITIAL_HASH_SIZE 2017
  87 #define HASH_TABLE_GROWS  size = size * 2;
  88 */
  89
  90 /* end of hash functions */
  91
  92 /*
  93  * The hash table is used to store atoms via their NAME:
  94  *
  95  * NAME --hash--> ATOM |--name--> "foo"
  96  *                     |--data--> any value which has to be stored
  97  *
  98  */
  99
 100 /*
 101  * xpmHashSlot gives the slot (pointer to xpmHashAtom) of a name
 102  * (slot points to NULL if it is not defined)
 103  *
 104  */
 105
 106 xpmHashAtom *
 107 xpmHashSlot(table, s)
 108     xpmHashTable *table;
 109     char *s;
 110 {
 111     xpmHashAtom *atomTable = table->atomTable;
 112     unsigned int hash;
 113     xpmHashAtom *p;
 114     char *hp = s;
 115     char *ns;
 116
 117     hash = 0;
 118     while (*hp) {                       /* computes hash function */
 119         HASH_FUNCTION
 120     }
 121     p = atomTable + hash % table->size;
 122     while (*p) {
 123         ns = (*p)->name;
 124         if (ns[0] == s[0] && strcmp(ns, s) == 0)
 125             break;
 126         p--;
 127         if (p < atomTable)
 128             p = atomTable + table->size - 1;
 129     }
 130     return p;
 131 }
 132
 133 static int
 134 HashTableGrows(table)
 135     xpmHashTable *table;
 136 {
 137     xpmHashAtom *atomTable = table->atomTable;
 138     int size = table->size;
 139     xpmHashAtom *t, *p;
 140     int i;
 141     int oldSize = size;
 142
 143     t = atomTable;
 144     HASH_TABLE_GROWS
 145         table->size = size;
 146     table->limit = size / 3;
 147     atomTable = (xpmHashAtom *) XpmMalloc(size * sizeof(*atomTable));
 148     if (!atomTable)
 149         return (XpmNoMemory);
 150     table->atomTable = atomTable;
 151     for (p = atomTable + size; p > atomTable;)
 152         *--p = NULL;
 153     for (i = 0, p = t; i < oldSize; i++, p++)
 154         if (*p) {
 155             xpmHashAtom *ps = xpmHashSlot(table, (*p)->name);
 156
 157             *ps = *p;
 158         }
 159     XpmFree(t);
 160     return (XpmSuccess);
 161 }
 162
 163 /*
 164  * xpmHashIntern(table, name, data)
 165  * an xpmHashAtom is created if name doesn't exist, with the given data.
 166  */
 167
 168 int
 169 xpmHashIntern(table, tag, data)
 170     xpmHashTable *table;
 171     char *tag;
 172     void *data;
 173 {
 174     xpmHashAtom *slot;
 175
 176     if (!*(slot = xpmHashSlot(table, tag))) {
 177         /* undefined, make a new atom with the given data */
 178         if (!(*slot = AtomMake(tag, data)))
 179             return (XpmNoMemory);
 180         if (table->used >= table->limit) {
 181             int ErrorStatus;
 182
 183             if ((ErrorStatus = HashTableGrows(table)) != XpmSuccess)
 184                 return (ErrorStatus);
 185             table->used++;
 186             return (XpmSuccess);
 187         }
 188         table->used++;
 189     }
 190     return (XpmSuccess);
 191 }
 192
 193 /*
 194  *  must be called before allocating any atom
 195  */
 196
 197 int
 198 xpmHashTableInit(table)
 199     xpmHashTable *table;
 200 {
 201     xpmHashAtom *p;
 202     xpmHashAtom *atomTable;
 203
 204     table->size = INITIAL_HASH_SIZE;
 205     table->limit = table->size / 3;
 206     table->used = 0;
 207     atomTable = (xpmHashAtom *) XpmMalloc(table->size * sizeof(*atomTable));
 208     if (!atomTable)
 209         return (XpmNoMemory);
 210     for (p = atomTable + table->size; p > atomTable;)
 211         *--p = NULL;
 212     table->atomTable = atomTable;
 213     return (XpmSuccess);
 214 }
 215
 216 /*
 217  *   frees a hashtable and all the stored atoms
 218  */
 219
 220 void
 221 xpmHashTableFree(table)
 222     xpmHashTable *table;
 223 {
 224     xpmHashAtom *p;
 225     xpmHashAtom *atomTable = table->atomTable;
 226
 227     if (!atomTable)
 228         return;
 229     for (p = atomTable + table->size; p > atomTable;)
 230         if (*--p)
 231             XpmFree(*p);
 232     XpmFree(atomTable);
 233     table->atomTable = NULL;
 234 }