/* 
   NSHashMap.m

   Copyright (C) 1995, 1996 Ovidiu Predescu and Mircea Oancea.
   All rights reserved.

   Author: Ovidiu Predescu <ovidiu@bx.logicnet.ro>
	   Mircea Oancea <mircea@jupiter.elcom.pub.ro>

   This file is part of libFoundation.

   Permission to use, copy, modify, and distribute this software and its
   documentation for any purpose and without fee is hereby granted, provided
   that the above copyright notice appear in all copies and that both that
   copyright notice and this permission notice appear in supporting
   documentation.

   We disclaim all warranties with regard to this software, including all
   implied warranties of merchantability and fitness, in no event shall
   we be liable for any special, indirect or consequential damages or any
   damages whatsoever resulting from loss of use, data or profits, whether in
   an action of contract, negligence or other tortious action, arising out of
   or in connection with the use or performance of this software.
*/

#include <math.h>

#include <Foundation/common.h>
#include <Foundation/NSString.h>
#include <Foundation/NSException.h>
#include <Foundation/NSArray.h>
#include <Foundation/NSUtilities.h>
#include <Foundation/exceptions/GeneralExceptions.h>

static void __NSHashGrow(NSHashTable *table, unsigned newSize);
static void __NSMapGrow(NSMapTable *table, unsigned newSize);

/*
 *  Hash and Map Table utilities
 */

static BOOL is_prime(unsigned n)
{
    int i, n2 = sqrt(n);

    for(i = 2; i <= n2; i++)
        if(n % i == 0)
            return NO;
    return YES;
}

static unsigned nextPrime(unsigned old_value)
{
    unsigned i, new_value = old_value | 1;

    for(i = new_value; i >= new_value; i += 2)
        if(is_prime(i))
            return i;
	return old_value;
}

/* Check if nodeTable isn't full. */
static void __NSCheckHashTableFull(NSHashTable* table)
{
    if( ++(table->itemsCount) >= ((table->hashSize * 3) / 4)) {
	int newSize = nextPrime((table->hashSize * 4) / 3);
	if(newSize != table->hashSize)
	    __NSHashGrow(table, newSize);
    }
}

static void __NSCheckMapTableFull(NSMapTable* table)
{
    if( ++(table->itemsCount) >= ((table->hashSize * 3) / 4)) {
	int newSize = nextPrime((table->hashSize * 4) / 3);
	if(newSize != table->hashSize)
	    __NSMapGrow(table, newSize);
    }
}

/*
 * NSHashTable functions
 */

/* Create a Table */
NSHashTable *NSCreateHashTable(NSHashTableCallBacks callBacks, 
	unsigned capacity)
{
    return NSCreateHashTableWithZone(callBacks, capacity, NULL);
}

NSHashTable *NSCreateHashTableWithZone(NSHashTableCallBacks callBacks, 
	unsigned capacity, NSZone *zone)
{
    NSHashTable* table = NSZoneMalloc(zone, sizeof(NSHashTable));

    capacity = capacity ? capacity : 13;
    if (!is_prime(capacity))
	capacity = nextPrime(capacity);

    table->hashSize = capacity;
    table->nodes = NSZoneCalloc(zone, table->hashSize, sizeof(void*));
    table->itemsCount = 0;
    table->callbacks = callBacks;
    table->zone = zone ? zone : NSDefaultMallocZone();
    if (table->callbacks.hash == NULL)
	table->callbacks.hash = 
	    (unsigned(*)(NSHashTable*, const void*))__NSHashPointer;
    if (table->callbacks.isEqual == NULL)
	table->callbacks.isEqual = 
	(BOOL(*)(NSHashTable*, const void*, const void*)) __NSComparePointers;
    if (table->callbacks.retain == NULL)
	table->callbacks.retain = 
	    (void(*)(NSHashTable*, const void*))__NSRetainNothing;
    if (table->callbacks.release == NULL)
	table->callbacks.release = 
	    (void(*)(NSHashTable*, void*))__NSReleaseNothing;
    if (table->callbacks.describe == NULL)
	table->callbacks.describe = 
	    (NSString*(*)(NSHashTable*, const void*))__NSDescribePointers;
    return table;
}

NSHashTable *NSCopyHashTableWithZone(NSHashTable *table, NSZone *zone)
{
    NSHashTable *new;
    struct _NSHashNode *oldnode, *newnode;
    int i;
    
    zone = zone ? zone : NSDefaultMallocZone();
    new = NSZoneMalloc(zone, sizeof(NSHashTable));
    new->zone = zone;
    new->hashSize = table->hashSize;
    new->itemsCount = table->itemsCount;
    new->callbacks = table->callbacks;
    new->nodes = NSZoneCalloc(zone, new->hashSize, sizeof(void*));
    
    for (i = 0; i < new->hashSize; i++) {
	for (oldnode = table->nodes[i]; oldnode; oldnode = oldnode->next) {
	    newnode = NSZoneMalloc(zone, sizeof(struct _NSHashNode));
	    newnode->key = oldnode->key;
	    newnode->next = new->nodes[i];
	    new->nodes[i] = newnode;
	    table->callbacks.retain(new, oldnode->key);
	}
    }
    
    return new;
}

/* Free a Table */
void NSFreeHashTable(NSHashTable *table)
{
    NSResetHashTable(table);
    NSZoneFree(table->zone, table->nodes);
    NSZoneFree(table->zone, table);
}

void NSResetHashTable(NSHashTable *table)
{
    int i;
    for(i=0; i < table->hashSize; i++) {
	struct _NSHashNode *next, *node;
	
	node = table->nodes[i];
	table->nodes[i] = NULL;		
	while (node) {
	    table->callbacks.release(table, node->key);
	    next = node->next;
	    NSZoneFree(table->zone, node);
	    node = next;
	}
    }
    table->itemsCount = 0;
}

/* Compare Two Tables */
BOOL NSCompareHashTables(NSHashTable *table1, NSHashTable *table2)
{
    int i;
    struct _NSHashNode *node1;
    
    if (table1->hashSize != table2->hashSize)
	return NO;
    for (i=0; i<table1->hashSize; i++) {
	for (node1 = table1->nodes[i]; node1; node1 = node1->next) {
	    if (NSHashGet(table2, node1->key) == NULL)
		return NO;
	}
    }
    return YES;;
}	

/* Get the Number of Items */
unsigned NSCountHashTable(NSHashTable *table)
{
    return table->itemsCount;
}

/* Retrieve Items */
void *NSHashGet(NSHashTable *table, const void *pointer)
{
    struct _NSHashNode* node = table->nodes[
		table->callbacks.hash(table, pointer) % table->hashSize];
    for(; node; node = node->next)
        if(table->callbacks.isEqual(table, pointer, node->key))
            return node->key;
    return NULL;
}

NSArray *NSAllHashTableObjects(NSHashTable *table)
{
    id array = [NSMutableArray arrayWithCapacity:table->itemsCount];
    struct _NSHashNode *node;
    int i;

    for(i=0; i < table->hashSize; i++)
	for(node=table->nodes[i]; node; node=node->next)
		[array addObject:(NSObject*)(node->key)];
    return array;
}

NSHashEnumerator NSEnumerateHashTable(NSHashTable *table)
{
    NSHashEnumerator en;
    en.table = table;
    en.node = NULL;
    en.bucket = -1;
    return en;
}

void *NSNextHashEnumeratorItem(NSHashEnumerator *en)
{
    if(en->node)
	en->node = en->node->next;
    if(en->node == NULL) {
	for(en->bucket++; en->bucket<en->table->hashSize; en->bucket++)
	    if (en->table->nodes[en->bucket]) {
		    en->node = en->table->nodes[en->bucket];
		    break;
	    };
	if (en->bucket >= en->table->hashSize) {
	    en->node = NULL;
	    en->bucket = en->table->hashSize-1;
	    return NULL;
	}
    }
    return en->node->key;
}

/* Add or Remove an Item */
static void __NSHashGrow(NSHashTable *table, unsigned newSize)
{
    int i;
    struct _NSHashNode** newNodeTable = NSZoneCalloc(table->zone, 
	newSize, sizeof(struct _NSHashNode*));
    
    for(i = 0; i < table->hashSize; i++) {
	struct _NSHashNode *next, *node;
	unsigned int h;

	node = table->nodes[i];
	while(node) {
	    next = node->next;
	h = table->callbacks.hash(table, node->key) % table->hashSize;
	    node->next = newNodeTable[h];
	    newNodeTable[h] = node;
	    node = next;
	}
    }
    NSZoneFree(table->zone, table->nodes);
	table->nodes = newNodeTable;
    table->hashSize = newSize;
}

void NSHashInsert(NSHashTable *table, const void *pointer)
{
    unsigned int h;
    struct _NSHashNode *node;

    if (pointer == nil)
	THROW([[InvalidArgumentException alloc] initWithReason:
		@"Nil object to be added in NSHashTable"]);

    h = table->callbacks.hash(table, pointer) % table->hashSize;
    for(node = table->nodes[h]; node; node = node->next)
        if(table->callbacks.isEqual(table, pointer, node->key))
            break;

    /* Check if an entry for key exist in nodeTable. */
    if(node) {
        /* key exist. Set for it new value and return the old value of it. */
	if (pointer != node->key) {
	    table->callbacks.retain(table, pointer);
	    table->callbacks.release(table, node->key);
	}
	node->key = (void*)pointer;
        return;
    }

    /* key not found. Allocate a new bucket and initialize it. */
    node = NSZoneMalloc(table->zone, sizeof(struct _NSHashNode));
	table->callbacks.retain(table, pointer);
    node->key = (void*)pointer;
    node->next = table->nodes[h];
    table->nodes[h] = node;

    __NSCheckHashTableFull(table);
}

void NSHashInsertKnownAbsent(NSHashTable *table, const void *pointer)
{
    unsigned int h;
    struct _NSHashNode *node;

    if (pointer == nil)
	THROW([[InvalidArgumentException alloc] initWithReason:
		@"Nil object to be added in NSHashTable"]);

    h = table->callbacks.hash(table, pointer) % table->hashSize;
    for(node = table->nodes[h]; node; node = node->next)
        if(table->callbacks.isEqual(table, pointer, node->key))
            break;

    /* Check if an entry for key exist in nodeTable. */
    if(node) 
	THROW([[InvalidArgumentException alloc] initWithReason:
		@"Nil object already existing in NSHashTable"]);

    /* key not found. Allocate a new bucket and initialize it. */
    node = NSZoneMalloc(table->zone, sizeof(struct _NSHashNode));
	table->callbacks.retain(table, pointer);
    node->key = (void*)pointer;
    node->next = table->nodes[h];
    table->nodes[h] = node;

    __NSCheckHashTableFull(table);
}

void *NSHashInsertIfAbsent(NSHashTable *table, const void *pointer)
{
    unsigned int h;
    struct _NSHashNode *node;

    if (pointer == nil)
	THROW([[InvalidArgumentException alloc] initWithReason:
		@"Nil object to be added in NSHashTable"]);

    h = table->callbacks.hash(table, pointer) % table->hashSize;
    for(node = table->nodes[h]; node; node = node->next)
        if(table->callbacks.isEqual(table, pointer, node->key))
            break;

    /* Check if an entry for key exist in nodeTable. */
    if(node)
	return node->key;
	
    /* key not found. Allocate a new bucket and initialize it. */
    node = NSZoneMalloc(table->zone, sizeof(struct _NSHashNode));
    table->callbacks.retain(table, pointer);
    node->key = (void*)pointer;
    node->next = table->nodes[h];
    table->nodes[h] = node;

    __NSCheckHashTableFull(table);
    
    return NULL;
}

void NSHashRemove(NSHashTable *table, const void *pointer)
{
    unsigned int h;
    struct _NSHashNode *node, *node1 = NULL;

    if (pointer == nil)
	    return;

    h = table->callbacks.hash(table, pointer) % table->hashSize;

    // node point to current bucket, and node1 to previous bucket or to NULL
    // if current node is the first node in the list 

    for(node = table->nodes[h]; node; node1 = node, node = node->next)
        if(table->callbacks.isEqual(table, pointer, node->key)) {
	    table->callbacks.release(table, node->key);
            if(!node1)
                table->nodes[h] = node->next;
            else
                node1->next = node->next;
	    NSZoneFree(table->zone, node);
	    (table->itemsCount)--;
	    return;
        }
}

/* Get a String Representation */
NSString *NSStringFromHashTable(NSHashTable *table)
{
    id ret = [NSMutableString new];
    int i;
    struct _NSHashNode *node;
    
    for (i=0; i<table->hashSize; i++)
	for (node = table->nodes[i]; node; node = node->next) {
	    [ret appendString:table->callbacks.describe(table, node->key)];
	    [ret appendString:@" "];
	}
    
    return ret;
}

/* 
 * Map Table Functions 
 */

/* Create a Table */
NSMapTable *NSCreateMapTable(NSMapTableKeyCallBacks keyCallbacks, 
	NSMapTableValueCallBacks valueCallbacks, unsigned capacity)
{
    return NSCreateMapTableWithZone(keyCallbacks, valueCallbacks, capacity, NULL);
}

NSMapTable *NSCreateMapTableWithZone(NSMapTableKeyCallBacks keyCallbacks, 
	NSMapTableValueCallBacks valueCallbacks, unsigned capacity, NSZone *zone)
{
	NSMapTable* table = NSZoneMalloc(zone, sizeof(NSMapTable));
    
    capacity = capacity ? capacity : 13;
    if (!is_prime(capacity))
	capacity = nextPrime(capacity);

    table->hashSize = capacity;
    table->nodes = NSZoneCalloc(zone, table->hashSize, sizeof(void*));
    table->itemsCount = 0;
    table->keyCallbacks = keyCallbacks;
    table->valueCallbacks = valueCallbacks;
    table->zone = zone ? zone : NSDefaultMallocZone();
    if (table->keyCallbacks.hash == NULL)
	table->keyCallbacks.hash = 
		(unsigned(*)(NSMapTable*, const void*))__NSHashPointer;
    if (table->keyCallbacks.isEqual == NULL)
	table->keyCallbacks.isEqual = 
	(BOOL(*)(NSMapTable*, const void*, const void*)) __NSComparePointers;
    if (table->keyCallbacks.retain == NULL)
	table->keyCallbacks.retain = 
	    (void(*)(NSMapTable*, const void*))__NSRetainNothing;
    if (table->keyCallbacks.release == NULL)
	table->keyCallbacks.release = 
	    (void(*)(NSMapTable*, void*))__NSReleaseNothing;
    if (table->keyCallbacks.describe == NULL)
	table->keyCallbacks.describe = 
	    (NSString*(*)(NSMapTable*, const void*))__NSDescribePointers;
    if (table->valueCallbacks.retain == NULL)
	table->valueCallbacks.retain = 
	    (void(*)(NSMapTable*, const void*))__NSRetainNothing;
    if (table->valueCallbacks.release == NULL)
	table->valueCallbacks.release = 
	    (void(*)(NSMapTable*, void*))__NSReleaseNothing;
    if (table->valueCallbacks.describe == NULL)
	table->valueCallbacks.describe = 
	    (NSString*(*)(NSMapTable*, const void*))__NSDescribePointers;
    return table;
}

NSMapTable *NSCopyMapTableWithZone(NSMapTable *table, NSZone *zone)
{
    NSMapTable *new;
    struct _NSMapNode *oldnode, *newnode;
    int i;
    
    zone = zone ? zone : NSDefaultMallocZone();
    new = NSZoneMalloc(zone, sizeof(NSMapTable));
    new->zone = zone;
    new->hashSize = table->hashSize;
    new->itemsCount = table->itemsCount;
    new->keyCallbacks = table->keyCallbacks;
    new->valueCallbacks = table->valueCallbacks;
    new->nodes = NSZoneCalloc(zone, new->hashSize, sizeof(void*));
    
    for (i=0; i<new->hashSize; i++) {
	for (oldnode = table->nodes[i]; oldnode; oldnode = oldnode->next) {
	    newnode = NSZoneMalloc(zone, sizeof(struct _NSMapNode));
	    newnode->key = oldnode->key;
	    newnode->value = oldnode->value;
	    newnode->next = new->nodes[i];
	    new->nodes[i] = newnode;
	    table->keyCallbacks.retain(new, oldnode->key);
	    table->valueCallbacks.retain(new, oldnode->value);
	}
    }
    
    return new;
}

/* Free a Table */
void NSFreeMapTable(NSMapTable *table)
{
    NSResetMapTable(table);
    NSZoneFree(table->zone, table->nodes);
    NSZoneFree(table->zone, table);
}

void NSResetMapTable(NSMapTable *table)
{
    int i;
    for(i=0; i < table->hashSize; i++) {
	struct _NSMapNode *next, *node;
	
	node = table->nodes[i];
	table->nodes[i] = NULL;		
	while (node) {
	    table->keyCallbacks.release(table, node->key);
	    table->valueCallbacks.release(table, node->value);
	    next = node->next;
	    NSZoneFree(table->zone, node);
	    node = next;
	}
    }
    table->itemsCount = 0;
}

/* Compare Two Tables */
BOOL NSCompareMapTables(NSMapTable *table1, NSMapTable *table2)
{
    int i;
    struct _NSMapNode *node1;
    
    if (table1->hashSize != table2->hashSize)
	return NO;
    for (i=0; i<table1->hashSize; i++) {
	for (node1 = table1->nodes[i]; node1; node1 = node1->next) {
	    if (NSMapGet(table2, node1->key) != node1->value)
		return NO;
	}
    }
    return YES;
}

/* Get the Number of Items */
unsigned NSCountMapTable(NSMapTable *table)
{
    return table->itemsCount;
}

/* Retrieve Items */
BOOL NSMapMember(NSMapTable *table, const void *key, 
	void **originalKey, void **value)
{
    struct _NSMapNode* node = table->nodes[
		table->keyCallbacks.hash(table, key) % table->hashSize];
    for(; node; node = node->next)
        if(table->keyCallbacks.isEqual(table, key, node->key)) {
            *originalKey = node->key;
	    *value = node->value;
	    return YES;
	}
    return NO;
}

void *NSMapGet(NSMapTable *table, const void *key)
{
    struct _NSMapNode* node = table->nodes[
		table->keyCallbacks.hash(table, key) % table->hashSize];
    for(; node; node = node->next)
        if(table->keyCallbacks.isEqual(table, key, node->key))
            return node->value;
    return NULL;
}

NSMapEnumerator NSEnumerateMapTable(NSMapTable *table)
{
    NSMapEnumerator en;
    en.table = table;
    en.node = NULL;
    en.bucket = -1;
    return en;
}

BOOL NSNextMapEnumeratorPair(NSMapEnumerator *en, 
    void **key, void **value)
{
    if(en->node)
	en->node = en->node->next;
    if(en->node == NULL) {
	for(en->bucket++; en->bucket<en->table->hashSize; en->bucket++)
	    if (en->table->nodes[en->bucket]) {
		    en->node = en->table->nodes[en->bucket];
		    break;
	    }
	if (en->bucket >= en->table->hashSize) {
	    en->node = NULL;
	    en->bucket = en->table->hashSize-1;
	    return NO;
	}
    }
    *key = en->node->key;
    *value = en->node->value;
    return YES;
}

NSArray *NSAllMapTableKeys(NSMapTable *table)
{
    id array = [NSMutableArray arrayWithCapacity:table->itemsCount];
    struct _NSMapNode *node;
    int i;

    for(i=0; i < table->hashSize; i++)
	for(node=table->nodes[i]; node; node=node->next)
	    [array addObject:(NSObject*)(node->key)];
    return array;
}

NSArray *NSAllMapTableValues(NSMapTable *table)
{
    id array = [NSMutableArray arrayWithCapacity:table->itemsCount];
    struct _NSMapNode *node;
    int i;

    for(i=0; i < table->hashSize; i++)
	for(node=table->nodes[i]; node; node=node->next)
	    [array addObject:(NSObject*)(node->value)];
    return array;
}

/* Add or Remove an Item */
static void __NSMapGrow(NSMapTable *table, unsigned newSize)
{
    int i;
    struct _NSMapNode** newNodeTable = NSZoneCalloc(table->zone,
	newSize, sizeof(struct _NSMapNode*));
    
    for(i = 0; i < table->hashSize; i++) {
	struct _NSMapNode *next, *node;
	unsigned int h;

	node = table->nodes[i];
	while(node) {
	    next = node->next;
	    h = table->keyCallbacks.hash(table, node->key) % newSize;
	    node->next = newNodeTable[h];
	    newNodeTable[h] = node;
	    node = next;
	}
    }
    NSZoneFree(table->zone, table->nodes);
    table->nodes = newNodeTable;
    table->hashSize = newSize;
}

void NSMapInsert(NSMapTable *table, const void *key, const void *value)
{
    unsigned int h;
    struct _NSMapNode *node;

    if (key == table->keyCallbacks.notAKeyMarker)
	THROW([[InvalidArgumentException alloc] initWithReason:
		@"Invalid key to be added in NSMapTable"]);

    h = table->keyCallbacks.hash(table, key) % table->hashSize;
    for(node = table->nodes[h]; node; node = node->next)
        if(table->keyCallbacks.isEqual(table, key, node->key))
            break;

    /* Check if an entry for key exist in nodeTable. */
    if(node) {
        /* key exist. Set for it new value and return the old value of it. */
	if (key != node->key) {
	    table->keyCallbacks.retain(table, key);
	    table->keyCallbacks.release(table, node->key);
	}
	if (value != node->value) {
	    table->valueCallbacks.retain(table, value);
	    table->valueCallbacks.release(table, node->value);
	}
	node->key = (void*)key;
	node->value = (void*)value;
        return;
    }

    /* key not found. Allocate a new bucket and initialize it. */
    node = NSZoneMalloc(table->zone, sizeof(struct _NSMapNode));
    table->keyCallbacks.retain(table, key);
    table->valueCallbacks.retain(table, value);
    node->key = (void*)key;
    node->value = (void*)value;
    node->next = table->nodes[h];
    table->nodes[h] = node;

    __NSCheckMapTableFull(table);
}

void *NSMapInsertIfAbsent(NSMapTable *table, const void *key, 
	const void *value)
{
    unsigned int h;
    struct _NSMapNode *node;

    if (key == table->keyCallbacks.notAKeyMarker)
	THROW([[InvalidArgumentException alloc] initWithReason:
		@"Invalid key to be added in NSMapTable"]);

    h = table->keyCallbacks.hash(table, key) % table->hashSize;
    for(node = table->nodes[h]; node; node = node->next)
        if(table->keyCallbacks.isEqual(table, key, node->key))
            break;

    /* Check if an entry for key exist in nodeTable. */
    if(node) {
        return node->key;
    }

    /* key not found. Allocate a new bucket and initialize it. */
    node = NSZoneMalloc(table->zone, sizeof(struct _NSMapNode));
    table->keyCallbacks.retain(table, key);
    table->valueCallbacks.retain(table, value);
    node->key = (void*)key;
    node->value = (void*)value;
    node->next = table->nodes[h];
    table->nodes[h] = node;

    __NSCheckMapTableFull(table);

    return NULL;
}

void NSMapInsertKnownAbsent(NSMapTable *table, const void *key, 
	const void *value)
{
    unsigned int h;
    struct _NSMapNode *node;

    if (key == table->keyCallbacks.notAKeyMarker)
	THROW([[InvalidArgumentException alloc] initWithReason:
		@"Invalid key to be added in NSMapTable"]);

    h = table->keyCallbacks.hash(table, key) % table->hashSize;
    for(node = table->nodes[h]; node; node = node->next)
        if(table->keyCallbacks.isEqual(table, key, node->key))
            break;

    /* Check if an entry for key exist in nodeTable. */
    if(node) 
	THROW([[InvalidArgumentException alloc] initWithReason:
		@"Nil object already existing in NSMapTable"]);

    /* key not found. Allocate a new bucket and initialize it. */
    node = NSZoneMalloc(table->zone, sizeof(struct _NSMapNode));
    table->keyCallbacks.retain(table, key);
    table->valueCallbacks.retain(table, value);
    node->key = (void*)key;
    node->value = (void*)value;
    node->next = table->nodes[h];
    table->nodes[h] = node;

    __NSCheckMapTableFull(table);
}

void NSMapRemove(NSMapTable *table, const void *key)
{
    unsigned int h;
    struct _NSMapNode *node, *node1 = NULL;

    if (key == nil)
	    return;

    h = table->keyCallbacks.hash(table, key) % table->hashSize;

    // node point to current bucket, and node1 to previous bucket or to NULL
    // if current node is the first node in the list 

    for(node = table->nodes[h]; node; node1 = node, node = node->next)
        if(table->keyCallbacks.isEqual(table, key, node->key)) {
	    table->keyCallbacks.release(table, node->key);
	    table->valueCallbacks.release(table, node->value);
            if(!node1)
                table->nodes[h] = node->next;
            else
                node1->next = node->next;
	    NSZoneFree(table->zone, node);
	    (table->itemsCount)--;
	    return;
        }
}

NSString *NSStringFromMapTable(NSMapTable *table)
{
    id ret = [NSMutableString new];
    int i;
    struct _NSMapNode *node;
    
    for (i=0; i<table->hashSize; i++)
	for (node = table->nodes[i]; node; node = node->next) {
	    [ret appendString:table->keyCallbacks.describe(table, node->key)];
	    [ret appendString:@"="];
	    [ret appendString:table->valueCallbacks.describe(table, node->value)];
	    [ret appendString:@"\n"];
	}
    
    return ret;
}

/*
 * Convenience functions
 */
 
unsigned __NSHashObject(void *table, const void *anObject)
{
    return [(id)anObject hash];
}

unsigned __NSHashPointer(void *table, const void *anObject)
{
    return (int)anObject / 4;
}

unsigned __NSHashInteger(void *table, const void *anObject)
{
    return (unsigned)anObject;
}

/* From Aho, Sethi & Ullman: Principles of compiler design. */
unsigned __NSHashCString(void *table, const void *aString)
{
    register const char* p = (char*)aString;
    register unsigned hash = 0, hash2;
    register int i, n = Strlen((char*)aString);

    for(i=0; i < n; i++) {
        hash <<= 4;
        hash += *p++;
        if((hash2 = hash & 0xf0000000))
            hash ^= (hash2 >> 24) ^ hash2;
    }
    return hash;
}

BOOL __NSCompareObjects(void *table, 
	const void *anObject1, const void *anObject2)
{
    return [(NSObject*)anObject1 isEqual:(NSObject*)anObject2];
}

BOOL __NSComparePointers(void *table, 
    const void *anObject1, const void *anObject2)
{
    return anObject1 == anObject2;
}

BOOL __NSCompareInts(void *table, 
    const void *anObject1, const void *anObject2)
{
    return (int)anObject1 == (int)anObject2;
}

BOOL __NSCompareCString(void *table, 
    const void *anObject1, const void *anObject2)
{
    return Strcmp((char*)anObject1, (char*)anObject2) == 0;
}

void __NSRetainNothing(void *table, const void *anObject)
{
}

void __NSRetainObjects(void *table, const void *anObject)
{
    [(NSObject*)anObject retain];
}

void __NSReleaseNothing(void *table, void *anObject)
{
}

void __NSReleaseObjects(void *table, void *anObject)
{
    [(NSObject*)anObject release];
}

void __NSReleasePointers(void *table, void *anObject)
{
    Free(anObject);
}

NSString* __NSDescribeObjects(void *table, const void *anObject)
{
    return [(NSObject*)anObject description];
}

NSString* __NSDescribePointers(void *table, const void *anObject)
{
    return [NSString stringWithFormat:@"%p", anObject];
}

NSString* __NSDescribeInts(void *table, const void *anObject)
{
    return [NSString stringWithFormat:@"%d", (int)anObject];
}

/*
* NSHashTable predefined callbacks
*/

const NSHashTableCallBacks NSIntHashCallBacks = { 
    (unsigned(*)(NSHashTable*, const void*))__NSHashInteger, 
    (BOOL(*)(NSHashTable*, const void*, const void*))__NSCompareInts, 
    (void(*)(NSHashTable*, const void*))__NSRetainNothing, 
    (void(*)(NSHashTable*, void*))__NSReleaseNothing, 
    (NSString*(*)(NSHashTable*, const void*))__NSDescribeInts 
};

const NSHashTableCallBacks NSNonOwnedPointerHashCallBacks = { 
    (unsigned(*)(NSHashTable*, const void*))__NSHashPointer, 
    (BOOL(*)(NSHashTable*, const void*, const void*))__NSComparePointers, 
    (void(*)(NSHashTable*, const void*))__NSRetainNothing, 
    (void(*)(NSHashTable*, void*))__NSReleaseNothing, 
    (NSString*(*)(NSHashTable*, const void*))__NSDescribePointers 
};

const NSHashTableCallBacks NSNonRetainedObjectHashCallBacks = { 
    (unsigned(*)(NSHashTable*, const void*))__NSHashObject, 
    (BOOL(*)(NSHashTable*, const void*, const void*))__NSCompareObjects, 
    (void(*)(NSHashTable*, const void*))__NSRetainNothing, 
    (void(*)(NSHashTable*, void*))__NSReleaseNothing, 
    (NSString*(*)(NSHashTable*, const void*))__NSDescribeObjects 
};
 
const NSHashTableCallBacks NSObjectHashCallBacks = { 
    (unsigned(*)(NSHashTable*, const void*))__NSHashObject, 
    (BOOL(*)(NSHashTable*, const void*, const void*))__NSCompareObjects, 
    (void(*)(NSHashTable*, const void*))__NSRetainObjects, 
    (void(*)(NSHashTable*, void*))__NSReleaseObjects, 
    (NSString*(*)(NSHashTable*, const void*))__NSDescribeObjects 
};

const NSHashTableCallBacks NSOwnedObjectIdentityHashCallBacks = { 
    (unsigned(*)(NSHashTable*, const void*))__NSHashPointer, 
    (BOOL(*)(NSHashTable*, const void*, const void*))__NSComparePointers, 
    (void(*)(NSHashTable*, const void*))__NSRetainObjects, 
    (void(*)(NSHashTable*, void*))__NSReleaseObjects, 
    (NSString*(*)(NSHashTable*, const void*))__NSDescribeObjects 
};

const NSHashTableCallBacks NSOwnedPointerHashCallBacks = { 
    (unsigned(*)(NSHashTable*, const void*))__NSHashObject, 
    (BOOL(*)(NSHashTable*, const void*, const void*))__NSCompareObjects, 
    (void(*)(NSHashTable*, const void*))__NSRetainNothing, 
    (void(*)(NSHashTable*, void*))__NSReleasePointers, 
    (NSString*(*)(NSHashTable*, const void*))__NSDescribePointers 
};

const NSHashTableCallBacks NSPointerToStructHashCallBacks = { 
    (unsigned(*)(NSHashTable*, const void*))__NSHashPointer, 
    (BOOL(*)(NSHashTable*, const void*, const void*))__NSComparePointers, 
    (void(*)(NSHashTable*, const void*))__NSRetainNothing, 
    (void(*)(NSHashTable*, void*))__NSReleasePointers, 
    (NSString*(*)(NSHashTable*, const void*))__NSDescribePointers 
};

/*
* NSMapTable predefined callbacks
*/

const NSMapTableKeyCallBacks NSIntMapKeyCallBacks = {
    (unsigned(*)(NSMapTable *, const void *))__NSHashInteger,
    (BOOL(*)(NSMapTable *, const void *, const void *))__NSCompareInts,
    (void (*)(NSMapTable *, const void *anObject))__NSRetainNothing,
    (void (*)(NSMapTable *, void *anObject))__NSReleaseNothing,
    (NSString *(*)(NSMapTable *, const void *))__NSDescribeInts,
    (const void *)NULL
};

const NSMapTableValueCallBacks NSIntMapValueCallBacks = {
    (void (*)(NSMapTable *, const void *))__NSRetainNothing,
    (void (*)(NSMapTable *, void *))__NSReleaseNothing,
    (NSString *(*)(NSMapTable *, const void *))__NSDescribeInts
};

const NSMapTableKeyCallBacks NSNonOwnedPointerMapKeyCallBacks = {
    (unsigned(*)(NSMapTable *, const void *))__NSHashPointer,
    (BOOL(*)(NSMapTable *, const void *, const void *))__NSComparePointers,
    (void (*)(NSMapTable *, const void *anObject))__NSRetainNothing,
    (void (*)(NSMapTable *, void *anObject))__NSReleaseNothing,
    (NSString *(*)(NSMapTable *, const void *))__NSDescribePointers,
    (const void *)NULL
}; 

const NSMapTableKeyCallBacks NSNonOwnedCStringMapKeyCallBacks = {
    (unsigned(*)(NSMapTable *, const void *))__NSHashCString,
    (BOOL(*)(NSMapTable *, const void *, const void *))__NSCompareCString,
    (void (*)(NSMapTable *, const void *anObject))__NSRetainNothing,
    (void (*)(NSMapTable *, void *anObject))__NSReleaseNothing,
    (NSString *(*)(NSMapTable *, const void *))__NSDescribePointers,
    (const void *)NULL
}; 

const NSMapTableValueCallBacks NSNonOwnedPointerMapValueCallBacks = {
    (void (*)(NSMapTable *, const void *))__NSRetainNothing,
    (void (*)(NSMapTable *, void *))__NSReleaseNothing,
    (NSString *(*)(NSMapTable *, const void *))__NSDescribePointers
};

const NSMapTableKeyCallBacks NSNonOwnedPointerOrNullMapKeyCallBacks = {
    (unsigned(*)(NSMapTable *, const void *))__NSHashPointer,
    (BOOL(*)(NSMapTable *, const void *, const void *))__NSComparePointers,
    (void (*)(NSMapTable *, const void *anObject))__NSRetainNothing,
    (void (*)(NSMapTable *, void *anObject))__NSReleaseNothing,
    (NSString *(*)(NSMapTable *, const void *))__NSDescribePointers,
    (const void *)NSNotAPointerMapKey
};

const NSMapTableKeyCallBacks NSNonRetainedObjectMapKeyCallBacks = {
    (unsigned(*)(NSMapTable *, const void *))__NSHashObject,
    (BOOL(*)(NSMapTable *, const void *, const void *))__NSCompareObjects,
    (void (*)(NSMapTable *, const void *anObject))__NSRetainNothing,
    (void (*)(NSMapTable *, void *anObject))__NSReleaseNothing,
    (NSString *(*)(NSMapTable *, const void *))__NSDescribeObjects,
    (const void *)NULL
};

const NSMapTableValueCallBacks NSNonRetainedObjectMapValueCallBacks = {
    (void (*)(NSMapTable *, const void *))__NSRetainNothing,
    (void (*)(NSMapTable *, void *))__NSReleaseNothing,
    (NSString *(*)(NSMapTable *, const void *))__NSDescribeObjects
}; 

const NSMapTableKeyCallBacks NSObjectMapKeyCallBacks = {
    (unsigned(*)(NSMapTable *, const void *))__NSHashObject,
    (BOOL(*)(NSMapTable *, const void *, const void *))__NSCompareObjects,
    (void (*)(NSMapTable *, const void *anObject))__NSRetainObjects,
    (void (*)(NSMapTable *, void *anObject))__NSReleaseObjects,
    (NSString *(*)(NSMapTable *, const void *))__NSDescribeObjects,
    (const void *)NULL
}; 

const NSMapTableValueCallBacks NSObjectMapValueCallBacks = {
    (void (*)(NSMapTable *, const void *))__NSRetainObjects,
    (void (*)(NSMapTable *, void *))__NSReleaseObjects,
    (NSString *(*)(NSMapTable *, const void *))__NSDescribeObjects
}; 

const NSMapTableKeyCallBacks NSOwnedPointerMapKeyCallBacks = {
    (unsigned(*)(NSMapTable *, const void *))__NSHashPointer,
    (BOOL(*)(NSMapTable *, const void *, const void *))__NSComparePointers,
    (void (*)(NSMapTable *, const void *anObject))__NSRetainNothing,
    (void (*)(NSMapTable *, void *anObject))__NSReleasePointers,
    (NSString *(*)(NSMapTable *, const void *))__NSDescribePointers,
    (const void *)NULL
};

const NSMapTableValueCallBacks NSOwnedPointerMapValueCallBacks = {
    (void (*)(NSMapTable *, const void *))__NSRetainNothing,
    (void (*)(NSMapTable *, void *))__NSReleasePointers,
    (NSString *(*)(NSMapTable *, const void *))__NSDescribePointers
}; 

