vcs.maemo.org Git - monky/blob - src/hash.h

   1 /* ------------------------------------------------------
   2  * Open-addressed hash using double hash probing
   3  *
   4  * for i in 0 to m-1:
   5  *      h(k, i) = ( h1(k) + i*h2(k) ) mod m
   6  *
   7  * requires: 1) m must be a power of two
   8  *           2) h2(k) must return an odd number
   9  *
  10  * Besed on code published in _Mastering Algorithms in C_
  11  * by Kyle Loudon (O'Reilly 1999).
  12  * Modified by Philip Kovacs (kovacsp3@comcast.net)
  13  *
  14  * $Id$
  15  * ------------------------------------------------------ */
  16
  17 #ifndef HASH_H
  18 #define HASH_H
  19
  20 typedef struct _hash_table_t {
  21         int     positions;
  22         int     size;
  23         int     vacated;
  24         int     sentinel_vacated;
  25         void    *p_vacated;
  26         int     (*p_hash_fun1)(const void *p_data);
  27         int     (*p_hash_fun2)(const void *p_data);
  28         int     (*p_match_fun)(const void *p_data1, const void *p_data2);
  29         void    (*p_destroy_fun)(void *p_data);
  30         void    **pp_table;
  31 } hash_table_t;
  32
  33 /* Create and initialize a hash table on the heap.
  34    Returns 0 on success, -1 otherwise. */
  35 int hash_create( hash_table_t *p_hash_table,
  36                  int positions,
  37                  int (*p_hash_fun1)(const void *p_data),
  38                  int (*p_hash_fun2)(const void *p_data),
  39                  int (*p_match_fun)(const void *p_data1, const void *p_data2),
  40                  void (*p_destroy_fun)(void *p_data)
  41         );
  42
  43 /* Destroy a hash table */
  44 void hash_destroy( hash_table_t *p_hash_table );
  45
  46 /* Insert an element into a hash table.
  47    Returns 0 on successful insert, 1 if data already in hash and -1 if unable to insert. */
  48 int hash_insert( hash_table_t *p_hash_table, const void *p_data);
  49
  50 /* Delete an element from a hash table.
  51    Returns 0 on successful delete, -1 if not found. */
  52 int hash_remove( hash_table_t *p_hash_table, void **pp_data);
  53
  54 /* Lookup an element in a hash table.
  55    Returns 0 if found (data passed back byref), -1 if not found. */
  56 int hash_lookup(const hash_table_t *p_hash_table, void **pp_data);
  57
  58 /* Return size of a hash table */
  59 #define hash_size(p_hash_table) ((p_hash_table)->size)
  60
  61 #endif