← Back to branch summary

~mmach/netext73/mesa-haswell

« back to all changes in this revision

Viewing changes to src/util/set.h

  • Committer: mmach
  • Date: 2022-09-22 19:56:13 UTC
  • Revision ID: netbit73@gmail.com-20220922195613-wtik9mmy20tmor0i
2022-09-22 21:17:09

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/util/set.h
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_entry *
118
 
_mesa_set_random_entry(struct set *set,
119
 
                       int (*predicate)(struct set_entry *entry));
120
 
 
121
 
struct set *
122
 
_mesa_pointer_set_create(void *mem_ctx);
123
 
 
124
 
bool
125
 
_mesa_set_intersects(struct set *a, struct set *b);
126
 
 
127
 
/**
128
 
 * This foreach function is safe against deletion, but not against
129
 
 * insertion (which may rehash the set, making entry a dangling
130
 
 * pointer).
131
 
 */
132
 
#define set_foreach(set, entry)                                     \
133
 
   for (struct set_entry *entry = _mesa_set_next_entry(set, NULL);  \
134
 
        entry != NULL;                                              \
135
 
        entry = _mesa_set_next_entry(set, entry))
136
 
 
137
 
/**
138
 
 * This foreach function destroys the table as it iterates.
139
 
 * It is not safe to use when inserting or removing entries.
140
 
 */
141
 
#define set_foreach_remove(set, entry)                              \
142
 
   for (struct set_entry *entry = _mesa_set_next_entry_unsafe(set, NULL);  \
143
 
        (set)->entries;                                              \
144
 
        entry->hash = 0, entry->key = (void*)NULL, (set)->entries--, entry = _mesa_set_next_entry_unsafe(set, entry))
145
 
 
146
 
#ifdef __cplusplus
147
 
} /* extern C */
148
 
#endif
149
 
 
150
 
#endif /* _SET_H */