X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Fmesa%2Fmain%2Fhash.c;h=61c369a80cdada0d2fc67562875942a5fd92e877;hb=d012e6d8fe2f4f1139af9e47a684960e8cde103e;hp=0861af1055d83c8a33c3c2f8fae52e583d25ac58;hpb=5f92c38f0efddf575466381a2ab47046255b29f1;p=mesa.git

diff --git a/src/mesa/main/hash.c b/src/mesa/main/hash.c
index 0861af1055d..61c369a80cd 100644
--- a/src/mesa/main/hash.c
+++ b/src/mesa/main/hash.c
@@ -12,9 +12,9 @@
 
 /*
  * Mesa 3-D graphics library
- * Version:  6.3
+ * Version:  6.5.1
  *
- * Copyright (C) 1999-2005  Brian Paul   All Rights Reserved.
+ * Copyright (C) 1999-2006  Brian Paul   All Rights Reserved.
  *
  * Permission is hereby granted, free of charge, to any person obtaining a
  * copy of this software and associated documentation files (the "Software"),
@@ -37,16 +37,17 @@
 
 #include "glheader.h"
 #include "imports.h"
-#include "glthread.h"
+#include "glapi/glthread.h"
 #include "hash.h"
 
 
-#define TABLE_SIZE 1024  /**< Size of lookup table/array */
+#define TABLE_SIZE 1023  /**< Size of lookup table/array */
+
+#define HASH_FUNC(K)  ((K) % TABLE_SIZE)
+
 
 /**
  * An entry in the hash table.  
- *
- * This struct is private to this file.
  */
 struct HashEntry {
    GLuint Key;             /**< the entry's key */
@@ -54,18 +55,20 @@ struct HashEntry {
    struct HashEntry *Next; /**< pointer to next entry */
 };
 
+
 /**
  * The hash table data structure.  
- *
- * This is an opaque types (it's not defined in hash.h file).
  */
 struct _mesa_HashTable {
    struct HashEntry *Table[TABLE_SIZE];  /**< the lookup table */
    GLuint MaxKey;                        /**< highest key inserted so far */
    _glthread_Mutex Mutex;                /**< mutual exclusion lock */
+   _glthread_Mutex WalkMutex;            /**< for _mesa_HashWalk() */
+   GLboolean InDeleteAll;                /**< Debug check */
 };
 
 
+
 /**
  * Create a new hash table.
  * 
@@ -77,6 +80,7 @@ _mesa_NewHashTable(void)
    struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable);
    if (table) {
       _glthread_INIT_MUTEX(table->Mutex);
+      _glthread_INIT_MUTEX(table->WalkMutex);
    }
    return table;
 }
@@ -94,32 +98,33 @@ _mesa_NewHashTable(void)
 void
 _mesa_DeleteHashTable(struct _mesa_HashTable *table)
 {
-   GLuint i;
+   GLuint pos;
    assert(table);
-   for (i = 0; i < TABLE_SIZE; i++) {
-      struct HashEntry *entry = table->Table[i];
+   for (pos = 0; pos < TABLE_SIZE; pos++) {
+      struct HashEntry *entry = table->Table[pos];
       while (entry) {
 	 struct HashEntry *next = entry->Next;
-	 FREE(entry);
+         if (entry->Data) {
+            _mesa_problem(NULL,
+                          "In _mesa_DeleteHashTable, found non-freed data");
+         }
+	 free(entry);
 	 entry = next;
       }
    }
    _glthread_DESTROY_MUTEX(table->Mutex);
-   FREE(table);
+   _glthread_DESTROY_MUTEX(table->WalkMutex);
+   free(table);
 }
 
 
 
 /**
- * Lookup an entry in the hash table.
- * 
- * \param table the hash table.
- * \param key the key.
- * 
- * \return pointer to user's data or NULL if key not in table
+ * Lookup an entry in the hash table, without locking.
+ * \sa _mesa_HashLookup
  */
-void *
-_mesa_HashLookup(const struct _mesa_HashTable *table, GLuint key)
+static inline void *
+_mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key)
 {
    GLuint pos;
    const struct HashEntry *entry;
@@ -127,11 +132,11 @@ _mesa_HashLookup(const struct _mesa_HashTable *table, GLuint key)
    assert(table);
    assert(key);
 
-   pos = key & (TABLE_SIZE-1);
+   pos = HASH_FUNC(key);
    entry = table->Table[pos];
    while (entry) {
       if (entry->Key == key) {
-	 return entry->Data;
+         return entry->Data;
       }
       entry = entry->Next;
    }
@@ -139,6 +144,25 @@ _mesa_HashLookup(const struct _mesa_HashTable *table, GLuint key)
 }
 
 
+/**
+ * Lookup an entry in the hash table.
+ * 
+ * \param table the hash table.
+ * \param key the key.
+ * 
+ * \return pointer to user's data or NULL if key not in table
+ */
+void *
+_mesa_HashLookup(struct _mesa_HashTable *table, GLuint key)
+{
+   void *res;
+   assert(table);
+   _glthread_LOCK_MUTEX(table->Mutex);
+   res = _mesa_HashLookup_unlocked(table, key);
+   _glthread_UNLOCK_MUTEX(table->Mutex);
+   return res;
+}
+
 
 /**
  * Insert a key/pointer pair into the hash table.  
@@ -163,24 +187,31 @@ _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)
    if (key > table->MaxKey)
       table->MaxKey = key;
 
-   pos = key & (TABLE_SIZE-1);
-   entry = table->Table[pos];
-   while (entry) {
+   pos = HASH_FUNC(key);
+
+   /* check if replacing an existing entry with same key */
+   for (entry = table->Table[pos]; entry; entry = entry->Next) {
       if (entry->Key == key) {
          /* replace entry's data */
+#if 0 /* not sure this check is always valid */
+         if (entry->Data) {
+            _mesa_problem(NULL, "Memory leak detected in _mesa_HashInsert");
+         }
+#endif
 	 entry->Data = data;
          _glthread_UNLOCK_MUTEX(table->Mutex);
 	 return;
       }
-      entry = entry->Next;
    }
 
    /* alloc and insert new table entry */
    entry = MALLOC_STRUCT(HashEntry);
-   entry->Key = key;
-   entry->Data = data;
-   entry->Next = table->Table[pos];
-   table->Table[pos] = entry;
+   if (entry) {
+      entry->Key = key;
+      entry->Data = data;
+      entry->Next = table->Table[pos];
+      table->Table[pos] = entry;
+   }
 
    _glthread_UNLOCK_MUTEX(table->Mutex);
 }
@@ -205,9 +236,16 @@ _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
    assert(table);
    assert(key);
 
+   /* have to check this outside of mutex lock */
+   if (table->InDeleteAll) {
+      _mesa_problem(NULL, "_mesa_HashRemove illegally called from "
+                    "_mesa_HashDeleteAll callback function");
+      return;
+   }
+
    _glthread_LOCK_MUTEX(table->Mutex);
 
-   pos = key & (TABLE_SIZE-1);
+   pos = HASH_FUNC(key);
    prev = NULL;
    entry = table->Table[pos];
    while (entry) {
@@ -219,7 +257,7 @@ _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
          else {
             table->Table[pos] = entry->Next;
          }
-         FREE(entry);
+         free(entry);
          _glthread_UNLOCK_MUTEX(table->Mutex);
 	 return;
       }
@@ -233,17 +271,80 @@ _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
 
 
 /**
- * Get the key of the "first" entry in the hash table.
- * 
- * This is used in the course of deleting all display lists when
- * a context is destroyed.
- * 
- * \param table the hash table
- * 
- * \return key for the "first" entry in the hash table.
+ * Delete all entries in a hash table, but don't delete the table itself.
+ * Invoke the given callback function for each table entry.
  *
+ * \param table  the hash table to delete
+ * \param callback  the callback function
+ * \param userData  arbitrary pointer to pass along to the callback
+ *                  (this is typically a struct gl_context pointer)
+ */
+void
+_mesa_HashDeleteAll(struct _mesa_HashTable *table,
+                    void (*callback)(GLuint key, void *data, void *userData),
+                    void *userData)
+{
+   GLuint pos;
+   ASSERT(table);
+   ASSERT(callback);
+   _glthread_LOCK_MUTEX(table->Mutex);
+   table->InDeleteAll = GL_TRUE;
+   for (pos = 0; pos < TABLE_SIZE; pos++) {
+      struct HashEntry *entry, *next;
+      for (entry = table->Table[pos]; entry; entry = next) {
+         callback(entry->Key, entry->Data, userData);
+         next = entry->Next;
+         free(entry);
+      }
+      table->Table[pos] = NULL;
+   }
+   table->InDeleteAll = GL_FALSE;
+   _glthread_UNLOCK_MUTEX(table->Mutex);
+}
+
+
+/**
+ * Walk over all entries in a hash table, calling callback function for each.
+ * Note: we use a separate mutex in this function to avoid a recursive
+ * locking deadlock (in case the callback calls _mesa_HashRemove()) and to
+ * prevent multiple threads/contexts from getting tangled up.
+ * A lock-less version of this function could be used when the table will
+ * not be modified.
+ * \param table  the hash table to walk
+ * \param callback  the callback function
+ * \param userData  arbitrary pointer to pass along to the callback
+ *                  (this is typically a struct gl_context pointer)
+ */
+void
+_mesa_HashWalk(const struct _mesa_HashTable *table,
+               void (*callback)(GLuint key, void *data, void *userData),
+               void *userData)
+{
+   /* cast-away const */
+   struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table;
+   GLuint pos;
+   ASSERT(table);
+   ASSERT(callback);
+   _glthread_LOCK_MUTEX(table2->WalkMutex);
+   for (pos = 0; pos < TABLE_SIZE; pos++) {
+      struct HashEntry *entry, *next;
+      for (entry = table->Table[pos]; entry; entry = next) {
+         /* save 'next' pointer now in case the callback deletes the entry */
+         next = entry->Next;
+         callback(entry->Key, entry->Data, userData);
+      }
+   }
+   _glthread_UNLOCK_MUTEX(table2->WalkMutex);
+}
+
+
+/**
+ * Return the key of the "first" entry in the hash table.
  * While holding the lock, walks through all table positions until finding
  * the first entry of the first non-empty one.
+ * 
+ * \param table  the hash table
+ * \return key for the "first" entry in the hash table.
  */
 GLuint
 _mesa_HashFirstEntry(struct _mesa_HashTable *table)
@@ -251,7 +352,7 @@ _mesa_HashFirstEntry(struct _mesa_HashTable *table)
    GLuint pos;
    assert(table);
    _glthread_LOCK_MUTEX(table->Mutex);
-   for (pos=0; pos < TABLE_SIZE; pos++) {
+   for (pos = 0; pos < TABLE_SIZE; pos++) {
       if (table->Table[pos]) {
          _glthread_UNLOCK_MUTEX(table->Mutex);
          return table->Table[pos]->Key;
@@ -278,17 +379,15 @@ _mesa_HashNextEntry(const struct _mesa_HashTable *table, GLuint key)
    assert(key);
 
    /* Find the entry with given key */
-   pos = key & (TABLE_SIZE - 1);
-   entry = table->Table[pos];
-   while (entry) {
+   pos = HASH_FUNC(key);
+   for (entry = table->Table[pos]; entry ; entry = entry->Next) {
       if (entry->Key == key) {
          break;
       }
-      entry = entry->Next;
    }
 
    if (!entry) {
-      /* the key was not found, we can't find next entry */
+      /* the given key was not found, so we can't find the next entry */
       return 0;
    }
 
@@ -318,10 +417,10 @@ _mesa_HashNextEntry(const struct _mesa_HashTable *table, GLuint key)
 void
 _mesa_HashPrint(const struct _mesa_HashTable *table)
 {
-   GLuint i;
+   GLuint pos;
    assert(table);
-   for (i=0;i<TABLE_SIZE;i++) {
-      const struct HashEntry *entry = table->Table[i];
+   for (pos = 0; pos < TABLE_SIZE; pos++) {
+      const struct HashEntry *entry = table->Table[pos];
       while (entry) {
 	 _mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data);
 	 entry = entry->Next;
@@ -347,7 +446,7 @@ _mesa_HashPrint(const struct _mesa_HashTable *table)
 GLuint
 _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
 {
-   GLuint maxKey = ~((GLuint) 0);
+   const GLuint maxKey = ~((GLuint) 0);
    _glthread_LOCK_MUTEX(table->Mutex);
    if (maxKey - numKeys > table->MaxKey) {
       /* the quick solution */
@@ -359,8 +458,8 @@ _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
       GLuint freeCount = 0;
       GLuint freeStart = 1;
       GLuint key;
-      for (key=1; key!=maxKey; key++) {
-	 if (_mesa_HashLookup(table, key)) {
+      for (key = 1; key != maxKey; key++) {
+	 if (_mesa_HashLookup_unlocked(table, key)) {
 	    /* darn, this key is already in use */
 	    freeCount = 0;
 	    freeStart = key+1;
@@ -381,6 +480,28 @@ _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
 }
 
 
+/**
+ * Return the number of entries in the hash table.
+ */
+GLuint
+_mesa_HashNumEntries(const struct _mesa_HashTable *table)
+{
+   GLuint pos, count = 0;
+
+   for (pos = 0; pos < TABLE_SIZE; pos++) {
+      const struct HashEntry *entry;
+      for (entry = table->Table[pos]; entry; entry = entry->Next) {
+         count++;
+      }
+   }
+
+   return count;
+}
+
+
+
+#if 0 /* debug only */
+
 /**
  * Test walking over all the entries in a hash table.
  */
@@ -442,3 +563,5 @@ _mesa_test_hash_functions(void)
 
    test_hash_walking();
 }
+
+#endif