hash.c File Reference

---

Detailed Description

Generic hash table.

Used for display lists, texture objects, vertex/fragment programs, buffer objects, etc. The hash functions are thread-safe.

Note:

key=0 is illegal.

Author:

Brian Paul

#include "glheader.h"
#include "imports.h"
#include "glapi/glthread.h"
#include "hash.h"

Data Structures
struct	HashEntry
	An entry in the hash table. More...
struct	_mesa_HashTable
	The hash table data structure. More...
Defines
#define	TABLE_SIZE   1023
	Size of lookup table/array.
#define	HASH_FUNC(K)   ((K) % TABLE_SIZE)
Functions
struct _mesa_HashTable *	_mesa_NewHashTable (void)
	Create a new hash table.
void	_mesa_DeleteHashTable (struct _mesa_HashTable *table)
	Delete a hash table.
void *	_mesa_HashLookup (const struct _mesa_HashTable *table, GLuint key)
	Lookup an entry in the hash table.
void	_mesa_HashInsert (struct _mesa_HashTable *table, GLuint key, void *data)
	Insert a key/pointer pair into the hash table.
void	_mesa_HashRemove (struct _mesa_HashTable *table, GLuint key)
	Remove an entry from the hash table.
void	_mesa_HashDeleteAll (struct _mesa_HashTable *table, void(*callback)(GLuint key, void *data, void *userData), void *userData)
	Delete all entries in a hash table, but don't delete the table itself.
void	_mesa_HashWalk (const struct _mesa_HashTable *table, void(*callback)(GLuint key, void *data, void *userData), void *userData)
	Walk over all entries in a hash table, calling callback function for each.
GLuint	_mesa_HashFirstEntry (struct _mesa_HashTable *table)
	Return the key of the "first" entry in the hash table.
GLuint	_mesa_HashNextEntry (const struct _mesa_HashTable *table, GLuint key)
	Given a hash table key, return the next key.
void	_mesa_HashPrint (const struct _mesa_HashTable *table)
	Dump contents of hash table for debugging.
GLuint	_mesa_HashFindFreeKeyBlock (struct _mesa_HashTable *table, GLuint numKeys)
	Find a block of adjacent unused hash keys.

---

Define Documentation

#define HASH_FUNC

(

K

)

((K) % TABLE_SIZE)

#define TABLE_SIZE   1023

Size of lookup table/array.

---

Function Documentation

void _mesa_DeleteHashTable

(

struct _mesa_HashTable *

table

)

Delete a hash table.

Frees each entry on the hash table and then the hash table structure itself. Note that the caller should have already traversed the table and deleted the objects in the table (i.e. We don't free the entries' data pointer).

Parameters:

table

the hash table to delete.

void _mesa_HashDeleteAll	(	struct _mesa_HashTable *	table,
		void(*)(GLuint key, void *data, void *userData)	callback,
		void *	userData
	)

Delete all entries in a hash table, but don't delete the table itself.

Invoke the given callback function for each table entry.

Parameters:

	table	the hash table to delete
	callback	the callback function
	userData	arbitrary pointer to pass along to the callback (this is typically a GLcontext pointer)

GLuint _mesa_HashFindFreeKeyBlock	(	struct _mesa_HashTable *	table,
		GLuint	numKeys
	)

Find a block of adjacent unused hash keys.

Parameters:

	table	the hash table.
	numKeys	number of keys needed.

Returns:

Starting key of free block or 0 if failure.

If there are enough free keys between the maximum key existing in the table (_mesa_HashTable::MaxKey) and the maximum key possible, then simply return the adjacent key. Otherwise do a full search for a free key block in the allowable key range.

GLuint _mesa_HashFirstEntry

(

struct _mesa_HashTable *

table

)

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.

Parameters:

table

the hash table

Returns:

key for the "first" entry in the hash table.

void _mesa_HashInsert	(	struct _mesa_HashTable *	table,
		GLuint	key,
		void *	data
	)

Insert a key/pointer pair into the hash table.

If an entry with this key already exists we'll replace the existing entry.

Parameters:

	table	the hash table.
	key	the key (not zero).
	data	pointer to user data.

void* _mesa_HashLookup	(	const struct _mesa_HashTable *	table,
		GLuint	key
	)

Lookup an entry in the hash table.

Parameters:

	table	the hash table.
	key	the key.

Returns:

pointer to user's data or NULL if key not in table

GLuint _mesa_HashNextEntry	(	const struct _mesa_HashTable *	table,
		GLuint	key
	)

Given a hash table key, return the next key.

This is used to walk over all entries in the table. Note that the keys returned during walking won't be in any particular order.

Returns:

next hash key or 0 if end of table.

void _mesa_HashPrint

(

const struct _mesa_HashTable *

table

)

Dump contents of hash table for debugging.

Parameters:

table

the hash table.

void _mesa_HashRemove	(	struct _mesa_HashTable *	table,
		GLuint	key
	)

Remove an entry from the hash table.

Parameters:

	table	the hash table.
	key	key of entry to remove.

While holding the hash table's lock, searches the entry with the matching key and unlinks it.

void _mesa_HashWalk	(	const struct _mesa_HashTable *	table,
		void(*)(GLuint key, void *data, void *userData)	callback,
		void *	userData
	)

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.

Parameters:

	table	the hash table to walk
	callback	the callback function
	userData	arbitrary pointer to pass along to the callback (this is typically a GLcontext pointer)

struct _mesa_HashTable* _mesa_NewHashTable

(

void

)

[read]

Create a new hash table.

Returns:

pointer to a new, empty hash table.

---