/*
** This file is part of the C Utility Toolkit (CUTK)
** Copyright (C) 2002-2005 Chris Osgood
** http://www.cutk.org
**
** This library is free software; you can redistribute it and/or
** modify it under the terms of the GNU Lesser General Public
** License as published by the Free Software Foundation; either
** version 2.1 of the License, or (at your option) any later version.
**
** This library is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
** Lesser General Public License for more details.
**
** You should have received a copy of the GNU Lesser General Public
** License along with this library; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
**
** Please report all bugs and problems to "bugs at cutk.org".
*/

/*
** A fast hash map implementation similar to STL hash_map<char*,void*>.  It's
** very important to note that the keys in the hash map are just stored as
** pointers, therefore you can't reuse the same string pointer for inserting
** different keys.  It's also not a good idea to change the value of a key
** while it's still in a hash map.
**
** Erased items do not free memory unless StrHmapCompact is called.  However,
** erased item's memory will be reused if new items are inserted.
**
** Function reference:
**   StrHmapAlloc   -- Allocates a new hash map with space for "size"
**                     initial elements.
**   StrHmapFree    -- Free a hash map
**   StrHmapFind    -- Finds an element in the hash map
**   StrHmapSize    -- Approx number of elements in hash map (erased items
**                     may still show up in the count).
**   StrHmapReserve -- Allocates memory for "size" elements and rehashes
**                     the map.
**   StrHmapInsert  -- Inserts a new element into the hash map.  Will get an
**                     error if the key already exists.
**   StrHmapReplace -- Inserts or replaces an element in the hash map
**   StrHmapErase   -- Removes element from hash map
**   StrHmapDup     -- Duplicates a hash map
**   StrHmapCompact -- Frees memory held by erased items & rebuilds the tables
**   StrHmapClear   -- Erases all elements in the hash map.  Does not free
**                     memory.  Usr StrHmapClear then StrHmapCompact to free
**                     memory.
**
** Example usage:
**
**   int sample_value;
**   StrHmap* map = StrHmapAlloc(0);
**   StrHmapInsert(map, "1234", "value for key 1234");
**   StrHmapInsert(map, "5678", "value for key 5678");
**   StrHmapInsert(map, "intvalue", &sample_value);
**   int* findval = StrHmapFind(map, "intvalue");
**   if (findval)
**      printf("the value is %d\n", *findval);
**    ...
**   StrHmapFree(map);
**
** $Id: strhmap.h 7 2005-01-02 01:02:22Z chris $
*/

#ifndef _STRHMAP_H
#define _STRHMAP_H

#include <cutk/array.h>
#include <string.h>

#ifdef __cplusplus
extern "C" {
#endif

/* Type used to store items in the hash map */
typedef struct StrHmap_itemtype
{
   const char* key;
   const void* item;
   size_t next;
} StrHmap_itemtype;

/* Hash map type.  "items" is an array that can be used for iteration. */
/* When iterating, test the item->key value for NULL (erased items).   */
/* Use StrHmapSize to determine the number of items.                   */
typedef struct StrHmap
{
   size_t* hash_tbl;
   StrHmap_itemtype* items;
   size_t deleted;
} StrHmap;

#define StrHmapSize(x) (arysize(&(x)->items))

StrHmap* StrHmapAlloc(size_t size);
   void  StrHmapClear(StrHmap* hashmap);
    int  StrHmapCompact(StrHmap* hashmap);
StrHmap* StrHmapDup(const StrHmap* hashmap);
    int  StrHmapErase(StrHmap* hashmap, const char* key);
   void  StrHmapFree(StrHmap* hashmap);
   void* StrHmapFind(StrHmap* hashmap, const char* key);
    int  StrHmapInsert(StrHmap* hashmap, const char* key, const void* item);
    int  StrHmapReplace(StrHmap* hashmap, const char* key, const void* item);
    int  StrHmapReserve(StrHmap* hashmap, size_t size);

#ifdef __cplusplus
}
#endif

#endif /* _STRHMAP_H */