/*
 * Copyright (C) 1989-94 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.
 */

/*
 * Warning:
 * This module is part of the Thot library, which was originally
 * developed in French. That's why some comments are still in
 * French, but their translation is in progress and the full module
 * will be available in English in the next release.
 * 
 */

/*****************************************************************************\
* hashtable.c:                                                                *
*                                                                             *
*  XPM library                                                                *
*                                                                             *
*  Developed by Arnaud Le Hors                                                *
*  this originaly comes from Colas Nahaboo as a part of Wool                  *
*                                                                             *
\*****************************************************************************/

#include "thot_gui.h"
#include "thot_sys.h"

#include "xpmP.h"

LFUNC (AtomMake, xpmHashAtom, (char *name, void *data));
LFUNC (HashTableGrows, int, (xpmHashTable * table));

#ifdef __STDC__
static              xpmHashAtom
                    AtomMake (char *name, void *data)

#else  /* __STDC__ */
static              xpmHashAtom
                    AtomMake (name, data)
char               *name;
void               *data;

#endif /* __STDC__ */

{
   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 __STDC__
xpmHashAtom        *
                    xpmHashSlot (xpmHashTable * table, char *s)

#else  /* __STDC__ */
xpmHashAtom        *
                    xpmHashSlot (table, s)
xpmHashTable       *table;
char               *s;

#endif /* __STDC__ */

{
   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 __STDC__
static int
                    HashTableGrows (xpmHashTable * table)

#else  /* __STDC__ */
static int
                    HashTableGrows (table)
xpmHashTable       *table;

#endif /* __STDC__ */

{
   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->CHKR_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 __STDC__
int
                    xpmHashIntern (xpmHashTable * table, char *tag, void *data)

#else  /* __STDC__ */
int
                    xpmHashIntern (table, tag, data)
xpmHashTable       *table;
char               *tag;
void               *data;

#endif /* __STDC__ */

{
   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->CHKR_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 __STDC__
int
                    xpmHashTableInit (xpmHashTable * table)

#else  /* __STDC__ */
int
                    xpmHashTableInit (table)
xpmHashTable       *table;

#endif /* __STDC__ */

{
   xpmHashAtom        *p;
   xpmHashAtom        *atomTable;

   table->size = INITIAL_HASH_SIZE;
   table->CHKR_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 __STDC__
void
                    xpmHashTableFree (xpmHashTable * table)

#else  /* __STDC__ */
void
                    xpmHashTableFree (table)
xpmHashTable       *table;

#endif /* __STDC__ */

{
   xpmHashAtom        *p;
   xpmHashAtom        *atomTable = table->atomTable;

   for (p = atomTable + table->size; p > atomTable;)
      if (*--p)
	 XpmFree (*p);
   XpmFree (atomTable);
   table->atomTable = NULL;
}