lib/Xm/Hash.c

/* $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