From ee18200a9d3817728d6d09745cd29900649d4508 Mon Sep 17 00:00:00 2001 From: ken Date: Tue, 17 Jan 2017 21:19:42 -0800 Subject: [PATCH] xxhash integrated --- src/ir.c | 214 ++++++++++++++++++++++++++++++++++++++----------------- src/ir.h | 4 +- 2 files changed, 151 insertions(+), 67 deletions(-) diff --git a/src/ir.c b/src/ir.c index a175ef3..706f677 100644 --- a/src/ir.c +++ b/src/ir.c @@ -21,9 +21,12 @@ #include "ir.h" #undef do_error #define do_error(...) exit(-1) +#define XXH_PRIVATE_API +#include "../xxHash/xxhash.h" /* Public */ int ir_init(void); void ir_quit(void); +void ir_test(void); int ir_linker(void); int ir_condenser(void); /* Memory allocation structures */ @@ -40,7 +43,7 @@ struct pagelist_t { struct pagenode_t* root, * head; size_t pagesize; }; -#define DATA_PAGESIZE (sys_pagesize) +#define SYS_PAGESIZE (sys_pagesize) #define NAME_PAGESIZE (APC_NAME_MAX * 1024) #define PL_HEADERSIZE (sizeof(struct pagenode_header_t)) #define PL_HEADSIZE(_PL) (_PL.head->header.head - _PL.head->root) @@ -100,7 +103,7 @@ struct ir_class_t struct ir_set_t { struct ir_set_t* nextchild, * nextsib; struct ir_class_t* class; - long long ref; + uint32_t ref; uint8_t* name; struct ir_framebox_t* frameboxes; struct ir_simplex_t* audio; @@ -112,10 +115,6 @@ struct ir_framebox_t* ir_set_add_framebox(struct ir_set_t*,const uint8_t*); static inline union ir_setdata_t* ir_framedata (enum dtype,const uint8_t*,apc_facing,int,int); static inline -int init_pagelist(struct pagelist_t*,size_t); -static -void ir_free_pagenodes(struct pagenode_t*); -static inline int bytes_identical(const uint8_t*,const uint8_t*); static inline int classnames_identical(const uint8_t*,const uint8_t*); @@ -126,62 +125,68 @@ static uint8_t* name_alloc(const uint8_t*); static uint8_t* classname_alloc(const uint8_t*); +static inline +void* pagelist_pop(struct pagelist_t*,size_t); +#define pagelist_alloc(pagelist) do { \ + pagelist.head->header.next = (struct pagenode_t*) calloc(pagelist.pagesize,1); \ + if (pagelist.head->header.next == NULL) \ + eprintf("Memory allocation error\n"); \ + pagelist.head = pagelist.head->header.next; \ + pagelist.head->header.head = pagelist.head->root; \ + } while (0) +#define pagelist_init(pagelist,size) do { \ + pagelist.pagesize = size; \ + pagelist.root = (struct pagenode_t*) calloc(size,1); \ + if (pagelist.root == NULL) \ + eprintf("Memory allocation error\n"); \ + pagelist.root->header.head = pagelist.root->root; \ + pagelist.head = pagelist.root; \ + } while (0) +static +void pagenode_free(struct pagenode_t*); +#define REFHASH(ref) (XXH32(&ref, sizeof(uint32_t), 0xCEED) & 0xCFF) + extern //apc.c long sys_pagesize; static -struct pagelist_t datapages, namepages; +struct pagelist_t datapages, namepages, refhashpages; static struct ir_class_t root_class = { .name = (uint8_t*)"." }; /* Init */ int ir_init ( void ) -{ if (init_pagelist(&datapages, (size_t)DATA_PAGESIZE)) - eprintf("Memory allocation error\n"); - if (init_pagelist(&namepages, (size_t)NAME_PAGESIZE)) - eprintf("Memory allocation error\n"); +{ pagelist_init(datapages, (size_t)SYS_PAGESIZE); + pagelist_init(namepages, (size_t)NAME_PAGESIZE); + pagelist_init(refhashpages, (size_t)SYS_PAGESIZE); return 0; } -static inline -int init_pagelist -( struct pagelist_t* pl, - size_t size -) -{ pl->pagesize = size; - pl->root = (struct pagenode_t*) calloc(size,1); - if (pl->root == NULL) - return -1; - pl->root->header.head = pl->root->root; - pl->head = pl->root; - return 0; -} - -/* Quit/Cleanup - Recursively clean pagenode linked list -*/ +/* Quit/Cleanup */ void ir_quit ( void ) -{ ir_free_pagenodes(datapages.root); - ir_free_pagenodes(namepages.root); +{ pagenode_free(datapages.root); + pagenode_free(namepages.root); + pagenode_free(refhashpages.root); } +/* Recursively clean pagenode linked list, freeing last first */ static -void ir_free_pagenodes +void pagenode_free ( struct pagenode_t* pagenode ) { if (pagenode->header.next != NULL) - ir_free_pagenodes(pagenode->header.next); + pagenode_free(pagenode->header.next); free(pagenode); } -/* Link -*/ +/* Link */ int ir_linker ( void ) -{ return 0; } +{ + return 0; +} -/* Condense -*/ +/* Condense */ int ir_condenser ( void ) { return 0; } @@ -256,6 +261,20 @@ struct ir_set_t* ir_class_addset return class->root_set = iter; } +struct ir_set_t* ir_set_from_ref +( uint32_t ref ) +{ uint16_t hash; + struct ir_set_t** iters; + struct pagenode_t* iterp; + iterp = refhashpages.root; + hash = REFHASH(ref); + do + iters = ((struct ir_set_t**) iterp->root) + hash; + while (*iters != NULL && (*iters)->ref != ref && (iterp = iterp->header.next) != NULL); + return *iters; +} + + /* Add a set to a set Attempts to create a new subset of the specified set, returning the child if it already exists @@ -342,9 +361,7 @@ int classnames_identical return (ca == cb); } -/* Assign Setdata to Set - - */ +/* Assign Setdata to Set */ void ir_set_assign_data ( struct ir_set_t* set, union ir_setdata_t* setdata @@ -396,13 +413,37 @@ void ir_set_assign_data void ir_set_assign_ref ( struct ir_set_t* set, - long long ref + uint32_t ref ) -{ if (set->ref != 0) - wprintf("Ref override: 0x%lx -> 0x%lx for set %s\n", - (long unsigned) set->ref, (long unsigned) ref, set->name); +{ uint16_t hash, oldhash; + struct ir_set_t** iters; + struct pagenode_t* iterp; + uint32_t oldref; + oldref = set->ref; + oldhash = 0; + hash = REFHASH(ref); + iterp = refhashpages.root; + check_depth: + iters = ((struct ir_set_t**) iterp->root) + hash; + if (*iters == NULL || *iters == set) + *iters = set; + else + { if (iterp->header.next == NULL) + pagelist_alloc(refhashpages); + iterp = iterp->header.next; + goto check_depth; + } + if (oldref != 0) + { wprintf("Ref override: 0x%x -> 0x%x for set %s\n", oldref, ref, set->name); + if (oldhash != 0) + *iters = NULL; + else + { oldhash = hash; + hash = REFHASH(oldref); + goto check_depth; + } + } set->ref = ref; - //TODO: reflist_add(set); } void ir_data_assign_path @@ -475,7 +516,7 @@ struct ir_classld_t* ir_classld_from_class } struct ir_setld_t* ir_setld_from_ref -( long long ref ) +( uint32_t ref ) { struct ir_setld_t* setld; setld = struct_alloc(ir_setld_t); setld->ref = ref; @@ -527,19 +568,29 @@ union ir_setdata_t* ir_link return (union ir_setdata_t*) link; } +static inline +void* pagelist_pop +( struct pagelist_t* pagelist, + size_t size +) +{ size_t headsize = PL_HEADSIZE((*pagelist)); + if (!headsize) + { free(pagelist->head); + pagelist->head = pagelist->root; + while (pagelist->head->header.next != NULL) + pagelist->head = pagelist->head->header.next; + } + if (headsize < size) + eprintf("Attempted to pop unaligned value from pagelist\n"); + pagelist->head->header.head -= size; + return pagelist->head->header.head; +} static void* stack_alloc ( size_t bytes ) -{ if (!bytes) //valid behavior to attain current head - return datapages.head->header.head; - if (PL_HEADMEM(datapages) < bytes) - { datapages.head->header.next = (struct pagenode_t*) calloc(datapages.pagesize,1); - if (datapages.head->header.next == NULL) - eprintf("Memory allocation error \n"); - datapages.head = datapages.head->header.next; - datapages.head->header.head = datapages.head->root; - } +{ if (PL_HEADMEM(datapages) < bytes) + pagelist_alloc(datapages); datapages.head->header.head += bytes; return (void*) datapages.head->header.head - bytes; } @@ -556,11 +607,7 @@ uint8_t* name_alloc for (head_mem = PL_HEADMEM(namepages); *iter && *iter != '_' && head_mem; head_mem--) *(namepages.head->header.head)++ = *iter++; if (head_mem == 0) //not enough room - { namepages.head->header.next = (struct pagenode_t*) calloc(namepages.pagesize,1); - if (namepages.head->header.next == NULL) - eprintf("Memory allocation error\n"); - namepages.head = namepages.head->header.next; - namepages.head->header.head = namepages.head->root; + { pagelist_alloc(namepages); goto copy; } *(namepages.head->header.head)++ = '\0'; @@ -579,13 +626,50 @@ uint8_t* classname_alloc for (head_mem = PL_HEADMEM(namepages); *iter && head_mem; head_mem--) *(namepages.head->header.head)++ = *iter++; if (head_mem == 0) //not enough room - { namepages.head->header.next = (struct pagenode_t*) calloc(namepages.pagesize,1); - if (namepages.head->header.next == NULL) - eprintf("Memory allocation error\n"); - namepages.head = namepages.head->header.next; - namepages.head->header.head = namepages.head->root; + { pagelist_alloc(namepages); goto copy; } *(namepages.head->header.head)++ = '\0'; return name; } + +#define pdepth() do { for (i = 0; i < depth * 2; i++) putchar(' '); } while (0) +void ir_test(void) +{ struct ir_class_t* class, * classbuf; + struct ir_set_t* set, * set_child; + int depth, i, olddepth; + depth = olddepth = 0; + classbuf = NULL; + for(class = ir_class_root(); class != NULL; class = class->nextchild) + {handle_class: + pdepth(); + uprintf("%U\n",class->name); + old_depth = depth; + set = class->root_set; + handle_set: + while(set != NULL) + { pdepth();uprintf("|"); + pdepth(); + uprintf("-[%U]",set->name); + set_child = set->nextchild; + while (set_child != NULL) + { depth++; + uprintf("--[%U]",set_child->name); + set_child = set_child->nextchild; + } + uprintf("\n"); + set = set->nextsib; + } + if (class->nextsib != NULL) + { if (classbuf == NULL) + classbuf = class; + class = class->nextsib; + goto handle_class; + } + if (classbuf != NULL) + class = classbuf; + classbuf = NULL; + uprintf("\n"); + depth = olddepth + 1; + } +} diff --git a/src/ir.h b/src/ir.h index aec70db..68fcde2 100644 --- a/src/ir.h +++ b/src/ir.h @@ -65,7 +65,7 @@ ir_set ir_set_addchild(ir_set,const uint8_t*); */ enum ltype { OLINK, MLINK, VLINK, ALINK }; void ir_set_assign_data(ir_set,ir_setdata); -void ir_set_assign_ref(ir_set,long long); +void ir_set_assign_ref(ir_set,uint32_t); void ir_data_assign_path(ir_setdata,const uint8_t*); ir_setdata ir_framesheet(const uint8_t*, apc_facing, int,int); ir_setdata ir_mapsheet(const uint8_t*, apc_facing, int,int); @@ -82,7 +82,7 @@ ir_setdata ir_link(enum ltype,ir_setld,const uint8_t*); ir_classld ir_classld_from_class(ir_class); ir_classld ir_classld_from_root(void); ir_classld ir_classld_addchild(ir_classld,const uint8_t*); -ir_setld ir_setld_from_ref(long long); +ir_setld ir_setld_from_ref(uint32_t); ir_setld ir_setld_from_classld(ir_classld,const uint8_t*); ir_setld ir_setld_addchild(ir_setld,const uint8_t*); #endif //_IR_H_ -- 2.18.0