/*
Copyright (c) 2004 Joseph Gleason

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, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

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. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

Current versions of this and other code can be downloaded at:
http://gleason.cc/

*/

#ifndef __HASH_TABLE__
#define __HASH_TABLE__

#include <netdb.h>

/* Joseph Gleason 2004
   hash_table.c and hash_table.h

   This set of functions provides a basic hash table
   with linked lists for fast traversal.

   The key can be any data type, expressed
   as a void pointer and a key length.

   Different types of keys may be used, although
   the user should take care in that some disparit
   data types could have the same key data and key length
   and thus be considered the same record.

*/

/* holds an entry to the hash table */

struct hash_table_entry
{

   //Pointers for linked list that covers
   //entire table
   struct hash_table_entry* InsertPrev;
   struct hash_table_entry* InsertNext;

   //Pointer for other entries in same hash slot
   struct hash_table_entry* SlotNext;

   //Key Data
   //Should never be modified
   size_t KeyLen;
   void* Key;

   //Pointer to data associated with this key
   void* Data;

};
typedef struct hash_table_entry hash_table_entry_t;


/* Holds the information for one slot of the hash table
   obviously, just a pointer to the linked list, but I thought
   it wise to make a separate data type for clairity */
struct hash_table_slot
{
   hash_table_entry_t* First;
};
typedef struct hash_table_slot hash_table_slot_t;


struct hash_table
{
   double LoadFactor; //The ratio of TableTotalElements/TableLength
                      //that is sufficent to cause resize
                      //*RESIZING IS NOT YET IMPLEMENTED*

   size_t TableLength; //Length of table array
   size_t TableTotalElements; //Total number of elements
   size_t TableSlotsInUse; //Total number of used slots in table array

   //Pointers to total linked list
   hash_table_entry_t* InsertFirst;
   hash_table_entry_t* InsertLast;

   //Hash table slots
   hash_table_slot_t* Array;

};
typedef struct hash_table hash_table_t;

//Initalize the table specified by T
//- T: is assumed to be a pointer to already allocated
//  memory of length sizeof(hash_table_t)
//
//- InitalSize: the inital number of array entries
//  Note: table can hold more than initialsize without
//  resizing because collisions are handled through linked lists
//  Note2: The actual initalsize will be next highest power of 2.
//  If InitalSize of 10 is passed in, table will be created with inital size
//  of 16.
//
//- LoadFactor: the ratio of TableTotalElements/TableLength that
//  is sufficent to trigger resizing. RESIZING IS NOT YET IMPLEMENTED.
//  Currently the table just gets less efficent as more entries are added
void hash_table_init(hash_table_t *T, int InitalSize, double LoadFactor);

//Deallocates all memory associated with table T
//That was allocated by these functions.
//This includes the copies of keys, the hash_table_entries, hash_table_slots
//This DOES NOT include the 'Data' pointers provided by the user.
void hash_table_destroy(hash_table_t *T);

//Accessors
//Note: All get functions return a pointer to the hash_table_entry
//in question or NULL.  Modify key or the linked list pointers
//of the hash_table_entries at your own risk.
//Feel free to change Data pointer.
//Pointers returned by the get functions will still be valid
//after put or erase (below) as long as, the key in question
//was not itself erased and resizing is not implemented.
hash_table_entry_t* hash_table_getfirst(hash_table_t *T);
hash_table_entry_t* hash_table_getlast(hash_table_t *T);
hash_table_entry_t* hash_table_get(hash_table_t *T,void* Key, size_t KeyLen);

//Modifiers

//Put inserts the entry with the given key and data pointers
//into the table.  The Key is copied into new memory, so the caller
//is free to modify/destroy key after the put call returns.
//The the memory referenced by Data is not copied.  The value of the
//Data pointer is just stored.
//returns 1 on success where item with same key did not exist
//returns 2 on success where item with same key was overwritten
//Note: Linked list order is not changed on overwrite otherwise
//the linked list is garanteed to be in insertion order.
int hash_table_put(hash_table_t *T,void* Key, size_t KeyLen, void* Data);

//Removes entry with specified key from table.
//If key was present and removed, the Data pointer is returned.
//If the key was not present in the table, the NULL is returned.
//Note: if you are fond of storing NULLs as the data values
//in the table, you wont be able to distingish between the above
//cases
void* hash_table_erase(hash_table_t *T,void* Key, size_t KeyLen);



#endif