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 <inttypes.h>
  32. #include <stdbool.h>
  33.  
  34. #include "compiler.h"
  35.  
  36. #ifdef __cplusplus
  37. extern "C" {
  38. #endif
  39.  
  40. struct hash_entry {
  41.    uint32_t hash;
  42.    const void *key;
  43.    void *data;
  44. };
  45.  
  46. struct hash_table {
  47.    void *mem_ctx;
  48.    struct hash_entry *table;
  49.    bool (*key_equals_function)(const void *a, const void *b);
  50.    const void *deleted_key;
  51.    uint32_t size;
  52.    uint32_t rehash;
  53.    uint32_t max_entries;
  54.    uint32_t size_index;
  55.    uint32_t entries;
  56.    uint32_t deleted_entries;
  57. };
  58.  
  59. struct hash_table *
  60. _mesa_hash_table_create(void *mem_ctx,
  61.                         bool (*key_equals_function)(const void *a,
  62.                                                     const void *b));
  63. void _mesa_hash_table_destroy(struct hash_table *ht,
  64.                               void (*delete_function)(struct hash_entry *entry));
  65. void _mesa_hash_table_set_deleted_key(struct hash_table *ht,
  66.                                       const void *deleted_key);
  67.  
  68. struct hash_entry *
  69. _mesa_hash_table_insert(struct hash_table *ht, uint32_t hash,
  70.                         const void *key, void *data);
  71. struct hash_entry *
  72. _mesa_hash_table_search(struct hash_table *ht, uint32_t hash,
  73.                         const void *key);
  74. void _mesa_hash_table_remove(struct hash_table *ht,
  75.                              struct hash_entry *entry);
  76.  
  77. struct hash_entry *_mesa_hash_table_next_entry(struct hash_table *ht,
  78.                                                struct hash_entry *entry);
  79. struct hash_entry *
  80. _mesa_hash_table_random_entry(struct hash_table *ht,
  81.                               bool (*predicate)(struct hash_entry *entry));
  82.  
  83. uint32_t _mesa_hash_data(const void *data, size_t size);
  84. uint32_t _mesa_hash_string(const char *key);
  85. bool _mesa_key_string_equal(const void *a, const void *b);
  86. bool _mesa_key_pointer_equal(const void *a, const void *b);
  87.  
  88. static inline uint32_t _mesa_hash_pointer(const void *pointer)
  89. {
  90.    return _mesa_hash_data(&pointer, sizeof(pointer));
  91. }
  92.  
  93. /**
  94.  * This foreach function is safe against deletion (which just replaces
  95.  * an entry's data with the deleted marker), but not against insertion
  96.  * (which may rehash the table, making entry a dangling pointer).
  97.  */
  98. #define hash_table_foreach(ht, entry)                   \
  99.    for (entry = _mesa_hash_table_next_entry(ht, NULL);  \
  100.         entry != NULL;                                  \
  101.         entry = _mesa_hash_table_next_entry(ht, entry))
  102.  
  103. #ifdef __cplusplus
  104. } /* extern C */
  105. #endif
  106.  
  107. #endif /* _HASH_TABLE_H */
  108.