1f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 2f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \file hash.c 3f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Generic hash table. 4f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 5f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Used for display lists, texture objects, vertex/fragment programs, 6f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * buffer objects, etc. The hash functions are thread-safe. 7f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 8f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \note key=0 is illegal. 9f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 10f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \author Brian Paul 11f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 12f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 13f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/* 14f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Mesa 3-D graphics library 15f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Version: 6.5.1 16f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 17f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Copyright (C) 1999-2006 Brian Paul All Rights Reserved. 18f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 19f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Permission is hereby granted, free of charge, to any person obtaining a 20f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * copy of this software and associated documentation files (the "Software"), 21f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * to deal in the Software without restriction, including without limitation 22f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * the rights to use, copy, modify, merge, publish, distribute, sublicense, 23f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * and/or sell copies of the Software, and to permit persons to whom the 24f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Software is furnished to do so, subject to the following conditions: 25f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 26f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * The above copyright notice and this permission notice shall be included 27f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * in all copies or substantial portions of the Software. 28f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 29f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 30f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 31f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 32f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 33f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 34f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 35f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 36f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 37f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 38f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "glheader.h" 39f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "imports.h" 40f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "glapi/glthread.h" 41f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "hash.h" 42f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 43f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 44f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define TABLE_SIZE 1023 /**< Size of lookup table/array */ 45f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 46f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define HASH_FUNC(K) ((K) % TABLE_SIZE) 47f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 48f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 49f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 50f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * An entry in the hash table. 51f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 52f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstruct HashEntry { 53f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint Key; /**< the entry's key */ 54f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *Data; /**< the entry's data */ 55f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct HashEntry *Next; /**< pointer to next entry */ 56f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 57f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 58f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 59f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 60f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * The hash table data structure. 61f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 62f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstruct _mesa_HashTable { 63f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct HashEntry *Table[TABLE_SIZE]; /**< the lookup table */ 64f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint MaxKey; /**< highest key inserted so far */ 65f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_Mutex Mutex; /**< mutual exclusion lock */ 66f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_Mutex WalkMutex; /**< for _mesa_HashWalk() */ 67f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLboolean InDeleteAll; /**< Debug check */ 68f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 69f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 70f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 71f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 72f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 73f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Create a new hash table. 74f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 75f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \return pointer to a new, empty hash table. 76f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 77f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstruct _mesa_HashTable * 78f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_NewHashTable(void) 79f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 80f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable); 81f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (table) { 82f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_INIT_MUTEX(table->Mutex); 83f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_INIT_MUTEX(table->WalkMutex); 84f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 85f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return table; 86f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 87f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 88f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 89f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 90f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 91f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Delete a hash table. 92f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Frees each entry on the hash table and then the hash table structure itself. 93f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Note that the caller should have already traversed the table and deleted 94f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * the objects in the table (i.e. We don't free the entries' data pointer). 95f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 96f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param table the hash table to delete. 97f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 98f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 99f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_DeleteHashTable(struct _mesa_HashTable *table) 100f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 101f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint pos; 102f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(table); 103f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (pos = 0; pos < TABLE_SIZE; pos++) { 104f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct HashEntry *entry = table->Table[pos]; 105f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (entry) { 106f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct HashEntry *next = entry->Next; 107f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (entry->Data) { 108f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _mesa_problem(NULL, 109f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org "In _mesa_DeleteHashTable, found non-freed data"); 110f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 111f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org free(entry); 112f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = next; 113f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 114f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 115f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_DESTROY_MUTEX(table->Mutex); 116f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_DESTROY_MUTEX(table->WalkMutex); 117f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org free(table); 118f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 119f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 120f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 121f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 122f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 123f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Lookup an entry in the hash table, without locking. 124f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \sa _mesa_HashLookup 125f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 126f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstatic inline void * 127f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key) 128f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 129f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint pos; 130f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const struct HashEntry *entry; 131f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 132f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(table); 133f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(key); 134f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 135f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = HASH_FUNC(key); 136f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = table->Table[pos]; 137f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (entry) { 138f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (entry->Key == key) { 139f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return entry->Data; 140f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 141f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = entry->Next; 142f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 143f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return NULL; 144f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 145f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 146f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 147f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 148f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Lookup an entry in the hash table. 149f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 150f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param table the hash table. 151f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param key the key. 152f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 153f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \return pointer to user's data or NULL if key not in table 154f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 155f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid * 156f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_HashLookup(struct _mesa_HashTable *table, GLuint key) 157f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 158f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *res; 159f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(table); 160f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_LOCK_MUTEX(table->Mutex); 161f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org res = _mesa_HashLookup_unlocked(table, key); 162f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_UNLOCK_MUTEX(table->Mutex); 163f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return res; 164f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 165f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 166f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 167f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 168f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Insert a key/pointer pair into the hash table. 169f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * If an entry with this key already exists we'll replace the existing entry. 170f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 171f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param table the hash table. 172f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param key the key (not zero). 173f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param data pointer to user data. 174f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 175f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 176f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data) 177f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 178f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* search for existing entry with this key */ 179f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint pos; 180f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct HashEntry *entry; 181f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 182f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(table); 183f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(key); 184f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 185f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_LOCK_MUTEX(table->Mutex); 186f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 187f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (key > table->MaxKey) 188f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org table->MaxKey = key; 189f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 190f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = HASH_FUNC(key); 191f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 192f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* check if replacing an existing entry with same key */ 193f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (entry = table->Table[pos]; entry; entry = entry->Next) { 194f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (entry->Key == key) { 195f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* replace entry's data */ 196f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#if 0 /* not sure this check is always valid */ 197f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (entry->Data) { 198f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _mesa_problem(NULL, "Memory leak detected in _mesa_HashInsert"); 199f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 200f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#endif 201f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry->Data = data; 202f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_UNLOCK_MUTEX(table->Mutex); 203f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return; 204f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 205f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 206f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 207f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* alloc and insert new table entry */ 208f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = MALLOC_STRUCT(HashEntry); 209f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (entry) { 210f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry->Key = key; 211f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry->Data = data; 212f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry->Next = table->Table[pos]; 213f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org table->Table[pos] = entry; 214f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 215f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 216f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_UNLOCK_MUTEX(table->Mutex); 217f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 218f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 219f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 220f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 221f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 222f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Remove an entry from the hash table. 223f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 224f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param table the hash table. 225f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param key key of entry to remove. 226f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 227f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * While holding the hash table's lock, searches the entry with the matching 228f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * key and unlinks it. 229f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 230f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 231f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_HashRemove(struct _mesa_HashTable *table, GLuint key) 232f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 233f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint pos; 234f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct HashEntry *entry, *prev; 235f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 236f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(table); 237f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(key); 238f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 239f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* have to check this outside of mutex lock */ 240f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (table->InDeleteAll) { 241f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _mesa_problem(NULL, "_mesa_HashRemove illegally called from " 242f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org "_mesa_HashDeleteAll callback function"); 243f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return; 244f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 245f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 246f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_LOCK_MUTEX(table->Mutex); 247f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 248f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = HASH_FUNC(key); 249f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org prev = NULL; 250f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = table->Table[pos]; 251f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (entry) { 252f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (entry->Key == key) { 253f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* found it! */ 254f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (prev) { 255f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org prev->Next = entry->Next; 256f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 257f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else { 258f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org table->Table[pos] = entry->Next; 259f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 260f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org free(entry); 261f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_UNLOCK_MUTEX(table->Mutex); 262f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return; 263f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 264f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org prev = entry; 265f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = entry->Next; 266f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 267f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 268f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_UNLOCK_MUTEX(table->Mutex); 269f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 270f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 271f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 272f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 273f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 274f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Delete all entries in a hash table, but don't delete the table itself. 275f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Invoke the given callback function for each table entry. 276f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 277f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param table the hash table to delete 278f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param callback the callback function 279f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param userData arbitrary pointer to pass along to the callback 280f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * (this is typically a struct gl_context pointer) 281f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 282f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 283f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_HashDeleteAll(struct _mesa_HashTable *table, 284f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void (*callback)(GLuint key, void *data, void *userData), 285f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *userData) 286f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 287f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint pos; 288f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ASSERT(table); 289f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ASSERT(callback); 290f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_LOCK_MUTEX(table->Mutex); 291f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org table->InDeleteAll = GL_TRUE; 292f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (pos = 0; pos < TABLE_SIZE; pos++) { 293f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct HashEntry *entry, *next; 294f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (entry = table->Table[pos]; entry; entry = next) { 295f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org callback(entry->Key, entry->Data, userData); 296f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org next = entry->Next; 297f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org free(entry); 298f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 299f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org table->Table[pos] = NULL; 300f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 301f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org table->InDeleteAll = GL_FALSE; 302f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_UNLOCK_MUTEX(table->Mutex); 303f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 304f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 305f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 306f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 307f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Walk over all entries in a hash table, calling callback function for each. 308f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Note: we use a separate mutex in this function to avoid a recursive 309f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * locking deadlock (in case the callback calls _mesa_HashRemove()) and to 310f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * prevent multiple threads/contexts from getting tangled up. 311f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * A lock-less version of this function could be used when the table will 312f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * not be modified. 313f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param table the hash table to walk 314f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param callback the callback function 315f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param userData arbitrary pointer to pass along to the callback 316f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * (this is typically a struct gl_context pointer) 317f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 318f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 319f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_HashWalk(const struct _mesa_HashTable *table, 320f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void (*callback)(GLuint key, void *data, void *userData), 321f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org void *userData) 322f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 323f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* cast-away const */ 324f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table; 325f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint pos; 326f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ASSERT(table); 327f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ASSERT(callback); 328f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_LOCK_MUTEX(table2->WalkMutex); 329f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (pos = 0; pos < TABLE_SIZE; pos++) { 330f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct HashEntry *entry, *next; 331f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (entry = table->Table[pos]; entry; entry = next) { 332f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* save 'next' pointer now in case the callback deletes the entry */ 333f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org next = entry->Next; 334f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org callback(entry->Key, entry->Data, userData); 335f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 336f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 337f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_UNLOCK_MUTEX(table2->WalkMutex); 338f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 339f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 340f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 341f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 342f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Return the key of the "first" entry in the hash table. 343f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * While holding the lock, walks through all table positions until finding 344f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * the first entry of the first non-empty one. 345f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 346f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param table the hash table 347f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \return key for the "first" entry in the hash table. 348f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 349f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgGLuint 350f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_HashFirstEntry(struct _mesa_HashTable *table) 351f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 352f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint pos; 353f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(table); 354f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_LOCK_MUTEX(table->Mutex); 355f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (pos = 0; pos < TABLE_SIZE; pos++) { 356f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (table->Table[pos]) { 357f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_UNLOCK_MUTEX(table->Mutex); 358f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return table->Table[pos]->Key; 359f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 360f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 361f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_UNLOCK_MUTEX(table->Mutex); 362f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return 0; 363f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 364f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 365f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 366f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 367f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Given a hash table key, return the next key. This is used to walk 368f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * over all entries in the table. Note that the keys returned during 369f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * walking won't be in any particular order. 370f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \return next hash key or 0 if end of table. 371f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 372f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgGLuint 373f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_HashNextEntry(const struct _mesa_HashTable *table, GLuint key) 374f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 375f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const struct HashEntry *entry; 376f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint pos; 377f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 378f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(table); 379f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(key); 380f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 381f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* Find the entry with given key */ 382f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = HASH_FUNC(key); 383f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (entry = table->Table[pos]; entry ; entry = entry->Next) { 384f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (entry->Key == key) { 385f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 386f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 387f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 388f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 389f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!entry) { 390f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* the given key was not found, so we can't find the next entry */ 391f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return 0; 392f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 393f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 394f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (entry->Next) { 395f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* return next in linked list */ 396f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return entry->Next->Key; 397f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 398f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else { 399f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* look for next non-empty table slot */ 400f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos++; 401f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (pos < TABLE_SIZE) { 402f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (table->Table[pos]) { 403f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return table->Table[pos]->Key; 404f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 405f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos++; 406f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 407f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return 0; 408f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 409f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 410f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 411f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 412f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 413f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Dump contents of hash table for debugging. 414f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 415f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param table the hash table. 416f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 417f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 418f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_HashPrint(const struct _mesa_HashTable *table) 419f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 420f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint pos; 421f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(table); 422f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (pos = 0; pos < TABLE_SIZE; pos++) { 423f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const struct HashEntry *entry = table->Table[pos]; 424f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (entry) { 425f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data); 426f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org entry = entry->Next; 427f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 428f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 429f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 430f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 431f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 432f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 433f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 434f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Find a block of adjacent unused hash keys. 435f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 436f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param table the hash table. 437f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param numKeys number of keys needed. 438f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 439f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \return Starting key of free block or 0 if failure. 440f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 441f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * If there are enough free keys between the maximum key existing in the table 442f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * (_mesa_HashTable::MaxKey) and the maximum key possible, then simply return 443f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * the adjacent key. Otherwise do a full search for a free key block in the 444f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * allowable key range. 445f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 446f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgGLuint 447f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys) 448f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 449f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const GLuint maxKey = ~((GLuint) 0); 450f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_LOCK_MUTEX(table->Mutex); 451f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (maxKey - numKeys > table->MaxKey) { 452f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* the quick solution */ 453f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_UNLOCK_MUTEX(table->Mutex); 454f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return table->MaxKey + 1; 455f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 456f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else { 457f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* the slow solution */ 458f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint freeCount = 0; 459f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint freeStart = 1; 460f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint key; 461f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (key = 1; key != maxKey; key++) { 462f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (_mesa_HashLookup_unlocked(table, key)) { 463f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* darn, this key is already in use */ 464f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org freeCount = 0; 465f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org freeStart = key+1; 466f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 467f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else { 468f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* this key not in use, check if we've found enough */ 469f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org freeCount++; 470f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (freeCount == numKeys) { 471f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_UNLOCK_MUTEX(table->Mutex); 472f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return freeStart; 473f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 474f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 475f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 476f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* cannot allocate a block of numKeys consecutive keys */ 477f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _glthread_UNLOCK_MUTEX(table->Mutex); 478f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return 0; 479f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 480f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 481f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 482f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 483f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 484f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Return the number of entries in the hash table. 485f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 486f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgGLuint 487f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_HashNumEntries(const struct _mesa_HashTable *table) 488f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 489f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint pos, count = 0; 490f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 491f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (pos = 0; pos < TABLE_SIZE; pos++) { 492f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const struct HashEntry *entry; 493f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (entry = table->Table[pos]; entry; entry = entry->Next) { 494f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org count++; 495f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 496f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 497f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 498f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return count; 499f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 500f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 501f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 502f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 503f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#if 0 /* debug only */ 504f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 505f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 506f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Test walking over all the entries in a hash table. 507f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 508f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstatic void 509f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgtest_hash_walking(void) 510f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 511f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct _mesa_HashTable *t = _mesa_NewHashTable(); 512f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const GLuint limit = 50000; 513f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint i; 514f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 515f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* create some entries */ 516f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (i = 0; i < limit; i++) { 517f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint dummy; 518f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint k = (rand() % (limit * 10)) + 1; 519f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (_mesa_HashLookup(t, k)) { 520f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* id already in use, try another */ 521f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org k = (rand() % (limit * 10)) + 1; 522f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 523f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _mesa_HashInsert(t, k, &dummy); 524f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 525f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 526f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* walk over all entries */ 527f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 528f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint k = _mesa_HashFirstEntry(t); 529f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint count = 0; 530f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (k) { 531f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org GLuint knext = _mesa_HashNextEntry(t, k); 532f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(knext != k); 533f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _mesa_HashRemove(t, k); 534f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org count++; 535f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org k = knext; 536f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 537f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(count == limit); 538f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org k = _mesa_HashFirstEntry(t); 539f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(k==0); 540f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 541f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 542f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _mesa_DeleteHashTable(t); 543f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 544f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 545f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 546f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 547f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org_mesa_test_hash_functions(void) 548f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 549f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int a, b, c; 550f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct _mesa_HashTable *t; 551f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 552f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org t = _mesa_NewHashTable(); 553f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _mesa_HashInsert(t, 501, &a); 554f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _mesa_HashInsert(t, 10, &c); 555f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _mesa_HashInsert(t, 0xfffffff8, &b); 556f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /*_mesa_HashPrint(t);*/ 557f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 558f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(_mesa_HashLookup(t,501)); 559f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(!_mesa_HashLookup(t,1313)); 560f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(_mesa_HashFindFreeKeyBlock(t, 100)); 561f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 562f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _mesa_DeleteHashTable(t); 563f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 564f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org test_hash_walking(); 565f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 566f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 567f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#endif 568