-
Notifications
You must be signed in to change notification settings - Fork 31
/
ohashtbl.h
198 lines (183 loc) · 7.23 KB
/
ohashtbl.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
/*
* _____
* ANSI / ___/
* / /__
* \___/
*
* Filename: ohashtbl.h
* Author : Kyle Loudon/Dan Levin
* Date : Mon Apr 08 12:15:18 2013
* Version : 0.51
* ---
* Description: An open-addressed hashtable implemented as a pure, generic ADT - written in ANSI C
*
* Date Revision message
* 150331 This code ready for version 0.51
*
*/
/**
* @file ohashtbl.h
**/
#ifndef _OHASHTBL_H_
#define _OHASHTBL_H_
#include <stdio.h>
#include <stdlib.h>
#ifdef __cplusplus
extern "C" {
#endif
/**
* Use a @b typedef - to hide the interior of @b OHtbl_ - in the
* implementation file. This is how @a data @a hiding can be done in C.
*
**/
typedef struct OHtbl_ *OHtbl;
/* FUNCTION DECLARATIONS */
/**
* Initialize the open-addressed hash table
*
* @param[in] positions - The number of positions you want the
* table to contain when created.
* @param[in] h1 - A reference to a user-defined hash function.
* This function returns the @a hash @a value of the @a key
* parameter - given to function @b h1() - when called.
* @param[in] h2 - A reference to a user-defined hash function.
* This function returns the @a hash @a value of the @a key
* parameter - given to function @b h2() - when called.
* @param[in] match - A reference to a user-defined @a match
* function. This function shall return 1 - if @a key1 is equal
* to @a key2 - or 0 otherwise.
* @param[in] destroy - A reference to a user-defined function,
* reponsible for freeing @a element @a data, when the table is
* destroyed. If @a destroy is set to NULL - then element data will
* be left untouched upon table destruction.
* @return A reference - to a new, empty table - if dynamic memory
* allocation for the ADT was successful - or NULL otherwise. Take
* really good care of this return value, since it will be needed
* as a parameter in subsequent calls - to the majority of other
* table functions in this function interface - i.e. a sort
* of "handle" to the table.
* @see OHTBLdestroy()
**/
OHtbl OHTBLinit(int positions, int (*h1)(const void *key), int (*h2)(const void *key),
int (*match)(const void *key1, const void *key2), void (*destroy)(void *data));
/**
* Destroy the hash table
*
* The table is destroyed - that is, all memory occupied by
* the elements - will be deallocated. The user-defined callback
* function @a destroy, given as an argument to @b CHTBLinit(), is
* responsible for freeing dynamically allocated element data, when
* this function is called. If @a destroy is set to NULL when
* @b CHTBLinit() is called, all data will be left untouched after
* the table is dismounted and destroyed. When all elements and data
* have been deallocated - the rest of the table is freed, too.
*
* @param[in] htbl - a reference to current table.
* @return Nothing.
* @see OHTBLinit()
**/
void OHTBLdestroy(OHtbl htbl);
/**
* Insert a data element into the table
*
* Inserts an element into the current hash table - referenced by
* the parameter @a htbl. The data to be inserted, is referenced by
* parameter @a data. It is the responsability of the caller to
* ensure, that this memory is valid as long as it is present in the
* table.
*
* @param[in] htbl - a reference to current table.
* @param[in] data - a reference to data to be inserted into
* the table.
* @return Value 0 - if insertion was succesful\n
* Value 1 - if the element is already present in the table\n
* Value -1 - otherwise (implies fatal error).
**/
int OHTBLinsert(OHtbl htbl, const void *data);
/**
* Remove a data element from the table
*
* When called, the 2nd parameter of this function, @a data,
* should reference an (external, user-defined) pointer, that
* points to the search key data.
* After the call - this referenced, external pointer has been
* redirected by this function, to point to the data of the
* removed element - if the call was succesful. The caller is
* responsible for the future of this memory - deallocating it,
* if needed, for example.
* Moreover, a user-defined @b callback @b function, responsible
* for doing the @b matching of element data - and data referenced
* by parameter @a data - must exist for this function to work.
* This user-supplied @b match-callback was set when the hash
* table was initialized - see OHTBLinit().
*
* @param[in] htbl - reference to current table.
* @param[in,out] data - reference to a pointer. After the call,
* this referenced pointer has been redirected to point to
* the data of the removed element - if the call was
* successful. The caller is responsible for the future of
* this memory - deallocating it, for example.
*
* @return Value 0 -- if the call was OK - that is, element
* found and removed.\n
* Value -1 -- node not found.\n
**/
int OHTBLremove(OHtbl htbl, void **data);
/**
* Determine if a data element exists in the table
*
* Determines whether an element, with key data matching
* the data referenced by the parameter @a data - is
* present in the current table @a htbl. This 2nd parameter,
* @a data, should reference an (external, user-defined)
* pointer, that points to the search key data.
* After the call - this referenced, external pointer has been
* redirected by this function, to point to the data of the
* element hit - if the call was succesful.
* Moreover, a user-defined @b callback @b function, responsible
* for doing the @b matching of element data - and data referenced
* by parameter @a data - must exist for this function to work.
* This user-supplied @b match-callback was set when the hash
* table was initialized - see OHTBLinit().
*
* @param[in] htbl - a reference to current table.
* @param[in,out] data - a reference to a pointer, pointing at
* the data to be searched for - at the call. Upon return - this
* pointer has been redirected by this function - and points
* instead to data in the element hit - if any.
*
* @return Value 0 - if element with matching data was found.\n
* Value -1 - otherwise.
*
* @see OHTBLinit()
**/
int OHTBLlookup(const OHtbl htbl, void **data);
/**
* Get the size of the table
*
* @param[in] htbl - a reference to the current table.
*
* @return The size, that is, the number of elements
* in the table.
**/
int OHTBLsize(OHtbl htbl);
/**
* Print all data of the open-addressed hash table -
* on screen
*
* @param[in] htbl - reference to current table.
* @param[in] callback - reference to user-defined callback function,
* that gets @b read @b access to element data via its parameter
* @a data - to do whatever is relevant. In this case it is a matter
* of formatting data for printing on screen. The printed data
* should be kept to a minimum (the key value, for example) in order
* not to clutter the screen. This function is primarily for small
* tables and debugging purposes.
*
* @return - Nothing.
**/
void OHTBLprint(OHtbl htbl, void (*callback)(const void *data));
#ifdef __cplusplus
}
#endif
#endif /* _OHASHTBL_H_ */