tools/cfzy/libconfizery/cfzy_htable.h

   1 /*
   2  * Copyright (c) 2013, Olivier MATZ <zer0@droids-corp.org>
   3  * All rights reserved.
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are met:
   6  *
   7  *     * Redistributions of source code must retain the above copyright
   8  *       notice, this list of conditions and the following disclaimer.
   9  *     * Redistributions in binary form must reproduce the above copyright
  10  *       notice, this list of conditions and the following disclaimer in the
  11  *       documentation and/or other materials provided with the distribution.
  12  *     * Neither the name of the University of California, Berkeley nor the
  13  *       names of its contributors may be used to endorse or promote products
  14  *       derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
  20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #ifndef _CFZY_HTABLE_H_
  29 #define _CFZY_HTABLE_H_
  30
  31 /**
  32  * @file
  33  * Confizery Hash Table
  34  *
  35  * This module is a simple hash table implementation, based on LIST
  36  * from sys/queue.h --see queue(3)-- and with a constant number of
  37  * buckets. It handles the allocation of chaining structure so any
  38  * kind of element can be added/deleted. Each element is referenced by
  39  * a string (key).
  40  */
  41
  42 #include <sys/queue.h>
  43
  44 /* we use a constant size of htable, it simplifies the code and it is
  45  * enough for our purpose */
  46
  47 #define CFZY_HTABLE_ORDER 10
  48 #define CFZY_HTABLE_SIZE  (1 << CFZY_HTABLE_ORDER)
  49 #define CFZY_HTABLE_MASK  (CFZY_HTABLE_SIZE - 1)
  50
  51 /**
  52  * A hash table bucket
  53  */
  54 LIST_HEAD(cfzy_hlist_head, cfzy_hlist_elt);
  55
  56 /**
  57  * A hash table element, used to chain objects together and store the
  58  * name (key). This structure is allocated by cfzy_htable_add().
  59  */
  60 struct cfzy_hlist_elt {
  61         LIST_ENTRY(cfzy_hlist_elt) next;
  62         char *name;
  63         void *ptr;
  64 };
  65
  66 /**
  67  * A hash table structure
  68  */
  69 struct cfzy_htable {
  70         struct cfzy_hlist_head buckets[CFZY_HTABLE_SIZE];
  71 };
  72
  73 /**
  74  * Lookup for an element matching the given key
  75  *
  76  * @param htable
  77  *   Hash table pointer
  78  * @param name
  79  *   String identifying the element (key)
  80  * @return
  81  *   Pointer to the element, or NULL on error
  82  */
  83 void *cfzy_htable_lookup(const struct cfzy_htable *htable, const char *name);
  84
  85
  86 /**
  87  * Add an element in the hash table
  88  *
  89  * Allocate a new cfzy_hlist_elt structure, initialize it to point to
  90  * the given pointer "ptr", then queue the structure in the
  91  * appropriate hash table bucket.
  92  *
  93  * @param htable
  94  *   Hash table pointer
  95  * @param name
  96  *   String identifying the element (key)
  97  * @param ptr
  98  *   Pointer to the element (must not be NULL)
  99  * @return
 100  *   0 on success, -1 on error
 101  */
 102 int cfzy_htable_add(struct cfzy_htable *htable, const char *name,
 103                     void *ptr);
 104
 105 /**
 106  * Remove an element from the hash table
 107  *
 108  * Unchain the structure from the hash table bucket, and free the
 109  * cfzy_hlist_elt structure.
 110  *
 111  * @param htable
 112  *   Hash table pointer
 113  * @param name
 114  *   String identifying the element (key)
 115  * @return
 116  *   0 on success, -1 on error (element not found)
 117  */
 118 int cfzy_htable_del(struct cfzy_htable *htable, const char *name);
 119
 120 /**
 121  * Allocate and initialize a new empty htable
 122  *
 123  * @return
 124  *   Hash table pointer or NULL on error
 125  */
 126 struct cfzy_htable *cfzy_htable_alloc(void);
 127
 128 /**
 129  * Free a htable
 130  *
 131  * Empty the htable, freeing all elements (cfzy_hlist_elt structures,
 132  * and its pointer, using the provided free_fct), then free the
 133  * cfzy_htable.
 134  *
 135  * @param htable
 136  *   Hash table pointer
 137  * @param free_fct
 138  *   Function to free an element
 139  */
 140 void cfzy_htable_free(struct cfzy_htable *htable, void (*free_fct)(void *));
 141
 142 #endif /* _CFZY_HTABLE_H_ */