summaryrefslogtreecommitdiff
path: root/wiki/2016-10-miniperi
ModeNameSize
-rw-r--r--20160712_renesascom-v3.pdf341580logplain
-rw-r--r--bsp_patch_list_20160930.xlsx234119logplain
-rw-r--r--out_0145.jpg31229logplain
-rw-r--r--out_0146.jpg39463logplain
-rw-r--r--out_0147.jpg36258logplain
-rw-r--r--out_0152.jpg24641logplain
-rw-r--r--out_0153.jpg52821logplain
-rw-r--r--out_0154.jpg26255logplain
-rw-r--r--out_0155.jpg20548logplain
-rw-r--r--out_0156.jpg24832logplain
-rw-r--r--out_0158.jpg21340logplain
-rw-r--r--out_0160.jpg21393logplain
-rw-r--r--out_0161.jpg18942logplain
-rw-r--r--out_0162.jpg18739logplain
-rw-r--r--out_0163.jpg26649logplain
-rw-r--r--out_0164.jpg44361logplain
-rw-r--r--out_0167.jpg48750logplain
-rw-r--r--out_0170.jpg23281logplain
-rw-r--r--out_0171.jpg27429logplain
-rw-r--r--out_0172.jpg43576logplain
-rw-r--r--out_0174.jpg29699logplain
-rw-r--r--out_0175.jpg22678logplain
-rw-r--r--out_0179.jpg24086logplain
-rw-r--r--out_1.jpg6507logplain
-rw-r--r--out_2.jpg8894logplain
-rw-r--r--out_3.jpg5934logplain
-rw-r--r--out_4.jpg7893logplain
-rw-r--r--out_5.jpg8681logplain
-rw-r--r--out_6.jpg12475logplain
-rw-r--r--outg_1.jpg23960logplain
-rw-r--r--outg_2.jpg20386logplain
-rw-r--r--outg_3.jpg26248logplain
-rw-r--r--outg_4.jpg20951logplain
-rw-r--r--outg_5.jpg22829logplain
-rw-r--r--vsp2_running_count.patch1560logplain
-rw-r--r--vsp_state_bug.xlsx46355logplain
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-19 22:45:32 +0000
om"> * * [Pugh90] William Pugh. Skip Lists: A Probabilistic Alternative to * Balanced Trees. CACM 33(6), June 1990, pp. 668-676. * */ #define SL_MAIN 0 #if SL_MAIN # include <stdio.h> # include <stdlib.h> # include <sys/time.h> #else # include "xf86drm.h" # ifdef XFree86LOADER # include "xf86.h" # include "xf86_ansic.h" # else # include <stdio.h> # include <stdlib.h> # endif #endif #define N(x) drm##x #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 #if SL_MAIN #define SL_ALLOC malloc #define SL_FREE free #define SL_RANDOM_DECL static int state = 0; #define SL_RANDOM_INIT(seed) if (!state) { srandom(seed); ++state; } #define SL_RANDOM random() #else #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) #endif typedef struct SLEntry { unsigned long magic; /* SL_ENTRY_MAGIC */ unsigned long key; void *value; int levels; struct SLEntry *forward[1]; /* variable sized array */ } SLEntry, *SLEntryPtr; typedef struct SkipList { unsigned long magic; /* SL_LIST_MAGIC */ int level; int count; SLEntryPtr head; SLEntryPtr p0; /* Position for iteration */ } SkipList, *SkipListPtr; #if SL_MAIN extern void *N(SLCreate)(void); extern int N(SLDestroy)(void *l); extern int N(SLLookup)(void *l, unsigned long key, void **value); extern int N(SLInsert)(void *l, unsigned long key, void *value); extern int N(SLDelete)(void *l, unsigned long key); extern int N(SLNext)(void *l, unsigned long *key, void **value); extern int N(SLFirst)(void *l, unsigned long *key, void **value); extern void N(SLDump)(void *l); extern int N(SLLookupNeighbors)(void *l, unsigned long key, unsigned long *prev_key, void **prev_value, unsigned long *next_key, void **next_value); #endif static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value) { 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; } static int SLRandomLevel(void) { int level = 1; SL_RANDOM_DECL; SL_RANDOM_INIT(SL_RANDOM_SEED); while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level; return level; } void *N(SLCreate)(void) { 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; } int N(SLDestroy)(void *l) { 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; } static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update) { 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]; } int N(SLInsert)(void *l, unsigned long key, void *value) { 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 */ } int N(SLDelete)(void *l, unsigned long key) { 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; } int N(SLLookup)(void *l, unsigned long key, void **value) { 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; } int N(SLLookupNeighbors)(void *l, unsigned long key, unsigned long *prev_key, void **prev_value, unsigned long *next_key, void **next_value) { SkipListPtr list = (SkipListPtr)l; SLEntryPtr update[SL_MAX_LEVEL + 1]; SLEntryPtr entry; int retcode = 0; entry = SLLocate(list, key, update); *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 N(SLNext)(void *l, unsigned long *key, void **value) { 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; } int N(SLFirst)(void *l, unsigned long *key, void **value) { SkipListPtr list = (SkipListPtr)l; if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ list->p0 = list->head->forward[0]; return N(SLNext)(list, key, value); } /* Dump internal data structures for debugging. */ void N(SLDump)(void *l) { 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]); } } } } #if SL_MAIN static void print(SkipListPtr list) { unsigned long key; void *value; if (N(SLFirst)(list, &key, &value)) { do { printf("key = %5lu, value = %p\n", key, value); } while (N(SLNext)(list, &key, &value)); } } static double do_time(int size, int iter) { SkipListPtr list; int i, j; unsigned long keys[1000000]; unsigned long previous; unsigned long key; void *value; struct timeval start, stop; double usec; SL_RANDOM_DECL; SL_RANDOM_INIT(12345); list = N(SLCreate)(); for (i = 0; i < size; i++) { keys[i] = SL_RANDOM; N(SLInsert)(list, keys[i], NULL); } previous = 0; if (N(SLFirst)(list, &key, &value)) { do { if (key <= previous) { printf( "%lu !< %lu\n", previous, key); } previous = key; } while (N(SLNext)(list, &key, &value)); } gettimeofday(&start, NULL); for (j = 0; j < iter; j++) { for (i = 0; i < size; i++) { if (N(SLLookup)(list, keys[i], &value)) printf("Error %lu %d\n", keys[i], i); } } gettimeofday(&stop, NULL); usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec - start.tv_sec * 1000000 - start.tv_usec) / (size * iter); printf("%0.2f microseconds for list length %d\n", usec, size); N(SLDestroy)(list); return usec; } static void print_neighbors(void *list, unsigned long key) { unsigned long prev_key = 0; unsigned long next_key = 0; void *prev_value; void *next_value; int retval; retval = drmSLLookupNeighbors(list, key, &prev_key, &prev_value, &next_key, &next_value); printf("Neighbors of %5lu: %d %5lu %5lu\n", key, retval, prev_key, next_key); } int main(void) { SkipListPtr list; double usec, usec2, usec3, usec4; list = N(SLCreate)(); printf( "list at %p\n", list); print(list); printf("\n==============================\n\n"); N(SLInsert)(list, 123, NULL); N(SLInsert)(list, 213, NULL); N(SLInsert)(list, 50, NULL); print(list); printf("\n==============================\n\n"); print_neighbors(list, 0); print_neighbors(list, 50); print_neighbors(list, 51); print_neighbors(list, 123); print_neighbors(list, 200); print_neighbors(list, 213); print_neighbors(list, 256); printf("\n==============================\n\n"); N(SLDelete)(list, 50); print(list); printf("\n==============================\n\n"); N(SLDump)(list); N(SLDestroy)(list); printf("\n==============================\n\n"); usec = do_time(100, 10000); usec2 = do_time(1000, 500); printf("Table size increased by %0.2f, search time increased by %0.2f\n", 1000.0/100.0, usec2 / usec); usec3 = do_time(10000, 50); printf("Table size increased by %0.2f, search time increased by %0.2f\n", 10000.0/100.0, usec3 / usec); usec4 = do_time(100000, 4); printf("Table size increased by %0.2f, search time increased by %0.2f\n", 100000.0/100.0, usec4 / usec); return 0; } #endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-19 22:45:31 +0000