hash.c File Reference

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include "hash.h"

Include dependency graph for hash.c:

Go to the source code of this file.

Classes
struct	HashEntry
struct	HashTable

Macros
#define	TABLE_SIZE   1001

Functions
struct HashTable *	NewHashTable (void)
void	DeleteHashTable (struct HashTable *table)
void *	HashLookup (const struct HashTable *table, GLuint key)
void	HashInsert (struct HashTable *table, GLuint key, void *data)
void	HashRemove (struct HashTable *table, GLuint key)
GLuint	HashFirstEntry (const struct HashTable *table)
void	HashPrint (const struct HashTable *table)
GLuint	HashFindFreeKeyBlock (const struct HashTable *table, GLuint numKeys)

Macro Definition Documentation

TABLE_SIZE

#define TABLE_SIZE   1001

Definition at line 59 of file hash.c.

Function Documentation

DeleteHashTable()

void DeleteHashTable

(

struct HashTable *

table

)

Definition at line 87 of file hash.c.

{
   GLuint i;
   assert(table);
   for (i=0;i<TABLE_SIZE;i++) {
      struct HashEntry *entry = table->Table[i];
      while (entry) {
     struct HashEntry *next = entry->Next;
     free(entry);
     entry = next;
      }
   }
   free(table);
}

Referenced by alloc_shared_state(), and free_shared_state().

HashFindFreeKeyBlock()

GLuint HashFindFreeKeyBlock	(	const struct HashTable *	table,
		GLuint	numKeys
	)

Definition at line 248 of file hash.c.

{
   GLuint maxKey = ~((GLuint) 0);
   if (maxKey - numKeys > table->MaxKey) {
      /* the quick solution */
      return table->MaxKey + 1;
   }
   else {
      /* the slow solution */
      GLuint freeCount = 0;
      GLuint freeStart = 0;
      GLuint key;
      for (key=0; key!=maxKey; key++) {
     if (HashLookup(table, key)) {
        /* darn, this key is already in use */
        freeCount = 0;
        freeStart = key+1;
     }
     else {
        /* this key not in use, check if we've found enough */
        freeCount++;
        if (freeCount == numKeys) {
           return freeStart;
        }
     }
      }
      /* cannot allocate a block of numKeys consecutive keys */
      return 0;
   }
}

Referenced by gl_GenLists(), and gl_GenTextures().

HashFirstEntry()

GLuint HashFirstEntry

(

const struct HashTable *

table

)

Definition at line 211 of file hash.c.

{
   GLuint pos;
   assert(table);
   for (pos=0; pos < TABLE_SIZE; pos++) {
      if (table->Table[pos])
         return table->Table[pos]->Key;
   }
   return 0;
}

Referenced by free_shared_state().

HashInsert()

void HashInsert	(	struct HashTable *	table,
		GLuint	key,
		void *	data
	)

Definition at line 138 of file hash.c.

{
   /* search for existing entry with this key */
   GLuint pos;
   struct HashEntry *entry;

   assert(table);
   assert(key);

   if (key > table->MaxKey)
      table->MaxKey = key;

   pos = key % TABLE_SIZE;
   entry = table->Table[pos];
   while (entry) {
      if (entry->Key == key) {
         /* replace entry's data */
     entry->Data = data;
     return;
      }
      entry = entry->Next;
   }

   /* alloc and insert new table entry */
   entry = (struct HashEntry *) calloc(sizeof(struct HashEntry), 1);
   entry->Key = key;
   entry->Data = data;
   entry->Next = table->Table[pos];
   table->Table[pos] = entry;
}

Referenced by gl_alloc_texture_object(), gl_EndList(), and gl_GenLists().

HashLookup()

void* HashLookup	(	const struct HashTable *	table,
		GLuint	key
	)

Definition at line 110 of file hash.c.

{
   GLuint pos;
   struct HashEntry *entry;

   assert(table);
   assert(key);

   pos = key % TABLE_SIZE;
   entry = table->Table[pos];
   while (entry) {
      if (entry->Key == key) {
     return entry->Data;
      }
      entry = entry->Next;
   }
   return NULL;
}

Referenced by execute_list(), gl_AreTexturesResident(), gl_BindTexture(), gl_DeleteTextures(), gl_destroy_list(), gl_IsList(), gl_IsTexture(), gl_PrioritizeTextures(), and HashFindFreeKeyBlock().

HashPrint()

void HashPrint

(

const struct HashTable *

table

)

Definition at line 227 of file hash.c.

{
   GLuint i;
   assert(table);
   for (i=0;i<TABLE_SIZE;i++) {
      struct HashEntry *entry = table->Table[i];
      while (entry) {
     printf("%u %p\n", entry->Key, entry->Data);
     entry = entry->Next;
      }
   }
}

HashRemove()

void HashRemove	(	struct HashTable *	table,
		GLuint	key
	)

Definition at line 176 of file hash.c.

{
   GLuint pos;
   struct HashEntry *entry, *prev;

   assert(table);
   assert(key);

   pos = key % TABLE_SIZE;
   prev = NULL;
   entry = table->Table[pos];
   while (entry) {
      if (entry->Key == key) {
         /* found it! */
         if (prev) {
            prev->Next = entry->Next;
         }
         else {
            table->Table[pos] = entry->Next;
         }
         free(entry);
     return;
      }
      prev = entry;
      entry = entry->Next;
   }
}

Referenced by gl_destroy_list(), and gl_free_texture_object().

NewHashTable()

struct HashTable* NewHashTable

(

void

)

Definition at line 77 of file hash.c.

{
   return (struct HashTable *) calloc(sizeof (struct HashTable), 1);
}

Referenced by alloc_shared_state(), and WahInsertHandleContext().