ia64/xen-unstable

view tools/vtpm_manager/util/hashtable.h @ 6946:e703abaf6e3d

Add behaviour to the remove methods to remove the transaction's path itself. This allows us to write Remove(path) to remove the specified path rather than having to slice the path ourselves.
author emellor@ewan
date Sun Sep 18 14:42:13 2005 +0100 (2005-09-18)
parents 3233e7ecfa9f
children 06d84bf87159
line source
1 /*
2 * Copyright (c) 2005, Intel Corp
3 * Copyright (c) 2002, Christopher Clark <firstname.lastname@cl.cam.ac.uk>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * * Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * * Neither the name of the original author; nor the names of any contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
25 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
26 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
27 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
28 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
29 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
30 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
31 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
32 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 */
36 #ifndef __HASHTABLE_CWC22_H__
37 #define __HASHTABLE_CWC22_H__
39 struct hashtable;
41 /* Example of use:
42 *
43 * struct hashtable *h;
44 * struct some_key *k;
45 * struct some_value *v;
46 *
47 * static unsigned int hash_from_key_fn( void *k );
48 * static int keys_equal_fn ( void *key1, void *key2 );
49 *
50 * h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
51 * k = (struct some_key *) malloc(sizeof(struct some_key));
52 * v = (struct some_value *) malloc(sizeof(struct some_value));
53 *
54 * (initialise k and v to suitable values)
55 *
56 * if (! hashtable_insert(h,k,v) )
57 * { exit(-1); }
58 *
59 * if (NULL == (found = hashtable_search(h,k) ))
60 * { printf("not found!"); }
61 *
62 * if (NULL == (found = hashtable_remove(h,k) ))
63 * { printf("Not found\n"); }
64 *
65 */
67 /* Macros may be used to define type-safe(r) hashtable access functions, with
68 * methods specialized to take known key and value types as parameters.
69 *
70 * Example:
71 *
72 * Insert this at the start of your file:
73 *
74 * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
75 * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
76 * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
77 *
78 * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
79 * These operate just like hashtable_insert etc., with the same parameters,
80 * but their function signatures have 'struct some_key *' rather than
81 * 'void *', and hence can generate compile time errors if your program is
82 * supplying incorrect data as a key (and similarly for value).
83 *
84 * Note that the hash and key equality functions passed to create_hashtable
85 * still take 'void *' parameters instead of 'some key *'. This shouldn't be
86 * a difficult issue as they're only defined and passed once, and the other
87 * functions will ensure that only valid keys are supplied to them.
88 *
89 * The cost for this checking is increased code size and runtime overhead
90 * - if performance is important, it may be worth switching back to the
91 * unsafe methods once your program has been debugged with the safe methods.
92 * This just requires switching to some simple alternative defines - eg:
93 * #define insert_some hashtable_insert
94 *
95 */
97 /*****************************************************************************
98 * create_hashtable
100 * @name create_hashtable
101 * @param minsize minimum initial size of hashtable
102 * @param hashfunction function for hashing keys
103 * @param key_eq_fn function for determining key equality
104 * @return newly created hashtable or NULL on failure
105 */
107 struct hashtable *
108 create_hashtable(unsigned int minsize,
109 unsigned int (*hashfunction) (void*),
110 int (*key_eq_fn) (void*,void*));
112 /*****************************************************************************
113 * hashtable_insert
115 * @name hashtable_insert
116 * @param h the hashtable to insert into
117 * @param k the key - hashtable claims ownership and will free on removal
118 * @param v the value - does not claim ownership
119 * @return non-zero for successful insertion
120 *
121 * This function will cause the table to expand if the insertion would take
122 * the ratio of entries to table size over the maximum load factor.
123 *
124 * This function does not check for repeated insertions with a duplicate key.
125 * The value returned when using a duplicate key is undefined -- when
126 * the hashtable changes size, the order of retrieval of duplicate key
127 * entries is reversed.
128 * If in doubt, remove before insert.
129 */
131 int
132 hashtable_insert(struct hashtable *h, void *k, void *v);
134 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
135 int fnname (struct hashtable *h, keytype *k, valuetype *v) \
136 { \
137 return hashtable_insert(h,k,v); \
138 }
140 /*****************************************************************************
141 * hashtable_search
143 * @name hashtable_search
144 * @param h the hashtable to search
145 * @param k the key to search for - does not claim ownership
146 * @return the value associated with the key, or NULL if none found
147 */
149 void *
150 hashtable_search(struct hashtable *h, void *k);
152 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
153 valuetype * fnname (struct hashtable *h, keytype *k) \
154 { \
155 return (valuetype *) (hashtable_search(h,k)); \
156 }
158 /*****************************************************************************
159 * hashtable_remove
161 * @name hashtable_remove
162 * @param h the hashtable to remove the item from
163 * @param k the key to search for - does not claim ownership
164 * @return the value associated with the key, or NULL if none found
165 */
167 void * /* returns value */
168 hashtable_remove(struct hashtable *h, void *k);
170 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
171 valuetype * fnname (struct hashtable *h, keytype *k) \
172 { \
173 return (valuetype *) (hashtable_remove(h,k)); \
174 }
177 /*****************************************************************************
178 * hashtable_count
180 * @name hashtable_count
181 * @param h the hashtable
182 * @return the number of items stored in the hashtable
183 */
184 unsigned int
185 hashtable_count(struct hashtable *h);
188 /*****************************************************************************
189 * hashtable_destroy
191 * @name hashtable_destroy
192 * @param h the hashtable
193 * @param free_values whether to call 'free' on the remaining values
194 */
196 void
197 hashtable_destroy(struct hashtable *h, int free_values);
199 #endif /* __HASHTABLE_CWC22_H__ */