· 8 years ago · Jul 07, 2018, 08:40 PM
1/**
2 * This file is part of Piranha, a lightweight multi-protocol application server.
3 * Copyright (c) 2009 Sean Kerr. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification, are permitted
6 * provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice, this list of conditions
9 * and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright notice, this list of
11 * conditions and the following disclaimer in the documentation and/or other materials provided
12 * with the distribution.
13 * * Neither the name Piranha nor the names of its contributors may be used to endorse or promote
14 * products derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
18 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
19 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
22 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
23 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 *
25 * Author: Sean Kerr <sean@code-box.org>
26 */
27
28#ifndef PI_TABLE_H
29#define PI_TABLE_H
30
31// -------------------------------------------------------------------------------------------------
32// STRUCTS
33// -------------------------------------------------------------------------------------------------
34
35typedef struct _pi_table_bucket_t {
36
37 // in order of size
38 void* key;
39 void* value;
40 unsigned int hash;
41 struct _pi_table_bucket_t* next;
42
43} pi_table_bucket_t;
44
45typedef struct _pi_table_t {
46
47 // in order of size
48 float load_factor;
49 unsigned int bucket_count;
50 unsigned int key_count;
51 unsigned int prime_index;
52 unsigned int resize_count;
53 pi_table_bucket_t** buckets;
54
55 unsigned int (*comp_func) (void*, void*);
56 unsigned int (*hash_func) (void*);
57
58} pi_table_t;
59
60typedef struct _pi_table_iter_t {
61
62 // in order of size
63 void* key;
64 void* value;
65 unsigned int hash;
66 unsigned int bucket_index;
67 pi_table_bucket_t* bucket;
68 pi_table_t* table;
69
70} pi_table_iter_t;
71
72// -------------------------------------------------------------------------------------------------
73// HASH TABLE PROTOTYPES
74// -------------------------------------------------------------------------------------------------
75
76/**
77 * The default key comparison function.
78 *
79 * @param key1 The first key.
80 * @param key2 The second key.
81 *
82 * @return 1, if the keys match, otherwise 0.
83 */
84unsigned int pi_table_compare (void* key1, void* key2);
85
86/**
87 * Create a new hash table instance.
88 *
89 * @param size The initial bucket count.
90 * @param load_factor The maximum table load before a resize occurs.
91 * @param hash_func The hash function.
92 * @param comp_func The compare function.
93 */
94pi_table_t* pi_table_create (unsigned int size, float load_factor,
95 unsigned int (*hash_func) (void* key),
96 unsigned int (*comp_func) (void* key1, void* key2));
97
98/**
99 * Indicates that a key exists in the table.
100 *
101 * @param table The hash table.
102 * @param key The key.
103 *
104 * @return 1, if the key exists, otherwise 0.
105 */
106unsigned int pi_table_contains (pi_table_t* table, void* key);
107
108/**
109 * Destroy a hash table instance.
110 *
111 * Notes: You cannot delete a hash table that contains key/value pairs.
112 *
113 * @param table The hash table.
114 *
115 * @return 1, if the table was destroyed, otherwise 0.
116 */
117unsigned int pi_table_destroy (pi_table_t* table);
118
119/**
120 * Retrieve a value from the table.
121 *
122 * @param table The table.
123 * @param key The key.
124 *
125 * @return The value, if the key exists, otherwise NULL.
126 */
127void* pi_table_get (pi_table_t* table, void* key);
128
129/**
130 * Insert a key/value pair into the table.
131 *
132 * Notes: You must check pi_table_contains() to verify the key does not exist before-hand,
133 * otherwise a new value will be added with the same key. This would yield uncertain results
134 * when retrieving the value.
135 *
136 * Also, this will store NULL values, but NULL is also returned with pi_table_get() so it's
137 * best to avoid storing NULL when possible.
138 *
139 * @param table The hash table.
140 * @param key The key.
141 * @param value The value.
142 *
143 * @return 1, if the key/value pair were inserted, otherwise 0.
144 */
145unsigned int pi_table_put (pi_table_t* table, void* key, void* value);
146
147/**
148 * Remove a key from the table.
149 *
150 * @param table The hash table.
151 * @param key The key.
152 *
153 * @return The matching value for the key, if the key was removed, otherwise NULL.
154 */
155void* pi_table_remove (pi_table_t* table, void* key);
156
157/**
158 * Force the table to be resized.
159 *
160 * @param table The hash table.
161 *
162 * @return 1, if the table resize succeeded, otherwise 0.
163 */
164unsigned int pi_table_resize (pi_table_t* table);
165
166// -------------------------------------------------------------------------------------------------
167// HASH TABLE ITERATOR PROTOTYPES
168// -------------------------------------------------------------------------------------------------
169
170/**
171 * Create a new hash table iterator instance.
172 *
173 * @param table The hash table.
174 *
175 * @return The new hash table.
176 */
177pi_table_iter_t* pi_table_iter_create (pi_table_t* table);
178
179/**
180 * Destroy a hash table iterator instance.
181 *
182 * @param iter The hash table iterator.
183 *
184 * @return 1, if the hash table iterator was destroyed, otherwise 0.
185 */
186unsigned int pi_table_iter_destroy (pi_table_iter_t* iter);
187
188/**
189 * Advance to the next iterator item.
190 *
191 * Notes: This must be called before the first item can be accessed.
192 *
193 * @param iter The hash table iterator.
194 *
195 * @return 1, if a new item is available, otherwise 0.
196 */
197unsigned int pi_table_iter_next (pi_table_iter_t* iter);
198
199#endif