/* $XConsortium: Hash.c /main/6 1995/10/25 20:06:11 cde-sun $ */

/*

 * Motif

 *

 * Copyright (c) 1987-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 librararies and programs; if not, write

 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth

 * Floor, Boston, MA 02110-1301 USA

 */

/*

 * HISTORY

 */

#ifdef HAVE_CONFIG_H

#include <config.h>

#endif

#include "XmI.h"

#include "HashI.h"

#define FIX_1264

/* Private data structures */

typedef struct _XmHashBucketRec {

  XmHashValue		  hashed_key;

  XmHashKey		  hash_key;

  XtPointer		  value;

  struct _XmHashBucketRec *next;

} XmHashBucketRec, *XmHashBucket;

typedef struct _XmHashTableRec {

  Cardinal		size;

  Cardinal		count;

  XmHashCompareProc	compare;

  XmHashFunction	hasher;

  XmHashBucket		*buckets;

} XmHashTableRec;

/* Static functions */

static XmHashBucket NewBucket(void);

static void FreeBucket(XmHashBucket);

/* Static data */

static XmHashBucket FreeBucketList = NULL;

/* Dumb default hash functions */

static Boolean 

Compare(XmHashKey x, XmHashKey y)

{

  return(x == y);

}

static XmHashValue

Hash(XmHashKey x)

{

  return((XmHashValue) (long) x);

}

/* Available table sizes,  should be prime numbers */

static XmConst int size_table[] = 

	{ 17, 31, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 0 };

XmHashTable

_XmAllocHashTable(Cardinal size_hint, XmHashCompareProc cproc, 

		  XmHashFunction hproc)

{

  XmHashTable   table;

  int		i;

  table = (XmHashTable) XtMalloc(sizeof(XmHashTableRec));

  if (hproc)

    table -> hasher = hproc;

  else

    table -> hasher = Hash;

  if (cproc)

    table -> compare = cproc;

  else

    table -> compare = Compare;

  i = 0;

  /* Search size_table for size which is bigger than size_hint */

  while(size_table[i] != 0 &&

	size_table[i] < size_hint) i++;

  if (size_table[i] == 0) i--;

  table -> size = size_table[i];

  table -> count = 0;

  /* Create the array of pointers */

  table->buckets = (XmHashBucket*) XtCalloc(table->size, sizeof(XmHashBucket));

  return(table);

}

void

_XmFreeHashTable(XmHashTable table)

{

  int i;

  XmHashBucket bucket, next;

  for(i = 0; i < table -> size; i++) {

    bucket = table -> buckets[i];

    while(bucket) {

      next = bucket -> next;

      FreeBucket(bucket);

      bucket = next;

    }

  }

  XtFree((char*) table -> buckets);

  XtFree((char*) table);

}

void

_XmResizeHashTable(XmHashTable table, Cardinal new_size)

{

  int i, index;

  int oldsize;

  XmHashBucket current, last, next, new_h;

  i = 0;

  /* Search size_table for size which is bigger than size_hint */

  while(size_table[i] != 0 &&

	size_table[i] < new_size) i++;

  if (size_table[i] == 0) i--;

  /* New size should be larger,  otherwise return */

  if (size_table[i] <= table -> size) return;

  /* Realloc table */

  oldsize = table -> size;

  table -> size = size_table[i];

  table -> buckets = 

    (XmHashBucket*) XtRealloc((char*) table -> buckets, 

			      table -> size * sizeof(XmHashBucket));

  /* NULL new array entries */

  for(i = oldsize; i < table -> size; i++) table -> buckets[i] = NULL;

  /* Rearrange buckets,  this is a slow method,  but always

     correct.  We will end up rescanning any moved buckets */

  for(i = 0; i < table -> size; i++) {

    last = NULL;

    current = table -> buckets[i];

    while(current) {

      /* If this bucket goes somewhere else,  remove 

	 from this chain and reinstall */

      next = current -> next;

      index = current -> hashed_key % table -> size;

      if (index != i) {

	if (last != NULL)

	  last -> next = current -> next;

	else

	  table -> buckets[i] = current -> next;

	/* Now put at end of new bucket chain,  we must do

	   this to maintain ordering */

	current -> next = NULL;

	new_h = table -> buckets[index];

	if (new_h != NULL) {

	  while(new_h -> next != NULL) 

	    new_h = new_h -> next;

	  new_h -> next = current;

	} else {

	  table -> buckets[index] = current;

	}

      }

#ifdef FIX_1264

      else last = current;

#endif

      current = next;

    }

  }

}

XtPointer

_XmGetHashEntryIterate(XmHashTable table, XmHashKey key, XtPointer *iterator)

{

  XmHashValue index;

  XmHashBucket entry;

  if (iterator && *iterator != NULL) {

    /* If iterating over a number of matching entries */

    entry = (XmHashBucket) *iterator;

    entry = entry -> next;

  } else { 

    /* Normal case */

    index = (table -> hasher(key)) % table -> size;

    entry = table -> buckets[index];

  }

  while(entry) {

    if (table -> compare(entry -> hash_key, key)) {

      if (iterator) *iterator = (XtPointer) entry;

      return(entry -> value);

    }

    entry = entry -> next;

  }

  if (iterator) *iterator = NULL;

  return(NULL);

}

void 

_XmAddHashEntry(XmHashTable table, XmHashKey key, XtPointer value)

{

  int hash;

  XmHashValue index;

  XmHashBucket entry;

  hash = table -> hasher(key);

  index = hash % table -> size;

  entry = NewBucket();

  entry -> hashed_key = hash;

  entry -> hash_key = key;

  entry -> value = value;

  entry -> next = table -> buckets[index];

  table -> buckets[index] = entry;

  table -> count++;

}

XtPointer

_XmRemoveHashEntry(XmHashTable table, XmHashKey key)

{

  XmHashValue index;

  XmHashBucket entry, last = NULL;

  index = (table -> hasher(key)) % table -> size;

  entry = table -> buckets[index];

  while(entry) {

    if (table -> compare(entry -> hash_key, key)) {

      if (last == NULL) {

	/* First entry is handled differently */

	table -> buckets[index] = entry -> next;

      } else {

	last -> next = entry -> next;

      }

      table -> count--;

      FreeBucket(entry);

      return(entry -> hash_key);

    }

    last = entry;

    entry = entry -> next;

  }

  return(NULL);

}

XtPointer 

_XmRemoveHashIterator(XmHashTable table, XtPointer *iterator)

{

  XmHashValue index;

  XmHashBucket entry, current, last = NULL;

  if (! iterator) return(NULL);

  entry = (XmHashBucket) *iterator;

  index = (table -> hasher(entry -> hash_key)) % table -> size;

  current = table -> buckets[index];

  while(current) {

    if (current == entry) {

      if (last == NULL) {

	/* First entry is handled differently */

	table -> buckets[index] = current -> next;

      } else {

	last -> next = current -> next;

      }

      table -> count--;

      FreeBucket(current);

      return(current -> hash_key);

    }

    last = current;

    current = current -> next;

  }

  return(NULL);

}

Cardinal

_XmHashTableCount(XmHashTable table)

{

  return(table -> count);

}

Cardinal

_XmHashTableSize(XmHashTable table)

{

  return(table -> size);

}

/****************************************************************/

/* _XmMapHashTable(table, proc, client_data)			*/

/* Iterate over entire hash table.  Mostly useful for debugging */

/* code using hash tables.					*/

/****************************************************************/

void 

_XmMapHashTable(XmHashTable table, XmHashMapProc proc, XtPointer client_data)

{

  int i;

  XmHashBucket entry, next;

  for(i = 0; i < table -> size; i++) {

    entry = table -> buckets[i];

    while(entry) {

      /* Can free key and value in this proc */

      next = entry -> next;

      /* Terminate processing if the XmHashMapProc return True. */

      if (proc (entry -> hash_key, entry -> value, client_data))

	return;

      entry = next;

    }

  }

}

/* Bucket management */

#define NUMBUCKETS 256

static XmHashBucket 

NewBucket(void)

{

  XmHashBucket rbucket;

  XmHashBucket buckets;

  int i;

  if (FreeBucketList == NULL) {

    /* Allocate alot of buckets at once to cut down on fragmentation */

    buckets = (XmHashBucket) XtMalloc(NUMBUCKETS * sizeof(XmHashBucketRec));

    /* Chain them together */

    for(i = 0; i < NUMBUCKETS; i++) buckets[i].next = &buckets[i+1];

    /* The last points to nothing */

    buckets[NUMBUCKETS - 1].next = (XmHashBucket) NULL;

    FreeBucketList = buckets;

  }

  rbucket = FreeBucketList;

  FreeBucketList = FreeBucketList -> next;

  return(rbucket);

}

static void

FreeBucket(XmHashBucket b)

{

  b -> next = FreeBucketList;

  FreeBucketList = b;

}

#ifdef DEBUG

void

_XmPrintHashTable(XmHashTable table)

{

  int i, max, total_in_use;

  int count;

  XmHashBucket entry;

  max = 0;

  total_in_use = 0;

  printf("size %d hash function %lx compare function %lx\n",

	 table->size, (unsigned long) table->hasher, 

	 (unsigned long) table->compare);

  for (i = 0; i < table -> size; i++) {

    entry = table -> buckets[i];

    count = 0;

    while(entry) {

      count++;

      entry = entry -> next;

    }

    if (count > 0) total_in_use++;

    if (count > max) max = count;

  }

  printf("total entries %d\n", table -> count);

  printf("total bucket chains in use %d or %d percent\n", total_in_use,

	 (total_in_use * 100)/table -> size);

  printf("bucket chain length %d average / %d max\n",

	 table -> count / total_in_use, max);

}

#endif