Back to index

plt-scheme  4.2.1
hashtab.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 1989-95 GROUPE BULL
00003  *
00004  * Permission is hereby granted, free of charge, to any person obtaining a copy
00005  * of this software and associated documentation files (the "Software"), to
00006  * deal in the Software without restriction, including without limitation the
00007  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
00008  * sell copies of the Software, and to permit persons to whom the Software is
00009  * furnished to do so, subject to the following conditions:
00010  *
00011  * The above copyright notice and this permission notice shall be included in
00012  * all copies or substantial portions of the Software.
00013  *
00014  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00015  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00016  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
00017  * GROUPE BULL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
00018  * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
00019  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00020  *
00021  * Except as contained in this notice, the name of GROUPE BULL shall not be
00022  * used in advertising or otherwise to promote the sale, use or other dealings
00023  * in this Software without prior written authorization from GROUPE BULL.
00024  */
00025 
00026 /*****************************************************************************\
00027 * hashtab.c:                                                                  *
00028 *                                                                             *
00029 *  XPM library                                                                *
00030 *                                                                             *
00031 *  Developed by Arnaud Le Hors                                                *
00032 *  this originaly comes from Colas Nahaboo as a part of Wool                  *
00033 *                                                                             *
00034 \*****************************************************************************/
00035 
00036 #include "xpmP.h"
00037 #if defined(SYSV) || defined(SVR4) || defined(VMS) || defined(__GNUC__)
00038 #include <string.h>
00039 #else
00040 #include <strings.h>
00041 #endif
00042 
00043 LFUNC(AtomMake, xpmHashAtom, (char *name, void *data));
00044 LFUNC(HashTableGrows, int, (xpmHashTable * table));
00045 
00046 static xpmHashAtom
00047 AtomMake(name, data)               /* makes an atom */
00048     char *name;                           /* WARNING: is just pointed to */
00049     void *data;
00050 {
00051     xpmHashAtom object = (xpmHashAtom) XpmMalloc(sizeof(struct _xpmHashAtom));
00052 
00053     if (object) {
00054        object->name = name;
00055        object->data = data;
00056     }
00057     return object;
00058 }
00059 
00060 /************************\
00061 *                     *
00062 *  hash table routines       *
00063 *                     *
00064 \************************/
00065 
00066 /*
00067  * Hash function definition:
00068  * HASH_FUNCTION: hash function, hash = hashcode, hp = pointer on char,
00069  *                           hash2 = temporary for hashcode.
00070  * INITIAL_TABLE_SIZE in slots
00071  * HASH_TABLE_GROWS how hash table grows.
00072  */
00073 
00074 /* Mock lisp function */
00075 #define HASH_FUNCTION         hash = (hash << 5) - hash + *hp++;
00076 /* #define INITIAL_HASH_SIZE 2017 */
00077 #define INITIAL_HASH_SIZE 256             /* should be enough for colors */
00078 #define HASH_TABLE_GROWS  size = size * 2;
00079 
00080 /* aho-sethi-ullman's HPJ (sizes should be primes)*/
00081 #ifdef notdef
00082 #define HASH_FUNCTION       hash <<= 4; hash += *hp++; \
00083     if(hash2 = hash & 0xf0000000) hash ^= (hash2 >> 24) ^ hash2;
00084 #define INITIAL_HASH_SIZE 4095            /* should be 2^n - 1 */
00085 #define HASH_TABLE_GROWS  size = size << 1 + 1;
00086 #endif
00087 
00088 /* GNU emacs function */
00089 /*
00090 #define HASH_FUNCTION         hash = (hash << 3) + (hash >> 28) + *hp++;
00091 #define INITIAL_HASH_SIZE 2017
00092 #define HASH_TABLE_GROWS  size = size * 2;
00093 */
00094 
00095 /* end of hash functions */
00096 
00097 /*
00098  * The hash table is used to store atoms via their NAME:
00099  *
00100  * NAME --hash--> ATOM |--name--> "foo"
00101  *                   |--data--> any value which has to be stored
00102  *
00103  */
00104 
00105 /*
00106  * xpmHashSlot gives the slot (pointer to xpmHashAtom) of a name
00107  * (slot points to NULL if it is not defined)
00108  *
00109  */
00110 
00111 xpmHashAtom *
00112 xpmHashSlot(table, s)
00113     xpmHashTable *table;
00114     char *s;
00115 {
00116     xpmHashAtom *atomTable = table->atomTable;
00117     unsigned int hash;
00118     xpmHashAtom *p;
00119     char *hp = s;
00120     char *ns;
00121 
00122     hash = 0;
00123     while (*hp) {                  /* computes hash function */
00124        HASH_FUNCTION
00125     }
00126     p = atomTable + hash % table->size;
00127     while (*p) {
00128        ns = (*p)->name;
00129        if (ns[0] == s[0] && strcmp(ns, s) == 0)
00130            break;
00131        p--;
00132        if (p < atomTable)
00133            p = atomTable + table->size - 1;
00134     }
00135     return p;
00136 }
00137 
00138 static int
00139 HashTableGrows(table)
00140     xpmHashTable *table;
00141 {
00142     xpmHashAtom *atomTable = table->atomTable;
00143     int size = table->size;
00144     xpmHashAtom *t, *p;
00145     int i;
00146     int oldSize = size;
00147 
00148     t = atomTable;
00149     HASH_TABLE_GROWS
00150        table->size = size;
00151     table->limit = size / 3;
00152     atomTable = (xpmHashAtom *) XpmMalloc(size * sizeof(*atomTable));
00153     if (!atomTable)
00154        return (XpmNoMemory);
00155     table->atomTable = atomTable;
00156     for (p = atomTable + size; p > atomTable;)
00157        *--p = NULL;
00158     for (i = 0, p = t; i < oldSize; i++, p++)
00159        if (*p) {
00160            xpmHashAtom *ps = xpmHashSlot(table, (*p)->name);
00161 
00162            *ps = *p;
00163        }
00164     XpmFree(t);
00165     return (XpmSuccess);
00166 }
00167 
00168 /*
00169  * xpmHashIntern(table, name, data)
00170  * an xpmHashAtom is created if name doesn't exist, with the given data.
00171  */
00172 
00173 int
00174 xpmHashIntern(table, tag, data)
00175     xpmHashTable *table;
00176     char *tag;
00177     void *data;
00178 {
00179     xpmHashAtom *slot;
00180 
00181     if (!*(slot = xpmHashSlot(table, tag))) {
00182        /* undefined, make a new atom with the given data */
00183        if (!(*slot = AtomMake(tag, data)))
00184            return (XpmNoMemory);
00185        if (table->used >= table->limit) {
00186            int ErrorStatus;
00187 
00188            if ((ErrorStatus = HashTableGrows(table)) != XpmSuccess)
00189               return (ErrorStatus);
00190            table->used++;
00191            return (XpmSuccess);
00192        }
00193        table->used++;
00194     }
00195     return (XpmSuccess);
00196 }
00197 
00198 /*
00199  *  must be called before allocating any atom
00200  */
00201 
00202 int
00203 xpmHashTableInit(table)
00204     xpmHashTable *table;
00205 {
00206     xpmHashAtom *p;
00207     xpmHashAtom *atomTable;
00208 
00209     table->size = INITIAL_HASH_SIZE;
00210     table->limit = table->size / 3;
00211     table->used = 0;
00212     atomTable = (xpmHashAtom *) XpmMalloc(table->size * sizeof(*atomTable));
00213     if (!atomTable)
00214        return (XpmNoMemory);
00215     for (p = atomTable + table->size; p > atomTable;)
00216        *--p = NULL;
00217     table->atomTable = atomTable;
00218     return (XpmSuccess);
00219 }
00220 
00221 /*
00222  *   frees a hashtable and all the stored atoms
00223  */
00224 
00225 void
00226 xpmHashTableFree(table)
00227     xpmHashTable *table;
00228 {
00229     xpmHashAtom *p;
00230     xpmHashAtom *atomTable = table->atomTable;
00231 
00232     for (p = atomTable + table->size; p > atomTable;)
00233        if (*--p)
00234            XpmFree(*p);
00235     XpmFree(atomTable);
00236     table->atomTable = NULL;
00237 }