Initial revisionXORG-STABLE

1 files changed, 234 insertions, 0 deletions

diff --git a/src/hashtab.c b/src/hashtab.c
new file mode 100644
index 0000000..7d596ec
--- /dev/null
+++ b/src/hashtab.c
@@ -0,0 +1,234 @@
+/*
+ * 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                  *
+*                                                                             *
+\*****************************************************************************/
+
+#include "XpmI.h"
+
+LFUNC(AtomMake, xpmHashAtom, (char *name, void *data));
+LFUNC(HashTableGrows, int, (xpmHashTable * table));
+
+static xpmHashAtom
+AtomMake(name, data)			/* 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(table, s)
+    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(table)
+    xpmHashTable *table;
+{
+    xpmHashAtom *atomTable = table->atomTable;
+    int size = table->size;
+    xpmHashAtom *t, *p;
+    int i;
+    int oldSize = size;
+
+    t = atomTable;
+    HASH_TABLE_GROWS
+	table->size = size;
+    table->limit = size / 3;
+    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(table, tag, data)
+    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(table)
+    xpmHashTable *table;
+{
+    xpmHashAtom *p;
+    xpmHashAtom *atomTable;
+
+    table->size = INITIAL_HASH_SIZE;
+    table->limit = table->size / 3;
+    table->used = 0;
+    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(table)
+    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;
+}