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
|
/*
* The MIT License
*
* Copyright (C) 2010-2016 Alexander Saprykin <saprykin.spb@gmail.com>
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* 'Software'), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
/**
* @file phashtable.h
* @brief Hash table
* @author Alexander Saprykin
*
* A hash table is a data structure used to map keys to values. The hash table
* consists of several internal slots which hold a list of values. A hash
* function is used to compute an index in the array of the slots from a given
* key. The hash function itself is fast and it takes a constant time to compute
* the internal slot index.
*
* When the number of pairs in the hash table is small the lookup and insert
* (remove) operations are very fast and have average complexity O(1), because
* every slot holds almost the only one pair. As the number of internal slots is
* fixed, the increasing number of pairs will lead to degraded performance and
* the average complexity of the operations can drop to O(N) in the worst case.
* This is because the more pairs are inserted the more longer the list of
* values is placed in every slot.
*
* This is a simple hash table implementation which is not intended for heavy
* usage (several thousands), see #PTree if you need the best performance on
* large data sets. This implementation doesn't support multi-inserts when
* several values belong to the same key.
*
* Note that #PHashTable stores keys and values only as pointers, so you need
* to free used memory manually, p_hash_table_free() will not do it in any way.
*
* Integers (up to 32 bits) can be stored in pointers using #P_POINTER_TO_INT
* and #P_INT_TO_POINTER macros.
*/
#if !defined (PLIBSYS_H_INSIDE) && !defined (PLIBSYS_COMPILATION)
# error "Header files shouldn't be included directly, consider using <plibsys.h> instead."
#endif
#ifndef PLIBSYS_HEADER_PHASHTABLE_H
#define PLIBSYS_HEADER_PHASHTABLE_H
#include <pmacros.h>
#include <ptypes.h>
#include <plist.h>
P_BEGIN_DECLS
/** Opaque data structure for a hash table. */
typedef struct PHashTable_ PHashTable;
/**
* @brief Initializes a new hash table.
* @return Pointer to a newly initialized #PHashTable structure in case of
* success, NULL otherwise.
* @since 0.0.1
* @note Free with p_hash_table_free() after usage.
*/
P_LIB_API PHashTable * p_hash_table_new (void);
/**
* @brief Inserts a new key-value pair into a hash table.
* @param table Initialized hash table.
* @param key Key to insert.
* @param value Value to insert.
* @since 0.0.1
*
* This function only stores pointers, so you need to manually free pointed
* data after using the hash table.
*/
P_LIB_API void p_hash_table_insert (PHashTable *table,
ppointer key,
ppointer value);
/**
* @brief Searches for a specifed key in the hash table.
* @param table Hash table to lookup in.
* @param key Key to lookup for.
* @return Value related to its key pair (can be NULL), (#ppointer) -1 if no
* value was found.
* @since 0.0.1
*/
P_LIB_API ppointer p_hash_table_lookup (const PHashTable *table,
pconstpointer key);
/**
* @brief Gives a list of all the stored keys in the hash table.
* @param table Hash table to collect the keys from.
* @return List of all the stored keys, the list can be empty if no keys were
* found.
* @since 0.0.1
* @note You should manually free the returned list with p_list_free() after
* using it.
*/
P_LIB_API PList * p_hash_table_keys (const PHashTable *table);
/**
* @brief Gives a list of all the stored values in the hash table.
* @param table Hash table to collect the values from.
* @return List of all the stored values, the list can be empty if no keys were
* found.
* @since 0.0.1
* @note You should manually free the returned list with p_list_free() after
* using it.
*/
P_LIB_API PList * p_hash_table_values (const PHashTable *table);
/**
* @brief Frees a previously initialized #PHashTable.
* @param table Hash table to free.
* @since 0.0.1
*/
P_LIB_API void p_hash_table_free (PHashTable *table);
/**
* @brief Removes @a key from a hash table.
* @param table Hash table to remove the key from.
* @param key Key to remove (if exists).
* @since 0.0.1
*/
P_LIB_API void p_hash_table_remove (PHashTable *table,
pconstpointer key);
/**
* @brief Searches for a specifed key in the hash table by its value.
* @param table Hash table to lookup in.
* @param val Value to lookup keys for.
* @param func Function to compare table's values with @a val, if NULL then
* values will be compared as pointers.
* @return List of the keys with @a val (can be NULL), NULL if no keys were
* found.
* @since 0.0.1
* @note Caller is responsible to call p_list_free() on the returned list after
* usage.
*
* The compare function should return 0 if a value from the hash table (the
* first parameter) is accepted related to the given lookup value (the second
* parameter), and -1 or 1 otherwise.
*/
P_LIB_API PList * p_hash_table_lookup_by_value (const PHashTable *table,
pconstpointer val,
PCompareFunc func);
P_END_DECLS
#endif /* PLIBSYS_HEADER_PHASHTABLE_H */
|
