Annotation of embedaddon/strongswan/src/libstrongswan/collections/hashtable.h, revision 1.1.1.2
1.1 misho 1: /*
1.1.1.2 ! misho 2: * Copyright (C) 2008-2020 Tobias Brunner
1.1 misho 3: * HSR Hochschule fuer Technik Rapperswil
4: *
5: * This program is free software; you can redistribute it and/or modify it
6: * under the terms of the GNU General Public License as published by the
7: * Free Software Foundation; either version 2 of the License, or (at your
8: * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
9: *
10: * This program is distributed in the hope that it will be useful, but
11: * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13: * for more details.
14: */
15:
16: /**
17: * @defgroup hashtable hashtable
18: * @{ @ingroup collections
19: */
20:
21: #ifndef HASHTABLE_H_
22: #define HASHTABLE_H_
23:
24: #include <collections/enumerator.h>
25:
26: typedef struct hashtable_t hashtable_t;
1.1.1.2 ! misho 27: typedef struct hashlist_t hashlist_t;
1.1 misho 28:
29: /**
30: * Prototype for a function that computes the hash code from the given key.
31: *
32: * @param key key to hash
33: * @return hash code
34: */
35: typedef u_int (*hashtable_hash_t)(const void *key);
36:
37: /**
38: * Hashtable hash function calculation the hash solely based on the key pointer.
39: *
40: * @param key key to hash
41: * @return hash of key
42: */
43: u_int hashtable_hash_ptr(const void *key);
44:
45: /**
46: * Hashtable hash function calculation the hash for char* keys.
47: *
48: * @param key key to hash, a char*
49: * @return hash of key
50: */
51: u_int hashtable_hash_str(const void *key);
52:
53: /**
54: * Prototype for a function that compares the two keys for equality.
55: *
1.1.1.2 ! misho 56: * @param key first key (the one we are looking for/inserting)
1.1 misho 57: * @param other_key second key
58: * @return TRUE if the keys are equal
59: */
60: typedef bool (*hashtable_equals_t)(const void *key, const void *other_key);
61:
62: /**
63: * Hashtable equals function comparing pointers.
64: *
65: * @param key key to compare
66: * @param other_key other key to compare
67: * @return TRUE if key == other_key
68: */
69: bool hashtable_equals_ptr(const void *key, const void *other_key);
70:
71: /**
72: * Hashtable equals function comparing char* keys.
73: *
74: * @param key key to compare
75: * @param other_key other key to compare
76: * @return TRUE if streq(key, other_key)
77: */
78: bool hashtable_equals_str(const void *key, const void *other_key);
79:
80: /**
1.1.1.2 ! misho 81: * Prototype for a function that compares the two keys in order to sort them.
! 82: *
! 83: * @param key first key (the one we are looking for/inserting)
! 84: * @param other_key second key
! 85: * @return less than, equal to, or greater than 0 if key is
! 86: * less than, equal to, or greater than other_key
! 87: */
! 88: typedef int (*hashtable_cmp_t)(const void *key, const void *other_key);
! 89:
! 90: /**
1.1 misho 91: * Class implementing a hash table.
92: *
93: * General purpose hash table. This hash table is not synchronized.
1.1.1.2 ! misho 94: *
! 95: * The insertion order is maintained when enumerating entries.
1.1 misho 96: */
97: struct hashtable_t {
98:
99: /**
100: * Create an enumerator over the hash table key/value pairs.
101: *
102: * @return enumerator over (void *key, void *value)
103: */
1.1.1.2 ! misho 104: enumerator_t *(*create_enumerator)(hashtable_t *this);
1.1 misho 105:
106: /**
107: * Adds the given value with the given key to the hash table, if there
108: * exists no entry with that key. NULL is returned in this case.
109: * Otherwise the existing value is replaced and the function returns the
110: * old value.
111: *
112: * @param key the key to store
113: * @param value the value to store
114: * @return NULL if no item was replaced, the old value otherwise
115: */
1.1.1.2 ! misho 116: void *(*put)(hashtable_t *this, const void *key, void *value);
1.1 misho 117:
118: /**
119: * Returns the value with the given key, if the hash table contains such an
120: * entry, otherwise NULL is returned.
121: *
122: * @param key the key of the requested value
123: * @return the value, NULL if not found
124: */
1.1.1.2 ! misho 125: void *(*get)(hashtable_t *this, const void *key);
1.1 misho 126:
127: /**
128: * Removes the value with the given key from the hash table and returns the
129: * removed value (or NULL if no such value existed).
130: *
131: * @param key the key of the value to remove
132: * @return the removed value, NULL if not found
133: */
1.1.1.2 ! misho 134: void *(*remove)(hashtable_t *this, const void *key);
1.1 misho 135:
136: /**
137: * Removes the key and value pair from the hash table at which the given
138: * enumerator currently points.
139: *
140: * @param enumerator enumerator, from create_enumerator
141: */
1.1.1.2 ! misho 142: void (*remove_at)(hashtable_t *this, enumerator_t *enumerator);
1.1 misho 143:
144: /**
145: * Gets the number of items in the hash table.
146: *
147: * @return number of items
148: */
1.1.1.2 ! misho 149: u_int (*get_count)(hashtable_t *this);
1.1 misho 150:
151: /**
152: * Destroys a hash table object.
153: */
1.1.1.2 ! misho 154: void (*destroy)(hashtable_t *this);
1.1 misho 155:
156: /**
157: * Destroys a hash table object and calls the given function for each
158: * item and its key in the hash table.
159: *
160: * @param function function to call on each item and key
161: */
162: void (*destroy_function)(hashtable_t *this,
163: void (*)(void *val, const void *key));
164: };
165:
166: /**
1.1.1.2 ! misho 167: * Class implementing a hash table with ordered keys/items and special query
! 168: * method.
! 169: *
! 170: * @note The ordering only pertains to keys/items in the same bucket (with or
! 171: * without the same hash value), not to the order when enumerating. So unlike
! 172: * hashtable_t this class does not guarantee any specific order when enumerating
! 173: * all entries.
! 174: *
! 175: * This is intended to be used with hash functions that intentionally return the
! 176: * same hash value for different keys so multiple items can be retrieved for a
! 177: * key.
! 178: *
! 179: * It's like storing sorted linked lists in a hash table but with less overhead.
! 180: */
! 181: struct hashlist_t {
! 182:
! 183: /**
! 184: * Implements the hash table interface.
! 185: */
! 186: hashtable_t ht;
! 187:
! 188: /**
! 189: * Returns the first value with a matching key if the hash table contains
! 190: * such an entry, otherwise NULL is returned.
! 191: *
! 192: * Compared to get() the given match function is used to compare the keys
! 193: * for equality. The hash function does have to be devised specially in
! 194: * order to make this work if the match function compares keys differently
! 195: * than the equals/comparison function provided to the constructor.
! 196: *
! 197: * This basically allows to enumerate all entries with the same hash value
! 198: * in their key's order (insertion order, i.e. without comparison function)
! 199: * is only guaranteed for items with the same hash value.
! 200: *
! 201: * @param key the key to match against
! 202: * @param match match function to be used when comparing keys
! 203: * @return the value, NULL if not found
! 204: */
! 205: void *(*get_match)(hashlist_t *this, const void *key,
! 206: hashtable_equals_t match);
! 207:
! 208: /**
! 209: * Destroys a hash list object.
! 210: */
! 211: void (*destroy)(hashlist_t *this);
! 212: };
! 213:
! 214: /**
1.1 misho 215: * Creates an empty hash table object.
216: *
217: * @param hash hash function
218: * @param equals equals function
1.1.1.2 ! misho 219: * @param size initial size
! 220: * @return hashtable_t object
1.1 misho 221: */
222: hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals,
1.1.1.2 ! misho 223: u_int size);
! 224:
! 225: /**
! 226: * Creates an empty hash list object with each bucket's keys in insertion order.
! 227: *
! 228: * @param hash hash function
! 229: * @param equals equals function
! 230: * @param size initial size
! 231: * @return hashtable_t object
! 232: */
! 233: hashlist_t *hashlist_create(hashtable_hash_t hash, hashtable_equals_t equals,
! 234: u_int size);
! 235:
! 236: /**
! 237: * Creates an empty hash list object with sorted keys in each bucket.
! 238: *
! 239: * @param hash hash function
! 240: * @param cmp comparison function
! 241: * @param size initial size
! 242: * @return hashtable_t object.
! 243: */
! 244: hashlist_t *hashlist_create_sorted(hashtable_hash_t hash,
! 245: hashtable_cmp_t cmp, u_int size);
1.1 misho 246:
247: #endif /** HASHTABLE_H_ @}*/
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>