1/**************************************************************************
2 *
3 * Copyright 2007 VMware, Inc.
4 * All Rights Reserved.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sub license, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
16 * of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 *
26 **************************************************************************/
27
28/**
29 * @file
30 * Hash table implementation.
31 *
32 * This file provides a hash implementation that is capable of dealing
33 * with collisions. It stores colliding entries in linked list. All
34 * functions operating on the hash return an iterator. The iterator
35 * itself points to the collision list. If there wasn't any collision
36 * the list will have just one entry, otherwise client code should
37 * iterate over the entries to find the exact entry among ones that
38 * had the same key (e.g. memcmp could be used on the data to check
39 * that)
40 *
41 * @author Zack Rusin <zackr@vmware.com>
42 */
43
44#ifndef CSO_HASH_H
45#define CSO_HASH_H
46
47#include "pipe/p_compiler.h"
48
49#ifdef __cplusplus
50extern "C" {
51#endif
52
53
54struct cso_node {
55   struct cso_node *next;
56   void *value;
57   unsigned key;
58};
59
60struct cso_hash_iter {
61   struct cso_hash *hash;
62   struct cso_node  *node;
63};
64
65struct cso_hash {
66   struct cso_node *fakeNext;
67   struct cso_node **buckets;
68   struct cso_node *end;
69   int size;
70   short userNumBits;
71   short numBits;
72   int numBuckets;
73};
74
75void cso_hash_init(struct cso_hash *hash);
76void cso_hash_deinit(struct cso_hash *hash);
77
78
79int cso_hash_size(struct cso_hash *hash);
80
81
82/**
83 * Adds a data with the given key to the hash. If entry with the given
84 * key is already in the hash, this current entry is instered before it
85 * in the collision list.
86 * Function returns iterator pointing to the inserted item in the hash.
87 */
88struct cso_hash_iter cso_hash_insert(struct cso_hash *hash, unsigned key,
89                                     void *data);
90/**
91 * Removes the item pointed to by the current iterator from the hash.
92 * Note that the data itself is not erased and if it was a malloc'ed pointer
93 * it will have to be freed after calling this function by the callee.
94 * Function returns iterator pointing to the item after the removed one in
95 * the hash.
96 */
97struct cso_hash_iter cso_hash_erase(struct cso_hash *hash, struct cso_hash_iter iter);
98
99void *cso_hash_take(struct cso_hash *hash, unsigned key);
100
101
102
103struct cso_hash_iter cso_hash_first_node(struct cso_hash *hash);
104
105/**
106 * Returns true if a value with the given key exists in the hash
107 */
108bool cso_hash_contains(struct cso_hash *hash, unsigned key);
109
110
111unsigned cso_hash_iter_key(struct cso_hash_iter iter);
112
113
114/**
115 * Convenience routine to iterate over the collision list while doing a memory
116 * comparison to see which entry in the list is a direct copy of our template
117 * and returns that entry.
118 */
119void *cso_hash_find_data_from_template(struct cso_hash *hash,
120				       unsigned hash_key,
121				       void *templ,
122				       int size);
123
124struct cso_node *cso_hash_data_next(struct cso_node *node);
125
126static inline bool
127cso_hash_iter_is_null(struct cso_hash_iter iter)
128{
129   return !iter.node || iter.node == iter.hash->end;
130}
131
132static inline void *
133cso_hash_iter_data(struct cso_hash_iter iter)
134{
135   if (!iter.node || iter.hash->end == iter.node)
136      return NULL;
137   return iter.node->value;
138}
139
140static inline struct cso_node **
141cso_hash_find_node(struct cso_hash *hash, unsigned akey)
142{
143   struct cso_node **node;
144
145   if (hash->numBuckets) {
146      node = &hash->buckets[akey % hash->numBuckets];
147      assert(*node == hash->end || (*node)->next);
148      while (*node != hash->end && (*node)->key != akey)
149         node = &(*node)->next;
150   } else {
151      node = &hash->end;
152   }
153   return node;
154}
155
156/**
157 * Return an iterator pointing to the first entry in the collision list.
158 */
159static inline struct cso_hash_iter
160cso_hash_find(struct cso_hash *hash, unsigned key)
161{
162   struct cso_node **nextNode = cso_hash_find_node(hash, key);
163   struct cso_hash_iter iter = {hash, *nextNode};
164   return iter;
165}
166
167static inline struct cso_hash_iter
168cso_hash_iter_next(struct cso_hash_iter iter)
169{
170   struct cso_hash_iter next = {iter.hash, cso_hash_data_next(iter.node)};
171   return next;
172}
173
174#ifdef __cplusplus
175}
176#endif
177
178#endif
179