Annotation of embedaddon/libpdel/util/ghash.3, revision 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