lib/hindex.h

   1 /*
   2  * Copyright (c) 2013 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef HINDEX_H
  18 #define HINDEX_H 1
  19
  20 /* Hashed multimap.
  21  *
  22  * hindex is a hash table data structure that gracefully handles duplicates.
  23  * With a high-quality hash function, insertion, deletion, and search are O(1)
  24  * expected time, regardless of the number of duplicates for a given key.  */
  25
  26 #include <stdbool.h>
  27 #include <stdlib.h>
  28 #include "util.h"
  29
  30 /* A hash index node, to embed inside the data structure being indexed.
  31  *
  32  * Nodes are linked together like this (the boxes are labeled with hash
  33  * values):
  34  *
  35  *             +--------+ d   +--------+ d   +--------+ d
  36  *  bucket---> |    6   |---->|   20   |---->|   15   |---->null
  37  *             +-|------+     +-|------+     +-|------+
  38  *               |    ^         |              |    ^
  39  *              s|    |d        |s            s|    |d
  40  *               V    |         V              V    |
  41  *             +------|-+      null          +------|-+
  42  *             |    6   |                    |   15   |
  43  *             +-|------+                    +-|------+
  44  *               |    ^                        |
  45  *              s|    |d                      s|
  46  *               V    |                        V
  47  *             +------|-+                     null
  48  *             |    6   |
  49  *             +-|------+
  50  *               |
  51  *              s|
  52  *               V
  53  *              null
  54  *
  55  * The basic usage is:
  56  *
  57  *     - To visit the unique hash values in the hindex, follow the 'd'
  58  *       ("different") pointers starting from each bucket.  The nodes visited
  59  *       this way are called "head" nodes, because they are at the head of the
  60  *       vertical chains.
  61  *
  62  *     - To visit the nodes with hash value H, follow the 'd' pointers in the
  63  *       appropriate bucket until you find one with hash H, then follow the 's'
  64  *       ("same") pointers until you hit a null pointer.  The non-head nodes
  65  *       visited this way are called "body" nodes.
  66  *
  67  *     - The 'd' pointers in body nodes point back to the previous body node
  68  *       or, for the first body node, to the head node.  (This makes it
  69  *       possible to remove a body node without traversing all the way downward
  70  *       from the head).
  71  */
  72 struct hindex_node {
  73     /* Hash value. */
  74     size_t hash;
  75
  76     /* In a head node, the next head node (with a hash different from this
  77      * node), or NULL if this is the last node in this bucket.
  78      *
  79      * In a body node, the previous head or body node (with the same hash as
  80      * this node).  Never null. */
  81     struct hindex_node *d;
  82
  83     /* In a head or a body node, the next body node with the same hash as this
  84      * node.  NULL if this is the last node with this hash. */
  85     struct hindex_node *s;
  86 };
  87
  88 /* A hash index. */
  89 struct hindex {
  90     struct hindex_node **buckets; /* Must point to 'one' iff 'mask' == 0. */
  91     struct hindex_node *one;
  92     size_t mask;      /* 0 or more lowest-order bits set, others cleared. */
  93     size_t n_unique;  /* Number of unique hashes (the number of head nodes). */
  94 };
  95
  96 /* Initializer for an empty hash index. */
  97 #define HINDEX_INITIALIZER(HINDEX) \
  98     { (struct hindex_node **const) &(HINDEX)->one, NULL, 0, 0 }
  99
 100 /* Initialization. */
 101 void hindex_init(struct hindex *);
 102 void hindex_destroy(struct hindex *);
 103 void hindex_clear(struct hindex *);
 104 void hindex_swap(struct hindex *a, struct hindex *b);
 105 void hindex_moved(struct hindex *hindex);
 106 static inline bool hindex_is_empty(const struct hindex *);
 107
 108 /* Adjusting capacity. */
 109 void hindex_expand(struct hindex *);
 110 void hindex_shrink(struct hindex *);
 111 void hindex_reserve(struct hindex *, size_t capacity);
 112
 113 /* Insertion and deletion. */
 114 void hindex_insert_fast(struct hindex *, struct hindex_node *, size_t hash);
 115 void hindex_insert(struct hindex *, struct hindex_node *, size_t hash);
 116 void hindex_remove(struct hindex *, struct hindex_node *);
 117
 118 /* Search.
 119  *
 120  * HINDEX_FOR_EACH_WITH_HASH iterates NODE over all of the nodes in HINDEX that
 121  * have hash value equal to HASH.  MEMBER must be the name of the 'struct
 122  * hindex_node' member within NODE.
 123  *
 124  * The loop should not change NODE to point to a different node or insert or
 125  * delete nodes in HINDEX (unless it "break"s out of the loop to terminate
 126  * iteration).
 127  *
 128  * Evaluates HASH only once.
 129  */
 130 #define HINDEX_FOR_EACH_WITH_HASH(NODE, MEMBER, HASH, HINDEX)               \
 131     for (ASSIGN_CONTAINER(NODE, hindex_node_with_hash(HINDEX, HASH), MEMBER); \
 132          NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER);                     \
 133          ASSIGN_CONTAINER(NODE, (NODE)->MEMBER.s, MEMBER))
 134
 135 /* Returns the head node in 'hindex' with the given 'hash', or a null pointer
 136  * if no nodes have that hash value. */
 137 static inline struct hindex_node *
 138 hindex_node_with_hash(const struct hindex *hindex, size_t hash)
 139 {
 140     struct hindex_node *node = hindex->buckets[hash & hindex->mask];
 141
 142     while (node && node->hash != hash) {
 143         node = node->d;
 144     }
 145     return node;
 146 }
 147
 148 /* Iteration. */
 149
 150 /* Iterates through every node in HINDEX. */
 151 #define HINDEX_FOR_EACH(NODE, MEMBER, HINDEX)                           \
 152     for (ASSIGN_CONTAINER(NODE, hindex_first(HINDEX), MEMBER);          \
 153          NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER);                 \
 154          ASSIGN_CONTAINER(NODE, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER))
 155
 156 /* Safe when NODE may be freed (not needed when NODE may be removed from the
 157  * hash index but its members remain accessible and intact). */
 158 #define HINDEX_FOR_EACH_SAFE(NODE, NEXT, MEMBER, HINDEX)                \
 159     for (ASSIGN_CONTAINER(NODE, hindex_first(HINDEX), MEMBER);          \
 160          (NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER)                 \
 161           ? ASSIGN_CONTAINER(NEXT, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER), 1 \
 162           : 0);                                                         \
 163          (NODE) = (NEXT))
 164
 165 struct hindex_node *hindex_first(const struct hindex *);
 166 struct hindex_node *hindex_next(const struct hindex *,
 167                                 const struct hindex_node *);
 168
 169 /* Returns true if 'hindex' currently contains no nodes, false otherwise. */
 170 static inline bool
 171 hindex_is_empty(const struct hindex *hindex)
 172 {
 173     return hindex->n_unique == 0;
 174 }
 175
 176 #endif /* hindex.h */