Annotation of embedaddon/libpdel/util/ghash.3, revision 1.1.1.1
1.1 misho 1: .\" Copyright (c) 2001-2002 Packet Design, LLC.
2: .\" All rights reserved.
3: .\"
4: .\" Subject to the following obligations and disclaimer of warranty,
5: .\" use and redistribution of this software, in source or object code
6: .\" forms, with or without modifications are expressly permitted by
7: .\" Packet Design; provided, however, that:
8: .\"
9: .\" (i) Any and all reproductions of the source or object code
10: .\" must include the copyright notice above and the following
11: .\" disclaimer of warranties; and
12: .\" (ii) No rights are granted, in any manner or form, to use
13: .\" Packet Design trademarks, including the mark "PACKET DESIGN"
14: .\" on advertising, endorsements, or otherwise except as such
15: .\" appears in the above copyright notice or in the software.
16: .\"
17: .\" THIS SOFTWARE IS BEING PROVIDED BY PACKET DESIGN "AS IS", AND
18: .\" TO THE MAXIMUM EXTENT PERMITTED BY LAW, PACKET DESIGN MAKES NO
19: .\" REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING
20: .\" THIS SOFTWARE, INCLUDING WITHOUT LIMITATION, ANY AND ALL IMPLIED
21: .\" WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
22: .\" OR NON-INFRINGEMENT. PACKET DESIGN DOES NOT WARRANT, GUARANTEE,
23: .\" OR MAKE ANY REPRESENTATIONS REGARDING THE USE OF, OR THE RESULTS
24: .\" OF THE USE OF THIS SOFTWARE IN TERMS OF ITS CORRECTNESS, ACCURACY,
25: .\" RELIABILITY OR OTHERWISE. IN NO EVENT SHALL PACKET DESIGN BE
26: .\" LIABLE FOR ANY DAMAGES RESULTING FROM OR ARISING OUT OF ANY USE
27: .\" OF THIS SOFTWARE, INCLUDING WITHOUT LIMITATION, ANY DIRECT,
28: .\" INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, PUNITIVE, OR CONSEQUENTIAL
29: .\" DAMAGES, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, LOSS OF
30: .\" USE, DATA OR PROFITS, HOWEVER CAUSED AND UNDER ANY THEORY OF
31: .\" LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32: .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
33: .\" THE USE OF THIS SOFTWARE, EVEN IF PACKET DESIGN IS ADVISED OF
34: .\" THE POSSIBILITY OF SUCH DAMAGE.
35: .\"
36: .\" Author: Archie Cobbs <archie@freebsd.org>
37: .\"
38: .\" $Id: ghash.3,v 1.10 2004/06/02 17:24:38 archie Exp $
39: .\"
40: .Dd April 22, 2002
41: .Dt GHASH 3
42: .Os
43: .Sh NAME
44: .Nm ghash
45: .Nd generic hash table library
46: .Sh LIBRARY
47: PDEL Library (libpdel, \-lpdel)
48: .Sh SYNOPSIS
49: .In sys/types.h
50: .In pdel/util/ghash.h
51: .Ft "struct ghash *"
52: .Fn ghash_create "void *arg" "u_int isize" "u_int maxload" "const char *mtype" "ghash_hash_t *hash" "ghash_equal_t *equal" "ghash_add_t *add" "ghash_del_t *del"
53: .Ft void
54: .Fn ghash_destroy "struct ghash **gp"
55: .Ft void
56: .Fn ghash_arg "struct ghash *g"
57: .Ft "void *"
58: .Fn ghash_get "struct ghash *g" "const void *item"
59: .Ft int
60: .Fn ghash_put "struct ghash *g" "const void *item"
61: .Ft int
62: .Fn ghash_remove "struct ghash *g" "const void *item"
63: .Ft u_int
64: .Fn ghash_size "struct ghash *g"
65: .Ft int
66: .Fn ghash_dump "struct ghash *g" "void ***listp" "const char *mtype"
67: .Ft void
68: .Fn ghash_walk_init "struct ghash *g" "struct ghash_walk *walk"
69: .Ft "void *"
70: .Fn ghash_walk_next "struct ghash *g" "struct ghash_walk *walk"
71: .Ft "struct ghash_iter *"
72: .Fn ghash_iter_create "struct ghash *g"
73: .Ft void
74: .Fn ghash_iter_destroy "struct ghash_iter **iterp"
75: .Ft int
76: .Fn ghash_iter_has_next "struct ghash_iter *iter"
77: .Ft "void *"
78: .Fn ghash_iter_next "struct ghash_iter *iter"
79: .Ft int
80: .Fn ghash_iter_remove "struct ghash_iter *iter"
81: .Sh DESCRIPTION
82: The
83: .Nm ghash
84: functions implement a generic hash table data structure.
85: The hash table stores
86: .Em items
87: of type
88: .Ft "void *" .
89: The user code supplies callback routines for:
90: .Bl -bullet -offset 3n
91: .It
92: Computing the hash value of an item
93: .It
94: Comparing two items for equality
95: .It
96: Housekeeping associated with adding and removing an item
97: .El
98: .Pp
99: .Fn ghash_create
100: creates a new hash table.
101: The
102: .Fa arg
103: parameter can be retrieved at any time via
104: .Fn ghash_arg
105: and is otherwise ignored.
106: The initial size of the hash table (in buckets) is determined by
107: .Fa isize ,
108: or defaults to 31 if
109: .Fa isize
110: is zero.
111: .Fa mtype
112: is a typed memory type string (see
113: .Xr typed_mem 3 )
114: used when allocating memory for the hash table.
115: .Pp
116: .Fa maxload
117: is a maximum load value, measured in percent.
118: If the ratio of the number of items in the hash table to the number
119: of buckets grows larger than this value, the number of buckets is
120: increased.
121: For example, if
122: .Fa maxload
123: is 200, then on average there will never be more than 2 items per bucket.
124: If
125: .Fa maxload
126: is given as zero, the default value of 75% is used.
127: .Pp
128: The
129: .Fa hash ,
130: .Fa equal ,
131: .Fa add ,
132: and
133: .Fa del
134: parameters are pointers to user-supplied callback functions having
135: the following types:
136: .Bd -literal -offset 3n
137: typedef int ghash_equal_t(struct ghash *g,
138: const void *item1, const void *item2);
139: typedef u_int32_t ghash_hash_t(struct ghash *g, const void *item);
140: typedef void ghash_add_t(struct ghash *g, void *item);
141: typedef void ghash_del_t(struct ghash *g, void *item);
142:
143: .Ed
144: The
145: .Fa equal
146: function should return 1 if the items are equal, otherwise 0.
147: The
148: .Fa hash
149: function should return the item's 32-bit hash value.
150: Note that
151: .Fa equal
152: and
153: .Fa hash
154: must be consistent, i.e., two items that are equal must
155: have the same hash value.
156: If
157: .Fa equal
158: and
159: .Fa hash
160: are
161: .Dv NULL ,
162: the item pointers themselves are compared and hashed;
163: in effect, the hash table behaves like a set of pointers.
164: .Pp
165: The
166: .Fa add
167: and
168: .Fa del
169: routines, if not
170: .Dv NULL ,
171: will be called whenever an item is added to, or removed from, the hash table.
172: For example, if
173: .Fn ghash_put
174: causes a new item to replace an old item, there will be a call to the
175: .Fa del
176: function for the old item, followed by a call to the
177: .Fa add
178: function for the new item.
179: These callbacks are typically used to increase and decrease reference counts.
180: .Pp
181: .Fn ghash_destroy
182: destroys a hash table and free's all associated memory.
183: If any items remain in the hash table, the
184: .Fa del
185: callback will be invoked once for each item.
186: Note that this function takes a pointer to a pointer to a hash table.
187: Upon return, the pointer to the hash table will be set to
188: .Dv NULL .
189: If it is already equal to
190: .Dv NULL ,
191: .Fn ghash_destroy
192: does nothing.
193: .Pp
194: .Fn ghash_get
195: retrieves an item previously stored in the hash table, or else returns
196: .Dv NULL
197: if the item is not found.
198: .Pp
199: .Fn ghash_put
200: adds an item to the hash table, replacing any item that is equal to it
201: (as determined by the
202: .Fa equal
203: callback).
204: .Dv NULL
205: is an invalid item and may not be stored in a hash table.
206: .Pp
207: .Fn ghash_remove
208: removes an item from the hash table.
209: If the item does not exist, nothing happens.
210: .Pp
211: .Fn ghash_size
212: returns the number of items in the hash table.
213: .Pp
214: .Fn ghash_dump
215: generates an array of all the items in the hash table.
216: A pointer to the array is stored in
217: .Fa "*listp" .
218: The array is allocated with memory type
219: .Fa mtype .
220: The caller must eventually free the array, also using
221: .Fa mtype .
222: .Pp
223: .Fn ghash_walk_init
224: and
225: .Fn ghash_walk_next
226: are used to traverse all items in the hash table consecutively.
227: First,
228: .Fn ghash_walk_init
229: is called with a pointer to the caller-supplied
230: .Dv "struct ghash_walk" .
231: Then, each invocation of
232: .Fn ghash_walk_next
233: returns the next item in the hash table, or
234: .Dv NULL
235: if no more items remain.
236: .Pp
237: Another way to traverse all hash table elements is using a
238: .Dv "struct ghash_iter" ,
239: which acts as an iterator object.
240: .Fn ghash_iter_create
241: returns such a structure.
242: .Fn ghash_iter_has_next
243: returns non-zero if there are items remaining.
244: Each invocation of
245: .Fn ghash_iter_next
246: returns the next item.
247: .Fn ghash_iter_remove
248: removes item the most recently returned by
249: .Fn ghash_iter_next .
250: .Fn ghash_iter_destroy
251: destroys the iterator.
252: Note: all associated iterators must be destroyed before calling
253: .Fn ghash_destroy .
254: .Sh RETURN VALUES
255: .Fn ghash_put
256: returns 0 if the item is new, or 1 if the item replaced an existing item.
257: .Fn ghash_remove
258: returns 0 if the item was not found, or 1 if the item was found and removed.
259: .Fn ghash_dump
260: returns the number of items in the generated array.
261: .Fn ghash_create ,
262: .Fn ghash_put ,
263: .Fn ghash_dump ,
264: and
265: .Fn ghash_iter_create
266: return -1 or
267: .Dv NULL
268: to indicate an error;
269: .Va errno
270: will be set to the appropriate value.
271: .Sh IMPLEMENTATION NOTES
272: The
273: .Nm ghash
274: library is designed to gracefully handle buggy code.
275: For example, a reentrant call to
276: .Fn ghash_put
277: from within the
278: .Fa add
279: callback function called as a result of a previous call to
280: .Fn ghash_put
281: will return an error with
282: .Va errno
283: set to
284: .Er EBUSY .
285: Similarly, if the hash table is modified in the middle of a traversal,
286: .Fn ghash_walk_next
287: or
288: .Fn ghash_iter_next
289: will return an error.
290: .Sh SEE ALSO
291: .Xr gtree 3 ,
292: .Xr libpdel 3 ,
293: .Xr typed_mem 3
294: .Sh HISTORY
295: The PDEL library was developed at Packet Design, LLC.
296: .Dv "http://www.packetdesign.com/"
297: .Sh AUTHORS
298: .An Archie Cobbs Aq archie@freebsd.org
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ghash.3 CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / libpdel / util