/* */
/* */
/* */
-/* (C) 2003 Ullrich von Bassewitz */
-/* Römerstrasse 52 */
-/* D-70794 Filderstadt */
-/* EMail: uz@cc65.org */
+/* (C) 2003-2011, Ullrich von Bassewitz */
+/* Roemerstrasse 52 */
+/* D-70794 Filderstadt */
+/* EMail: uz@cc65.org */
/* */
/* */
/* This software is provided 'as-is', without any expressed or implied */
/*****************************************************************************/
-/* Data */
+/* Data */
/*****************************************************************************/
-/* Hash table node */
+/* Hash table node. NOTE: This structure must be the first member of a struct
+** that is hashed by the module. Having it first allows to omit a pointer to
+** the entry itself, because the C standard guarantees that a pointer to a
+** struct can be converted to its first member.
+*/
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 }
+#define STATIC_HASHNODE_INITIALIZER { 0, 0, 0 }
/* Hash table functions */
typedef struct HashFunctions HashFunctions;
unsigned (*GenHash) (const void* Key);
/* Generate the hash over a key. */
- const void* (*GetKey) (void* Entry);
+ const void* (*GetKey) (const void* Entry);
/* Given a pointer to the user entry data, return a pointer to the key */
- HashNode* (*GetHashNode) (void* Entry);
- /* Given a pointer to the user entry data, return a pointer to the hash node */
-
int (*Compare) (const void* Key1, const void* Key2);
- /* Compare two keys for equality */
+ /* Compare two keys. The function must return a value less than zero if
+ ** Key1 is smaller than Key2, zero if both are equal, and a value greater
+ ** than zero if Key1 is greater then Key2.
+ */
};
/* Hash table */
#if defined(HAVE_INLINE)
-INLINE void InitHashNode (HashNode* N, void* Entry)
+INLINE void InitHashNode (HashNode* N)
/* 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)
+#define InitHashNode(N) do { (N)->Next = 0; } while (0)
#endif
-#if defined(HAVE_INLINE)
-INLINE HashTable* InitHashTable (HashTable* T, unsigned Slots, const HashFunctions* Func)
+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)
+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
+** in the table!
+*/
#if defined(HAVE_INLINE)
INLINE HashTable* NewHashTable (unsigned Slots, const HashFunctions* Func)
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* Key);
-/* Find the node with the given key*/
+#if defined(HAVE_INLINE)
+INLINE unsigned HT_GetCount (const HashTable* T)
+/* Return the number of items in the table. */
+{
+ return T->Count;
+}
+#else
+#define HT_GetCount(T) ((T)->Count)
+#endif
-void* HT_FindEntry (const HashTable* T, const void* Key);
-/* Find the node with the given key and return the corresponding entry */
+HashNode* HT_FindHash (const HashTable* T, const void* Key, unsigned Hash);
+/* Find the node with the given key. Differs from HT_Find in that the hash
+** for the key is precalculated and passed to the function.
+*/
-void HT_Insert (HashTable* T, HashNode* N);
-/* Insert a node into the given hash table */
+void* HT_Find (const HashTable* T, const void* Key);
+/* Find the entry with the given key and return it */
-void HT_InsertEntry (HashTable* T, void* Entry);
+void HT_Insert (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.
- */
+void HT_Remove (HashTable* T, void* Entry);
+/* Remove an entry from the given hash table */
+
+void HT_Walk (HashTable* T, int (*F) (void* Entry, void* Data), void* Data);
+/* Walk over all nodes of a hash table, optionally deleting entries from the
+** 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.
+** If F returns true, the node is deleted from the hash table otherwise it's
+** left in place. While deleting the node, the node is not accessed, so it is
+** safe for F to free the memory associcated with the entry.
+*/
/* End of hashtab.h */
#endif
-
-
-