/*
* Copyright (c) 2000, 2001, 2002, 2003, 2004 by Martin C. Shepherd.
*
* All rights reserved.
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* to whom the Software is furnished to do so, provided that the above
* copyright notice(s) and this permission notice appear in all copies of
* the Software and that both the above copyright notice(s) and this
* permission notice appear in supporting documentation.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT
* OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR 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.
*
* Except as contained in this notice, the name of a copyright holder
* shall not be used in advertising or otherwise to promote the sale, use
* or other dealings in this Software without prior written authorization
* of the copyright holder.
*/
/*
* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>
#include "hash.h"
#include "strngmem.h"
#include "freelist.h"
/*
* The following container object contains free-lists to be used
* for allocation of HashTable containers and nodes.
*/
struct HashMemory {
};
/*
* Define a hash symbol-table entry.
* See symbol.h for the definition of the Symbol container type.
*/
struct HashNode {
};
/*
* Each hash-table bucket contains a linked list of entries that
* hash to the same bucket.
*/
typedef struct {
} HashBucket;
/*
* A hash-table consists of 'size' hash buckets.
* Note that the HashTable typedef for this struct is contained in hash.h.
*/
struct HashTable {
};
/*.......................................................................
* Allocate a free-list for use in allocating hash tables and their nodes.
*
* Input:
* list_count int The number of HashTable containers per free-list
* block.
* node_count int The number of HashTable nodes per free-list block.
* Output:
* return HashMemory * The new free-list for use in allocating hash tables
* and their nodes.
*/
{
/*
* Allocate the free-list container.
*/
if(!mem) {
return NULL;
};
/*
* Initialize the container at least up to the point at which it can
* safely be passed to _del_HashMemory().
*/
/*
* Allocate the two free-lists.
*/
if(!mem->hash_memory)
if(!mem->node_memory)
if(!mem->string_memory)
/*
* Return the free-list container.
*/
return mem;
}
/*.......................................................................
* Delete a HashTable free-list. An error will be displayed if the list is
* still in use and the deletion will be aborted.
*
* Input:
* mem HashMemory * The free-list container to be deleted.
* force int If force==0 then _del_HashMemory() will complain
* and refuse to delete the free-list if any
* of nodes have not been returned to the free-list.
* If force!=0 then _del_HashMemory() will not check
* whether any nodes are still in use and will
* always delete the list.
* Output:
* return HashMemory * Always NULL (even if the memory could not be
* deleted).
*/
{
if(mem) {
return NULL;
};
};
return NULL;
}
/*.......................................................................
* Create a new hash table.
*
* Input:
* mem HashMemory * An optional free-list for use in allocating
* HashTable containers and nodes. See explanation
* in hash.h. If you are going to allocate more
* than one hash table, then it will be more
* efficient to allocate a single free-list for
* all of them than to force each hash table
* to allocate its own private free-list.
* size int The size of the hash table. Best performance
* will be acheived if this is a prime number.
* hcase HashCase Specify how symbol case is considered when
* looking up symbols, from:
* IGNORE_CASE - Upper and lower case versions
* of a letter are treated as
* being identical.
* HONOUR_CASE - Upper and lower case versions
* of a letter are treated as
* being distinct.
* characters in a lookup name is significant.
* app_data void * Optional application data to be registered
* to the table. This is presented to user
* provided SYM_DEL_FN() symbol destructors along
* with the symbol data.
* del_fn() HASH_DEL_FN(*) If you want app_data to be free'd when the
* hash-table is destroyed, register a suitable
* destructor function here.
* Output:
* return HashTable * The new hash table, or NULL on error.
*/
{
int i;
/*
* Check arguments.
*/
if(size <= 0) {
return NULL;
};
/*
* Allocate an internal free-list?
*/
if(allocate_mem) {
if(!mem)
return NULL;
};
/*
* Allocate the container.
*/
if(!hash) {
if(allocate_mem)
return NULL;
};
/*
* Before attempting any operation that might fail, initialize
* the container at least up to the point at which it can safely
* be passed to _del_HashTable().
*/
/*
* Allocate the array of 'size' hash buckets.
*/
return _del_HashTable(hash);
};
/*
* Initialize the bucket array.
*/
for(i=0; i<size; i++) {
b->count = 0;
};
/*
* The table is ready for use - albeit currently empty.
*/
return hash;
}
/*.......................................................................
* Delete a hash-table.
*
* Input:
* hash HashTable * The hash table to be deleted.
* Output:
* return HashTable * The deleted hash table (always NULL).
*/
{
if(hash) {
/*
* Clear and delete the bucket array.
*/
};
/*
* Delete application data.
*/
/*
* If the hash table was allocated from an internal free-list, delete
* it and the hash table by deleting the free-list. Otherwise just
* return the hash-table to the external free-list.
*/
if(hash->internal_mem)
else
};
return NULL;
}
/*.......................................................................
* Create and install a new entry in a hash table. If an entry with the
* same name already exists, replace its contents with the new data.
*
* Input:
* hash HashTable * The hash table to insert the symbol into.
* name const char * The name to tag the entry with.
* code int An application-specific code to be stored in
* the entry.
* fn void (*)(void) An application-specific function to be stored
* in the entry.
* data void * An application-specific pointer to data to be
* associated with the entry, or NULL if not
* relevant.
* del_fn SYM_DEL_FN(*) An optional destructor function. When the
* symbol is deleted this function will be called
* with the 'code' and 'data' arguments given
* above. Any application data that was registered
* to the table via the app_data argument of
* _new_HashTable() will also be passed.
* Output:
* return HashNode * The new entry, or NULL if there was insufficient
* memory or the arguments were invalid.
*/
{
/*
* Check arguments.
*/
return NULL;
};
/*
* Get the hash bucket of the specified name.
*/
/*
* See if a node with the same name already exists.
*/
/*
* If found, delete its contents by calling the user-supplied
* destructor function, if provided.
*/
if(node) {
};
/*
* Allocate a new node if necessary.
*/
} else {
if(!node)
return NULL;
};
/*
* Install the node at the head of the hash-bucket list.
*/
}
/*.......................................................................
* Remove and delete a given hash-table entry.
*
* Input:
* hash HashTable * The hash table to find the symbol in.
* name const char * The name of the entry.
* Output:
* return HashNode * The deleted hash node (always NULL).
*/
{
/*
* Node found?
*/
if(node) {
/*
* Remove the node from the bucket list.
*/
if(prev) {
} else {
};
/*
* Record the loss of a node.
*/
/*
* Delete the node.
*/
};
};
return NULL;
}
/*.......................................................................
* Look up a symbol in the hash table.
*
* Input:
* hash HashTable * The table to look up the string in.
* name const char * The name of the symbol to look up.
* Output:
* return Symbol * The located hash-table symbol, or NULL if not
* found.
*/
{
/*
* Check arguments.
*/
if(!hash)
return NULL;
/*
* Nothing to lookup?
*/
if(!name)
return NULL;
/*
* Hash the name to a hash-table bucket.
*/
/*
* Find the bucket entry that exactly matches the name.
*/
if(!node)
return NULL;
}
/*.......................................................................
* Private function used to allocate a hash-table node.
* The caller is responsible for checking that the specified symbol
* is unique and for installing the returned entry in the table.
*
* Input:
* hash HashTable * The table to allocate the node for.
* name const char * The name of the new entry.
* code int A user-supplied context code.
* fn void (*)(void) A user-supplied function pointer.
* data void * A user-supplied data pointer.
* del_fn SYM_DEL_FN(*) An optional 'data' destructor function.
* Output:
* return HashNode * The new node, or NULL on error.
*/
{
/*
* Allocate the new node from the free list.
*/
if(!node)
return NULL;
/*
* Before attempting any operation that might fail, initialize the
* contents of 'node' at least up to the point at which it can be
* safely passed to _del_HashNode().
*/
/*
* Allocate a copy of 'name'.
*/
/*
* If character-case is insignificant in the current table, convert the
* name to lower case while copying it.
*/
if(hash->case_sensitive) {
} else {
*dst = '\0';
};
return node;
}
/*.......................................................................
* Private function used to delete a hash-table node.
* The node must have been removed from its list before calling this
* function.
*
* Input:
* hash HashTable * The table for which the node was originally
* allocated.
* node HashNode * The node to be deleted.
* Output:
* return HashNode * The deleted node (always NULL).
*/
{
if(node) {
/*
* Call the user-supplied data-destructor if provided.
*/
/*
* Return the node to the free-list.
*/
};
return NULL;
}
/*.......................................................................
* Private function to locate the hash bucket associated with a given
* name.
*
* This uses a hash-function described in the dragon-book
* ("Compilers - Principles, Techniques and Tools", by Aho, Sethi and
* Ullman; pub. Adison Wesley) page 435.
*
* Input:
* hash HashTable * The table to look up the string in.
* name const char * The name of the symbol to look up.
* Output:
* return HashBucket * The located hash-bucket.
*/
{
unsigned const char *kp;
unsigned long h = 0L;
if(hash->case_sensitive) {
} else {
};
}
/*.......................................................................
* Search for a given name in the entries of a given bucket.
*
* Input:
* hash HashTable * The hash-table being searched.
* bucket HashBucket * The bucket to search (use _find_HashBucket()).
* name const char * The name to search for.
* Output:
* prev HashNode ** If prev!=NULL then the pointer to the node
* preceding the located node in the list will
* be recorded in *prev. This will be NULL either
* if the name is not found or the located node is
* at the head of the list of entries.
* return HashNode * The located hash-table node, or NULL if not
* found.
*/
{
/*
* Search the list for a node containing the specified name.
*/
;
if(prev)
return node;
}
/*.......................................................................
* When hash->case_sensitive is zero this function is called
* in place of strcmp(). In such cases the hash-table names are stored
* as lower-case versions of the original strings so this function
* performs the comparison against lower-case copies of the characters
* of the string being compared.
*
* Input:
* node_key const char * The lower-case hash-node key being compared
* against.
* look_key const char * The lookup key.
* Output:
* return int <0 if node_key < look_key.
* 0 if node_key == look_key.
* >0 if node_key > look_key.
*/
{
do {
}
/*.......................................................................
* This is a wrapper around strcmp for comparing hash-keys in a case
* sensitive manner. The reason for having this wrapper, instead of using
* strcmp() directly, is to make some C++ compilers happy. The problem
* is that when the library is compiled with a C++ compiler, the
* declaration of the comparison function is a C++ declaration, whereas
* strcmp() is a pure C function and thus although it appears to have the
* same declaration, the compiler disagrees.
*
* Input:
* node_key char * The lower-case hash-node key being compared against.
* look_key char * The lookup key.
* Output:
* return int <0 if node_key < look_key.
* 0 if node_key == look_key.
* >0 if node_key > look_key.
*/
{
}
/*.......................................................................
* Empty a hash-table by deleting all of its entries.
*
* Input:
* hash HashTable * The hash table to clear.
* Output:
* return int 0 - OK.
* 1 - Invalid arguments.
*/
{
int i;
/*
* Check the arguments.
*/
if(!hash)
return 1;
/*
* Clear the contents of the bucket array.
*/
/*
* Delete the list of active hash nodes from the bucket.
*/
while(node) {
};
/*
* Mark the bucket as empty.
*/
};
return 0;
}
/*.......................................................................
* Execute a given function on each entry of a hash table, returning
* before completion if the the specified function returns non-zero.
*
* Input:
* hash HashTable * The table to traverse.
* scan_fn HASH_SCAN_FN(*) The function to call.
* context void * Optional caller-specific context data
* to be passed to scan_fn().
* Output:
* return int 0 - OK.
* 1 - Either the arguments were invalid, or
* scan_fn() returned non-zero at some
* point.
*/
{
int i;
/*
* Check the arguments.
*/
return 1;
/*
* Iterate through the buckets of the table.
*/
/*
* Iterate through the list of symbols that fall into bucket i,
* passing each one to the caller-specified function.
*/
return 1;
};
};
return 0;
}