/* xf86drmHash.c -- Small hash table support for integer -> integer mapping
* Created: Sun Apr 18 09:35:45 1999 by faith@precisioninsight.com
- * Revised: Thu Jun 3 16:11:06 1999 by faith@precisioninsight.com
*
* Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
* All Rights Reserved.
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
- *
+ *
* The above copyright notice and this permission notice (including the next
* paragraph) shall be included in all copies or substantial portions of the
* Software.
- *
+ *
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
* DEALINGS IN THE SOFTWARE.
- *
- * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmHash.c,v 1.2 2000/02/23 04:47:23 martin Exp $
+ *
+ * Authors: Rickard E. (Rik) Faith <faith@valinux.com>
+ *
+ * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmHash.c,v 1.4 2001/03/21 18:08:54 dawes Exp $
*
* DESCRIPTION
*
*
*/
+#ifdef HAVE_XORG_CONFIG_H
+#include <xorg-config.h>
+#endif
+
#define HASH_MAIN 0
#if HASH_MAIN
# include <stdio.h>
# include <stdlib.h>
#else
+# include "drm.h"
# include "xf86drm.h"
# ifdef XFree86LOADER
# include "xf86.h"
# endif
#endif
-#define N(x) drm##x
-
#define HASH_MAGIC 0xdeadbeef
#define HASH_DEBUG 0
#define HASH_SIZE 512 /* Good for about 100 entries */
#define HASH_RANDOM_DECL
#define HASH_RANDOM_INIT(seed) srandom(seed)
#define HASH_RANDOM random()
+#define HASH_RANDOM_DESTROY
#else
#define HASH_ALLOC drmMalloc
#define HASH_FREE drmFree
#define HASH_RANDOM_DECL void *state
#define HASH_RANDOM_INIT(seed) state = drmRandomCreate(seed)
#define HASH_RANDOM drmRandom(state)
+#define HASH_RANDOM_DESTROY drmRandomDestroy(state)
#endif
} HashTable, *HashTablePtr;
#if HASH_MAIN
-extern void *N(HashCreate)(void);
-extern int N(HashDestroy)(void *t);
-extern int N(HashLookup)(void *t, unsigned long key, unsigned long *value);
-extern int N(HashInsert)(void *t, unsigned long key, unsigned long value);
-extern int N(HashDelete)(void *t, unsigned long key);
+extern void *drmHashCreate(void);
+extern int drmHashDestroy(void *t);
+extern int drmHashLookup(void *t, unsigned long key, unsigned long *value);
+extern int drmHashInsert(void *t, unsigned long key, unsigned long value);
+extern int drmHashDelete(void *t, unsigned long key);
#endif
static unsigned long HashHash(unsigned long key)
HASH_RANDOM_DECL;
HASH_RANDOM_INIT(37);
for (i = 0; i < 256; i++) scatter[i] = HASH_RANDOM;
+ HASH_RANDOM_DESTROY;
++init;
}
return hash;
}
-void *N(HashCreate)(void)
+void *drmHashCreate(void)
{
HashTablePtr table;
int i;
return table;
}
-int N(HashDestroy)(void *t)
+int drmHashDestroy(void *t)
{
HashTablePtr table = (HashTablePtr)t;
HashBucketPtr bucket;
int i;
if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
-
+
for (i = 0; i < HASH_SIZE; i++) {
for (bucket = table->buckets[i]; bucket;) {
next = bucket->next;
return NULL;
}
-int N(HashLookup)(void *t, unsigned long key, void **value)
+int drmHashLookup(void *t, unsigned long key, void **value)
{
HashTablePtr table = (HashTablePtr)t;
HashBucketPtr bucket;
- if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
-
+ if (!table || table->magic != HASH_MAGIC) return -1; /* Bad magic */
+
bucket = HashFind(table, key, NULL);
if (!bucket) return 1; /* Not found */
*value = bucket->value;
return 0; /* Found */
}
-int N(HashInsert)(void *t, unsigned long key, void *value)
+int drmHashInsert(void *t, unsigned long key, void *value)
{
HashTablePtr table = (HashTablePtr)t;
HashBucketPtr bucket;
unsigned long hash;
if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
-
+
if (HashFind(table, key, &hash)) return 1; /* Already in table */
bucket = HASH_ALLOC(sizeof(*bucket));
return 0; /* Added to table */
}
-int N(HashDelete)(void *t, unsigned long key)
+int drmHashDelete(void *t, unsigned long key)
{
HashTablePtr table = (HashTablePtr)t;
unsigned long hash;
HashBucketPtr bucket;
if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
-
+
bucket = HashFind(table, key, &hash);
if (!bucket) return 1; /* Not found */
return 0;
}
-int N(HashNext)(void *t, unsigned long *key, void **value)
+int drmHashNext(void *t, unsigned long *key, void **value)
{
HashTablePtr table = (HashTablePtr)t;
-
- for (; table->p0 < HASH_SIZE;
- ++table->p0, table->p1 = table->buckets[table->p0]) {
+
+ while (table->p0 < HASH_SIZE) {
if (table->p1) {
*key = table->p1->key;
*value = table->p1->value;
table->p1 = table->p1->next;
return 1;
}
+ table->p1 = table->buckets[table->p0];
+ ++table->p0;
}
return 0;
}
-int N(HashFirst)(void *t, unsigned long *key, void **value)
+int drmHashFirst(void *t, unsigned long *key, void **value)
{
HashTablePtr table = (HashTablePtr)t;
-
+
if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
table->p0 = 0;
table->p1 = table->buckets[0];
- return N(HashNext)(table, key, value);
+ return drmHashNext(table, key, value);
}
#if HASH_MAIN
{
int i;
HashBucketPtr bucket;
-
+
printf("Entries = %ld, hits = %ld, partials = %ld, misses = %ld\n",
table->entries, table->hits, table->partials, table->misses);
clear_dist();
unsigned long key, unsigned long value)
{
unsigned long retval = 0;
- int retcode = N(HashLookup)(table, key, &retval);
-
+ int retcode = drmHashLookup(table, key, &retval);
+
switch (retcode) {
case -1:
printf("Bad magic = 0x%08lx:"
int i;
printf("\n***** 256 consecutive integers ****\n");
- table = N(HashCreate)();
- for (i = 0; i < 256; i++) N(HashInsert)(table, i, i);
+ table = drmHashCreate();
+ for (i = 0; i < 256; i++) drmHashInsert(table, i, i);
for (i = 0; i < 256; i++) check_table(table, i, i);
for (i = 256; i >= 0; i--) check_table(table, i, i);
compute_dist(table);
- N(HashDestroy)(table);
-
+ drmHashDestroy(table);
+
printf("\n***** 1024 consecutive integers ****\n");
- table = N(HashCreate)();
- for (i = 0; i < 1024; i++) N(HashInsert)(table, i, i);
+ table = drmHashCreate();
+ for (i = 0; i < 1024; i++) drmHashInsert(table, i, i);
for (i = 0; i < 1024; i++) check_table(table, i, i);
for (i = 1024; i >= 0; i--) check_table(table, i, i);
compute_dist(table);
- N(HashDestroy)(table);
-
+ drmHashDestroy(table);
+
printf("\n***** 1024 consecutive page addresses (4k pages) ****\n");
- table = N(HashCreate)();
- for (i = 0; i < 1024; i++) N(HashInsert)(table, i*4096, i);
+ table = drmHashCreate();
+ for (i = 0; i < 1024; i++) drmHashInsert(table, i*4096, i);
for (i = 0; i < 1024; i++) check_table(table, i*4096, i);
for (i = 1024; i >= 0; i--) check_table(table, i*4096, i);
compute_dist(table);
- N(HashDestroy)(table);
-
+ drmHashDestroy(table);
+
printf("\n***** 1024 random integers ****\n");
- table = N(HashCreate)();
+ table = drmHashCreate();
srandom(0xbeefbeef);
- for (i = 0; i < 1024; i++) N(HashInsert)(table, random(), i);
+ for (i = 0; i < 1024; i++) drmHashInsert(table, random(), i);
srandom(0xbeefbeef);
for (i = 0; i < 1024; i++) check_table(table, random(), i);
srandom(0xbeefbeef);
for (i = 0; i < 1024; i++) check_table(table, random(), i);
compute_dist(table);
- N(HashDestroy)(table);
+ drmHashDestroy(table);
printf("\n***** 5000 random integers ****\n");
- table = N(HashCreate)();
+ table = drmHashCreate();
srandom(0xbeefbeef);
- for (i = 0; i < 5000; i++) N(HashInsert)(table, random(), i);
+ for (i = 0; i < 5000; i++) drmHashInsert(table, random(), i);
srandom(0xbeefbeef);
for (i = 0; i < 5000; i++) check_table(table, random(), i);
srandom(0xbeefbeef);
for (i = 0; i < 5000; i++) check_table(table, random(), i);
compute_dist(table);
- N(HashDestroy)(table);
-
+ drmHashDestroy(table);
+
return 0;
}
#endif
OSDN Git Service
