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 #ifdef __OS2__
  42 /* Visual Age cannot deal with old, non-ansi, code */
  43 static xpmHashAtom
  44 AtomMake(char* name, void* data)                        /* makes an atom */
  45 #else
  46 static xpmHashAtom
  47 AtomMake(name, data)                    /* makes an atom */
  48     char *name;                         /* WARNING: is just pointed to */
  49     void *data;
  50 #endif
  51 {
  52     xpmHashAtom object = (xpmHashAtom) XpmMalloc(sizeof(struct _xpmHashAtom));
  53
  54     if (object) {
  55         object->name = name;
  56         object->data = data;
  57     }
  58     return object;
  59 }
  60
  61 /************************\
  62 *                        *
  63 *  hash table routines   *
  64 *                        *
  65 \************************/
  66
  67 /*
  68  * Hash function definition:
  69  * HASH_FUNCTION: hash function, hash = hashcode, hp = pointer on char,
  70  *                               hash2 = temporary for hashcode.
  71  * INITIAL_TABLE_SIZE in slots
  72  * HASH_TABLE_GROWS how hash table grows.
  73  */
  74
  75 /* Mock lisp function */
  76 #define HASH_FUNCTION     hash = (hash << 5) - hash + *hp++;
  77 /* #define INITIAL_HASH_SIZE 2017 */
  78 #define INITIAL_HASH_SIZE 256           /* should be enough for colors */
  79 #define HASH_TABLE_GROWS  size = size * 2;
  80
  81 /* aho-sethi-ullman's HPJ (sizes should be primes)*/
  82 #ifdef notdef
  83 #define HASH_FUNCTION   hash <<= 4; hash += *hp++; \
  84     if(hash2 = hash & 0xf0000000) hash ^= (hash2 >> 24) ^ hash2;
  85 #define INITIAL_HASH_SIZE 4095          /* should be 2^n - 1 */
  86 #define HASH_TABLE_GROWS  size = size << 1 + 1;
  87 #endif
  88
  89 /* GNU emacs function */
  90 /*
  91 #define HASH_FUNCTION     hash = (hash << 3) + (hash >> 28) + *hp++;
  92 #define INITIAL_HASH_SIZE 2017
  93 #define HASH_TABLE_GROWS  size = size * 2;
  94 */
  95
  96 /* end of hash functions */
  97
  98 /*
  99  * The hash table is used to store atoms via their NAME:
 100  *
 101  * NAME --hash--> ATOM |--name--> "foo"
 102  *                     |--data--> any value which has to be stored
 103  *
 104  */
 105
 106 /*
 107  * xpmHashSlot gives the slot (pointer to xpmHashAtom) of a name
 108  * (slot points to NULL if it is not defined)
 109  *
 110  */
 111
 112 #ifdef __OS2__
 113 /* Visual Age cannot deal with old, non-ansi, code */
 114 xpmHashAtom* xpmHashSlot(xpmHashTable* table, char* s)
 115 #else
 116 xpmHashAtom *
 117 xpmHashSlot(table, s)
 118     xpmHashTable *table;
 119     char *s;
 120 #endif
 121 {
 122     xpmHashAtom *atomTable = table->atomTable;
 123     unsigned int hash;
 124     xpmHashAtom *p;
 125     char *hp = s;
 126     char *ns;
 127
 128     hash = 0;
 129     while (*hp) {                       /* computes hash function */
 130         HASH_FUNCTION
 131     }
 132     p = atomTable + hash % table->size;
 133     while (*p) {
 134         ns = (*p)->name;
 135         if (ns[0] == s[0] && strcmp(ns, s) == 0)
 136             break;
 137         p--;
 138         if (p < atomTable)
 139             p = atomTable + table->size - 1;
 140     }
 141     return p;
 142 }
 143
 144 #ifdef __OS2__
 145 /* Visual Age cannot deal with old, non-ansi, code */
 146 static int HashTableGrows(xpmHashTable* table)
 147 #else
 148 static int
 149 HashTableGrows(table)
 150     xpmHashTable *table;
 151 #endif
 152 {
 153     xpmHashAtom *atomTable = table->atomTable;
 154     int size = table->size;
 155     xpmHashAtom *t, *p;
 156     int i;
 157     int oldSize = size;
 158
 159     t = atomTable;
 160     HASH_TABLE_GROWS
 161         table->size = size;
 162     table->limit = size / 3;
 163     atomTable = (xpmHashAtom *) XpmMalloc(size * sizeof(*atomTable));
 164     if (!atomTable)
 165         return (XpmNoMemory);
 166     table->atomTable = atomTable;
 167     for (p = atomTable + size; p > atomTable;)
 168         *--p = NULL;
 169     for (i = 0, p = t; i < oldSize; i++, p++)
 170         if (*p) {
 171             xpmHashAtom *ps = xpmHashSlot(table, (*p)->name);
 172
 173             *ps = *p;
 174         }
 175     XpmFree(t);
 176     return (XpmSuccess);
 177 }
 178
 179 /*
 180  * xpmHashIntern(table, name, data)
 181  * an xpmHashAtom is created if name doesn't exist, with the given data.
 182  */
 183
 184 #ifdef __OS2__
 185 /* Visual Age cannot deal with old, non-ansi, code */
 186 int xpmHashIntern(xpmHashTable* table, char* tag, void* data)
 187 #else
 188 int
 189 xpmHashIntern(table, tag, data)
 190     xpmHashTable *table;
 191     char *tag;
 192     void *data;
 193 #endif
 194 {
 195     xpmHashAtom *slot;
 196
 197     if (!*(slot = xpmHashSlot(table, tag))) {
 198         /* undefined, make a new atom with the given data */
 199         if (!(*slot = AtomMake(tag, data)))
 200             return (XpmNoMemory);
 201         if (table->used >= table->limit) {
 202             int ErrorStatus;
 203
 204             if ((ErrorStatus = HashTableGrows(table)) != XpmSuccess)
 205                 return (ErrorStatus);
 206             table->used++;
 207             return (XpmSuccess);
 208         }
 209         table->used++;
 210     }
 211     return (XpmSuccess);
 212 }
 213
 214 /*
 215  *  must be called before allocating any atom
 216  */
 217
 218 #ifdef __OS2__
 219 /* Visual Age cannot deal with old, non-ansi, code */
 220 int xpmHashTableInit(xpmHashTable* table)
 221 #else
 222 int
 223 xpmHashTableInit(table)
 224     xpmHashTable *table;
 225 #endif
 226 {
 227     xpmHashAtom *p;
 228     xpmHashAtom *atomTable;
 229
 230     table->size = INITIAL_HASH_SIZE;
 231     table->limit = table->size / 3;
 232     table->used = 0;
 233     atomTable = (xpmHashAtom *) XpmMalloc(table->size * sizeof(*atomTable));
 234     if (!atomTable)
 235         return (XpmNoMemory);
 236     for (p = atomTable + table->size; p > atomTable;)
 237         *--p = NULL;
 238     table->atomTable = atomTable;
 239     return (XpmSuccess);
 240 }
 241
 242 /*
 243  *   frees a hashtable and all the stored atoms
 244  */
 245
 246 #ifdef __OS2__
 247 /* Visual Age cannot deal with old, non-ansi, code */
 248 void
 249 xpmHashTableFree(xpmHashTable* table)
 250 #else
 251 void
 252 xpmHashTableFree(table)
 253     xpmHashTable *table;
 254 #endif
 255 {
 256     xpmHashAtom *p;
 257     xpmHashAtom *atomTable = table->atomTable;
 258
 259     if (!atomTable)
 260         return;
 261     for (p = atomTable + table->size; p > atomTable;)
 262         if (*--p)
 263             XpmFree(*p);
 264     XpmFree(atomTable);
 265     table->atomTable = NULL;
 266 }