Home | History | Annotate | Download | only in util
      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 (at) anholt.net>
     25  *
     26  */
     27 
     28 #ifndef _HASH_TABLE_H
     29 #define _HASH_TABLE_H
     30 
     31 #include <stdlib.h>
     32 #include <inttypes.h>
     33 #include <stdbool.h>
     34 #include "c99_compat.h"
     35 #include "macros.h"
     36 
     37 #ifdef __cplusplus
     38 extern "C" {
     39 #endif
     40 
     41 struct hash_entry {
     42    uint32_t hash;
     43    const void *key;
     44    void *data;
     45 };
     46 
     47 struct hash_table {
     48    struct hash_entry *table;
     49    uint32_t (*key_hash_function)(const void *key);
     50    bool (*key_equals_function)(const void *a, const void *b);
     51    const void *deleted_key;
     52    uint32_t size;
     53    uint32_t rehash;
     54    uint32_t max_entries;
     55    uint32_t size_index;
     56    uint32_t entries;
     57    uint32_t deleted_entries;
     58 };
     59 
     60 struct hash_table *
     61 _mesa_hash_table_create(void *mem_ctx,
     62                         uint32_t (*key_hash_function)(const void *key),
     63                         bool (*key_equals_function)(const void *a,
     64                                                     const void *b));
     65 void _mesa_hash_table_destroy(struct hash_table *ht,
     66                               void (*delete_function)(struct hash_entry *entry));
     67 void _mesa_hash_table_clear(struct hash_table *ht,
     68                             void (*delete_function)(struct hash_entry *entry));
     69 void _mesa_hash_table_set_deleted_key(struct hash_table *ht,
     70                                       const void *deleted_key);
     71 
     72 static inline uint32_t _mesa_hash_table_num_entries(struct hash_table *ht)
     73 {
     74    return ht->entries;
     75 }
     76 
     77 struct hash_entry *
     78 _mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data);
     79 struct hash_entry *
     80 _mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
     81                                    const void *key, void *data);
     82 struct hash_entry *
     83 _mesa_hash_table_search(struct hash_table *ht, const void *key);
     84 struct hash_entry *
     85 _mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash,
     86                                   const void *key);
     87 void _mesa_hash_table_remove(struct hash_table *ht,
     88                              struct hash_entry *entry);
     89 
     90 struct hash_entry *_mesa_hash_table_next_entry(struct hash_table *ht,
     91                                                struct hash_entry *entry);
     92 struct hash_entry *
     93 _mesa_hash_table_random_entry(struct hash_table *ht,
     94                               bool (*predicate)(struct hash_entry *entry));
     95 
     96 uint32_t _mesa_hash_data(const void *data, size_t size);
     97 uint32_t _mesa_hash_string(const void *key);
     98 bool _mesa_key_string_equal(const void *a, const void *b);
     99 bool _mesa_key_pointer_equal(const void *a, const void *b);
    100 
    101 static inline uint32_t _mesa_key_hash_string(const void *key)
    102 {
    103    return _mesa_hash_string((const char *)key);
    104 }
    105 
    106 static inline uint32_t _mesa_hash_pointer(const void *pointer)
    107 {
    108    uintptr_t num = (uintptr_t) pointer;
    109    return (uint32_t) ((num >> 2) ^ (num >> 6) ^ (num >> 10) ^ (num >> 14));
    110 }
    111 
    112 enum {
    113    _mesa_fnv32_1a_offset_bias = 2166136261u,
    114 };
    115 
    116 static inline uint32_t
    117 _mesa_fnv32_1a_accumulate_block(uint32_t hash, const void *data, size_t size)
    118 {
    119    const uint8_t *bytes = (const uint8_t *)data;
    120 
    121    while (size-- != 0) {
    122       hash ^= *bytes;
    123       hash = hash * 0x01000193;
    124       bytes++;
    125    }
    126 
    127    return hash;
    128 }
    129 
    130 #define _mesa_fnv32_1a_accumulate(hash, expr) \
    131    _mesa_fnv32_1a_accumulate_block(hash, &(expr), sizeof(expr))
    132 
    133 /**
    134  * This foreach function is safe against deletion (which just replaces
    135  * an entry's data with the deleted marker), but not against insertion
    136  * (which may rehash the table, making entry a dangling pointer).
    137  */
    138 #define hash_table_foreach(ht, entry)                   \
    139    for (entry = _mesa_hash_table_next_entry(ht, NULL);  \
    140         entry != NULL;                                  \
    141         entry = _mesa_hash_table_next_entry(ht, entry))
    142 
    143 static inline void
    144 hash_table_call_foreach(struct hash_table *ht,
    145                         void (*callback)(const void *key,
    146                                          void *data,
    147                                          void *closure),
    148                         void *closure)
    149 {
    150    struct hash_entry *entry;
    151 
    152    hash_table_foreach(ht, entry)
    153       callback(entry->key, entry->data, closure);
    154 }
    155 
    156 /**
    157  * Hash table wrapper which supports 64-bit keys.
    158  */
    159 struct hash_table_u64 {
    160    struct hash_table *table;
    161    void *deleted_key_data;
    162 };
    163 
    164 struct hash_table_u64 *
    165 _mesa_hash_table_u64_create(void *mem_ctx);
    166 
    167 void
    168 _mesa_hash_table_u64_destroy(struct hash_table_u64 *ht,
    169                              void (*delete_function)(struct hash_entry *entry));
    170 
    171 void
    172 _mesa_hash_table_u64_insert(struct hash_table_u64 *ht, uint64_t key,
    173                             void *data);
    174 
    175 void *
    176 _mesa_hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key);
    177 
    178 void
    179 _mesa_hash_table_u64_remove(struct hash_table_u64 *ht, uint64_t key);
    180 
    181 #ifdef __cplusplus
    182 } /* extern C */
    183 #endif
    184 
    185 #endif /* _HASH_TABLE_H */
    186