1 /*
2  * Copyright © 2009-2012 Intel Corporation
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a
5  * copy of this software and associated documentation files (the "Software"),
6  * to deal in the Software without restriction, including without limitation
7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8  * and/or sell copies of the Software, and to permit persons to whom the
9  * Software is furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice (including the next
12  * paragraph) shall be included in all copies or substantial portions of the
13  * Software.
14  *
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21  * IN THE SOFTWARE.
22  *
23  * Authors:
24  *    Eric Anholt <eric@anholt.net>
25  *
26  */
27 
28 #ifndef _SET_H
29 #define _SET_H
30 
31 #include <inttypes.h>
32 #include <stdbool.h>
33 
34 #ifdef __cplusplus
35 extern "C" {
36 #endif
37 
38 struct set_entry {
39    uint32_t hash;
40    const void *key;
41 };
42 
43 struct set {
44    void *mem_ctx;
45    struct set_entry *table;
46    uint32_t (*key_hash_function)(const void *key);
47    bool (*key_equals_function)(const void *a, const void *b);
48    uint32_t size;
49    uint32_t rehash;
50    uint64_t size_magic;
51    uint64_t rehash_magic;
52    uint32_t max_entries;
53    uint32_t size_index;
54    uint32_t entries;
55    uint32_t deleted_entries;
56 };
57 
58 bool
59 _mesa_set_init(struct set *ht, void *mem_ctx,
60                  uint32_t (*key_hash_function)(const void *key),
61                  bool (*key_equals_function)(const void *a,
62                                              const void *b));
63 
64 struct set *
65 _mesa_set_create(void *mem_ctx,
66                  uint32_t (*key_hash_function)(const void *key),
67                  bool (*key_equals_function)(const void *a,
68                                              const void *b));
69 struct set *
70 _mesa_set_create_u32_keys(void *mem_ctx);
71 
72 struct set *
73 _mesa_set_clone(struct set *set, void *dst_mem_ctx);
74 
75 void
76 _mesa_set_destroy(struct set *set,
77                   void (*delete_function)(struct set_entry *entry));
78 void
79 _mesa_set_resize(struct set *set, uint32_t entries);
80 void
81 _mesa_set_clear(struct set *set,
82                 void (*delete_function)(struct set_entry *entry));
83 
84 struct set_entry *
85 _mesa_set_add(struct set *set, const void *key);
86 struct set_entry *
87 _mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key);
88 
89 struct set_entry *
90 _mesa_set_search_or_add(struct set *set, const void *key, bool *found);
91 struct set_entry *
92 _mesa_set_search_or_add_pre_hashed(struct set *set, uint32_t hash,
93                                    const void *key, bool *found);
94 
95 struct set_entry *
96 _mesa_set_search(const struct set *set, const void *key);
97 struct set_entry *
98 _mesa_set_search_pre_hashed(const struct set *set, uint32_t hash,
99                             const void *key);
100 
101 struct set_entry *
102 _mesa_set_search_and_add(struct set *set, const void *key, bool *replaced);
103 struct set_entry *
104 _mesa_set_search_and_add_pre_hashed(struct set *set, uint32_t hash,
105                                     const void *key, bool *replaced);
106 
107 void
108 _mesa_set_remove(struct set *set, struct set_entry *entry);
109 void
110 _mesa_set_remove_key(struct set *set, const void *key);
111 
112 struct set_entry *
113 _mesa_set_next_entry(const struct set *set, struct set_entry *entry);
114 struct set_entry *
115 _mesa_set_next_entry_unsafe(const struct set *set, struct set_entry *entry);
116 
117 struct set *
118 _mesa_pointer_set_create(void *mem_ctx);
119 
120 bool
121 _mesa_set_intersects(struct set *a, struct set *b);
122 
123 /**
124  * This foreach function is safe against deletion, but not against
125  * insertion (which may rehash the set, making entry a dangling
126  * pointer).
127  */
128 #define set_foreach(set, entry)                                     \
129    for (struct set_entry *entry = _mesa_set_next_entry(set, NULL);  \
130         entry != NULL;                                              \
131         entry = _mesa_set_next_entry(set, entry))
132 
133 /**
134  * This foreach function destroys the table as it iterates.
135  * It is not safe to use when inserting or removing entries.
136  */
137 #define set_foreach_remove(set, entry)                              \
138    for (struct set_entry *entry = _mesa_set_next_entry_unsafe(set, NULL);  \
139         (set)->entries;                                              \
140         entry->hash = 0, entry->key = (void*)NULL, (set)->entries--, entry = _mesa_set_next_entry_unsafe(set, entry))
141 
142 #ifdef __cplusplus
143 } /* extern C */
144 #endif
145 
146 #endif /* _SET_H */
147