Back to index

libdrm  2.4.37
Classes | Defines | Typedefs | Functions
xf86drmSL.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include "xf86drm.h"

Go to the source code of this file.

Classes

struct  SLEntry
struct  SkipList

Defines

#define SL_MAIN   0
#define SL_LIST_MAGIC   0xfacade00LU
#define SL_ENTRY_MAGIC   0x00fab1edLU
#define SL_FREED_MAGIC   0xdecea5edLU
#define SL_MAX_LEVEL   16
#define SL_DEBUG   0
#define SL_RANDOM_SEED   0xc01055a1LU
#define SL_ALLOC   drmMalloc
#define SL_FREE   drmFree
#define SL_RANDOM_DECL   static void *state = NULL
#define SL_RANDOM_INIT(seed)   if (!state) state = drmRandomCreate(seed)
#define SL_RANDOM   drmRandom(state)

Typedefs

typedef struct SLEntry SLEntry
typedef struct SLEntrySLEntryPtr
typedef struct SkipList SkipList
typedef struct SkipListSkipListPtr

Functions

static SLEntryPtr SLCreateEntry (int max_level, unsigned long key, void *value)
static int SLRandomLevel (void)
void * drmSLCreate (void)
int drmSLDestroy (void *l)
static SLEntryPtr SLLocate (void *l, unsigned long key, SLEntryPtr *update)
int drmSLInsert (void *l, unsigned long key, void *value)
int drmSLDelete (void *l, unsigned long key)
int drmSLLookup (void *l, unsigned long key, void **value)
int drmSLLookupNeighbors (void *l, unsigned long key, unsigned long *prev_key, void **prev_value, unsigned long *next_key, void **next_value)
int drmSLNext (void *l, unsigned long *key, void **value)
int drmSLFirst (void *l, unsigned long *key, void **value)
void drmSLDump (void *l)

Class Documentation

struct SLEntry

Definition at line 74 of file xf86drmSL.c.

Collaboration diagram for SLEntry:
Class Members
struct SLEntry * forward
unsigned long key
int levels
unsigned long magic
void * value
struct SkipList

Definition at line 82 of file xf86drmSL.c.

Collaboration diagram for SkipList:
Class Members
int count
SLEntryPtr head
int level
unsigned long magic
SLEntryPtr p0

Define Documentation

#define SL_ALLOC   drmMalloc

Definition at line 66 of file xf86drmSL.c.

#define SL_DEBUG   0

Definition at line 56 of file xf86drmSL.c.

#define SL_ENTRY_MAGIC   0x00fab1edLU

Definition at line 53 of file xf86drmSL.c.

#define SL_FREE   drmFree

Definition at line 67 of file xf86drmSL.c.

#define SL_FREED_MAGIC   0xdecea5edLU

Definition at line 54 of file xf86drmSL.c.

#define SL_LIST_MAGIC   0xfacade00LU

Definition at line 52 of file xf86drmSL.c.

#define SL_MAIN   0

Definition at line 44 of file xf86drmSL.c.

#define SL_MAX_LEVEL   16

Definition at line 55 of file xf86drmSL.c.

#define SL_RANDOM   drmRandom(state)

Definition at line 70 of file xf86drmSL.c.

#define SL_RANDOM_DECL   static void *state = NULL

Definition at line 68 of file xf86drmSL.c.

#define SL_RANDOM_INIT (   seed)    if (!state) state = drmRandomCreate(seed)

Definition at line 69 of file xf86drmSL.c.

#define SL_RANDOM_SEED   0xc01055a1LU

Definition at line 57 of file xf86drmSL.c.


Typedef Documentation

typedef struct SkipList SkipList
typedef struct SkipList * SkipListPtr
typedef struct SLEntry SLEntry
typedef struct SLEntry * SLEntryPtr

Function Documentation

void* drmSLCreate ( void  )

Definition at line 132 of file xf86drmSL.c.

{
    SkipListPtr  list;
    int          i;

    list           = SL_ALLOC(sizeof(*list));
    if (!list) return NULL;
    list->magic    = SL_LIST_MAGIC;
    list->level    = 0;
    list->head     = SLCreateEntry(SL_MAX_LEVEL, 0, NULL);
    list->count    = 0;

    for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL;
    
    return list;
}

Here is the call graph for this function:

int drmSLDelete ( void *  l,
unsigned long  key 
)

Definition at line 219 of file xf86drmSL.c.

{
    SkipListPtr   list = (SkipListPtr)l;
    SLEntryPtr    update[SL_MAX_LEVEL + 1];
    SLEntryPtr    entry;
    int           i;

    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */

    entry = SLLocate(list, key, update);

    if (!entry || entry->key != key) return 1; /* Not found */

                            /* Fix up forward pointers */
    for (i = 0; i <= list->level; i++) {
       if (update[i]->forward[i] == entry)
           update[i]->forward[i] = entry->forward[i];
    }

    entry->magic = SL_FREED_MAGIC;
    SL_FREE(entry);

    while (list->level && !list->head->forward[list->level]) --list->level;
    --list->count;
    return 0;
}

Here is the call graph for this function:

int drmSLDestroy ( void *  l)

Definition at line 149 of file xf86drmSL.c.

{
    SkipListPtr   list  = (SkipListPtr)l;
    SLEntryPtr    entry;
    SLEntryPtr    next;

    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */

    for (entry = list->head; entry; entry = next) {
       if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */
       next         = entry->forward[0];
       entry->magic = SL_FREED_MAGIC;
       SL_FREE(entry);
    }

    list->magic = SL_FREED_MAGIC;
    SL_FREE(list);
    return 0;
}
void drmSLDump ( void *  l)

Definition at line 316 of file xf86drmSL.c.

{
    SkipListPtr   list = (SkipListPtr)l;
    SLEntryPtr    entry;
    int           i;
    
    if (list->magic != SL_LIST_MAGIC) {
       printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
              list->magic, SL_LIST_MAGIC);
       return;
    }

    printf("Level = %d, count = %d\n", list->level, list->count);
    for (entry = list->head; entry; entry = entry->forward[0]) {
       if (entry->magic != SL_ENTRY_MAGIC) {
           printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
                 list->magic, SL_ENTRY_MAGIC);
       }
       printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
              entry, entry->key, entry->value, entry->levels);
       for (i = 0; i < entry->levels; i++) {
           if (entry->forward[i]) {
              printf("   %2d: %p <0x%08lx, %p>\n",
                     i,
                     entry->forward[i],
                     entry->forward[i]->key,
                     entry->forward[i]->value);
           } else {
              printf("   %2d: %p\n", i, entry->forward[i]);
           }
       }
    }
}
int drmSLFirst ( void *  l,
unsigned long *  key,
void **  value 
)

Definition at line 305 of file xf86drmSL.c.

{
    SkipListPtr   list = (SkipListPtr)l;
    
    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
    
    list->p0 = list->head->forward[0];
    return drmSLNext(list, key, value);
}

Here is the call graph for this function:

int drmSLInsert ( void *  l,
unsigned long  key,
void *  value 
)

Definition at line 186 of file xf86drmSL.c.

{
    SkipListPtr   list  = (SkipListPtr)l;
    SLEntryPtr    entry;
    SLEntryPtr    update[SL_MAX_LEVEL + 1];
    int           level;
    int           i;

    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */

    entry = SLLocate(list, key, update);

    if (entry && entry->key == key) return 1; /* Already in list */


    level = SLRandomLevel();
    if (level > list->level) {
       level = ++list->level;
       update[level] = list->head;
    }

    entry = SLCreateEntry(level, key, value);

                            /* Fix up forward pointers */
    for (i = 0; i <= level; i++) {
       entry->forward[i]     = update[i]->forward[i];
       update[i]->forward[i] = entry;
    }

    ++list->count;
    return 0;               /* Added to table */
}

Here is the call graph for this function:

int drmSLLookup ( void *  l,
unsigned long  key,
void **  value 
)

Definition at line 246 of file xf86drmSL.c.

{
    SkipListPtr   list = (SkipListPtr)l;
    SLEntryPtr    update[SL_MAX_LEVEL + 1];
    SLEntryPtr    entry;

    entry = SLLocate(list, key, update);

    if (entry && entry->key == key) {
       *value = entry;
       return 0;
    }
    *value = NULL;
    return -1;
}

Here is the call graph for this function:

int drmSLLookupNeighbors ( void *  l,
unsigned long  key,
unsigned long *  prev_key,
void **  prev_value,
unsigned long *  next_key,
void **  next_value 
)

Definition at line 262 of file xf86drmSL.c.

{
    SkipListPtr   list = (SkipListPtr)l;
    SLEntryPtr    update[SL_MAX_LEVEL + 1];
    int           retcode = 0;

    *prev_key   = *next_key   = key;
    *prev_value = *next_value = NULL;
       
    if (update[0]) {
       *prev_key   = update[0]->key;
       *prev_value = update[0]->value;
       ++retcode;
       if (update[0]->forward[0]) {
           *next_key   = update[0]->forward[0]->key;
           *next_value = update[0]->forward[0]->value;
           ++retcode;
       }
    }
    return retcode;
}
int drmSLNext ( void *  l,
unsigned long *  key,
void **  value 
)

Definition at line 286 of file xf86drmSL.c.

{
    SkipListPtr   list = (SkipListPtr)l;
    SLEntryPtr    entry;
    
    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */

    entry    = list->p0;

    if (entry) {
       list->p0 = entry->forward[0];
       *key     = entry->key;
       *value   = entry->value;
       return 1;
    }
    list->p0 = NULL;
    return 0;
}

Here is the caller graph for this function:

static SLEntryPtr SLCreateEntry ( int  max_level,
unsigned long  key,
void *  value 
) [static]

Definition at line 104 of file xf86drmSL.c.

{
    SLEntryPtr entry;
    
    if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL;

    entry         = SL_ALLOC(sizeof(*entry)
                          + (max_level + 1) * sizeof(entry->forward[0]));
    if (!entry) return NULL;
    entry->magic  = SL_ENTRY_MAGIC;
    entry->key    = key;
    entry->value  = value;
    entry->levels = max_level + 1;

    return entry;
}

Here is the caller graph for this function:

static SLEntryPtr SLLocate ( void *  l,
unsigned long  key,
SLEntryPtr update 
) [static]

Definition at line 169 of file xf86drmSL.c.

{
    SkipListPtr   list  = (SkipListPtr)l;
    SLEntryPtr    entry;
    int           i;

    if (list->magic != SL_LIST_MAGIC) return NULL;

    for (i = list->level, entry = list->head; i >= 0; i--) {
       while (entry->forward[i] && entry->forward[i]->key < key)
           entry = entry->forward[i];
       update[i] = entry;
    }

    return entry->forward[0];
}

Here is the caller graph for this function:

static int SLRandomLevel ( void  ) [static]

Definition at line 121 of file xf86drmSL.c.

{
    int level = 1;
    SL_RANDOM_DECL;

    SL_RANDOM_INIT(SL_RANDOM_SEED);
    
    while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level;
    return level;
}

Here is the caller graph for this function: