[mirror_ovs.git] / lib / hindex.h

/*
 * Copyright (c) 2013, 2016 Nicira, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef HINDEX_H
#define HINDEX_H 1

/* Hashed multimap.
 *
 * hindex is a hash table data structure that gracefully handles duplicates.
 * With a high-quality hash function, insertion, deletion, and search are O(1)
 * expected time, regardless of the number of duplicates for a given key.  */

#include <stdbool.h>
#include <stdlib.h>
#include "util.h"

/* A hash index node, to embed inside the data structure being indexed.
 *
 * Nodes are linked together like this (the boxes are labeled with hash
 * values):
 *
 *             +--------+ d   +--------+ d   +--------+ d
 *  bucket---> |    6   |---->|   20   |---->|   15   |---->null
 *             +-|------+     +-|------+     +-|------+
 *               |    ^         |              |    ^
 *              s|    |d        |s            s|    |d
 *               V    |         V              V    |
 *             +------|-+      null          +------|-+
 *             |    6   |                    |   15   |
 *             +-|------+                    +-|------+
 *               |    ^                        |
 *              s|    |d                      s|
 *               V    |                        V
 *             +------|-+                     null
 *             |    6   |
 *             +-|------+
 *               |
 *              s|
 *               V
 *              null
 *
 * The basic usage is:
 *
 *     - To visit the unique hash values in the hindex, follow the 'd'
 *       ("different") pointers starting from each bucket.  The nodes visited
 *       this way are called "head" nodes, because they are at the head of the
 *       vertical chains.
 *
 *     - To visit the nodes with hash value H, follow the 'd' pointers in the
 *       appropriate bucket until you find one with hash H, then follow the 's'
 *       ("same") pointers until you hit a null pointer.  The non-head nodes
 *       visited this way are called "body" nodes.
 *
 *     - The 'd' pointers in body nodes point back to the previous body node
 *       or, for the first body node, to the head node.  (This makes it
 *       possible to remove a body node without traversing all the way downward
 *       from the head).
 */
struct hindex_node {
    /* Hash value. */
    size_t hash;

    /* In a head node, the next head node (with a hash different from this
     * node), or NULL if this is the last node in this bucket.
     *
     * In a body node, the previous head or body node (with the same hash as
     * this node).  Never null. */
    struct hindex_node *d;

    /* In a head or a body node, the next body node with the same hash as this
     * node.  NULL if this is the last node with this hash. */
    struct hindex_node *s;
};

/* A hash index. */
struct hindex {
    struct hindex_node **buckets; /* Must point to 'one' iff 'mask' == 0. */
    struct hindex_node *one;
    size_t mask;      /* 0 or more lowest-order bits set, others cleared. */
    size_t n_unique;  /* Number of unique hashes (the number of head nodes). */
};

/* Initializer for an empty hash index. */
#define HINDEX_INITIALIZER(HINDEX) \
    { (struct hindex_node **const) &(HINDEX)->one, NULL, 0, 0 }

/* Initialization. */
void hindex_init(struct hindex *);
void hindex_destroy(struct hindex *);
void hindex_clear(struct hindex *);
void hindex_swap(struct hindex *a, struct hindex *b);
void hindex_moved(struct hindex *hindex);
static inline bool hindex_is_empty(const struct hindex *);

/* Adjusting capacity. */
void hindex_expand(struct hindex *);
void hindex_shrink(struct hindex *);
void hindex_reserve(struct hindex *, size_t capacity);

/* Insertion and deletion. */
void hindex_insert_fast(struct hindex *, struct hindex_node *, size_t hash);
void hindex_insert(struct hindex *, struct hindex_node *, size_t hash);
void hindex_remove(struct hindex *, struct hindex_node *);

/* Search.
 *
 * HINDEX_FOR_EACH_WITH_HASH iterates NODE over all of the nodes in HINDEX that
 * have hash value equal to HASH.  MEMBER must be the name of the 'struct
 * hindex_node' member within NODE.
 *
 * The loop should not change NODE to point to a different node or insert or
 * delete nodes in HINDEX (unless it "break"s out of the loop to terminate
 * iteration).
 *
 * Evaluates HASH only once.
 */
#define HINDEX_FOR_EACH_WITH_HASH(NODE, MEMBER, HASH, HINDEX)               \
    for (INIT_CONTAINER(NODE, hindex_node_with_hash(HINDEX, HASH), MEMBER); \
         NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER);                     \
         ASSIGN_CONTAINER(NODE, (NODE)->MEMBER.s, MEMBER))

/* Safe when NODE may be freed (not needed when NODE may be removed from the
 * hash map but its members remain accessible and intact). */
#define HINDEX_FOR_EACH_WITH_HASH_SAFE(NODE, NEXT, MEMBER, HASH, HINDEX) \
    for (INIT_CONTAINER(NODE, hindex_node_with_hash(HINDEX, HASH), MEMBER); \
         (NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER)                 \
          ? INIT_CONTAINER(NEXT, (NODE)->MEMBER.s, MEMBER), 1           \
          : 0);                                                         \
         (NODE) = (NEXT))

/* Returns the head node in 'hindex' with the given 'hash', or a null pointer
 * if no nodes have that hash value. */
static inline struct hindex_node *
hindex_node_with_hash(const struct hindex *hindex, size_t hash)
{
    struct hindex_node *node = hindex->buckets[hash & hindex->mask];

    while (node && node->hash != hash) {
        node = node->d;
    }
    return node;
}

/* Iteration. */

/* Iterates through every node in HINDEX. */
#define HINDEX_FOR_EACH(NODE, MEMBER, HINDEX)                           \
    for (INIT_CONTAINER(NODE, hindex_first(HINDEX), MEMBER);            \
         NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER);                 \
         ASSIGN_CONTAINER(NODE, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER))

/* Safe when NODE may be freed (not needed when NODE may be removed from the
 * hash index but its members remain accessible and intact). */
#define HINDEX_FOR_EACH_SAFE(NODE, NEXT, MEMBER, HINDEX)              \
    for (INIT_CONTAINER(NODE, hindex_first(HINDEX), MEMBER);          \
         (NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER)                 \
          ? INIT_CONTAINER(NEXT, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER), 1 \
          : 0);                                                         \
         (NODE) = (NEXT))

struct hindex_node *hindex_first(const struct hindex *);
struct hindex_node *hindex_next(const struct hindex *,
                                const struct hindex_node *);

/* Returns true if 'hindex' currently contains no nodes, false otherwise. */
static inline bool
hindex_is_empty(const struct hindex *hindex)
{
    return hindex->n_unique == 0;
}

#endif /* hindex.h */
Commit	Line	Data
822b7f52	1	/*
fdbdb595	2	* Copyright (c) 2013, 2016 Nicira, Inc.
822b7f52 BP	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) \
f17e8ad6	131	for (INIT_CONTAINER(NODE, hindex_node_with_hash(HINDEX, HASH), MEMBER); \
55d26906	132	NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER); \
822b7f52 BP	133	ASSIGN_CONTAINER(NODE, (NODE)->MEMBER.s, MEMBER))
822b7f52 BP	134
fdbdb595 RM	135	/* Safe when NODE may be freed (not needed when NODE may be removed from the
	136	* hash map but its members remain accessible and intact). */
	137	#define HINDEX_FOR_EACH_WITH_HASH_SAFE(NODE, NEXT, MEMBER, HASH, HINDEX) \
	138	for (INIT_CONTAINER(NODE, hindex_node_with_hash(HINDEX, HASH), MEMBER); \
	139	(NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER) \
	140	? INIT_CONTAINER(NEXT, (NODE)->MEMBER.s, MEMBER), 1 \
	141	: 0); \
	142	(NODE) = (NEXT))
	143
3d91d909 JR	144	/* Returns the head node in 'hindex' with the given 'hash', or a null pointer
	145	* if no nodes have that hash value. */
	146	static inline struct hindex_node *
	147	hindex_node_with_hash(const struct hindex *hindex, size_t hash)
	148	{
	149	struct hindex_node *node = hindex->buckets[hash & hindex->mask];
	150
	151	while (node && node->hash != hash) {
	152	node = node->d;
	153	}
	154	return node;
	155	}
822b7f52 BP	156
	157	/* Iteration. */
	158
	159	/* Iterates through every node in HINDEX. */
	160	#define HINDEX_FOR_EACH(NODE, MEMBER, HINDEX) \
f17e8ad6	161	for (INIT_CONTAINER(NODE, hindex_first(HINDEX), MEMBER); \
55d26906	162	NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER); \
822b7f52 BP	163	ASSIGN_CONTAINER(NODE, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER))
	164
	165	/* Safe when NODE may be freed (not needed when NODE may be removed from the
	166	* hash index but its members remain accessible and intact). */
f17e8ad6 GS	167	#define HINDEX_FOR_EACH_SAFE(NODE, NEXT, MEMBER, HINDEX) \
f17e8ad6 GS	168	for (INIT_CONTAINER(NODE, hindex_first(HINDEX), MEMBER); \
55d26906	169	(NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER) \
f17e8ad6	170	? INIT_CONTAINER(NEXT, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER), 1 \
822b7f52 BP	171	: 0); \
	172	(NODE) = (NEXT))
	173
	174	struct hindex_node hindex_first(const struct hindex );
	175	struct hindex_node hindex_next(const struct hindex ,
	176	const struct hindex_node *);
	177
	178	/* Returns true if 'hindex' currently contains no nodes, false otherwise. */
	179	static inline bool
	180	hindex_is_empty(const struct hindex *hindex)
	181	{
	182	return hindex->n_unique == 0;
	183	}
	184
	185	#endif /* hindex.h */