CDE/cde/lib/csa/hash.c

/*
 * CDE - Common Desktop Environment
 *
 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
 *
 * These libraries and programs are free software; you can
 * redistribute them and/or modify them under the terms of the GNU
 * Lesser General Public License as published by the Free Software
 * Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * These libraries and programs are distributed in the hope that
 * they will be useful, but WITHOUT ANY WARRANTY; without even the
 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 * PURPOSE. See the GNU Lesser General Public License for more
 * details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with these libraries and programs; if not, write
 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
 * Floor, Boston, MA 02110-1301 USA
 */
/* $XConsortium: hash.c /main/1 1996/04/21 19:23:21 drk $ */
/*
 *  (c) Copyright 1993, 1994 Hewlett-Packard Company
 *  (c) Copyright 1993, 1994 International Business Machines Corp.
 *  (c) Copyright 1993, 1994 Novell, Inc.
 *  (c) Copyright 1993, 1994 Sun Microsystems, Inc.
 */

/*

Synopsis:  

           #include "hash.h"

           void * _DtCmMakeHash(int size)

	   void * _DtCmMakeIHash(int size)

           void ** _DtCmGetHash(void * tbl, unsigned char * key)

	   void ** _DtCmFindHash(void * tbl,unsigned char * key)

	   void ** _DtCmDelHash(void * tbl, unsigned char * key)

	   int _DtCmOperateHash(void * tbl, void (*op_func)(), void * usr_arg)

	   void _DtCmDestroyHash(void * tbl, int (*des_func)(), void * usr_arg)


 Description: 

   These routines provide a general purpose hash table facility that
supports multiple open hash tables.  Each entry in the table consists of a
key and a data ptr.  The key is a null terminated character string, while
the data ptr is opaque. Since all the entries are maintained in a doubly
linked lists, deletions and operations on entire table execute very quickly.
This make these routines suitable for use when the tables may be very ephemeral.

  _DtCmMakeHash returns a pointer to the created table.  The size argument
indicate the number of buckets the routine is to allocate.  This should be ~
the max number of items expected in the table for maximum performance....
but /2 or /3 should still be ok.  Note that for maximum efficiency the hash
table size should be a prime number (a side effect of the hash alorithm).

  _DtCmMakeIHash performs the same function as _DtCmMakeHash, except that the hash
routines will use the key arguments as arbitrary integers rather than strings.

  _DtCmGetHash searches the specified hash table tbl for an entry with the
specified key.  If the entry does not exist, it is created with a NULL data
ptr.  The routine returns a ptr to the area where the data ptr is (can be)
stored.

  _DtCmFindHash searchs the table for an entry with the specified key.  If the
entry is found, the address of the data pointer associated with the key is
returned.  If no such entry exists, the routine returns NULL.

  _DtCmDelHash deletes the specified table entry and returns the associated data
ptr.  If the entry did not exist ( or the data ptr was NULL), the routine
returns NULL.

  _DtCmOperateHash calls the routine pointed to by op_func once for each entry
in tbl, with three arguments: the data ptr, the usr_arg ptr and a ptr to the
key for that entry (which should NOT be altered).  This is useful for
transversing a hash table quickly and operating on the entries. Note that
the order of the traversal of the hash table is the reverse order of
insertion.

  _DtCmDestroyHash destroys the specified hash table after operating on it
with the specified des_func function as described for _DtCmOperateHash.  All storage
allocated by the hash routines is reclaimed.

Author:  Bart Smaalders 1/89


*/
#include <EUSCompat.h>
#include <stdio.h> /* grab NULL define */
#include <stdlib.h>
#include <string.h>
#include "hash.h"

static int    hash_string();

typedef struct hash_entry {
  struct hash_entry 
    * next_entry,
    * right_entry,
    * left_entry;
  unsigned char *       	key;
  void 		* 		data;
} hash_entry;

typedef struct hash {
  int 		size;
  hash_entry ** table;
  hash_entry * 	start;   
  enum hash_type { String_Key = 0 , Integer_Key = 1} hash_type;
} hash;


void * _DtCmMakeHash(int size)
{
  hash * ptr;

  ptr        = (hash *) malloc(sizeof(*ptr));
  ptr->size  =   size;
  ptr->table = (hash_entry **) malloc( (unsigned) (sizeof(hash_entry *) * size) );
  (void)memset((char *) ptr->table, (char) 0, sizeof(hash_entry *)*size);
  ptr->start = NULL;
  ptr->hash_type = String_Key;
  return((void*)ptr);
}

void ** _DtCmGetHash(void * t, const unsigned char * key)
{	
  hash * tbl = (hash *) t;
  int bucket;
  hash_entry * tmp;
  hash_entry * new;

  if(tbl->hash_type == String_Key)
    tmp = tbl->table[bucket = hash_string(key, tbl->size)];
  else
    tmp = tbl->table[bucket = abs((long)key) % tbl->size];

  if(tbl->hash_type == String_Key)
    while(tmp!=NULL)
      {	
	if(strcmp((char *)tmp->key, (char *)key)==0)
	  return(&tmp->data);
	tmp = tmp->next_entry;
      }
  else
    while(tmp!=NULL)
      {	
	if(tmp->key == key)
	  return(&tmp->data);
	tmp = tmp->next_entry;
      }
    
  /*
    not found.... 
    insert new entry into bucket...
    */

  new = (hash_entry *) malloc(sizeof(*new));
  new->key = (unsigned char *)((tbl->hash_type == String_Key)?(unsigned char *)strdup((char *)key):key);
  /*
    hook into chain from tbl...
    */
  new->right_entry = NULL;
  new->left_entry = tbl->start;
  tbl->start = new;
  /*
    hook into bucket chain
    */
  new->next_entry = tbl->table[bucket];
  tbl->table[bucket] = new;
  new->data = NULL;   /* so we know that it is new */
  return((void*)& new->data);
}

void ** _DtCmFindHash(void * t, const unsigned char * key)
{
  hash * tbl = (hash *) t;
  hash_entry * tmp;

  if(tbl->hash_type == String_Key)
    {
      tmp = tbl->table[hash_string(key, tbl->size)];
      for(;tmp!=NULL; tmp = tmp->next_entry)
	if(!strcmp((char *)tmp->key, (char *)key))
	  return((void *)&tmp->data);
    }
  else
    {
      tmp = tbl->table[abs((long)key) % tbl->size];
      for(;tmp!=NULL; tmp = tmp->next_entry)
	if(tmp->key == key)
	  return((void *)&tmp->data);
    }

  return(NULL);
}

void _DtCmDestroyHash(void * t, int (*ptr)(), void * usr_arg)
{
  hash * tbl = (hash *) t;
  hash_entry * tmp = tbl->start, * prev;

  while(tmp)
    {
      if(ptr)
	(*ptr)(tmp->data,usr_arg, tmp->key);

      if(tbl->hash_type == String_Key)
	free(tmp->key);
      prev = tmp;
      tmp = tmp->left_entry;
      free((char *)prev);
    }
  free((char *)tbl->table);
  free(tbl);
}

static int hash_string(char *s, int modulo)
{
	unsigned result = 0;
	int i=1;

 	while(*s!=0)
	  result += (*s++ << i++);

 	return(result % modulo); 
}