From: ken Date: Thu, 23 Feb 2017 02:54:13 +0000 (-0800) Subject: ht insertion X-Git-Url: https://www.kengrimes.com/gitweb/?p=henge%2Fapc.git;a=commitdiff_plain;h=92a90286c61461f1de3d199d887fcb1951dca835 ht insertion --- diff --git a/src/binaryout.c b/src/binaryout.c index f8ce569..5c58a0c 100644 --- a/src/binaryout.c +++ b/src/binaryout.c @@ -25,7 +25,9 @@ /* Public */ void ir_binout_init(struct ir_class_t*); - +/* Private */ +static +long file_ht_insert(long,int,int,int,uint32_t*,uint32_t,uint32_t); /* Memory Allocation */ #define struct_alloc(_T) ((struct _T*) stack_alloc(&datapages, sizeof(struct _T))) static @@ -46,11 +48,11 @@ struct bin_ht_header_t { int entries; int size; }; -struct bin_default_ht_entry_t { +struct bin_ht_entry_t { uint32_t key; long value; }; -struct bin_var_ht_entry_t { +struct bin_variant_ht_entry_t { uint32_t key; long vvalue; long mvalue; @@ -128,13 +130,12 @@ struct bin_pixel_ht_entry_t struct bin_pixel_ht_t { struct bin_pixel_ht_t* next; - struct bin_pixel_ht_entry_t[] hash_entries; + struct bin_pixel_ht_entry_t* hash_entries; }; struct bin_attachment_list_t **attachment_stack, **asp; //attachment_stack, attachment_stack_pointer FILE* binaryout; - #define NAMEHASH(name, domain) (XXH32(name, u8_strlen(name), 0XCEED ) & domain) #define REFHASH(ref, domain) (XXH32(&ref, sizeof(uint32_t), 0xCEED) & domain) static inline @@ -170,20 +171,6 @@ int bin_set_sibcount return count; } -/* Given a position and a size, checks if the bytes are null and returns - the file position to where it started. 1 if not null, 0 if null*/ -/* TODO: Determine why fseeking file past end sets bytes to -1, and not 0 */ -static inline -int bytes_null( int len, int pos ) -{ while(len--) - { if(fgetc(binaryout) > 0) - { fseek(binaryout, pos, SEEK_SET); - return 1; - } - } - fseek(binaryout, pos, SEEK_SET); - return 0; -} /* Checks if the key at entrypos is the same as the parameter key. Returns 1 if so, 0 if not. */ static inline @@ -214,95 +201,128 @@ ir_binout_init(ir_class root_class) bin_traverse_class(root_class); } - +/* INSERT INTO HASH TABLE */ /* Returns the key position where the hash table entry was inserted. */ -#define ENTRY_OCCUPIED() (bytes_null(uint32_t), entry_pos)) -#define LOOP_ENTRY(_HTSTART) (entry_pos = _HTSTART) -#define WRITE_DEF_ENTRY() do { \ - if(fseek(binaryout, entry_pos, SEEK_SET) == -1) wprintf("fseek failed with %s", strerror(errno)); \ - fwrite(&def_ht_entry, sizeof def_ht_entry, 1, binaryout); \ +#define SEEK_TO(_FPOS) do { \ + errno = 0; \ + if (fseek(binaryout, _FPOS, SEEK_SET)) \ + eprintf("Failed to seek to position %l: %s\n", _FPOS, strerror(errno)); \ } while (0) -#define INC_DEF_ENTRY() do { \ - entry_pos += sizeof(def_ht_entry); \ - if(fseek(binaryout, entry_pos, SEEK_SET) == -1) eprintf("fseek failed with %s", strerror(errno)); \ +#define SEEK_REL(_FPOS) do { \ + errno = 0; \ + if (fseek(binaryout, _FPOS, SEEK_CUR)) \ + eprintf("Failed to seek to position %l: %s\n", _FPOS, strerror(errno)); \ + } while (0) +#define READ_DATA_AND_INCREMENT(_DATA,_SIZE) do { \ + errno = 0; \ + if (fread(_DATA, _SIZE, 1, binaryout) != 1) \ + eprintf("Failed to read data at file position %l: %s\n", \ + ftell(binaryout), \ + strerror(errno)); \ + } while (0) +#define READ_DATA(_DATA,_SIZE) do { \ + READ_DATA_AND_INCREMENT(_DATA,_SIZE); \ + SEEK_REL(-_SIZE); \ + } while (0) +#define WRITE_DATA_AND_INCREMENT(_DATA,_SIZE) do { \ + errno = 0; \ + if (fwrite(_DATA, _SIZE, 1, binaryout) != 1) \ + eprintf("Failed to write data to file at position %l: %s\n", \ + ftell(binaryout), \ + strerror(errno)); \ + } while (0) +#define WRITE_DATA(_DATA,_SIZE) do { \ + WRITE_DATA_AND_INCREMENT(_DATA,_SIZE); \ + SEEK_REL(-_SIZE); \ } while (0) -#define HT_END(_HTEND) (entry_pos >= _HTEND) //just in case at last entry -long -bin_insert_default_ht_entry -( long ht_start, - int ht_size, - struct bin_def_ht_entry_t* def_ht_entry, - int overwrite -) -{ long entry_pos, ht_end; - ht_end = ht_start + ht_size; - entry_pos = ht_start + sizeof(ht_entry) * ht_entry->key; - fseek(binaryout, entry_pos, SEEK_SET); - - if (!ENTRY_OCCUPIED()) - { uprintf("key not occupied\n"); - WRITE_DEF_ENTRY(); +/* Insert a value into an arbitrary hash table in-file */ +static +long file_ht_insert +( long ht_start, + int ht_row_values, + int ht_which_value, + int ht_rows, + uint32_t* overwrite, + uint32_t key, + uint32_t value +) +{ uint32_t entry[ht_row_values]; +# define ENTRY_VAL(N) entry[N] +# define ENTRY_KEY ENTRY_VAL(0) + uint8_t looped = 0; + size_t entry_row = key & (ht_rows - 1); + int i; + long writepos, startpos; + startpos = ftell(binaryout); + next_entry: + SEEK_TO(ht_start + (entry_row * sizeof(entry))); + READ_DATA(entry, sizeof(uint32_t) * ht_row_values); + for (i = 0; i < ht_row_values; i++) + if (entry[i] != 0) + goto populated; + write_position: + SEEK_REL(sizeof(uint32_t) * ht_which_value); + WRITE_DATA(entry + ht_which_value, sizeof(*entry)); + writepos = ftell(binaryout); + SEEK_TO(startpos); + return writepos; + populated: + if (ENTRY_KEY == key) + { if (overwrite != NULL) + *overwrite = ENTRY_VAL(ht_which_value); + ENTRY_VAL(ht_which_value) = value; + goto write_position; } - while( ENTRY_OCCUPIED() ) - { if(overwrite) - { if(bin_keys_identical(entry_pos, ht_entry->key)) - break; - else - { eprintf("error in hashtable insertion, keys are identical"); - } - } - if (HT_END(ht_end)) - LOOP_ENTRY(ht_start); - else - INC_DEF_ENTRY(); + if (entry_row < ht_rows) + entry_row++; + else if (looped) + eprintf("cannot insert into filled hashtable\n"); + else + { looped++; + entry_row = 0; } - WRITE_DEF_ENTRY(); - - return entry_pos; - + goto next_entry; } -long -#define WRITE_VAR_ENTRY() do { \ - if(fseek(binaryout, entry_pos, SEEK_SET) == -1) wprintf("fseek failed with %s", strerror(errno)); \ - fwrite(&var_ht_entry, sizeof var_ht_entry, 1, binaryout); \ -} while (0) -#define INC_VAR_ENTRY() do { \ - entry_pos += sizeof(var_ht_entry); \ - if(fseek(binaryout, entry_pos, SEEK_SET) == -1) eprintf("fseek failed with %s", strerror(errno)); \ - } while (0) -bin_insert_var_ht_entry -( long ht_start, - int ht_size, - struct bin_var_ht_entry_t* var_ht_entry, - int overwrite -) -{ long entry_pos, ht_end; - ht_end = ht_start + ht_size; - entry_pos = ht_start + sizeof(var_ht_entry) * ht_entry->key; - fseek(binaryout, entry_pos, SEEK_SET); - - if (!ENTRY_OCCUPIED()) - { uprintf("key not occupied\n"); - WRITE_VAR_ENTRY(); +static +uint32_t* mem_ht_insert +( void* ht_start, + int ht_row_values, + int ht_which_value, + int ht_rows, + uint32_t* overwrite, + uint32_t key, + uint32_t value +) +{ uint32_t* entry; + uint8_t looped = 0; + size_t entry_row = key & (ht_rows - 1); + int i; + next_entry: + entry = (uint32_t*)ht_start + (ht_row_values * entry_row); + for (i = 0; i < ht_row_values; i++) + if (entry[i] != 0) + goto populated; + write_position: + entry[ht_which_value] = value; + return &entry[ht_which_value]; + populated: + if (ENTRY_KEY == key) + { if (overwrite != NULL) + *overwrite = ENTRY_VAL(ht_which_value); + goto write_position; } - while( ENTRY_OCCUPIED() ) - { if(overwrite) - { if(bin_keys_identical(entry_pos, ht_entry->key)) - break; - else - { eprintf("error in hashtable insertion, keys are identical"); - } - } - if (HT_END(ht_end)) - LOOP_ENTRY(ht_start); - else - INC_VAR_ENTRY(); + if (entry_row < ht_rows) + entry_row++; + else if (looped) + eprintf("cannot insert into filled hashtable\n"); + else + { looped++; + entry_row = 0; } - WRITE_VAR_ENTRY(); - - return entry_pos; + goto next_entry; +} /** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */ static inline @@ -346,7 +366,6 @@ bin_traverse_class { ir_class citer; ir_set siter; struct bin_class_header_t class_header; - struct bin_def_ht_entry_t ht_entry; long class_start, classht_start, classht_size, rootsetht_start, rootsetht_size; int num_class_entries, num_rootset_entries; uint8_t* class_name; @@ -379,9 +398,11 @@ bin_traverse_class /* Start populating root_set hash table */ for ( siter = ir_class_rootset(class); siter != NULL; siter = ir_set_nextsib(siter)) { fseek(binaryout, 0, SEEK_END); - ht_entry.key = NAMEHASH(ir_set_name(siter), num_rootset_entries); - ht_entry.value = bin_traverse_set(siter); - bin_insert_def_ht_entry(rootsetht_start, rootsetht_size, &ht_entry, 0); + file_ht_insert(rootsetht_start, 2, 1, + rootsetht_size, + &old_value, + NAMEHASH(ir_set_name(siter), num_rootset_entries), + bin_traverse_set(siter)); } /* Start populating class child hash table */ @@ -389,9 +410,11 @@ bin_traverse_class { if(chdir((char*) class_name)) eprintf("CHDIR %U from %s\n",(char*) class_name,getcwd(NULL,255)); fseek(binaryout, 0, SEEK_END); - ht_entry.key = NAMEHASH(ir_class_name(citer), num_class_entries); - ht_entry.value = bin_traverse_class(citer); - bin_insert_def_ht_entry(classht_start, classht_size, &ht_entry, 0); + file_ht_insert(classht_start, 2, 1, + classht_size, + &old_value, + NAMEHASH(ir_class_name(citer), num_class_entries), + bin_traverse_class(citer)); if (chdir("..")) eprintf("CHDIR ..\n"); } @@ -448,7 +471,7 @@ bin_traverse_set { fseek(binaryout, 0, SEEK_END); ht_entry.key = NAMEHASH(ir_set_name(iter), num_entries); ht_entry.value = bin_traverse_set(iter); - bin_insert_def_ht_entry(childht_start, childht_size, &ht_entry, 0); + bin_insert_ht_entry(childht_start, childht_size, &ht_entry, 0); }