src/gallium/auxiliary/util/u_keymap.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2008 VMware, Inc.
   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 VMWARE 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
  40 #include "cso_cache/cso_hash.h"
  41
  42 #include "util/u_memory.h"
  43 #include "util/u_keymap.h"
  44
  45
  46 struct keymap
  47 {
  48    struct cso_hash *cso;
  49    unsigned key_size;
  50    unsigned max_entries; /* XXX not obeyed net */
  51    unsigned num_entries;
  52    keymap_delete_func delete_func;
  53 };
  54
  55
  56 struct keymap_item
  57 {
  58    void *key, *value;
  59 };
  60
  61
  62 /**
  63  * This the default key-delete function used when the client doesn't
  64  * provide one.
  65  */
  66 static void
  67 default_delete_func(const struct keymap *map,
  68                     const void *key, void *data, void *user)
  69 {
  70    FREE((void*) data);
  71 }
  72
  73
  74 static INLINE struct keymap_item *
  75 hash_table_item(struct cso_hash_iter iter)
  76 {
  77    return (struct keymap_item *) cso_hash_iter_data(iter);
  78 }
  79
  80
  81 /**
  82  * Return 4-byte hash key for a block of bytes.
  83  */
  84 static unsigned
  85 hash(const void *key, unsigned keySize)
  86 {
  87    unsigned i, hash;
  88
  89    keySize /= 4; /* convert from bytes to uints */
  90
  91    hash = 0;
  92    for (i = 0; i < keySize; i++) {
  93       hash ^= (i + 1) * ((const unsigned *) key)[i];
  94    }
  95
  96    /*hash = hash ^ (hash >> 11) ^ (hash >> 22);*/
  97
  98    return hash;
  99 }
 100
 101
 102 /**
 103  * Create a new map.
 104  * \param keySize  size of the keys in bytes
 105  * \param maxEntries  max number of entries to allow (~0 = infinity)
 106  * \param deleteFunc  optional callback to call when entries
 107  *                    are deleted/replaced
 108  */
 109 struct keymap *
 110 util_new_keymap(unsigned keySize, unsigned maxEntries,
 111                  keymap_delete_func deleteFunc)
 112 {
 113    struct keymap *map = MALLOC_STRUCT(keymap);
 114    if (!map)
 115       return NULL;
 116
 117    map->cso = cso_hash_create();
 118    if (!map->cso) {
 119       FREE(map);
 120       return NULL;
 121    }
 122
 123    map->max_entries = maxEntries;
 124    map->num_entries = 0;
 125    map->key_size = keySize;
 126    map->delete_func = deleteFunc ? deleteFunc : default_delete_func;
 127
 128    return map;
 129 }
 130
 131
 132 /**
 133  * Delete/free a keymap and all entries.  The deleteFunc that was given at
 134  * create time will be called for each entry.
 135  * \param user  user-provided pointer passed through to the delete callback
 136  */
 137 void
 138 util_delete_keymap(struct keymap *map, void *user)
 139 {
 140    util_keymap_remove_all(map, user);
 141    cso_hash_delete(map->cso);
 142    FREE(map);
 143 }
 144
 145
 146 static INLINE struct cso_hash_iter
 147 hash_table_find_iter(const struct keymap *map, const void *key,
 148                      unsigned key_hash)
 149 {
 150    struct cso_hash_iter iter;
 151    struct keymap_item *item;
 152
 153    iter = cso_hash_find(map->cso, key_hash);
 154    while (!cso_hash_iter_is_null(iter)) {
 155       item = (struct keymap_item *) cso_hash_iter_data(iter);
 156       if (!memcmp(item->key, key, map->key_size))
 157          break;
 158       iter = cso_hash_iter_next(iter);
 159    }
 160
 161    return iter;
 162 }
 163
 164
 165 static INLINE struct keymap_item *
 166 hash_table_find_item(const struct keymap *map, const void *key,
 167                      unsigned key_hash)
 168 {
 169    struct cso_hash_iter iter = hash_table_find_iter(map, key, key_hash);
 170    if (cso_hash_iter_is_null(iter)) {
 171       return NULL;
 172    }
 173    else {
 174       return hash_table_item(iter);
 175    }
 176 }
 177
 178
 179 /**
 180  * Insert a new key + data pointer into the table.
 181  * Note: we create a copy of the key, but not the data!
 182  * If the key is already present in the table, replace the existing
 183  * entry (calling the delete callback on the previous entry).
 184  * If the maximum capacity of the map is reached an old entry
 185  * will be deleted (the delete callback will be called).
 186  */
 187 boolean
 188 util_keymap_insert(struct keymap *map, const void *key,
 189                    const void *data, void *user)
 190 {
 191    unsigned key_hash;
 192    struct keymap_item *item;
 193    struct cso_hash_iter iter;
 194
 195    assert(map);
 196    if (!map)
 197       return FALSE;
 198
 199    key_hash = hash(key, map->key_size);
 200
 201    item = hash_table_find_item(map, key, key_hash);
 202    if (item) {
 203       /* call delete callback for old entry/item */
 204       map->delete_func(map, item->key, item->value, user);
 205       item->value = (void *) data;
 206       return TRUE;
 207    }
 208
 209    item = MALLOC_STRUCT(keymap_item);
 210    if (!item)
 211       return FALSE;
 212
 213    item->key = mem_dup(key, map->key_size);
 214    item->value = (void *) data;
 215
 216    iter = cso_hash_insert(map->cso, key_hash, item);
 217    if (cso_hash_iter_is_null(iter)) {
 218       FREE(item);
 219       return FALSE;
 220    }
 221
 222    map->num_entries++;
 223
 224    return TRUE;
 225 }
 226
 227
 228 /**
 229  * Look up a key in the map and return the associated data pointer.
 230  */
 231 const void *
 232 util_keymap_lookup(const struct keymap *map, const void *key)
 233 {
 234    unsigned key_hash;
 235    struct keymap_item *item;
 236
 237    assert(map);
 238    if (!map)
 239       return NULL;
 240
 241    key_hash = hash(key, map->key_size);
 242
 243    item = hash_table_find_item(map, key, key_hash);
 244    if (!item)
 245       return NULL;
 246
 247    return item->value;
 248 }
 249
 250
 251 /**
 252  * Remove an entry from the map.
 253  * The delete callback will be called if the given key/entry is found.
 254  * \param user  passed to the delete callback as the last param.
 255  */
 256 void
 257 util_keymap_remove(struct keymap *map, const void *key, void *user)
 258 {
 259    unsigned key_hash;
 260    struct cso_hash_iter iter;
 261    struct keymap_item *item;
 262
 263    assert(map);
 264    if (!map)
 265       return;
 266
 267    key_hash = hash(key, map->key_size);
 268
 269    iter = hash_table_find_iter(map, key, key_hash);
 270    if (cso_hash_iter_is_null(iter))
 271       return;
 272
 273    item = hash_table_item(iter);
 274    assert(item);
 275    if (!item)
 276       return;
 277    map->delete_func(map, item->key, item->value, user);
 278    FREE(item->key);
 279    FREE(item);
 280
 281    map->num_entries--;
 282
 283    cso_hash_erase(map->cso, iter);
 284 }
 285
 286
 287 /**
 288  * Remove all entries from the map, calling the delete callback for each.
 289  * \param user  passed to the delete callback as the last param.
 290  */
 291 void
 292 util_keymap_remove_all(struct keymap *map, void *user)
 293 {
 294    struct cso_hash_iter iter;
 295    struct keymap_item *item;
 296
 297    assert(map);
 298    if (!map)
 299       return;
 300
 301    iter = cso_hash_first_node(map->cso);
 302    while (!cso_hash_iter_is_null(iter)) {
 303       item = (struct keymap_item *)
 304          cso_hash_take(map->cso, cso_hash_iter_key(iter));
 305       map->delete_func(map, item->key, item->value, user);
 306       FREE(item->key);
 307       FREE(item);
 308       iter = cso_hash_first_node(map->cso);
 309    }
 310 }
 311
 312
 313 extern void
 314 util_keymap_info(const struct keymap *map)
 315 {
 316    debug_printf("Keymap %p: %u of max %u entries\n",
 317                 (void *) map, map->num_entries, map->max_entries);
 318 }