Return to ghash.3 CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / libpdel / util

libpdel

    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.1.1.1 2012/02/21 23:25:53 misho 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