sys/netpfil/ipfw/dn_heap.h

   1 /*-
   2  * Copyright (c) 1998-2010 Luigi Rizzo, Universita` di Pisa
   3  * All rights reserved
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  */
  26
  27 /*
  28  * Binary heap and hash tables, header file
  29  *
  30  * $FreeBSD$
  31  */
  32
  33 #ifndef _IP_DN_HEAP_H
  34 #define _IP_DN_HEAP_H
  35
  36 #define DN_KEY_LT(a,b)     ((int64_t)((a)-(b)) < 0)
  37 #define DN_KEY_LEQ(a,b)    ((int64_t)((a)-(b)) <= 0)
  38
  39 /*
  40  * This module implements a binary heap supporting random extraction.
  41  *
  42  * A heap entry contains an uint64_t key and a pointer to object.
  43  * DN_KEY_LT(a,b) returns true if key 'a' is smaller than 'b'
  44  *
  45  * The heap is a struct dn_heap plus a dynamically allocated
  46  * array of dn_heap_entry entries. 'size' represents the size of
  47  * the array, 'elements' count entries in use. The topmost
  48  * element has the smallest key.
  49  * The heap supports ordered insert, and extract from the top.
  50  * To extract an object from the middle of the heap, we the object
  51  * must reserve an 'int32_t' to store the position of the object
  52  * in the heap itself, and the location of this field must be
  53  * passed as an argument to heap_init() -- use -1 if the feature
  54  * is not used.
  55  */
  56 struct dn_heap_entry {
  57         uint64_t key;   /* sorting key, smallest comes first */
  58         void *object;   /* object pointer */
  59 };
  60
  61 struct dn_heap {
  62         int size;       /* the size of the array */
  63         int elements;   /* elements in use */
  64         int ofs;        /* offset in the object of heap index */
  65         struct dn_heap_entry *p;        /* array of "size" entries */
  66 };
  67
  68 enum {
  69         HEAP_SCAN_DEL = 1,
  70         HEAP_SCAN_END = 2,
  71 };
  72
  73 /*
  74  * heap_init() reinitializes the heap setting the size and the offset
  75  *      of the index for random extraction (use -1 if not used).
  76  *      The 'elements' counter is set to 0.
  77  *
  78  * SET_HEAP_OFS() indicates where, in the object, is stored the index
  79  *      for random extractions from the heap.
  80  *
  81  * heap_free() frees the memory associated to a heap.
  82  *
  83  * heap_insert() adds a key-pointer pair to the heap
  84  *
  85  * HEAP_TOP() returns a pointer to the top element of the heap,
  86  *      but makes no checks on its existance (XXX should we change ?)
  87  *
  88  * heap_extract() removes the entry at the top, returing the pointer.
  89  *      (the key should have been read before).
  90  *
  91  * heap_scan() invokes a callback on each entry of the heap.
  92  *      The callback can return a combination of HEAP_SCAN_DEL and
  93  *      HEAP_SCAN_END. HEAP_SCAN_DEL means the current element must
  94  *      be removed, and HEAP_SCAN_END means to terminate the scan.
  95  *      heap_scan() returns the number of elements removed.
  96  *      Because the order is not guaranteed, we should use heap_scan()
  97  *      only as a last resort mechanism.
  98  */
  99 #define HEAP_TOP(h)     ((h)->p)
 100 #define SET_HEAP_OFS(h, n)      do { (h)->ofs = n; } while (0)
 101 int     heap_init(struct dn_heap *h, int size, int ofs);
 102 int     heap_insert(struct dn_heap *h, uint64_t key1, void *p);
 103 void    heap_extract(struct dn_heap *h, void *obj);
 104 void heap_free(struct dn_heap *h);
 105 int heap_scan(struct dn_heap *, int (*)(void *, uintptr_t), uintptr_t);
 106
 107 /*------------------------------------------------------
 108  * This module implements a generic hash table with support for
 109  * running callbacks on the entire table. To avoid allocating
 110  * memory during hash table operations, objects must reserve
 111  * space for a link field. XXX if the heap is moderately full,
 112  * an SLIST suffices, and we can tolerate the cost of a hash
 113  * computation on each removal.
 114  *
 115  * dn_ht_init() initializes the table, setting the number of
 116  *      buckets, the offset of the link field, the main callbacks.
 117  *      Callbacks are:
 118  *
 119  *      hash(key, flags, arg) called to return a bucket index.
 120  *      match(obj, key, flags, arg) called to determine if key
 121  *              matches the current 'obj' in the heap
 122  *      newh(key, flags, arg) optional, used to allocate a new
 123  *              object during insertions.
 124  *
 125  * dn_ht_free() frees the heap or unlink elements.
 126  *      DNHT_REMOVE unlink elements, 0 frees the heap.
 127  *      You need two calls to do both.
 128  *
 129  * dn_ht_find() is the main lookup function, which can also be
 130  *      used to insert or delete elements in the hash table.
 131  *      The final 'arg' is passed to all callbacks.
 132  *
 133  * dn_ht_scan() is used to invoke a callback on all entries of
 134  *      the heap, or possibly on just one bucket. The callback
 135  *      is invoked with a pointer to the object, and must return
 136  *      one of DNHT_SCAN_DEL or DNHT_SCAN_END to request the
 137  *      removal of the object from the heap and the end of the
 138  *      scan, respectively.
 139  *
 140  * dn_ht_scan_bucket() is similar to dn_ht_scan(), except that it scans
 141  *      only the specific bucket of the table. The bucket is a in-out
 142  *      parameter and return a valid bucket number if the original
 143  *      is invalid.
 144  *
 145  * A combination of flags can be used to modify the operation
 146  * of the dn_ht_find(), and of the callbacks:
 147  *
 148  * DNHT_KEY_IS_OBJ      means the key is the object pointer.
 149  *      It is usally of interest for the hash and match functions.
 150  *
 151  * DNHT_MATCH_PTR       during a lookup, match pointers instead
 152  *      of calling match(). Normally used when removing specific
 153  *      entries. Does not imply KEY_IS_OBJ as the latter _is_ used
 154  *      by the match function.
 155  *
 156  * DNHT_INSERT          insert the element if not found.
 157  *      Calls new() to allocates a new object unless
 158  *      DNHT_KEY_IS_OBJ is set.
 159  *
 160  * DNHT_UNIQUE          only insert if object not found.
 161  *      XXX should it imply DNHT_INSERT ?
 162  *
 163  * DNHT_REMOVE          remove objects if we find them.
 164  */
 165 struct dn_ht;   /* should be opaque */
 166
 167 struct dn_ht *dn_ht_init(struct dn_ht *, int buckets, int ofs,
 168         uint32_t (*hash)(uintptr_t, int, void *),
 169         int (*match)(void *, uintptr_t, int, void *),
 170         void *(*newh)(uintptr_t, int, void *));
 171 void dn_ht_free(struct dn_ht *, int flags);
 172
 173 void *dn_ht_find(struct dn_ht *, uintptr_t, int, void *);
 174 int dn_ht_scan(struct dn_ht *, int (*)(void *, void *), void *);
 175 int dn_ht_scan_bucket(struct dn_ht *, int * , int (*)(void *, void *), void *);
 176 int dn_ht_entries(struct dn_ht *);
 177
 178 enum {  /* flags values.
 179          * first two are returned by the scan callback to indicate
 180          * to delete the matching element or to end the scan
 181          */
 182         DNHT_SCAN_DEL   = 0x0001,
 183         DNHT_SCAN_END   = 0x0002,
 184         DNHT_KEY_IS_OBJ = 0x0004,       /* key is the obj pointer */
 185         DNHT_MATCH_PTR  = 0x0008,       /* match by pointer, not match() */
 186         DNHT_INSERT     = 0x0010,       /* insert if not found */
 187         DNHT_UNIQUE     = 0x0020,       /* report error if already there */
 188         DNHT_REMOVE     = 0x0040,       /* remove on find or dn_ht_free */
 189 };
 190
 191 #endif /* _IP_DN_HEAP_H */