|
996
|
1 /*-*-c-*- ************************************************************
|
|
|
2 * Copyright (C) 2001-2005, Simon Kagstrom
|
|
|
3 *
|
|
|
4 * Filename: ght_hash_table.h.in
|
|
|
5 * Description: The definitions used in the hash table.
|
|
|
6 *
|
|
|
7 * This program is free software; you can redistribute it and/or
|
|
|
8 * modify it under the terms of the GNU Library General Public License
|
|
|
9 * as published by the Free Software Foundation; either version 2
|
|
|
10 * of the License, or (at your option) any later version.
|
|
|
11 *
|
|
|
12 * This program is distributed in the hope that it will be useful,
|
|
|
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
15 * GNU General Public License for more details.
|
|
|
16 *
|
|
|
17 * You should have received a copy of the GNU Library General Public
|
|
|
18 * License along with this program; if not, write to the Free Software
|
|
|
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
|
|
|
20 * 02111-1307, USA.
|
|
|
21 *
|
|
|
22 * $Id: ght_hash_table.h.in 15761 2007-07-15 06:08:52Z ska $
|
|
|
23 *
|
|
|
24 ********************************************************************/
|
|
|
25
|
|
|
26 /**
|
|
|
27 * @file
|
|
|
28 * libghthash is a generic hash table used for storing arbitrary
|
|
|
29 * data.
|
|
|
30 *
|
|
|
31 * Libghthash really stores pointers to data - the hash
|
|
|
32 * table knows nothing about the actual type of the data.
|
|
|
33 *
|
|
|
34 * A simple example to get started can be found in the
|
|
|
35 * <TT>example/simple.c</TT> file found in the distribution.
|
|
|
36 * <TT>hash_test.c</TT> provides a more complete example.
|
|
|
37 *
|
|
|
38 * Some basic properties of the hash table are:
|
|
|
39 *
|
|
|
40 * - Both the data stored and the keys are of void type, which
|
|
|
41 * means that you can store any kind of data.
|
|
|
42 *
|
|
|
43 * - The only functions you probably will need to start is:
|
|
|
44 * - ght_create(), which creates a new hash table.
|
|
|
45 * - ght_insert(), which inserts a new entry into a table.
|
|
|
46 * - ght_get(), which searches for an entry.
|
|
|
47 * - ght_remove(), which removes and entry.
|
|
|
48 * - ght_finalize(), which destroys a hash table.
|
|
|
49 *
|
|
|
50 * - Inserting entries is done without first creating a key,
|
|
|
51 * i.e. you insert with the data, the datasize, the key and the
|
|
|
52 * key size directly.
|
|
|
53 *
|
|
|
54 * - The hash table copies the key data when inserting new
|
|
|
55 * entries. This means that you should <I>not</I> malloc() the key
|
|
|
56 * before inserting a new entry.
|
|
|
57 *
|
|
|
58 */
|
|
|
59 #ifndef GHT_HASH_TABLE_H
|
|
|
60 #define GHT_HASH_TABLE_H
|
|
|
61
|
|
|
62 #include "../../src/global.h"
|
|
|
63 #include "../../src/funge-space/funge-space.h"
|
|
|
64 #include <stdlib.h> /* size_t */
|
|
|
65 #include <stdint.h>
|
|
|
66 #include <stdbool.h>
|
|
|
67
|
|
|
68 #define GHT_HEURISTICS_NONE 0
|
|
|
69 #define GHT_HEURISTICS_TRANSPOSE 1
|
|
|
70 #define GHT_HEURISTICS_MOVE_TO_FRONT 2
|
|
|
71 #define GHT_AUTOMATIC_REHASH 4
|
|
|
72
|
|
|
73 #ifndef TRUE
|
|
|
74 # define TRUE true
|
|
|
75 #endif
|
|
|
76
|
|
|
77 #ifndef FALSE
|
|
|
78 # define FALSE false
|
|
|
79 #endif
|
|
|
80
|
|
|
81 // Use macros for some stuff.
|
|
|
82 #define GHT_USE_MACROS
|
|
|
83 // What checksum to use, one of:
|
|
|
84 // one_at_a_time_hash
|
|
|
85 // crc_hash
|
|
|
86 // murmur_hash
|
|
|
87 // Be sure to change to #if 1 for the relevant function in hash_functions.c
|
|
|
88 #define GHT_HASH_NAME crc_hash
|
|
|
89 // Define to one of the GHT_HEURISTICS_* above
|
|
|
90 #define GHT_HEURISTICS GHT_HEURISTICS_NONE
|
|
|
91
|
|
|
92 /** unsigned 32 bit integer. */
|
|
|
93 typedef uint32_t ght_uint32_t;
|
|
|
94
|
|
|
95 #ifdef GHT_USE_MACROS
|
|
|
96 # define ght_size(p_ht) (p_ht->i_items)
|
|
|
97 # define ght_table_size(p_ht) (p_ht->i_size)
|
|
|
98 #endif
|
|
|
99
|
|
|
100 // I hate the preprocessor
|
|
|
101 #define CF_GHT_NAME_INTERN(m_prefix, m_variant, m_name) \
|
|
|
102 m_prefix ## m_variant ## _ ## m_name
|
|
|
103
|
|
|
104 #define CF_GHT_NAME(m_variant, m_name) \
|
|
|
105 CF_GHT_NAME_INTERN(ght_, m_variant, m_name)
|
|
|
106
|
|
|
107 #define CF_GHT_STRUCT(m_variant, m_name) \
|
|
|
108 CF_GHT_NAME_INTERN(s_, m_variant, m_name)
|
|
|
109
|
|
|
110 /*
|
|
|
111 * CF_GHT_VAR - Variant name
|
|
|
112 * CF_GHT_KEY - Type of key
|
|
|
113 * CF_GHT_DATA - Type of data
|
|
|
114 */
|
|
|
115
|
|
|
116 // Create funge space storage.
|
|
|
117 #define CF_GHT_VAR fspace
|
|
|
118 #define CF_GHT_KEY fungeSpaceHashKey
|
|
|
119 #define CF_GHT_DATA funge_cell
|
|
|
120
|
|
|
121 #include "ght_hash_table_priv.h"
|
|
|
122
|
|
|
123 #undef CF_GHT_VAR
|
|
|
124 #undef CF_GHT_KEY
|
|
|
125 #undef CF_GHT_DATA
|
|
|
126
|
|
|
127 // Create column/row count variant.
|
|
|
128 #ifdef CFUN_EXACT_BOUNDS
|
|
|
129 # define CF_GHT_VAR fspacecount
|
|
|
130 # define CF_GHT_KEY funge_cell
|
|
|
131 # define CF_GHT_DATA funge_unsigned_cell
|
|
|
132
|
|
|
133 # include "ght_hash_table_priv.h"
|
|
|
134
|
|
|
135 # undef CF_GHT_VAR
|
|
|
136 # undef CF_GHT_KEY
|
|
|
137 # undef CF_GHT_DATA
|
|
|
138 #endif
|
|
|
139
|
|
|
140 #ifndef CF_GHT_INTERNAL
|
|
|
141 # undef CF_GHT_NAME_INTERN
|
|
|
142 # undef CF_GHT_NAME
|
|
|
143 # undef CF_GHT_STRUCT
|
|
|
144 #endif
|
|
|
145
|
|
|
146 #endif /* GHT_HASH_TABLE_H */
|
