src/xpm/hashtab.c

/*
 * 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));

#ifdef __OS2__
/* Visual Age cannot deal with old, non-ansi, code */
static xpmHashAtom
AtomMake(char* name, void* data)			/* makes an atom */
#else
static xpmHashAtom
AtomMake(name, data)			/* makes an atom */
    char *name;				/* WARNING: is just pointed to */
    void *data;
#endif
{
    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)
 *
 */

#ifdef __OS2__
/* Visual Age cannot deal with old, non-ansi, code */
xpmHashAtom* xpmHashSlot(xpmHashTable* table, char* s)
#else
xpmHashAtom *
xpmHashSlot(table, s)
    xpmHashTable *table;
    char *s;
#endif
{
    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;
}

#ifdef __OS2__
/* Visual Age cannot deal with old, non-ansi, code */
static int HashTableGrows(xpmHashTable* table)
#else
static int
HashTableGrows(table)
    xpmHashTable *table;
#endif
{
    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.
 */

#ifdef __OS2__
/* Visual Age cannot deal with old, non-ansi, code */
int xpmHashIntern(xpmHashTable* table, char* tag, void* data)
#else
int
xpmHashIntern(table, tag, data)
    xpmHashTable *table;
    char *tag;
    void *data;
#endif
{
    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
 */

#ifdef __OS2__
/* Visual Age cannot deal with old, non-ansi, code */
int xpmHashTableInit(xpmHashTable* table)
#else
int
xpmHashTableInit(table)
    xpmHashTable *table;
#endif
{
    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
 */

#ifdef __OS2__
/* Visual Age cannot deal with old, non-ansi, code */
void
xpmHashTableFree(xpmHashTable* table)
#else
void
xpmHashTableFree(table)
    xpmHashTable *table;
#endif
{
    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;
}
Commit	Line	Data
	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	}