Back to index

libdrm  2.4.37
Classes | Defines | Typedefs | Functions
xf86drmHash.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include "xf86drm.h"
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  HashBucket
struct  HashTable

Defines

#define HASH_MAIN   0
#define HASH_MAGIC   0xdeadbeef
#define HASH_DEBUG   0
#define HASH_SIZE   512 /* Good for about 100 entries */
#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)

Typedefs

typedef struct HashBucket HashBucket
typedef struct HashBucketHashBucketPtr
typedef struct HashTable HashTable
typedef struct HashTableHashTablePtr

Functions

static unsigned long HashHash (unsigned long key)
void * drmHashCreate (void)
int drmHashDestroy (void *t)
static HashBucketPtr HashFind (HashTablePtr table, unsigned long key, unsigned long *h)
int drmHashLookup (void *t, unsigned long key, void **value)
int drmHashInsert (void *t, unsigned long key, void *value)
int drmHashDelete (void *t, unsigned long key)
int drmHashNext (void *t, unsigned long *key, void **value)
int drmHashFirst (void *t, unsigned long *key, void **value)

Class Documentation

struct HashBucket

Definition at line 104 of file xf86drmHash.c.

Collaboration diagram for HashBucket:
Class Members
unsigned long key
struct HashBucket * next
void * value
struct HashTable

Definition at line 110 of file xf86drmHash.c.

Collaboration diagram for HashTable:
Class Members
HashBucketPtr buckets
unsigned long entries
unsigned long hits
unsigned long magic
unsigned long misses
int p0
HashBucketPtr p1
unsigned long partials

Define Documentation

#define HASH_ALLOC   drmMalloc

Definition at line 95 of file xf86drmHash.c.

#define HASH_DEBUG   0

Definition at line 81 of file xf86drmHash.c.

#define HASH_FREE   drmFree

Definition at line 96 of file xf86drmHash.c.

#define HASH_MAGIC   0xdeadbeef

Definition at line 80 of file xf86drmHash.c.

#define HASH_MAIN   0

Definition at line 74 of file xf86drmHash.c.

#define HASH_RANDOM   drmRandom(state)

Definition at line 99 of file xf86drmHash.c.

#define HASH_RANDOM_DECL   void *state

Definition at line 97 of file xf86drmHash.c.

Definition at line 100 of file xf86drmHash.c.

#define HASH_RANDOM_INIT (   seed)    state = drmRandomCreate(seed)

Definition at line 98 of file xf86drmHash.c.

#define HASH_SIZE   512 /* Good for about 100 entries */

Definition at line 82 of file xf86drmHash.c.


Typedef Documentation

typedef struct HashBucket HashBucket
typedef struct HashBucket * HashBucketPtr
typedef struct HashTable HashTable
typedef struct HashTable * HashTablePtr

Function Documentation

void* drmHashCreate ( void  )

Definition at line 157 of file xf86drmHash.c.

{
    HashTablePtr table;
    int          i;

    table           = HASH_ALLOC(sizeof(*table));
    if (!table) return NULL;
    table->magic    = HASH_MAGIC;
    table->entries  = 0;
    table->hits     = 0;
    table->partials = 0;
    table->misses   = 0;

    for (i = 0; i < HASH_SIZE; i++) table->buckets[i] = NULL;
    return table;
}

Here is the caller graph for this function:

int drmHashDelete ( void *  t,
unsigned long  key 
)

Definition at line 260 of file xf86drmHash.c.

{
    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 */

    table->buckets[hash] = bucket->next;
    HASH_FREE(bucket);
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int drmHashDestroy ( void *  t)

Definition at line 174 of file xf86drmHash.c.

{
    HashTablePtr  table = (HashTablePtr)t;
    HashBucketPtr bucket;
    HashBucketPtr next;
    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;
           HASH_FREE(bucket);
           bucket = next;
       }
    }
    HASH_FREE(table);
    return 0;
}

Here is the caller graph for this function:

int drmHashFirst ( void *  t,
unsigned long *  key,
void **  value 
)

Definition at line 294 of file xf86drmHash.c.

{
    HashTablePtr  table = (HashTablePtr)t;

    if (table->magic != HASH_MAGIC) return -1; /* Bad magic */

    table->p0 = 0;
    table->p1 = table->buckets[0];
    return drmHashNext(table, key, value);
}

Here is the call graph for this function:

int drmHashInsert ( void *  t,
unsigned long  key,
void *  value 
)

Definition at line 238 of file xf86drmHash.c.

{
    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));
    if (!bucket) return -1; /* Error */
    bucket->key          = key;
    bucket->value        = value;
    bucket->next         = table->buckets[hash];
    table->buckets[hash] = bucket;
#if HASH_DEBUG
    printf("Inserted %d at %d/%p\n", key, hash, bucket);
#endif
    return 0;               /* Added to table */
}

Here is the call graph for this function:

Here is the caller graph for this function:

int drmHashLookup ( void *  t,
unsigned long  key,
void **  value 
)

Definition at line 225 of file xf86drmHash.c.

{
    HashTablePtr  table = (HashTablePtr)t;
    HashBucketPtr bucket;

    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 */
}

Here is the call graph for this function:

Here is the caller graph for this function:

int drmHashNext ( void *  t,
unsigned long *  key,
void **  value 
)

Definition at line 277 of file xf86drmHash.c.

{
    HashTablePtr  table = (HashTablePtr)t;

    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;
}

Here is the caller graph for this function:

static HashBucketPtr HashFind ( HashTablePtr  table,
unsigned long  key,
unsigned long *  h 
) [static]

Definition at line 197 of file xf86drmHash.c.

{
    unsigned long hash = HashHash(key);
    HashBucketPtr prev = NULL;
    HashBucketPtr bucket;

    if (h) *h = hash;

    for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {
       if (bucket->key == key) {
           if (prev) {
                            /* Organize */
              prev->next           = bucket->next;
              bucket->next         = table->buckets[hash];
              table->buckets[hash] = bucket;
              ++table->partials;
           } else {
              ++table->hits;
           }
           return bucket;
       }
       prev = bucket;
    }
    ++table->misses;
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static unsigned long HashHash ( unsigned long  key) [static]

Definition at line 129 of file xf86drmHash.c.

{
    unsigned long        hash = 0;
    unsigned long        tmp  = key;
    static int           init = 0;
    static unsigned long scatter[256];
    int                  i;

    if (!init) {
       HASH_RANDOM_DECL;
       HASH_RANDOM_INIT(37);
       for (i = 0; i < 256; i++) scatter[i] = HASH_RANDOM;
       HASH_RANDOM_DESTROY;
       ++init;
    }

    while (tmp) {
       hash = (hash << 1) + scatter[tmp & 0xff];
       tmp >>= 8;
    }

    hash %= HASH_SIZE;
#if HASH_DEBUG
    printf( "Hash(%d) = %d\n", key, hash);
#endif
    return hash;
}

Here is the caller graph for this function: