libs-base/Source/NSConcreteHashTable.m

/** Implementation of NSHashTable for GNUStep
   Copyright (C) 2009 Free Software Foundation, Inc.

   Written by:  Richard Frith-Macdonald <rfm@gnu.org>
   Date: April 2009

   Based on original o_hash code by Albin L. Jones <Albin.L.Jones@Dartmouth.EDU>

   This file is part of the GNUstep Base Library.

   This library is free software; you can redistribute it and/or
   modify it 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.

   This library is distributed in the hope that it 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 this library; if not, write to the Free
   Software Foundation, Inc., 31 Milk Street #960789 Boston, MA 02196 USA.

   $Date: 2008-06-08 11:38:33 +0100 (Sun, 08 Jun 2008) $ $Revision: 26606 $
   */

#import "common.h"

#import "Foundation/NSArray.h"
#import "Foundation/NSAutoreleasePool.h"
#import "Foundation/NSDictionary.h"
#import "Foundation/NSEnumerator.h"
#import "Foundation/NSException.h"
#import "Foundation/NSHashTable.h"

#import "NSConcretePointerFunctions.h"
#import "NSCallBacks.h"
#import "GSPrivate.h"

static Class	concreteClass = Nil;
static unsigned instanceSize = 0;


/* Here is the interface for the concrete class as used by the functions.
 */

typedef struct _GSIMapBucket GSIMapBucket_t;
typedef struct _GSIMapNode GSIMapNode_t;
typedef GSIMapBucket_t *GSIMapBucket;
typedef GSIMapNode_t *GSIMapNode;

@interface	NSConcreteHashTable : NSHashTable
{
@public
  NSZone	*zone;
  size_t	nodeCount;	/* Number of used nodes in hash.	*/
  size_t	bucketCount;	/* Number of buckets in hash.	*/
  GSIMapBucket	buckets;	/* Array of buckets.		*/
  GSIMapNode	freeNodes;	/* List of unused nodes.	*/
  GSIMapNode	*nodeChunks;	/* Chunks of allocated memory.	*/
  size_t	chunkCount;	/* Number of chunks in array.	*/
  size_t	increment;	/* Amount to grow by.		*/
  unsigned long	version;	/* For fast enumeration.	*/
  BOOL		legacy;		/* old style callbacks?		*/
  union {
    PFInfo	pf;
    NSHashTableCallBacks old;
  }cb;
}
@end

#define	GSI_MAP_HAS_VALUE	0
#define	GSI_MAP_KTYPES	GSUNION_PTR | GSUNION_OBJ
#define	GSI_MAP_TABLE_T	NSConcreteHashTable
#define	GSI_MAP_TABLE_S	instanceSize
  
#define IS_WEAK(M) \
  memoryType(M->cb.pf.options, NSPointerFunctionsWeakMemory)
#define GSI_MAP_HASH(M, X)\
 (M->legacy ? M->cb.old.hash(M, X.ptr) \
 : pointerFunctionsHash(&M->cb.pf, X.ptr))
#define GSI_MAP_EQUAL(M, X, Y)\
 (M->legacy ? M->cb.old.isEqual(M, X.ptr, Y.ptr) \
 : pointerFunctionsEqual(&M->cb.pf, X.ptr, Y.ptr))
#define GSI_MAP_ZEROED(M)\
 (M->legacy ? 0 : (IS_WEAK(M) ? YES : NO))

/* NSPointerFunctions provides functions which combine the actions of
 * memory allocation/deallocation with those of assignment, so we make
 * the separete retain/release macros a no-op nd do all the work in the
 * store/clear macros.
 */
#define GSI_MAP_RELEASE_KEY(M, X)
#define GSI_MAP_RETAIN_KEY(M, X) nil
#define GSI_MAP_CLEAR_KEY(M, addr)\
  if (M->legacy) \
    { M->cb.old.release(M, (*addr).ptr); (*addr).ptr = 0; }\
  else\
    pointerFunctionsRelinquish(&M->cb.pf, (void**)addr);
#define GSI_MAP_STORE_KEY(M, addr, x)\
  if (M->legacy)\
    { *(addr) = x; M->cb.old.retain(M, (*addr).ptr); }\
  else\
    pointerFunctionsReplace(&M->cb.pf, (void**)addr, (x).obj);

#define GSI_MAP_READ_KEY(M,addr) \
   (M->legacy ? *(addr) :\
   (__typeof__(*addr))pointerFunctionsRead(&M->cb.pf, (void**)addr))

#define	GSI_MAP_ENUMERATOR	NSHashEnumerator

#include "GNUstepBase/GSIMap.h"

/**** Function Implementations ****/

/**
 * Returns an array of all the objects in the table.
 * NB. The table <em>must</em> contain objects for its keys.
 */
NSArray *
NSAllHashTableObjects(NSHashTable *table)
{
  return [table allObjects];
}

/**
 * Compares the two hash tables for equality.
 * If the tables are different sizes, returns NO.
 * Otherwise, compares the values in the two tables
 * and returns NO if they differ.<br />
 * The GNUstep implementation enumerates the values in table1
 * and uses the hash and isEqual functions of table2 for comparison.
 */
BOOL
NSCompareHashTables(NSHashTable *table1, NSHashTable *table2)
{
  if (table1 == table2)
    {
      return YES;
    }
  if (table1 == nil)
    {
      NSWarnFLog(@"Nul first argument supplied");
      return NO;
    }
  if (table2 == nil)
    {
      NSWarnFLog(@"Nul second argument supplied");
      return NO;
    }
  if ([table1 count] != [table2 count])
    {
      return NO;
    }
  if (object_getClass(table1) != concreteClass
    && object_getClass(table2) == concreteClass)
    {
      id	t = table1;

      table1 = table2;
      table2 = t;
    }
  if (object_getClass(table1) == concreteClass)
    {
      BOOL		result = YES;
      NSHashEnumerator	enumerator;
      GSIMapNode	n1;

      enumerator = NSEnumerateHashTable(table1);
      if (object_getClass(table2) == concreteClass)
	{
          GSIMapTable	t2 = (GSIMapTable)table2;

	  while ((n1 = GSIMapEnumeratorNextNode(&enumerator)) != 0)
	    {
	      if (GSIMapNodeForKey(t2, n1->key) == 0)
		{
		  result = NO;
		  break;
		}
	    }
	}
      else
	{
	  while ((n1 = GSIMapEnumeratorNextNode(&enumerator)) != 0)
	    {
	      void	*v1 = n1->key.ptr;
	      void	*v2;

	      v2 = NSHashGet(table2, v1);
	      if (v2 == 0 && v2 != v1)
		{
		  result = NO;
		  break;
		}
	    }
	}
      NSEndHashTableEnumeration(&enumerator);
      return result;
    }
  else
    {
      BOOL		result = YES;
      NSHashEnumerator	enumerator;
      void		*v1;

      enumerator = NSEnumerateHashTable(table1);
      while ((v1 = NSNextHashEnumeratorItem(&enumerator)) != 0)
	{
	  void	*v2;

	  v2 = NSHashGet(table2, v1);
	  if (v2 == 0 && v2 != v1)
	    {
	      result = NO;
	      break;
	    }
	}
      NSEndHashTableEnumeration(&enumerator);
      return result;
    }
}

/**
 * Copy the supplied hash table.<br />
 * Returns a hash table, space for which is allocated in zone, which
 * has (newly retained) copies of table's contents.  As always,
 * if zone is 0, then NSDefaultMallocZone() is used.
 */
NSHashTable *
NSCopyHashTableWithZone(NSHashTable *table, NSZone *zone)
{
  GSIMapTable	o = (GSIMapTable)table;
  GSIMapTable	t;
  GSIMapNode	n;
  NSHashEnumerator enumerator;

  if (table == nil)
    {
      NSWarnFLog(@"Null table argument supplied");
      return 0;
    }
  t = (GSIMapTable)[concreteClass allocWithZone: zone];
  t->legacy = o->legacy;
  if (t->legacy == YES)
    {
      t->cb.old = o->cb.old;
    }
  else
    {
      t->cb.pf = o->cb.pf;
    }
  GSIMapInitWithZoneAndCapacity(t, zone, ((GSIMapTable)table)->nodeCount);

  enumerator = GSIMapEnumeratorForMap((GSIMapTable)table);
  while ((n = GSIMapEnumeratorNextNode(&enumerator)) != 0)
    {
      GSIMapAddKey(t, n->key);
    }
  GSIMapEndEnumerator((GSIMapEnumerator)&enumerator);

  return (NSHashTable*)t;
}

/**
 * Returns the number of items in the table.
 */
NSUInteger
NSCountHashTable(NSHashTable *table)
{
  return [table count];
}

/**
 * Create a new hash table by calling NSCreateHashTableWithZone() using
 * NSDefaultMallocZone().<br />
 * Returns a (pointer to) an NSHashTable space for which is allocated
 * in the default zone.  If capacity is small or 0, then the returned
 * table has a reasonable capacity.
 */
NSHashTable *
NSCreateHashTable(
  NSHashTableCallBacks callBacks,
  NSUInteger capacity)
{
  return NSCreateHashTableWithZone(callBacks, capacity, NSDefaultMallocZone());
}

/**
 * Create a new hash table using the supplied callbacks structures.
 * If any functions in the callback structures are null the default
 * values are used ... as for non-owned pointers.<br />
 * Of course, if you send 0 for zone, then the hash table will be
 * created in NSDefaultMallocZone().<br />
 * The table will be created with the specified capacity ... ie ready
 * to hold at least that many items.
 */
NSHashTable *
NSCreateHashTableWithZone(
  NSHashTableCallBacks k,
  NSUInteger capacity,
  NSZone *zone)
{
  GSIMapTable	table;

  if (concreteClass == Nil)
    {
      [NSConcreteHashTable class];	// Force +initialize
      NSCAssert(concreteClass != Nil, NSInternalInconsistencyException);
    }
  table = (GSIMapTable)[concreteClass allocWithZone: zone];

  if (k.hash == 0)
    k.hash = NSNonOwnedPointerHashCallBacks.hash;
  if (k.isEqual == 0)
    k.isEqual = NSNonOwnedPointerHashCallBacks.isEqual;
  if (k.retain == 0)
    k.retain = NSNonOwnedPointerHashCallBacks.retain;
  if (k.release == 0)
    k.release = NSNonOwnedPointerHashCallBacks.release;
  if (k.describe == 0)
    k.describe = NSNonOwnedPointerHashCallBacks.describe;

  table->legacy = YES;
  table->cb.old = k;

  GSIMapInitWithZoneAndCapacity(table, zone, capacity);

  return (NSHashTable*)table;
}

/**
 * Function to be called when finished with the enumerator.
 * This permits memory used by the enumerator to be released!
 */
void
NSEndHashTableEnumeration(NSHashEnumerator *enumerator)
{
  if (enumerator == 0)
    {
      NSWarnFLog(@"Null enumerator argument supplied");
      return;
    }
  if (enumerator->map != 0)
    {
      /* The 'map' field is non-null, so this NSHashEnumerator is actually
       * a GSIMapEnumerator.
       */
      GSIMapEndEnumerator((GSIMapEnumerator)enumerator);
    }
  else if (enumerator->node != 0)
    {
      /* The 'map' field is null but the 'node' field is not, so the
       * NSHashEnumerator structure actually contains an NSEnumerator
       * in the 'node' field.
       */
      [(id)enumerator->node release];
      memset(enumerator, '\0', sizeof(NSHashEnumerator));
    }
}

/**
 * Return an enumerator for stepping through a hash table using the
 * NSNextHashEnumeratorPair() function.
 */
NSHashEnumerator
NSEnumerateHashTable(NSHashTable *table)
{
  if (table == nil)
    {
      NSHashEnumerator	v = {0, 0, 0};

      NSWarnFLog(@"Null table argument supplied");
      return v;
    }
  if (object_getClass(table) == concreteClass)
    {
      return GSIMapEnumeratorForMap((GSIMapTable)table);
    }
  else
    {
      NSHashEnumerator	v = {0, 0, 0};

      v.node = (void*)[[table objectEnumerator] retain];
      return v;
    }
}

/**
 * Destroy the hash table and release its contents.<br />
 * Releases all the keys and values of table (using the key and
 * value callbacks specified at the time of table's creation),
 * and then proceeds to deallocate the space allocated for table itself.
 */
void
NSFreeHashTable(NSHashTable *table)
{
  [table release];
}

/**
 * Returns the value for the specified item, or a null pointer if the
 * item is not found in the table.
 */
void *
NSHashGet(NSHashTable *table, const void *element)
{
  if (table == nil)
    {
      NSWarnFLog(@"Null table argument supplied");
      return 0;
    }
  if (object_getClass(table) == concreteClass)
    {
      GSIMapNode	n;

      n = GSIMapNodeForKey((GSIMapTable)table, (GSIMapKey)element);
      if (n == 0)
	{
	  return 0;
	}
      else
	{
	  return n->key.ptr;
	}
    }
  return [table member: (id)element];
}

/**
 * Adds the element to table.<br />
 * If an equal element is already in table, replaces it with the new one.<br />
 * If element is null raises an NSInvalidArgumentException.
 */
void
NSHashInsert(NSHashTable *table, const void *element)
{
  if (table == 0)
    {
      [NSException raise: NSInvalidArgumentException
                  format: @"Attempt to place value in null hash table"];
    }
  if (element == 0)
    {
      [NSException raise: NSInvalidArgumentException
                  format: @"Attempt to place null in hash table"];
    }
  if (object_getClass(table) == concreteClass)
    {
      GSIMapTable   t = (GSIMapTable)table;
      GSIMapNode    n;

      n = GSIMapNodeForKey(t, (GSIMapKey)element);
      if (n == 0)
	{
	  GSIMapAddKey(t, (GSIMapKey)element);
	  ((NSConcreteHashTable*)table)->version++;
	}
      else if (GSI_MAP_READ_KEY(t, &n->key).ptr != element)
        {
	  if (t->legacy)
	    {
	      t->cb.old.release(t, n->key.ptr);
	      n->key = (GSIMapKey)element;
	      t->cb.old.retain(t, n->key.ptr);
	    }
	  else
	    {
	      pointerFunctionsRelinquish(&t->cb.pf, (void**)&n->key);
	      pointerFunctionsReplace(&t->cb.pf, (void**)&n->key,
		(void*)element);
	    }
	  ((NSConcreteHashTable*)table)->version++;
	}
    }
  else
    {
      [table addObject: (id)element];
    }
}

/**
 * Adds the element to table and returns nul.<br />
 * If an equal element is already in table, returns the old element
 * instead of adding the new one.<br />
 * If element is nul, raises an NSInvalidArgumentException.
 */
void *
NSHashInsertIfAbsent(NSHashTable *table, const void *element)
{
  if (table == 0)
    {
      [NSException raise: NSInvalidArgumentException
                  format: @"Attempt to place value in null hash table"];
    }
  if (element == 0)
    {
      [NSException raise: NSInvalidArgumentException
                  format: @"Attempt to place null in hash table"];
    }
  if (object_getClass(table) == concreteClass)
    {
      GSIMapTable   t = (GSIMapTable)table;
      GSIMapNode    n;

      n = GSIMapNodeForKey(t, (GSIMapKey)element);
      if (n == 0)
	{
	  GSIMapAddKey(t, (GSIMapKey)element);
	  ((NSConcreteHashTable*)table)->version++;
	  return 0;
	}
      else
	{
	  return n->key.ptr;
	}
    }
  else
    {
      id	old = [table member: (id)element];

      if (old == nil)
	{
	  [table addObject: (id)element];
	  return 0;
	}
      else
	{
	  return (void*)old;
	}
    }
}

/**
 * Adds the element to table and returns nul.<br />
 * If an equal element is already present, raises NSInvalidArgumentException.
 * <br />If element is null raises an NSInvalidArgumentException.
 */
void
NSHashInsertKnownAbsent(NSHashTable *table, const void *element)
{
  if (table == 0)
    {
      [NSException raise: NSInvalidArgumentException
                  format: @"Attempt to place value in null hash table"];
    }
  if (element == 0)
    {
      [NSException raise: NSInvalidArgumentException
                  format: @"Attempt to place null in hash table"];
    }
  if (object_getClass(table) == concreteClass)
    {
      GSIMapTable   t = (GSIMapTable)table;
      GSIMapNode    n;

      n = GSIMapNodeForKey(t, (GSIMapKey)element);
      if (n == 0)
	{
	  GSIMapAddKey(t, (GSIMapKey)element);
	  ((NSConcreteHashTable*)table)->version++;
	}
      else
	{
	  [NSException raise: NSInvalidArgumentException
		      format: @"NSHashInsertKnownAbsent ... item not absent"];
	}
    }
  else
    {
      id	old = [table member: (id)element];

      if (old == nil)
	{
	  [table addObject: (id)element];
	}
      else
	{
	  [NSException raise: NSInvalidArgumentException
		      format: @"NSHashInsertKnownAbsent ... item not absent"];
	}
    }
}

/**
 * Remove the specified element from the table.
 */
void
NSHashRemove(NSHashTable *table, const void *element)
{
  if (table == 0)
    {
      NSWarnFLog(@"Nul table argument supplied");
      return;
    }
  if (object_getClass(table) == concreteClass)
    {
      GSIMapTable	map = (GSIMapTable)table;
      GSIMapBucket	bucket;
      GSIMapNode	node;

      bucket = GSIMapBucketForKey(map, (GSIMapKey)element);
      node = GSIMapNodeForKeyInBucket(map, bucket, (GSIMapKey)element);
      if (node != 0)
	{
	  GSIMapRemoveNodeFromMap(map, bucket, node);
	  GSIMapFreeNode(map, node);
          ((NSConcreteHashTable*)table)->version++;
	}
    }
  else
    {
      [table removeObject: (id)element];
    }
}

/**
 * Step through the hash table ... return the next item or
 * return nul if we hit the of the table.
 */
void *
NSNextHashEnumeratorItem(NSHashEnumerator *enumerator)
{
  if (enumerator == 0)
    {
      NSWarnFLog(@"Nul enumerator argument supplied");
      return 0;
    }
  if (enumerator->map != 0)		// Got a GSIMapTable enumerator
    {
      GSIMapNode    n;

      /* The 'map' field is non-null, so this NSHashEnumerator is actually
       * a GSIMapEnumerator.
       */
      n = GSIMapEnumeratorNextNode((GSIMapEnumerator)enumerator);
      if (n == 0)
	{
	  return 0;
	}
      else
	{
          NSConcreteHashTable *map = enumerator->map;

          return GSI_MAP_READ_KEY(map, &n->key).ptr;
	}
    }
  else if (enumerator->node != 0)	// Got an enumerator object
    {
      /* The 'map' field is null but the 'node' field is not, so the
       * NSHashEnumerator structure actually contains an NSEnumerator
       * in the 'node' field, and the map table being enumerated in the
       * 'bucket' field.
       */
      return (void*)[(id)enumerator->node nextObject];
    }
  else
    {
      return 0;
    }
}

/**
 * Empty the hash table (releasing all elements), but preserve its capacity.
 */
void
NSResetHashTable(NSHashTable *table)
{
  if (table == 0)
    {
      NSWarnFLog(@"Nul table argument supplied");
      return;
    }
  if (object_getClass(table) == concreteClass)
    {
      NSConcreteHashTable	*t = (NSConcreteHashTable*)table;

      if (t->nodeCount > 0)
	{
	  GSIMapCleanMap((GSIMapTable)table);
	  t->version++;
	}
    }
  else
    {
      [table removeAllObjects];
    }
}

/**
 * Returns a string describing the table contents.<br />
 * For each item, a string of the form "value;\n"
 * is appended.  The appropriate describe function is used to generate
 * the strings for each item.
 */
GS_DECLARE NSString *
NSStringFromHashTable(NSHashTable *table)
{
  GSIMapTable		t = (GSIMapTable)table;
  NSMutableString	*string;
  NSHashEnumerator	enumerator;
  const void		*element;

  if (table == 0)
    {
      NSWarnFLog(@"Nul table argument supplied");
      return nil;
    }

  /* This will be our string. */
  string = [NSMutableString stringWithCapacity: 0];

  /* Get an enumerator for TABLE. */
  enumerator = NSEnumerateHashTable(table);

  /* Iterate over the elements of TABLE, appending the description of
   * each to the mutable string STRING. */
  if (t->legacy)
    {
      while ((element = NSNextHashEnumeratorItem(&enumerator)) != nil)
	{
	  [string appendFormat: @"%@;\n",
	    (t->cb.old.describe)(table, element)];
	}
    }
  else
    {
      while ((element = NSNextHashEnumeratorItem(&enumerator)) != nil)
	{
	  [string appendFormat: @"%@;\n",
	    (t->cb.pf.descriptionFunction)(element)];
	}
    }
  NSEndHashTableEnumeration(&enumerator);
  return string;
}




/* These are to increase readabilty locally. */
typedef NSUInteger (*NSHT_hash_func_t)(NSHashTable *, const void *);
typedef BOOL (*NSHT_isEqual_func_t)(NSHashTable *, const void *, const void *);
typedef void (*NSHT_retain_func_t)(NSHashTable *, const void *);
typedef void (*NSHT_release_func_t)(NSHashTable *, void *);
typedef NSString *(*NSHT_describe_func_t)(NSHashTable *, const void *);

/** For sets of pointer-sized or smaller quantities. */
const NSHashTableCallBacks NSIntegerHashCallBacks =
{
  (NSHT_hash_func_t) _NS_int_hash,
  (NSHT_isEqual_func_t) _NS_int_is_equal,
  (NSHT_retain_func_t) _NS_int_retain,
  (NSHT_release_func_t) _NS_int_release,
  (NSHT_describe_func_t) _NS_int_describe
};

/** For backward compatibility. */
const NSHashTableCallBacks NSIntHashCallBacks =
{
  (NSHT_hash_func_t) _NS_int_hash,
  (NSHT_isEqual_func_t) _NS_int_is_equal,
  (NSHT_retain_func_t) _NS_int_retain,
  (NSHT_release_func_t) _NS_int_release,
  (NSHT_describe_func_t) _NS_int_describe
};

/** For sets of pointers hashed by address. */
const NSHashTableCallBacks NSNonOwnedPointerHashCallBacks =
{
  (NSHT_hash_func_t) _NS_non_owned_void_p_hash,
  (NSHT_isEqual_func_t) _NS_non_owned_void_p_is_equal,
  (NSHT_retain_func_t) _NS_non_owned_void_p_retain,
  (NSHT_release_func_t) _NS_non_owned_void_p_release,
  (NSHT_describe_func_t) _NS_non_owned_void_p_describe
};

/** For sets of objects without retaining and releasing. */
const NSHashTableCallBacks NSNonRetainedObjectHashCallBacks =
{
  (NSHT_hash_func_t) _NS_non_retained_id_hash,
  (NSHT_isEqual_func_t) _NS_non_retained_id_is_equal,
  (NSHT_retain_func_t) _NS_non_retained_id_retain,
  (NSHT_release_func_t) _NS_non_retained_id_release,
  (NSHT_describe_func_t) _NS_non_retained_id_describe
};

/** For sets of objects; similar to [NSSet]. */
const NSHashTableCallBacks NSObjectHashCallBacks =
{
  (NSHT_hash_func_t) _NS_id_hash,
  (NSHT_isEqual_func_t) _NS_id_is_equal,
  (NSHT_retain_func_t) _NS_id_retain,
  (NSHT_release_func_t) _NS_id_release,
  (NSHT_describe_func_t) _NS_id_describe
};

/** For sets of pointers with transfer of ownership upon insertion. */
const NSHashTableCallBacks NSOwnedPointerHashCallBacks =
{
  (NSHT_hash_func_t) _NS_owned_void_p_hash,
  (NSHT_isEqual_func_t) _NS_owned_void_p_is_equal,
  (NSHT_retain_func_t) _NS_owned_void_p_retain,
  (NSHT_release_func_t) _NS_owned_void_p_release,
  (NSHT_describe_func_t) _NS_owned_void_p_describe
};

/** For sets of pointers to structs when the first field of the
 * struct is the size of an int. */
const NSHashTableCallBacks NSPointerToStructHashCallBacks =
{
  (NSHT_hash_func_t) _NS_int_p_hash,
  (NSHT_isEqual_func_t) _NS_int_p_is_equal,
  (NSHT_retain_func_t) _NS_int_p_retain,
  (NSHT_release_func_t) _NS_int_p_release,
  (NSHT_describe_func_t) _NS_int_p_describe
};



@interface NSConcreteHashTableEnumerator : NSEnumerator
{
  NSConcreteHashTable		*table;
  GSIMapEnumerator_t		enumerator;
}
- (id) initWithHashTable: (NSConcreteHashTable*)t;
@end

@implementation	NSConcreteHashTable

- (NSUInteger) sizeOfContentExcluding: (NSHashTable*)exclude
{
  /* Can't safely calculate for mutable object; just buffer size
   */
  return nodeCount * sizeof(GSIMapNode);
}

+ (void) initialize
{
  if (concreteClass == Nil)
    {
      concreteClass = [NSConcreteHashTable class];
      instanceSize = class_getInstanceSize(concreteClass);
    }
}

- (void) addObject: (id)anObject
{
  GSIMapTable   t = (GSIMapTable)self;
  GSIMapNode	n;

  if (nil == anObject)
    {
      /* Tested behavior on os-x 14.5 is to do nothing if the arg is nil
       */
      return;
    }

  n = GSIMapNodeForKey(t, (GSIMapKey)anObject);
  if (n == 0)
    {
      GSIMapAddKey(t, (GSIMapKey)anObject);
      version++;
    }
  else if (GSI_MAP_READ_KEY(t, &n->key).ptr != anObject)
    {
      if (t->legacy)
	{
	  t->cb.old.release(t, n->key.ptr);
	  n->key.ptr = anObject;
	  t->cb.old.retain(t, n->key.ptr);
	}
      else
	{
	  pointerFunctionsRelinquish(&t->cb.pf, (void**)&n->key);
	  pointerFunctionsReplace(&t->cb.pf, (void**)&n->key, (void*)anObject);
	}
      version++;
    }
}

- (NSArray*) allObjects
{
  NSHashEnumerator	enumerator;
  NSUInteger		index;
  NSArray		*a;
  GS_BEGINITEMBUF(objects, nodeCount, id);

  enumerator = NSEnumerateHashTable(self);
  index = 0;
  while (index < nodeCount
    && (objects[index] = NSNextHashEnumeratorItem(&enumerator)) != nil)
    {
      index++;
    }
  NSEndHashTableEnumeration(&enumerator);
  a = [[[NSArray alloc] initWithObjects: objects count: index] autorelease];
  GS_ENDITEMBUF();
  return a;
}

- (id) anyObject
{
  GSIMapNode	node = GSIMapFirstNode(self);

  if (node == 0)
    {
      return nil;
    }
  return node->key.obj;
}

- (BOOL) containsObject: (id)anObject
{
  if (anObject != nil)
    {
      GSIMapNode	node  = GSIMapNodeForKey(self, (GSIMapKey)anObject);

      if (node)
	{
	  return YES;
	}
    }
  return NO;
}

- (id) copyWithZone: (NSZone*)aZone
{
  return NSCopyHashTableWithZone(self, aZone);
}

- (NSUInteger) count
{
  GSIMapRemoveWeak(self);
  return (NSUInteger)nodeCount;
}

- (NSUInteger) countByEnumeratingWithState: (NSFastEnumerationState*)state 	
				   objects: (id*)stackbuf
				     count: (NSUInteger)len
{
  state->mutationsPtr = &version;
  return GSIMapCountByEnumeratingWithStateObjectsCount
    (self, state, stackbuf, len);
}

- (void) dealloc
{
  GSIMapEmptyMap(self);
  [super dealloc];
}

- (void) encodeWithCoder: (NSCoder*)aCoder
{
  [self subclassResponsibility: _cmd];
}

- (void) finalize
{
  GSIMapEmptyMap(self);
}

- (NSUInteger) hash
{
  return (NSUInteger)nodeCount;
}

- (id) init
{
  return [self initWithPointerFunctions: nil capacity: 0];
}

- (id) initWithCoder: (NSCoder*)aCoder
{
  [self subclassResponsibility: _cmd];
  return nil;
}

- (id) initWithPointerFunctions: (NSPointerFunctions*)functions
		       capacity: (NSUInteger)initialCapacity
{
  legacy = NO;
  if (![functions isKindOfClass: [NSConcretePointerFunctions class]])
    {
      static NSConcretePointerFunctions	*defaultFunctions = nil;

      if (defaultFunctions == nil)
	{
          defaultFunctions
	    = [[NSConcretePointerFunctions alloc] initWithOptions: 0];
	}
      functions = defaultFunctions;
    }
  memcpy(&self->cb.pf, &((NSConcretePointerFunctions*)functions)->_x,
    sizeof(self->cb.pf));

#if	GC_WITH_GC
  if (self->cb.pf.usesWeakReadAndWriteBarriers)
    {
      zone = (NSZone*)nodeW;
    }
  else
    {
      zone = (NSZone*)nodeS;
    }
#endif
  GSIMapInitWithZoneAndCapacity(self, zone, initialCapacity);
  return self;
}

- (NSEnumerator*) objectEnumerator
{
  NSEnumerator	*e;

  e = [[NSConcreteHashTableEnumerator alloc] initWithHashTable: self];
  return [e autorelease];
}

- (id) member: (id)aKey
{
  if (aKey != nil)
    {
      GSIMapNode	node  = GSIMapNodeForKey(self, (GSIMapKey)aKey);

      if (node)
	{
	  return node->key.obj;
	}
    }
  return nil;
}

- (NSPointerFunctions*) pointerFunctions
{
  NSConcretePointerFunctions	*p = [NSConcretePointerFunctions new];

  p->_x = self->cb.pf;
  return [p autorelease];
}

- (void) removeAllObjects
{
  if (nodeCount > 0)
    {
      GSIMapCleanMap(self);
      version++;
    }
}

- (void) removeObject: (id)anObject
{
  if (anObject == nil)
    {
      NSWarnMLog(@"attempt to remove nil object from hash table %@", self);
      return;
    }
  if (nodeCount > 0)
    {
      GSIMapTable	map = (GSIMapTable)self;
      GSIMapBucket	bucket;
      GSIMapNode	node;

      bucket = GSIMapBucketForKey(map, (GSIMapKey)anObject);
      node = GSIMapNodeForKeyInBucket(map, bucket, (GSIMapKey)anObject);
      if (node != 0)
	{
	  GSIMapRemoveNodeFromMap(map, bucket, node);
	  GSIMapFreeNode(map, node);
	  version++;
	}
    }
}

@end

@implementation NSConcreteHashTableEnumerator

- (id) initWithHashTable: (NSConcreteHashTable*)t
{
  table = RETAIN(t);
  enumerator = GSIMapEnumeratorForMap(table);
  return self;
}

- (id) nextObject
{
  GSIMapNode	node = GSIMapEnumeratorNextNode(&enumerator);

  if (node == 0)
    {
      return nil;
    }
  return node->key.obj;
}

- (void) dealloc
{
  GSIMapEndEnumerator(&enumerator);
  RELEASE(table);
  [super dealloc];
}

@end