← Back to branch summary

~mmach/netext73/mesa-haswell

« back to all changes in this revision

Viewing changes to src/util/set.c

  • 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.c
1
 
/*
2
 
 * Copyright © 2009-2012 Intel Corporation
3
 
 * Copyright © 1988-2004 Keith Packard and Bart Massey.
4
 
 *
5
 
 * Permission is hereby granted, free of charge, to any person obtaining a
6
 
 * copy of this software and associated documentation files (the "Software"),
7
 
 * to deal in the Software without restriction, including without limitation
8
 
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9
 
 * and/or sell copies of the Software, and to permit persons to whom the
10
 
 * Software is furnished to do so, subject to the following conditions:
11
 
 *
12
 
 * The above copyright notice and this permission notice (including the next
13
 
 * paragraph) shall be included in all copies or substantial portions of the
14
 
 * Software.
15
 
 *
16
 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17
 
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18
 
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
19
 
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20
 
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21
 
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22
 
 * IN THE SOFTWARE.
23
 
 *
24
 
 * Except as contained in this notice, the names of the authors
25
 
 * or their institutions shall not be used in advertising or
26
 
 * otherwise to promote the sale, use or other dealings in this
27
 
 * Software without prior written authorization from the
28
 
 * authors.
29
 
 *
30
 
 * Authors:
31
 
 *    Eric Anholt <eric@anholt.net>
32
 
 *    Keith Packard <keithp@keithp.com>
33
 
 */
34
 
 
35
 
#include <stdlib.h>
36
 
#include <assert.h>
37
 
#include <string.h>
38
 
 
39
 
#include "hash_table.h"
40
 
#include "macros.h"
41
 
#include "ralloc.h"
42
 
#include "set.h"
43
 
#include "fast_urem_by_const.h"
44
 
 
45
 
/*
46
 
 * From Knuth -- a good choice for hash/rehash values is p, p-2 where
47
 
 * p and p-2 are both prime.  These tables are sized to have an extra 10%
48
 
 * free to avoid exponential performance degradation as the hash table fills
49
 
 */
50
 
 
51
 
static const uint32_t deleted_key_value;
52
 
static const void *deleted_key = &deleted_key_value;
53
 
 
54
 
static const struct {
55
 
   uint32_t max_entries, size, rehash;
56
 
   uint64_t size_magic, rehash_magic;
57
 
} hash_sizes[] = {
58
 
#define ENTRY(max_entries, size, rehash) \
59
 
   { max_entries, size, rehash, \
60
 
      REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) }
61
 
 
62
 
   ENTRY(2,            5,            3            ),
63
 
   ENTRY(4,            7,            5            ),
64
 
   ENTRY(8,            13,           11           ),
65
 
   ENTRY(16,           19,           17           ),
66
 
   ENTRY(32,           43,           41           ),
67
 
   ENTRY(64,           73,           71           ),
68
 
   ENTRY(128,          151,          149          ),
69
 
   ENTRY(256,          283,          281          ),
70
 
   ENTRY(512,          571,          569          ),
71
 
   ENTRY(1024,         1153,         1151         ),
72
 
   ENTRY(2048,         2269,         2267         ),
73
 
   ENTRY(4096,         4519,         4517         ),
74
 
   ENTRY(8192,         9013,         9011         ),
75
 
   ENTRY(16384,        18043,        18041        ),
76
 
   ENTRY(32768,        36109,        36107        ),
77
 
   ENTRY(65536,        72091,        72089        ),
78
 
   ENTRY(131072,       144409,       144407       ),
79
 
   ENTRY(262144,       288361,       288359       ),
80
 
   ENTRY(524288,       576883,       576881       ),
81
 
   ENTRY(1048576,      1153459,      1153457      ),
82
 
   ENTRY(2097152,      2307163,      2307161      ),
83
 
   ENTRY(4194304,      4613893,      4613891      ),
84
 
   ENTRY(8388608,      9227641,      9227639      ),
85
 
   ENTRY(16777216,     18455029,     18455027     ),
86
 
   ENTRY(33554432,     36911011,     36911009     ),
87
 
   ENTRY(67108864,     73819861,     73819859     ),
88
 
   ENTRY(134217728,    147639589,    147639587    ),
89
 
   ENTRY(268435456,    295279081,    295279079    ),
90
 
   ENTRY(536870912,    590559793,    590559791    ),
91
 
   ENTRY(1073741824,   1181116273,   1181116271   ),
92
 
   ENTRY(2147483648ul, 2362232233ul, 2362232231ul )
93
 
};
94
 
 
95
 
ASSERTED static inline bool
96
 
key_pointer_is_reserved(const void *key)
97
 
{
98
 
   return key == NULL || key == deleted_key;
99
 
}
100
 
 
101
 
static int
102
 
entry_is_free(struct set_entry *entry)
103
 
{
104
 
   return entry->key == NULL;
105
 
}
106
 
 
107
 
static int
108
 
entry_is_deleted(struct set_entry *entry)
109
 
{
110
 
   return entry->key == deleted_key;
111
 
}
112
 
 
113
 
static int
114
 
entry_is_present(struct set_entry *entry)
115
 
{
116
 
   return entry->key != NULL && entry->key != deleted_key;
117
 
}
118
 
 
119
 
bool
120
 
_mesa_set_init(struct set *ht, void *mem_ctx,
121
 
                 uint32_t (*key_hash_function)(const void *key),
122
 
                 bool (*key_equals_function)(const void *a,
123
 
                                             const void *b))
124
 
{
125
 
   ht->size_index = 0;
126
 
   ht->size = hash_sizes[ht->size_index].size;
127
 
   ht->rehash = hash_sizes[ht->size_index].rehash;
128
 
   ht->size_magic = hash_sizes[ht->size_index].size_magic;
129
 
   ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
130
 
   ht->max_entries = hash_sizes[ht->size_index].max_entries;
131
 
   ht->key_hash_function = key_hash_function;
132
 
   ht->key_equals_function = key_equals_function;
133
 
   ht->table = rzalloc_array(mem_ctx, struct set_entry, ht->size);
134
 
   ht->entries = 0;
135
 
   ht->deleted_entries = 0;
136
 
 
137
 
   return ht->table != NULL;
138
 
}
139
 
 
140
 
struct set *
141
 
_mesa_set_create(void *mem_ctx,
142
 
                 uint32_t (*key_hash_function)(const void *key),
143
 
                 bool (*key_equals_function)(const void *a,
144
 
                                             const void *b))
145
 
{
146
 
   struct set *ht;
147
 
 
148
 
   ht = ralloc(mem_ctx, struct set);
149
 
   if (ht == NULL)
150
 
      return NULL;
151
 
 
152
 
   if (!_mesa_set_init(ht, ht, key_hash_function, key_equals_function)) {
153
 
      ralloc_free(ht);
154
 
      return NULL;
155
 
   }
156
 
 
157
 
   return ht;
158
 
}
159
 
 
160
 
static uint32_t
161
 
key_u32_hash(const void *key)
162
 
{
163
 
   uint32_t u = (uint32_t)(uintptr_t)key;
164
 
   return _mesa_hash_uint(&u);
165
 
}
166
 
 
167
 
static bool
168
 
key_u32_equals(const void *a, const void *b)
169
 
{
170
 
   return (uint32_t)(uintptr_t)a == (uint32_t)(uintptr_t)b;
171
 
}
172
 
 
173
 
/* key == 0 and key == deleted_key are not allowed */
174
 
struct set *
175
 
_mesa_set_create_u32_keys(void *mem_ctx)
176
 
{
177
 
   return _mesa_set_create(mem_ctx, key_u32_hash, key_u32_equals);
178
 
}
179
 
 
180
 
struct set *
181
 
_mesa_set_clone(struct set *set, void *dst_mem_ctx)
182
 
{
183
 
   struct set *clone;
184
 
 
185
 
   clone = ralloc(dst_mem_ctx, struct set);
186
 
   if (clone == NULL)
187
 
      return NULL;
188
 
 
189
 
   memcpy(clone, set, sizeof(struct set));
190
 
 
191
 
   clone->table = ralloc_array(clone, struct set_entry, clone->size);
192
 
   if (clone->table == NULL) {
193
 
      ralloc_free(clone);
194
 
      return NULL;
195
 
   }
196
 
 
197
 
   memcpy(clone->table, set->table, clone->size * sizeof(struct set_entry));
198
 
 
199
 
   return clone;
200
 
}
201
 
 
202
 
/**
203
 
 * Frees the given set.
204
 
 *
205
 
 * If delete_function is passed, it gets called on each entry present before
206
 
 * freeing.
207
 
 */
208
 
void
209
 
_mesa_set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entry))
210
 
{
211
 
   if (!ht)
212
 
      return;
213
 
 
214
 
   if (delete_function) {
215
 
      set_foreach (ht, entry) {
216
 
         delete_function(entry);
217
 
      }
218
 
   }
219
 
   ralloc_free(ht->table);
220
 
   ralloc_free(ht);
221
 
}
222
 
 
223
 
 
224
 
static void
225
 
set_clear_fast(struct set *ht)
226
 
{
227
 
   memset(ht->table, 0, sizeof(struct set_entry) * hash_sizes[ht->size_index].size);
228
 
   ht->entries = ht->deleted_entries = 0;
229
 
}
230
 
 
231
 
/**
232
 
 * Clears all values from the given set.
233
 
 *
234
 
 * If delete_function is passed, it gets called on each entry present before
235
 
 * the set is cleared.
236
 
 */
237
 
void
238
 
_mesa_set_clear(struct set *set, void (*delete_function)(struct set_entry *entry))
239
 
{
240
 
   if (!set)
241
 
      return;
242
 
 
243
 
   struct set_entry *entry;
244
 
 
245
 
   if (delete_function) {
246
 
      for (entry = set->table; entry != set->table + set->size; entry++) {
247
 
         if (entry_is_present(entry))
248
 
            delete_function(entry);
249
 
 
250
 
         entry->key = NULL;
251
 
      }
252
 
      set->entries = 0;
253
 
      set->deleted_entries = 0;
254
 
   } else
255
 
      set_clear_fast(set);
256
 
}
257
 
 
258
 
/**
259
 
 * Finds a set entry with the given key and hash of that key.
260
 
 *
261
 
 * Returns NULL if no entry is found.
262
 
 */
263
 
static struct set_entry *
264
 
set_search(const struct set *ht, uint32_t hash, const void *key)
265
 
{
266
 
   assert(!key_pointer_is_reserved(key));
267
 
 
268
 
   uint32_t size = ht->size;
269
 
   uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
270
 
   uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
271
 
                                           ht->rehash_magic) + 1;
272
 
   uint32_t hash_address = start_address;
273
 
   do {
274
 
      struct set_entry *entry = ht->table + hash_address;
275
 
 
276
 
      if (entry_is_free(entry)) {
277
 
         return NULL;
278
 
      } else if (entry_is_present(entry) && entry->hash == hash) {
279
 
         if (ht->key_equals_function(key, entry->key)) {
280
 
            return entry;
281
 
         }
282
 
      }
283
 
 
284
 
      hash_address += double_hash;
285
 
      if (hash_address >= size)
286
 
         hash_address -= size;
287
 
   } while (hash_address != start_address);
288
 
 
289
 
   return NULL;
290
 
}
291
 
 
292
 
struct set_entry *
293
 
_mesa_set_search(const struct set *set, const void *key)
294
 
{
295
 
   assert(set->key_hash_function);
296
 
   return set_search(set, set->key_hash_function(key), key);
297
 
}
298
 
 
299
 
struct set_entry *
300
 
_mesa_set_search_pre_hashed(const struct set *set, uint32_t hash,
301
 
                            const void *key)
302
 
{
303
 
   assert(set->key_hash_function == NULL ||
304
 
          hash == set->key_hash_function(key));
305
 
   return set_search(set, hash, key);
306
 
}
307
 
 
308
 
static void
309
 
set_add_rehash(struct set *ht, uint32_t hash, const void *key)
310
 
{
311
 
   uint32_t size = ht->size;
312
 
   uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
313
 
   uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
314
 
                                           ht->rehash_magic) + 1;
315
 
   uint32_t hash_address = start_address;
316
 
   do {
317
 
      struct set_entry *entry = ht->table + hash_address;
318
 
      if (likely(entry->key == NULL)) {
319
 
         entry->hash = hash;
320
 
         entry->key = key;
321
 
         return;
322
 
      }
323
 
 
324
 
      hash_address = hash_address + double_hash;
325
 
      if (hash_address >= size)
326
 
         hash_address -= size;
327
 
   } while (true);
328
 
}
329
 
 
330
 
static void
331
 
set_rehash(struct set *ht, unsigned new_size_index)
332
 
{
333
 
   struct set old_ht;
334
 
   struct set_entry *table;
335
 
 
336
 
   if (ht->size_index == new_size_index && ht->deleted_entries == ht->max_entries) {
337
 
      set_clear_fast(ht);
338
 
      assert(!ht->entries);
339
 
      return;
340
 
   }
341
 
 
342
 
   if (new_size_index >= ARRAY_SIZE(hash_sizes))
343
 
      return;
344
 
 
345
 
   table = rzalloc_array(ralloc_parent(ht->table), struct set_entry,
346
 
                         hash_sizes[new_size_index].size);
347
 
   if (table == NULL)
348
 
      return;
349
 
 
350
 
   old_ht = *ht;
351
 
 
352
 
   ht->table = table;
353
 
   ht->size_index = new_size_index;
354
 
   ht->size = hash_sizes[ht->size_index].size;
355
 
   ht->rehash = hash_sizes[ht->size_index].rehash;
356
 
   ht->size_magic = hash_sizes[ht->size_index].size_magic;
357
 
   ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
358
 
   ht->max_entries = hash_sizes[ht->size_index].max_entries;
359
 
   ht->entries = 0;
360
 
   ht->deleted_entries = 0;
361
 
 
362
 
   set_foreach(&old_ht, entry) {
363
 
      set_add_rehash(ht, entry->hash, entry->key);
364
 
   }
365
 
 
366
 
   ht->entries = old_ht.entries;
367
 
 
368
 
   ralloc_free(old_ht.table);
369
 
}
370
 
 
371
 
void
372
 
_mesa_set_resize(struct set *set, uint32_t entries)
373
 
{
374
 
   /* You can't shrink a set below its number of entries */
375
 
   if (set->entries > entries)
376
 
      entries = set->entries;
377
 
 
378
 
   unsigned size_index = 0;
379
 
   while (hash_sizes[size_index].max_entries < entries)
380
 
      size_index++;
381
 
 
382
 
   set_rehash(set, size_index);
383
 
}
384
 
 
385
 
/**
386
 
 * Find a matching entry for the given key, or insert it if it doesn't already
387
 
 * exist.
388
 
 *
389
 
 * Note that insertion may rearrange the table on a resize or rehash,
390
 
 * so previously found hash_entries are no longer valid after this function.
391
 
 */
392
 
static struct set_entry *
393
 
set_search_or_add(struct set *ht, uint32_t hash, const void *key, bool *found)
394
 
{
395
 
   struct set_entry *available_entry = NULL;
396
 
 
397
 
   assert(!key_pointer_is_reserved(key));
398
 
 
399
 
   if (ht->entries >= ht->max_entries) {
400
 
      set_rehash(ht, ht->size_index + 1);
401
 
   } else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
402
 
      set_rehash(ht, ht->size_index);
403
 
   }
404
 
 
405
 
   uint32_t size = ht->size;
406
 
   uint32_t start_address = util_fast_urem32(hash, size, ht->size_magic);
407
 
   uint32_t double_hash = util_fast_urem32(hash, ht->rehash,
408
 
                                           ht->rehash_magic) + 1;
409
 
   uint32_t hash_address = start_address;
410
 
   do {
411
 
      struct set_entry *entry = ht->table + hash_address;
412
 
 
413
 
      if (!entry_is_present(entry)) {
414
 
         /* Stash the first available entry we find */
415
 
         if (available_entry == NULL)
416
 
            available_entry = entry;
417
 
         if (entry_is_free(entry))
418
 
            break;
419
 
      }
420
 
 
421
 
      if (!entry_is_deleted(entry) &&
422
 
          entry->hash == hash &&
423
 
          ht->key_equals_function(key, entry->key)) {
424
 
         if (found)
425
 
            *found = true;
426
 
         return entry;
427
 
      }
428
 
 
429
 
      hash_address = hash_address + double_hash;
430
 
      if (hash_address >= size)
431
 
         hash_address -= size;
432
 
   } while (hash_address != start_address);
433
 
 
434
 
   if (available_entry) {
435
 
      /* There is no matching entry, create it. */
436
 
      if (entry_is_deleted(available_entry))
437
 
         ht->deleted_entries--;
438
 
      available_entry->hash = hash;
439
 
      available_entry->key = key;
440
 
      ht->entries++;
441
 
      if (found)
442
 
         *found = false;
443
 
      return available_entry;
444
 
   }
445
 
 
446
 
   /* We could hit here if a required resize failed. An unchecked-malloc
447
 
    * application could ignore this result.
448
 
    */
449
 
   return NULL;
450
 
}
451
 
 
452
 
/**
453
 
 * Inserts the key with the given hash into the table.
454
 
 *
455
 
 * Note that insertion may rearrange the table on a resize or rehash,
456
 
 * so previously found hash_entries are no longer valid after this function.
457
 
 */
458
 
static struct set_entry *
459
 
set_add(struct set *ht, uint32_t hash, const void *key)
460
 
{
461
 
   struct set_entry *entry = set_search_or_add(ht, hash, key, NULL);
462
 
 
463
 
   if (unlikely(!entry))
464
 
      return NULL;
465
 
 
466
 
   /* Note: If a matching entry already exists, this will replace it.  This is
467
 
    * a relatively common feature of hash tables, with the alternative
468
 
    * generally being "insert the new value as well, and return it first when
469
 
    * the key is searched for".
470
 
    *
471
 
    * Note that the hash table doesn't have a delete callback.  If freeing of
472
 
    * old keys is required to avoid memory leaks, use the alternative
473
 
    * _mesa_set_search_or_add function and implement the replacement yourself.
474
 
    */
475
 
   entry->key = key;
476
 
   return entry;
477
 
}
478
 
 
479
 
struct set_entry *
480
 
_mesa_set_add(struct set *set, const void *key)
481
 
{
482
 
   assert(set->key_hash_function);
483
 
   return set_add(set, set->key_hash_function(key), key);
484
 
}
485
 
 
486
 
struct set_entry *
487
 
_mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key)
488
 
{
489
 
   assert(set->key_hash_function == NULL ||
490
 
          hash == set->key_hash_function(key));
491
 
   return set_add(set, hash, key);
492
 
}
493
 
 
494
 
struct set_entry *
495
 
_mesa_set_search_and_add(struct set *set, const void *key, bool *replaced)
496
 
{
497
 
   assert(set->key_hash_function);
498
 
   return _mesa_set_search_and_add_pre_hashed(set,
499
 
                                              set->key_hash_function(key),
500
 
                                              key, replaced);
501
 
}
502
 
 
503
 
struct set_entry *
504
 
_mesa_set_search_and_add_pre_hashed(struct set *set, uint32_t hash,
505
 
                                    const void *key, bool *replaced)
506
 
{
507
 
   assert(set->key_hash_function == NULL ||
508
 
          hash == set->key_hash_function(key));
509
 
   struct set_entry *entry = set_search_or_add(set, hash, key, replaced);
510
 
 
511
 
   if (unlikely(!entry))
512
 
      return NULL;
513
 
 
514
 
   /* This implements the replacement, same as _mesa_set_add(). The user will
515
 
    * be notified if we're overwriting a found entry.
516
 
    */
517
 
   entry->key = key;
518
 
   return entry;
519
 
}
520
 
 
521
 
struct set_entry *
522
 
_mesa_set_search_or_add(struct set *set, const void *key, bool *found)
523
 
{
524
 
   assert(set->key_hash_function);
525
 
   return set_search_or_add(set, set->key_hash_function(key), key, found);
526
 
}
527
 
 
528
 
struct set_entry *
529
 
_mesa_set_search_or_add_pre_hashed(struct set *set, uint32_t hash,
530
 
                                   const void *key, bool *found)
531
 
{
532
 
   assert(set->key_hash_function == NULL ||
533
 
          hash == set->key_hash_function(key));
534
 
   return set_search_or_add(set, hash, key, found);
535
 
}
536
 
 
537
 
/**
538
 
 * This function deletes the given hash table entry.
539
 
 *
540
 
 * Note that deletion doesn't otherwise modify the table, so an iteration over
541
 
 * the table deleting entries is safe.
542
 
 */
543
 
void
544
 
_mesa_set_remove(struct set *ht, struct set_entry *entry)
545
 
{
546
 
   if (!entry)
547
 
      return;
548
 
 
549
 
   entry->key = deleted_key;
550
 
   ht->entries--;
551
 
   ht->deleted_entries++;
552
 
}
553
 
 
554
 
/**
555
 
 * Removes the entry with the corresponding key, if exists.
556
 
 */
557
 
void
558
 
_mesa_set_remove_key(struct set *set, const void *key)
559
 
{
560
 
   _mesa_set_remove(set, _mesa_set_search(set, key));
561
 
}
562
 
 
563
 
/**
564
 
 * This function is an iterator over the set when no deleted entries are present.
565
 
 *
566
 
 * Pass in NULL for the first entry, as in the start of a for loop.
567
 
 */
568
 
struct set_entry *
569
 
_mesa_set_next_entry_unsafe(const struct set *ht, struct set_entry *entry)
570
 
{
571
 
   assert(!ht->deleted_entries);
572
 
   if (!ht->entries)
573
 
      return NULL;
574
 
   if (entry == NULL)
575
 
      entry = ht->table;
576
 
   else
577
 
      entry = entry + 1;
578
 
   if (entry != ht->table + ht->size)
579
 
      return entry->key ? entry : _mesa_set_next_entry_unsafe(ht, entry);
580
 
 
581
 
   return NULL;
582
 
}
583
 
 
584
 
/**
585
 
 * This function is an iterator over the hash table.
586
 
 *
587
 
 * Pass in NULL for the first entry, as in the start of a for loop.  Note that
588
 
 * an iteration over the table is O(table_size) not O(entries).
589
 
 */
590
 
struct set_entry *
591
 
_mesa_set_next_entry(const struct set *ht, struct set_entry *entry)
592
 
{
593
 
   if (entry == NULL)
594
 
      entry = ht->table;
595
 
   else
596
 
      entry = entry + 1;
597
 
 
598
 
   for (; entry != ht->table + ht->size; entry++) {
599
 
      if (entry_is_present(entry)) {
600
 
         return entry;
601
 
      }
602
 
   }
603
 
 
604
 
   return NULL;
605
 
}
606
 
 
607
 
struct set_entry *
608
 
_mesa_set_random_entry(struct set *ht,
609
 
                       int (*predicate)(struct set_entry *entry))
610
 
{
611
 
   struct set_entry *entry;
612
 
   uint32_t i = rand() % ht->size;
613
 
 
614
 
   if (ht->entries == 0)
615
 
      return NULL;
616
 
 
617
 
   for (entry = ht->table + i; entry != ht->table + ht->size; entry++) {
618
 
      if (entry_is_present(entry) &&
619
 
          (!predicate || predicate(entry))) {
620
 
         return entry;
621
 
      }
622
 
   }
623
 
 
624
 
   for (entry = ht->table; entry != ht->table + i; entry++) {
625
 
      if (entry_is_present(entry) &&
626
 
          (!predicate || predicate(entry))) {
627
 
         return entry;
628
 
      }
629
 
   }
630
 
 
631
 
   return NULL;
632
 
}
633
 
 
634
 
/**
635
 
 * Helper to create a set with pointer keys.
636
 
 */
637
 
struct set *
638
 
_mesa_pointer_set_create(void *mem_ctx)
639
 
{
640
 
   return _mesa_set_create(mem_ctx, _mesa_hash_pointer,
641
 
                           _mesa_key_pointer_equal);
642
 
}
643
 
 
644
 
bool
645
 
_mesa_set_intersects(struct set *a, struct set *b)
646
 
{
647
 
   assert(a->key_hash_function == b->key_hash_function);
648
 
   assert(a->key_equals_function == b->key_equals_function);
649
 
 
650
 
   /* iterate over the set with less entries */
651
 
   if (b->entries < a->entries) {
652
 
      struct set *tmp = a;
653
 
      a = b;
654
 
      b = tmp;
655
 
   }
656
 
 
657
 
   set_foreach(a, entry) {
658
 
      if (_mesa_set_search_pre_hashed(b, entry->hash, entry->key))
659
 
         return true;
660
 
   }
661
 
   return false;
662
 
}