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 util_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 "util/u_debug.h"
  39 #include "pipe/p_defines.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    if (!map)
 198       return FALSE;
 199
 200    key_hash = hash(key, map->key_size);
 201
 202    item = hash_table_find_item(map, key, key_hash);
 203    if (item) {
 204       /* call delete callback for old entry/item */
 205       map->delete_func(map, item->key, item->value, user);
 206       item->value = (void *) data;
 207       return TRUE;
 208    }
 209
 210    item = MALLOC_STRUCT(keymap_item);
 211    if (!item)
 212       return FALSE;
 213
 214    item->key = mem_dup(key, map->key_size);
 215    item->value = (void *) data;
 216
 217    iter = cso_hash_insert(map->cso, key_hash, item);
 218    if (cso_hash_iter_is_null(iter)) {
 219       FREE(item);
 220       return FALSE;
 221    }
 222
 223    map->num_entries++;
 224
 225    return TRUE;
 226 }
 227
 228
 229 /**
 230  * Look up a key in the map and return the associated data pointer.
 231  */
 232 const void *
 233 util_keymap_lookup(const struct keymap *map, const void *key)
 234 {
 235    unsigned key_hash;
 236    struct keymap_item *item;
 237
 238    assert(map);
 239    if (!map)
 240       return NULL;
 241
 242    key_hash = hash(key, map->key_size);
 243
 244    item = hash_table_find_item(map, key, key_hash);
 245    if (!item)
 246       return NULL;
 247
 248    return item->value;
 249 }
 250
 251
 252 /**
 253  * Remove an entry from the map.
 254  * The delete callback will be called if the given key/entry is found.
 255  * \param user  passed to the delete callback as the last param.
 256  */
 257 void
 258 util_keymap_remove(struct keymap *map, const void *key, void *user)
 259 {
 260    unsigned key_hash;
 261    struct cso_hash_iter iter;
 262    struct keymap_item *item;
 263
 264    assert(map);
 265    if (!map)
 266       return;
 267
 268    key_hash = hash(key, map->key_size);
 269
 270    iter = hash_table_find_iter(map, key, key_hash);
 271    if (cso_hash_iter_is_null(iter))
 272       return;
 273
 274    item = hash_table_item(iter);
 275    assert(item);
 276    if (!item)
 277       return;
 278    map->delete_func(map, item->key, item->value, user);
 279    FREE(item->key);
 280    FREE(item);
 281
 282    map->num_entries--;
 283
 284    cso_hash_erase(map->cso, iter);
 285 }
 286
 287
 288 /**
 289  * Remove all entries from the map, calling the delete callback for each.
 290  * \param user  passed to the delete callback as the last param.
 291  */
 292 void
 293 util_keymap_remove_all(struct keymap *map, void *user)
 294 {
 295    struct cso_hash_iter iter;
 296    struct keymap_item *item;
 297
 298    assert(map);
 299    if (!map)
 300       return;
 301
 302    iter = cso_hash_first_node(map->cso);
 303    while (!cso_hash_iter_is_null(iter)) {
 304       item = (struct keymap_item *)
 305          cso_hash_take(map->cso, cso_hash_iter_key(iter));
 306       map->delete_func(map, item->key, item->value, user);
 307       FREE(item->key);
 308       FREE(item);
 309       iter = cso_hash_first_node(map->cso);
 310    }
 311 }
 312
 313
 314 extern void
 315 util_keymap_info(const struct keymap *map)
 316 {
 317    debug_printf("Keymap %p: %u of max %u entries\n",
 318                 (void *) map, map->num_entries, map->max_entries);
 319 }