From a492e6f895fab06c3497ed6f829fddab23afecf7 Mon Sep 17 00:00:00 2001 From: cuz Date: Wed, 22 Oct 2003 18:12:43 +0000 Subject: [PATCH] New generic hash table module git-svn-id: svn://svn.cc65.org/cc65/trunk@2557 b7a2c559-68d2-44c3-8de9-860c34a00d81 --- src/common/hashtab.c | 191 +++++++++++++++++++++++++++++++++++ src/common/hashtab.h | 197 +++++++++++++++++++++++++++++++++++++ src/common/make/gcc.mak | 1 + src/common/make/watcom.mak | 1 + 4 files changed, 390 insertions(+) create mode 100644 src/common/hashtab.c create mode 100644 src/common/hashtab.h diff --git a/src/common/hashtab.c b/src/common/hashtab.c new file mode 100644 index 000000000..7ba78ce1e --- /dev/null +++ b/src/common/hashtab.c @@ -0,0 +1,191 @@ +/*****************************************************************************/ +/* */ +/* hashtab.c */ +/* */ +/* Generic hash table */ +/* */ +/* */ +/* */ +/* (C) 2003 Ullrich von Bassewitz */ +/* Römerstrasse 52 */ +/* D-70794 Filderstadt */ +/* EMail: uz@cc65.org */ +/* */ +/* */ +/* This software is provided 'as-is', without any expressed or implied */ +/* warranty. In no event will the authors be held liable for any damages */ +/* arising from the use of this software. */ +/* */ +/* Permission is granted to anyone to use this software for any purpose, */ +/* including commercial applications, and to alter it and redistribute it */ +/* freely, subject to the following restrictions: */ +/* */ +/* 1. The origin of this software must not be misrepresented; you must not */ +/* claim that you wrote the original software. If you use this software */ +/* in a product, an acknowledgment in the product documentation would be */ +/* appreciated but is not required. */ +/* 2. Altered source versions must be plainly marked as such, and must not */ +/* be misrepresented as being the original software. */ +/* 3. This notice may not be removed or altered from any source */ +/* distribution. */ +/* */ +/*****************************************************************************/ + + + +/* common */ +#include "hashtab.h" +#include "xmalloc.h" + + + +/*****************************************************************************/ +/* struct HashTable */ +/*****************************************************************************/ + + + +void FreeHashTable (HashTable* T) +/* Free a hash table. Note: This will not free the entries in the table! */ +{ + if (T) { + /* Free the contents */ + DoneHashTable (T); + /* Free the table structure itself */ + xfree (T); + } +} + + + +static void HT_Alloc (HashTable* T) +/* Allocate table memory */ +{ + unsigned I; + + /* Allocate memory */ + T->Table = xmalloc (T->Slots * sizeof (T->Table[0])); + + /* Initialize the table */ + for (I = 0; I < T->Slots; ++I) { + T->Table[I] = 0; + } +} + + + +HashNode* HT_Find (const HashTable* T, const void* Index) +/* Find the node with the given index */ +{ + unsigned Hash; + HashNode* N; + + /* If we don't have a table, there's nothing to find */ + if (T->Table == 0) { + return 0; + } + + /* Generate the hash over the index */ + Hash = T->Func->GenHash (Index); + + /* Search for the entry in the given chain */ + N = T->Table[Hash % T->Slots]; + while (N) { + + /* First compare the full hash, to avoid calling the compare function + * if it is not really necessary. + */ + if (N->Hash == Hash && + T->Func->Compare (Index, T->Func->GetIndex (N->Entry))) { + /* Found */ + break; + } + + /* Not found, next entry */ + N = N->Next; + } + + /* Return what we found */ + return N; +} + + + +void* HT_FindEntry (const HashTable* T, const void* Index) +/* Find the node with the given index and return the corresponding entry */ +{ + /* First, search for the hash node */ + HashNode* N = HT_Find (T, Index); + + /* Convert the node into an entry if necessary */ + return N? N->Entry : 0; +} + + + +void HT_Insert (HashTable* T, HashNode* N) +/* Insert a node into the given hash table */ +{ + unsigned RHash; + + /* If we don't have a table, we need to allocate it now */ + if (T->Table == 0) { + HT_Alloc (T); + } + + /* Generate the hash for the node contents */ + N->Hash = T->Func->GenHash (T->Func->GetIndex (N->Entry)); + + /* Calculate the reduced hash */ + RHash = N->Hash % T->Slots; + + /* Insert the entry into the correct chain */ + N->Next = T->Table[RHash]; + T->Table[RHash] = N; + + /* One more entry */ + ++T->Count; +} + + + +void HT_InsertEntry (HashTable* T, void* Entry) +/* Insert an entry into the given hash table */ +{ + HT_Insert (T, T->Func->GetHashNode (Entry)); +} + + + +void HT_Walk (HashTable* T, void (*F) (void* Entry, void* Data), void* Data) +/* Walk over all nodes of a hash table. For each node, the user supplied + * function F is called, passing a pointer to the entry, and the data pointer + * passed to HT_Walk by the caller. + */ +{ + unsigned I; + + /* If we don't have a table there are no entries to walk over */ + if (T->Table == 0) { + return; + } + + /* Walk over all chains */ + for (I = 0; I < T->Slots; ++I) { + + /* Get the pointer to the first entry of the hash chain */ + HashNode* N = T->Table[I]; + + /* Walk over all entries in this chain */ + while (N) { + /* Call the user function */ + F (N->Entry, Data); + /* Next node in chain */ + N = N->Next; + } + + } +} + + + diff --git a/src/common/hashtab.h b/src/common/hashtab.h new file mode 100644 index 000000000..14e1398e9 --- /dev/null +++ b/src/common/hashtab.h @@ -0,0 +1,197 @@ +/*****************************************************************************/ +/* */ +/* hashtab.h */ +/* */ +/* Generic hash table */ +/* */ +/* */ +/* */ +/* (C) 2003 Ullrich von Bassewitz */ +/* Römerstrasse 52 */ +/* D-70794 Filderstadt */ +/* EMail: uz@cc65.org */ +/* */ +/* */ +/* This software is provided 'as-is', without any expressed or implied */ +/* warranty. In no event will the authors be held liable for any damages */ +/* arising from the use of this software. */ +/* */ +/* Permission is granted to anyone to use this software for any purpose, */ +/* including commercial applications, and to alter it and redistribute it */ +/* freely, subject to the following restrictions: */ +/* */ +/* 1. The origin of this software must not be misrepresented; you must not */ +/* claim that you wrote the original software. If you use this software */ +/* in a product, an acknowledgment in the product documentation would be */ +/* appreciated but is not required. */ +/* 2. Altered source versions must be plainly marked as such, and must not */ +/* be misrepresented as being the original software. */ +/* 3. This notice may not be removed or altered from any source */ +/* distribution. */ +/* */ +/*****************************************************************************/ + + + +#ifndef HASHTAB_H +#define HASHTAB_H + + + +/* common */ +#include "inline.h" +#include "xmalloc.h" + + + +/*****************************************************************************/ +/* Data */ +/*****************************************************************************/ + + + +/* Hash table node */ +typedef struct HashNode HashNode; +struct HashNode { + HashNode* Next; /* Next entry in hash list */ + struct HashTable* Owner; /* Owner table */ + unsigned Hash; /* The full hash value */ + void* Entry; /* Pointer to user entry data */ +}; + +#define STATIC_HASHNODE_INITIALIZER(Entry) { 0, 0, 0, Entry } + +/* Hash table functions */ +typedef struct HashFunctions HashFunctions; +struct HashFunctions { + + unsigned (*GenHash) (const void* Index); + /* Generate the hash over an index. */ + + const void* (*GetIndex) (void* Entry); + /* Given a pointer to the user entry data, return a pointer to the index */ + + HashNode* (*GetHashNode) (void* Entry); + /* Given a pointer to the user entry data, return a pointer to the hash node */ + + int (*Compare) (const void* Index1, const void* Index2); + /* Compare two indices for equality */ +}; + +/* Hash table */ +typedef struct HashTable HashTable; +struct HashTable { + unsigned Slots; /* Number of table slots */ + unsigned Count; /* Number of table entries */ + HashNode** Table; /* Table, dynamically allocated */ + const HashFunctions* Func; /* Table functions */ +}; + +#define STATIC_HASHTABLE_INITIALIZER(Slots, Func) { Slots, 0, 0, Func } + + + +/*****************************************************************************/ +/* struct HashNode */ +/*****************************************************************************/ + + + +#if defined(HAVE_INLINE) +INLINE void InitHashNode (HashNode* N, void* Entry) +/* Initialize a hash node */ +{ + N->Next = 0; + N->Owner = 0; + N->Entry = Entry; +} +#else +#define InitHashNode(N, Entry) \ + (N)->Next = 0; \ + (N)->Owner = 0; \ + (N)->Entry = (Entry) +#endif + + + +/*****************************************************************************/ +/* struct HashTable */ +/*****************************************************************************/ + + + +#if defined(HAVE_INLINE) +INLINE HashTable* InitHashTable (HashTable* T, unsigned Slots, const HashFunctions* Func) +/* Initialize a hash table and return it */ +{ + /* Initialize the fields */ + T->Slots = Slots; + T->Count = 0; + T->Table = 0; + T->Func = Func; + + /* Return the initialized table */ + return T; +} +#else +#define InitHashTable(T, Slots, Func) \ + (T)->Slots = (Slots), \ + (T)->Count = 0, \ + (T)->Table = 0, \ + (T)->Func = (Func), \ + (T) +#endif + +#if defined(HAVE_INLINE) +INLINE void DoneHashTable (HashTable* T) +/* Destroy the contents of a hash table. Note: This will not free the entries + * in the table! + */ +{ + /* Just free the array with the table pointers */ + xfree (T->Table); +} +#else +#define DoneHashTable(T) xfree ((T)->Table) +#endif + +#if defined(HAVE_INLINE) +INLINE HashTable* NewHashTable (unsigned Slots, const HashFunctions* Func) +/* Create a new hash table and return it. */ +{ + /* Allocate memory, initialize and return it */ + return InitHashTable (xmalloc (sizeof (HashTable)), Slots, Func); +} +#else +#define NewHashTable(Slots, Func) InitHashTable(xmalloc (sizeof (HashTable)), Slots, Func) +#endif + +void FreeHashTable (HashTable* T); +/* Free a hash table. Note: This will not free the entries in the table! */ + +HashNode* HT_Find (const HashTable* T, const void* Index); +/* Find the node with the given index */ + +void* HT_FindEntry (const HashTable* T, const void* Index); +/* Find the node with the given index and return the corresponding entry */ + +void HT_Insert (HashTable* T, HashNode* N); +/* Insert a node into the given hash table */ + +void HT_InsertEntry (HashTable* T, void* Entry); +/* Insert an entry into the given hash table */ + +void HT_Walk (HashTable* T, void (*F) (void* Entry, void* Data), void* Data); +/* Walk over all nodes of a hash table. For each node, the user supplied + * function F is called, passing a pointer to the entry, and the data pointer + * passed to HT_Walk by the caller. + */ + + + +/* End of hashtab.h */ + +#endif + + + diff --git a/src/common/make/gcc.mak b/src/common/make/gcc.mak index fccc131bf..1f7590ec1 100644 --- a/src/common/make/gcc.mak +++ b/src/common/make/gcc.mak @@ -22,6 +22,7 @@ OBJS = abend.o \ filetype.o \ fname.o \ hashstr.o \ + hashtab.o \ matchpat.o \ print.o \ searchpath.o \ diff --git a/src/common/make/watcom.mak b/src/common/make/watcom.mak index 057d1394c..bdd08a2f9 100644 --- a/src/common/make/watcom.mak +++ b/src/common/make/watcom.mak @@ -54,6 +54,7 @@ OBJS = abend.obj \ filetype.obj \ fname.obj \ hashstr.obj \ + hashtab.obj \ matchpat.obj \ print.obj \ searchpath.obj \ -- 2.39.5