src/gallium/auxiliary/util/u_keymap.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2008 Tungsten Graphics, Inc., Cedar Park, Texas.
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sub license, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial portions
  16  * of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  21  * IN NO EVENT SHALL TUNGSTEN GRAPHICS AND/OR ITS SUPPLIERS BE LIABLE FOR
  22  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  **************************************************************************/
  27
  28 /**
  29  * Key lookup/associative container.
  30  *
  31  * Like Jose's u_hash_table, based on CSO cache code for now.
  32  *
  33  * Author: Brian Paul
  34  */
  35
  36
  37 #include "pipe/p_compiler.h"
  38 #include "pipe/p_debug.h"
  39 #include "pipe/p_error.h"
  40
  41 #include "cso_cache/cso_hash.h"
  42
  43 #include "util/u_memory.h"
  44 #include "util/u_keymap.h"
  45
  46
  47 struct keymap
  48 {
  49    struct cso_hash *cso;
  50    unsigned key_size;
  51    unsigned max_entries; /* XXX not obeyed net */
  52    unsigned num_entries;
  53    keymap_delete_func delete_func;
  54 };
  55
  56
  57 struct keymap_item
  58 {
  59    void *key, *value;
  60 };
  61
  62
  63 /**
  64  * This the default key-delete function used when the client doesn't
  65  * provide one.
  66  */
  67 static void
  68 default_delete_func(const struct keymap *map,
  69                     const void *key, void *data, void *user)
  70 {
  71    FREE((void*) data);
  72 }
  73
  74
  75 static INLINE struct keymap_item *
  76 hash_table_item(struct cso_hash_iter iter)
  77 {
  78    return (struct keymap_item *) cso_hash_iter_data(iter);
  79 }
  80
  81
  82 /**
  83  * Return 4-byte hash key for a block of bytes.
  84  */
  85 static unsigned
  86 hash(const void *key, unsigned keySize)
  87 {
  88    unsigned i, hash;
  89
  90    keySize /= 4; /* convert from bytes to uints */
  91
  92    hash = 0;
  93    for (i = 0; i < keySize; i++) {
  94       hash ^= (i + 1) * ((const unsigned *) key)[i];
  95    }
  96
  97    /*hash = hash ^ (hash >> 11) ^ (hash >> 22);*/
  98
  99    return hash;
 100 }
 101
 102
 103 /**
 104  * Create a new map.
 105  * \param keySize  size of the keys in bytes
 106  * \param maxEntries  max number of entries to allow (~0 = infinity)
 107  * \param deleteFunc  optional callback to call when entries
 108  *                    are deleted/replaced
 109  */
 110 struct keymap *
 111 util_new_keymap(unsigned keySize, unsigned maxEntries,
 112                  keymap_delete_func deleteFunc)
 113 {
 114    struct keymap *map = MALLOC_STRUCT(keymap);
 115    if (!map)
 116       return NULL;
 117
 118    map->cso = cso_hash_create();
 119    if (!map->cso) {
 120       FREE(map);
 121       return NULL;
 122    }
 123
 124    map->max_entries = maxEntries;
 125    map->num_entries = 0;
 126    map->key_size = keySize;
 127    map->delete_func = deleteFunc ? deleteFunc : default_delete_func;
 128
 129    return map;
 130 }
 131
 132
 133 /**
 134  * Delete/free a keymap and all entries.  The deleteFunc that was given at
 135  * create time will be called for each entry.
 136  * \param user  user-provided pointer passed through to the delete callback
 137  */
 138 void
 139 util_delete_keymap(struct keymap *map, void *user)
 140 {
 141    util_keymap_remove_all(map, user);
 142    cso_hash_delete(map->cso);
 143    FREE(map);
 144 }
 145
 146
 147 static INLINE struct cso_hash_iter
 148 hash_table_find_iter(const struct keymap *map, const void *key,
 149                      unsigned key_hash)
 150 {
 151    struct cso_hash_iter iter;
 152    struct keymap_item *item;
 153
 154    iter = cso_hash_find(map->cso, key_hash);
 155    while (!cso_hash_iter_is_null(iter)) {
 156       item = (struct keymap_item *) cso_hash_iter_data(iter);
 157       if (!memcmp(item->key, key, map->key_size))
 158          break;
 159       iter = cso_hash_iter_next(iter);
 160    }
 161
 162    return iter;
 163 }
 164
 165
 166 static INLINE struct keymap_item *
 167 hash_table_find_item(const struct keymap *map, const void *key,
 168                      unsigned key_hash)
 169 {
 170    struct cso_hash_iter iter = hash_table_find_iter(map, key, key_hash);
 171    if (cso_hash_iter_is_null(iter)) {
 172       return NULL;
 173    }
 174    else {
 175       return hash_table_item(iter);
 176    }
 177 }
 178
 179
 180 /**
 181  * Insert a new key + data pointer into the table.
 182  * Note: we create a copy of the key, but not the data!
 183  * If the key is already present in the table, replace the existing
 184  * entry (calling the delete callback on the previous entry).
 185  * If the maximum capacity of the map is reached an old entry
 186  * will be deleted (the delete callback will be called).
 187  */
 188 boolean
 189 util_keymap_insert(struct keymap *map, const void *key,
 190                    const void *data, void *user)
 191 {
 192    unsigned key_hash;
 193    struct keymap_item *item;
 194    struct cso_hash_iter iter;
 195
 196    assert(map);
 197
 198    key_hash = hash(key, map->key_size);
 199
 200    item = hash_table_find_item(map, key, key_hash);
 201    if (item) {
 202       /* call delete callback for old entry/item */
 203       map->delete_func(map, item->key, item->value, user);
 204       item->value = (void *) data;
 205       return TRUE;
 206    }
 207
 208    item = MALLOC_STRUCT(keymap_item);
 209    if (!item)
 210       return FALSE;
 211
 212    item->key = mem_dup(key, map->key_size);
 213    item->value = (void *) data;
 214
 215    iter = cso_hash_insert(map->cso, key_hash, item);
 216    if (cso_hash_iter_is_null(iter)) {
 217       FREE(item);
 218       return FALSE;
 219    }
 220
 221    map->num_entries++;
 222
 223    return TRUE;
 224 }
 225
 226
 227 /**
 228  * Look up a key in the map and return the associated data pointer.
 229  */
 230 const void *
 231 util_keymap_lookup(const struct keymap *map, const void *key)
 232 {
 233    unsigned key_hash;
 234    struct keymap_item *item;
 235
 236    assert(map);
 237
 238    key_hash = hash(key, map->key_size);
 239
 240    item = hash_table_find_item(map, key, key_hash);
 241    if (!item)
 242       return NULL;
 243
 244    return item->value;
 245 }
 246
 247
 248 /**
 249  * Remove an entry from the map.
 250  * The delete callback will be called if the given key/entry is found.
 251  * \param user  passed to the delete callback as the last param.
 252  */
 253 void
 254 util_keymap_remove(struct keymap *map, const void *key, void *user)
 255 {
 256    unsigned key_hash;
 257    struct cso_hash_iter iter;
 258    struct keymap_item *item;
 259
 260    assert(map);
 261
 262    key_hash = hash(key, map->key_size);
 263
 264    iter = hash_table_find_iter(map, key, key_hash);
 265    if (cso_hash_iter_is_null(iter))
 266       return;
 267
 268    item = hash_table_item(iter);
 269    assert(item);
 270    map->delete_func(map, item->key, item->value, user);
 271    FREE(item->key);
 272    FREE(item);
 273
 274    map->num_entries--;
 275
 276    cso_hash_erase(map->cso, iter);
 277 }
 278
 279
 280 /**
 281  * Remove all entries from the map, calling the delete callback for each.
 282  * \param user  passed to the delete callback as the last param.
 283  */
 284 void
 285 util_keymap_remove_all(struct keymap *map, void *user)
 286 {
 287    struct cso_hash_iter iter;
 288    struct keymap_item *item;
 289
 290    assert(map);
 291
 292    iter = cso_hash_first_node(map->cso);
 293    while (!cso_hash_iter_is_null(iter)) {
 294       item = (struct keymap_item *)
 295          cso_hash_take(map->cso, cso_hash_iter_key(iter));
 296       map->delete_func(map, item->key, item->value, user);
 297       FREE(item->key);
 298       FREE(item);
 299       iter = cso_hash_first_node(map->cso);
 300    }
 301 }
 302
 303
 304 extern void
 305 util_keymap_info(const struct keymap *map)
 306 {
 307    debug_printf("Keymap %p: %u of max %u entries\n",
 308                 (void *) map, map->num_entries, map->max_entries);
 309 }