src/egl/main/eglhash.c

   1 /**
   2  * \file hash.c
   3  * Generic hash table.
   4  *
   5  * This code taken from Mesa and adapted.
   6  */
   7
   8 #include <assert.h>
   9 #include <stdlib.h>
  10 #include <stdio.h>
  11 #include "eglhash.h"
  12
  13
  14 #define TABLE_SIZE 1023  /**< Size of lookup table/array */
  15
  16 #define HASH_FUNC(K)  ((K) % TABLE_SIZE)
  17
  18
  19 /*
  20  * Unfinished mutex stuff
  21  */
  22
  23 typedef int _EGLMutex;
  24
  25 static void
  26 _eglInitMutex(_EGLMutex m)
  27 {
  28 }
  29
  30 static void
  31 _eglDestroyMutex(_EGLMutex m)
  32 {
  33 }
  34
  35 static void
  36 _eglLockMutex(_EGLMutex m)
  37 {
  38 }
  39
  40 static void
  41 _eglUnlockMutex(_EGLMutex m)
  42 {
  43 }
  44
  45
  46
  47 typedef struct _egl_hashentry _EGLHashentry;
  48
  49 struct _egl_hashentry
  50 {
  51    EGLuint Key;            /**< the entry's key */
  52    void *Data;             /**< the entry's data */
  53    _EGLHashentry *Next;    /**< pointer to next entry */
  54 };
  55
  56
  57 struct _egl_hashtable
  58 {
  59    _EGLHashentry *Table[TABLE_SIZE];  /**< the lookup table */
  60    EGLuint MaxKey;                    /**< highest key inserted so far */
  61    _EGLMutex Mutex;                   /**< mutual exclusion lock */
  62 };
  63
  64
  65 /**
  66  * Create a new hash table.
  67  *
  68  * \return pointer to a new, empty hash table.
  69  */
  70 _EGLHashtable *
  71 _eglNewHashTable(void)
  72 {
  73    _EGLHashtable *table = (_EGLHashtable *) calloc(1, sizeof(_EGLHashtable));
  74    if (table) {
  75       _eglInitMutex(table->Mutex);
  76       table->MaxKey = 1;
  77    }
  78    return table;
  79 }
  80
  81
  82
  83 /**
  84  * Delete a hash table.
  85  * Frees each entry on the hash table and then the hash table structure itself.
  86  * Note that the caller should have already traversed the table and deleted
  87  * the objects in the table (i.e. We don't free the entries' data pointer).
  88  *
  89  * \param table the hash table to delete.
  90  */
  91 void
  92 _eglDeleteHashTable(_EGLHashtable *table)
  93 {
  94    EGLuint i;
  95    assert(table);
  96    for (i = 0; i < TABLE_SIZE; i++) {
  97       _EGLHashentry *entry = table->Table[i];
  98       while (entry) {
  99          _EGLHashentry *next = entry->Next;
 100          free(entry);
 101          entry = next;
 102       }
 103    }
 104    _eglDestroyMutex(table->Mutex);
 105    free(table);
 106 }
 107
 108
 109
 110 /**
 111  * Lookup an entry in the hash table.
 112  *
 113  * \param table the hash table.
 114  * \param key the key.
 115  *
 116  * \return pointer to user's data or NULL if key not in table
 117  */
 118 void *
 119 _eglHashLookup(const _EGLHashtable *table, EGLuint key)
 120 {
 121    EGLuint pos;
 122    const _EGLHashentry *entry;
 123
 124    assert(table);
 125
 126    if (!key)
 127       return NULL;
 128
 129    pos = HASH_FUNC(key);
 130    entry = table->Table[pos];
 131    while (entry) {
 132       if (entry->Key == key) {
 133          return entry->Data;
 134       }
 135       entry = entry->Next;
 136    }
 137    return NULL;
 138 }
 139
 140
 141
 142 /**
 143  * Insert a key/pointer pair into the hash table.
 144  * If an entry with this key already exists we'll replace the existing entry.
 145  *
 146  * \param table the hash table.
 147  * \param key the key (not zero).
 148  * \param data pointer to user data.
 149  */
 150 void
 151 _eglHashInsert(_EGLHashtable *table, EGLuint key, void *data)
 152 {
 153    /* search for existing entry with this key */
 154    EGLuint pos;
 155    _EGLHashentry *entry;
 156
 157    assert(table);
 158    assert(key);
 159
 160    _eglLockMutex(table->Mutex);
 161
 162    if (key > table->MaxKey)
 163       table->MaxKey = key;
 164
 165    pos = HASH_FUNC(key);
 166    entry = table->Table[pos];
 167    while (entry) {
 168       if (entry->Key == key) {
 169          /* replace entry's data */
 170          entry->Data = data;
 171          _eglUnlockMutex(table->Mutex);
 172          return;
 173       }
 174       entry = entry->Next;
 175    }
 176
 177    /* alloc and insert new table entry */
 178    entry = (_EGLHashentry *) malloc(sizeof(_EGLHashentry));
 179    entry->Key = key;
 180    entry->Data = data;
 181    entry->Next = table->Table[pos];
 182    table->Table[pos] = entry;
 183
 184    _eglUnlockMutex(table->Mutex);
 185 }
 186
 187
 188
 189 /**
 190  * Remove an entry from the hash table.
 191  *
 192  * \param table the hash table.
 193  * \param key key of entry to remove.
 194  *
 195  * While holding the hash table's lock, searches the entry with the matching
 196  * key and unlinks it.
 197  */
 198 void
 199 _eglHashRemove(_EGLHashtable *table, EGLuint key)
 200 {
 201    EGLuint pos;
 202    _EGLHashentry *entry, *prev;
 203
 204    assert(table);
 205    assert(key);
 206
 207    _eglLockMutex(table->Mutex);
 208
 209    pos = HASH_FUNC(key);
 210    prev = NULL;
 211    entry = table->Table[pos];
 212    while (entry) {
 213       if (entry->Key == key) {
 214          /* found it! */
 215          if (prev) {
 216             prev->Next = entry->Next;
 217          }
 218          else {
 219             table->Table[pos] = entry->Next;
 220          }
 221          free(entry);
 222          _eglUnlockMutex(table->Mutex);
 223          return;
 224       }
 225       prev = entry;
 226       entry = entry->Next;
 227    }
 228
 229    _eglUnlockMutex(table->Mutex);
 230 }
 231
 232
 233
 234 /**
 235  * Get the key of the "first" entry in the hash table.
 236  *
 237  * This is used in the course of deleting all display lists when
 238  * a context is destroyed.
 239  *
 240  * \param table the hash table
 241  *
 242  * \return key for the "first" entry in the hash table.
 243  *
 244  * While holding the lock, walks through all table positions until finding
 245  * the first entry of the first non-empty one.
 246  */
 247 EGLuint
 248 _eglHashFirstEntry(_EGLHashtable *table)
 249 {
 250    EGLuint pos;
 251    assert(table);
 252    _eglLockMutex(table->Mutex);
 253    for (pos = 0; pos < TABLE_SIZE; pos++) {
 254       if (table->Table[pos]) {
 255          _eglUnlockMutex(table->Mutex);
 256          return table->Table[pos]->Key;
 257       }
 258    }
 259    _eglUnlockMutex(table->Mutex);
 260    return 0;
 261 }
 262
 263
 264 /**
 265  * Given a hash table key, return the next key.  This is used to walk
 266  * over all entries in the table.  Note that the keys returned during
 267  * walking won't be in any particular order.
 268  * \return next hash key or 0 if end of table.
 269  */
 270 EGLuint
 271 _eglHashNextEntry(const _EGLHashtable *table, EGLuint key)
 272 {
 273    const _EGLHashentry *entry;
 274    EGLuint pos;
 275
 276    assert(table);
 277    assert(key);
 278
 279    /* Find the entry with given key */
 280    pos = HASH_FUNC(key);
 281    entry = table->Table[pos];
 282    while (entry) {
 283       if (entry->Key == key) {
 284          break;
 285       }
 286       entry = entry->Next;
 287    }
 288
 289    if (!entry) {
 290       /* the key was not found, we can't find next entry */
 291       return 0;
 292    }
 293
 294    if (entry->Next) {
 295       /* return next in linked list */
 296       return entry->Next->Key;
 297    }
 298    else {
 299       /* look for next non-empty table slot */
 300       pos++;
 301       while (pos < TABLE_SIZE) {
 302          if (table->Table[pos]) {
 303             return table->Table[pos]->Key;
 304          }
 305          pos++;
 306       }
 307       return 0;
 308    }
 309 }
 310
 311
 312 /**
 313  * Dump contents of hash table for debugging.
 314  *
 315  * \param table the hash table.
 316  */
 317 void
 318 _eglHashPrint(const _EGLHashtable *table)
 319 {
 320    EGLuint i;
 321    assert(table);
 322    for (i = 0; i < TABLE_SIZE; i++) {
 323       const _EGLHashentry *entry = table->Table[i];
 324       while (entry) {
 325          printf("%u %p\n", entry->Key, entry->Data);
 326          entry = entry->Next;
 327       }
 328    }
 329 }
 330
 331
 332
 333 /**
 334  * Return a new, unused hash key.
 335  */
 336 EGLuint
 337 _eglHashGenKey(_EGLHashtable *table)
 338 {
 339    EGLuint k;
 340
 341    _eglLockMutex(table->Mutex);
 342    k = table->MaxKey;
 343    table->MaxKey++;
 344    _eglUnlockMutex(table->Mutex);
 345    return k;
 346 }
 347