aboutsummaryrefslogtreecommitdiff
path: root/libXpm/src/hashtab.c
diff options
context:
space:
mode:
Diffstat (limited to 'libXpm/src/hashtab.c')
-rw-r--r--libXpm/src/hashtab.c239
1 files changed, 239 insertions, 0 deletions
diff --git a/libXpm/src/hashtab.c b/libXpm/src/hashtab.c
new file mode 100644
index 000000000..49e6e4831
--- /dev/null
+++ b/libXpm/src/hashtab.c
@@ -0,0 +1,239 @@
+/*
+ * Copyright (C) 1989-95 GROUPE BULL
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to
+ * deal in the Software without restriction, including without limitation the
+ * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * GROUPE BULL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
+ * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ *
+ * Except as contained in this notice, the name of GROUPE BULL shall not be
+ * used in advertising or otherwise to promote the sale, use or other dealings
+ * in this Software without prior written authorization from GROUPE BULL.
+ */
+
+/*****************************************************************************\
+* hashtab.c: *
+* *
+* XPM library *
+* *
+* Developed by Arnaud Le Hors *
+* this originaly comes from Colas Nahaboo as a part of Wool *
+* *
+\*****************************************************************************/
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+#include "XpmI.h"
+
+LFUNC(AtomMake, xpmHashAtom, (char *name, void *data));
+LFUNC(HashTableGrows, int, (xpmHashTable * table));
+
+static xpmHashAtom
+AtomMake( /* makes an atom */
+ char *name, /* WARNING: is just pointed to */
+ void *data)
+{
+ xpmHashAtom object = (xpmHashAtom) XpmMalloc(sizeof(struct _xpmHashAtom));
+
+ if (object) {
+ object->name = name;
+ object->data = data;
+ }
+ return object;
+}
+
+/************************\
+* *
+* hash table routines *
+* *
+\************************/
+
+/*
+ * Hash function definition:
+ * HASH_FUNCTION: hash function, hash = hashcode, hp = pointer on char,
+ * hash2 = temporary for hashcode.
+ * INITIAL_TABLE_SIZE in slots
+ * HASH_TABLE_GROWS how hash table grows.
+ */
+
+/* Mock lisp function */
+#define HASH_FUNCTION hash = (hash << 5) - hash + *hp++;
+/* #define INITIAL_HASH_SIZE 2017 */
+#define INITIAL_HASH_SIZE 256 /* should be enough for colors */
+#define HASH_TABLE_GROWS size = size * 2;
+
+/* aho-sethi-ullman's HPJ (sizes should be primes)*/
+#ifdef notdef
+#define HASH_FUNCTION hash <<= 4; hash += *hp++; \
+ if(hash2 = hash & 0xf0000000) hash ^= (hash2 >> 24) ^ hash2;
+#define INITIAL_HASH_SIZE 4095 /* should be 2^n - 1 */
+#define HASH_TABLE_GROWS size = size << 1 + 1;
+#endif
+
+/* GNU emacs function */
+/*
+#define HASH_FUNCTION hash = (hash << 3) + (hash >> 28) + *hp++;
+#define INITIAL_HASH_SIZE 2017
+#define HASH_TABLE_GROWS size = size * 2;
+*/
+
+/* end of hash functions */
+
+/*
+ * The hash table is used to store atoms via their NAME:
+ *
+ * NAME --hash--> ATOM |--name--> "foo"
+ * |--data--> any value which has to be stored
+ *
+ */
+
+/*
+ * xpmHashSlot gives the slot (pointer to xpmHashAtom) of a name
+ * (slot points to NULL if it is not defined)
+ *
+ */
+
+xpmHashAtom *
+xpmHashSlot(
+ xpmHashTable *table,
+ char *s)
+{
+ xpmHashAtom *atomTable = table->atomTable;
+ unsigned int hash;
+ xpmHashAtom *p;
+ char *hp = s;
+ char *ns;
+
+ hash = 0;
+ while (*hp) { /* computes hash function */
+ HASH_FUNCTION
+ }
+ p = atomTable + hash % table->size;
+ while (*p) {
+ ns = (*p)->name;
+ if (ns[0] == s[0] && strcmp(ns, s) == 0)
+ break;
+ p--;
+ if (p < atomTable)
+ p = atomTable + table->size - 1;
+ }
+ return p;
+}
+
+static int
+HashTableGrows(xpmHashTable *table)
+{
+ xpmHashAtom *atomTable = table->atomTable;
+ unsigned int size = table->size;
+ xpmHashAtom *t, *p;
+ int i;
+ unsigned int oldSize = size;
+
+ t = atomTable;
+ HASH_TABLE_GROWS
+ table->size = size;
+ table->limit = size / 3;
+ if (size >= UINT_MAX / sizeof(*atomTable))
+ return (XpmNoMemory);
+ atomTable = (xpmHashAtom *) XpmMalloc(size * sizeof(*atomTable));
+ if (!atomTable)
+ return (XpmNoMemory);
+ table->atomTable = atomTable;
+ for (p = atomTable + size; p > atomTable;)
+ *--p = NULL;
+ for (i = 0, p = t; i < oldSize; i++, p++)
+ if (*p) {
+ xpmHashAtom *ps = xpmHashSlot(table, (*p)->name);
+
+ *ps = *p;
+ }
+ XpmFree(t);
+ return (XpmSuccess);
+}
+
+/*
+ * xpmHashIntern(table, name, data)
+ * an xpmHashAtom is created if name doesn't exist, with the given data.
+ */
+
+int
+xpmHashIntern(
+ xpmHashTable *table,
+ char *tag,
+ void *data)
+{
+ xpmHashAtom *slot;
+
+ if (!*(slot = xpmHashSlot(table, tag))) {
+ /* undefined, make a new atom with the given data */
+ if (!(*slot = AtomMake(tag, data)))
+ return (XpmNoMemory);
+ if (table->used >= table->limit) {
+ int ErrorStatus;
+
+ if ((ErrorStatus = HashTableGrows(table)) != XpmSuccess)
+ return (ErrorStatus);
+ table->used++;
+ return (XpmSuccess);
+ }
+ table->used++;
+ }
+ return (XpmSuccess);
+}
+
+/*
+ * must be called before allocating any atom
+ */
+
+int
+xpmHashTableInit(xpmHashTable *table)
+{
+ xpmHashAtom *p;
+ xpmHashAtom *atomTable;
+
+ table->size = INITIAL_HASH_SIZE;
+ table->limit = table->size / 3;
+ table->used = 0;
+ table->atomTable = NULL;
+ if (table->size >= UINT_MAX / sizeof(*atomTable))
+ return (XpmNoMemory);
+ atomTable = (xpmHashAtom *) XpmMalloc(table->size * sizeof(*atomTable));
+ if (!atomTable)
+ return (XpmNoMemory);
+ for (p = atomTable + table->size; p > atomTable;)
+ *--p = NULL;
+ table->atomTable = atomTable;
+ return (XpmSuccess);
+}
+
+/*
+ * frees a hashtable and all the stored atoms
+ */
+
+void
+xpmHashTableFree(xpmHashTable *table)
+{
+ xpmHashAtom *p;
+ xpmHashAtom *atomTable = table->atomTable;
+
+ if (!atomTable)
+ return;
+ for (p = atomTable + table->size; p > atomTable;)
+ if (*--p)
+ XpmFree(*p);
+ XpmFree(atomTable);
+ table->atomTable = NULL;
+}