/*****************************************************************************/
/*                                                                           */
/*                                 hashtab.h                                 */
/*                                                                           */
/*                            Generic hash table                             */
/*                                                                           */
/*                                                                           */
/*                                                                           */
/* (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       */
/* 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. 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 */
    unsigned            Hash;           /* The full hash value */
};

#define STATIC_HASHNODE_INITIALIZER     { 0, 0, 0 }

/* Hash table functions */
typedef struct HashFunctions HashFunctions;
struct HashFunctions {

    unsigned (*GenHash) (const void* Key);
    /* Generate the hash over a key. */

    const void* (*GetKey) (const void* Entry);
    /* Given a pointer to the user entry data, return a pointer to the key */

    int (*Compare) (const void* Key1, const void* Key2);
    /* 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 */
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)
/* Initialize a hash node. */
{
    N->Next     = 0;
}
#else
#define InitHashNode(N)         do { (N)->Next   = 0; } while (0)
#endif



/*****************************************************************************/
/*                             struct HashTable                              */
/*****************************************************************************/



HashTable* InitHashTable (HashTable* T, unsigned Slots, const HashFunctions* Func);
/* Initialize a hash table and return it */

void DoneHashTable (HashTable* T);
/* Destroy the contents of a hash table. Note: This will not free the entries
** in the table!
*/

#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! */

#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

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_Find (const HashTable* T, const void* Key);
/* Find the entry with the given key and return it */

void HT_Insert (HashTable* T, void* Entry);
/* Insert an entry into the given hash table */

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