Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  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 _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_set_deleted_key(struct hash_table *ht,
  68.                                       const void *deleted_key);
  69.  
  70. struct hash_entry *
  71. _mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data);
  72. struct hash_entry *
  73. _mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
  74.                                    const void *key, void *data);
  75. struct hash_entry *
  76. _mesa_hash_table_search(struct hash_table *ht, const void *key);
  77. struct hash_entry *
  78. _mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash,
  79.                                   const void *key);
  80. void _mesa_hash_table_remove(struct hash_table *ht,
  81.                              struct hash_entry *entry);
  82.  
  83. struct hash_entry *_mesa_hash_table_next_entry(struct hash_table *ht,
  84.                                                struct hash_entry *entry);
  85. struct hash_entry *
  86. _mesa_hash_table_random_entry(struct hash_table *ht,
  87.                               bool (*predicate)(struct hash_entry *entry));
  88.  
  89. uint32_t _mesa_hash_data(const void *data, size_t size);
  90. uint32_t _mesa_hash_string(const char *key);
  91. bool _mesa_key_string_equal(const void *a, const void *b);
  92. bool _mesa_key_pointer_equal(const void *a, const void *b);
  93.  
  94. static inline uint32_t _mesa_key_hash_string(const void *key)
  95. {
  96.    return _mesa_hash_string((const char *)key);
  97. }
  98.  
  99. static inline uint32_t _mesa_hash_pointer(const void *pointer)
  100. {
  101.    return _mesa_hash_data(&pointer, sizeof(pointer));
  102. }
  103.  
  104. static const uint32_t _mesa_fnv32_1a_offset_bias = 2166136261u;
  105.  
  106. static inline uint32_t
  107. _mesa_fnv32_1a_accumulate_block(uint32_t hash, const void *data, size_t size)
  108. {
  109.    const uint8_t *bytes = (const uint8_t *)data;
  110.  
  111.    while (size-- != 0) {
  112.       hash ^= *bytes;
  113.       hash = hash * 0x01000193;
  114.       bytes++;
  115.    }
  116.  
  117.    return hash;
  118. }
  119.  
  120. #define _mesa_fnv32_1a_accumulate(hash, expr) \
  121.    _mesa_fnv32_1a_accumulate_block(hash, &(expr), sizeof(expr))
  122.  
  123. /**
  124.  * This foreach function is safe against deletion (which just replaces
  125.  * an entry's data with the deleted marker), but not against insertion
  126.  * (which may rehash the table, making entry a dangling pointer).
  127.  */
  128. #define hash_table_foreach(ht, entry)                   \
  129.    for (entry = _mesa_hash_table_next_entry(ht, NULL);  \
  130.         entry != NULL;                                  \
  131.         entry = _mesa_hash_table_next_entry(ht, entry))
  132.  
  133. #ifdef __cplusplus
  134. } /* extern C */
  135. #endif
  136.  
  137. #endif /* _HASH_TABLE_H */
  138.