-#include "../ston/ston.h"
#include <stdlib.h> //malloc
#include <stdio.h> //print
+#include <string.h> //memcpy
+#include "../ston/ston.h"
+
+/* ansi terminal colors */
+#define RED "\x1b[31m"
+#define GREEN "\x1b[32m"
+#define YELLOW "\x1b[33m"
+#define BLUE "\x1b[34m"
+#define MAGENTA "\x1b[35m"
+#define CYAN "\x1b[36m"
+#define CLRC "\x1b[0m" //clear current color
+#define CLRCN CLRC"\n"
+
+#define print_val(val) do { \
+ for (i = 0; i < (size_t)columns; i++) \
+ printf("["YELLOW"%x"CLRC"]",val[i]); \
+ printf("\n"); \
+ } while(0)
+
+#define check_ht(_HT) \
+ if ((_HT) == NULL) \
+ { fprintf(stderr,RED"Could not allocate ht32"CLRCN); \
+ return -1; \
+ } \
+ else \
+ printf("ht_size: [units:%i][bytes:%li]\n",ston_ht_size(ht),ston_ht32_size(ht)); \
+
int main(int argc, char* argv[])
-{ ston_ht ht;
- uint32_t* htval;
-
- if ((ht = ston_ht32_new(2,1,0,malloc)) == NULL)
- fprintf(stderr,"Could not allocate ht32\n");
- ston_ht32_insertx(ht,50,1,200);
- htval = ston_ht32_entry(ht,50,1);
- printf("[50][1] = %i\n",*htval);
+{ static ston_ht ht;
+ uint32_t* htval, previous_val;
+ uint32_t val[255], key;
+ size_t idx;
+ size_t i;
+ size_t elements;
+ uint16_t columns;
+
+ printf("up2pow [5] = [%i]\n",ston_up2pow(5));
+ for (i = 0; i < 255; i += 7)
+ printf("trailing0 [%X] = [%x]\n",(uint32_t)i,ston_trailing0(i));
+
+ columns = 2;
+ elements = 1;
+ ht = ston_ht32_new(columns,elements,0,malloc);
+ check_ht(ht);
+ key = 0xFF;
+ val[0] = key;
+ val[1] = 0x5;
+ printf("ht32_insertx: [%x] = ", key);
+ print_val(val);
+ ston_ht32_insertx(ht,key,val,0,columns);
+ idx = 1;
+ htval = ston_ht32_row(ht,key);
+ printf("Read value [%x] matches: %s"CLRCN, htval[idx],
+ (htval[idx] == val[idx]) ? GREEN"PASS" : RED"FAIL");
+
+ val[1] = 0x2;
+ previous_val = ston_ht32_insert(ht,key,1,val[1]);
+ printf("ht32_insert: [%x] = ", key);
+ print_val(val);
+ printf("Previous value [%x] matches [5]: %s"CLRCN, previous_val,
+ (previous_val == 0x5) ? GREEN"PASS" : RED"FAIL");
+
+ free(ht);
+
+ columns = 4;
+ elements = 20;
+ ht = ston_ht32_new(columns,elements,0,malloc);
+ check_ht(ht);
+ printf("Filling hashtable with entries\n");
+ for(key = 0xCEED; elements--; key *= 7)
+ { val[0] = key;
+ for(i = 1; i < columns; i++)
+ val[i] = i * key;
+ ston_ht32_insertx(ht,key,val,0,columns);
+ }
+ printf("Reading entries\n");
+ elements = 20;
+ for(key = 0xCEED; elements--; key *= 7)
+ { htval = ston_ht32_row(ht,key);
+ printf("[%s%x"CLRC"]",(*htval == key) ? GREEN : RED,*htval);
+ for(i = 1; i < columns; i++)
+ printf("[%s%x"CLRC"]",(htval[i] == (uint32_t)(i * key)) ? GREEN : RED,htval[i]);
+ putchar('\n');
+ }
+ int max_capacity = ston_up2pow(20 << 1) - 20;
+ printf("Overfilling hashtable with %i entries\n", max_capacity);
+ int cap = max_capacity;
+ for(key = 0xCEED2; cap--; key *= 13)
+ { val[0] = key;
+ for(i = 1; i < columns; i++)
+ val[i] = key * -i;
+ ston_ht32_insertx(ht,key,val,0,columns);
+ }
+ printf("Reading entries\n");
+ cap = max_capacity;
+ for(key = 0xCEED2; cap--; key *= 13)
+ { htval = ston_ht32_row(ht,key);
+ printf("[%s%x"CLRC"]",(*htval == key) ? GREEN : RED,*htval);
+ for(i = 1; i < columns; i++)
+ printf("[%s%x"CLRC"]",(htval[i] == (uint32_t)(key * -i)) ? GREEN : RED,htval[i]);
+ printf("\n");
+ }
+
free(ht);
return 0;
}
#endif //STON_FUNC
#ifdef STON_HT_FREAD
#include <stdio.h>
-#include <string.h> //memcpy
#include <errno.h>
#include <alloca.h>
STON_FUNC_STATIC
#include <stddef.h>
#endif //STON_HT_FREAD
#include <stdint.h>
+#include <string.h> //mem*
/* STON Hashtable Structure
Hashtables are stored as dynamically sized two dimensional arrays
*/
{ uint16_t ht_columns;
uint8_t ht_2pow, ht_flags;
}* ston_ht;
+#define STON_HT_HEADERSIZE (sizeof(struct ston_ht_header_t))
STON_FUNC
-size_t ston_up2pow(size_t);
+uint32_t ston_up2pow(uint32_t);
STON_FUNC
-ston_ht ston_ht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t));
+uint8_t ston_trailing0(uint32_t);
+STON_FUNC
+ston_ht ston_ht32_create(struct ston_ht_header_t,void*(*)(size_t));
STON_FUNC
uint32_t* ston_ht32_row(ston_ht,uint32_t);
STON_FUNC
uint32_t ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t);
+STON_FUNC
+size_t ston_ht32_insertx(ston_ht,uint32_t,uint32_t*,size_t,size_t);
-#define ston_ht32_new(_COL,_N,_F,_FN) ston_ht32_create(_COL,ston_up2pow(_N << 1),_F,_FN)
-#define ston_ht32_entry(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL)
-#define ston_ht32_insertx(_HT,_KEY,_COL,_VAL) *ston_ht32_entry(_HT,_KEY,_COL) = _VAL
+#define ston_ht32_new(_COL,_N,_F,_FN) (ston_ht32_create((struct ston_ht_header_t){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_FN))
+#define ston_ht32_entry(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL)
#define ston_ht_size(_HT) ((_HT)->ht_columns << (_HT)->ht_2pow)
#define ston_ht_rows(_HT) (0x1 << (_HT)->ht_2pow)
#define ston_ht_cols(_HT) ((_HT)->ht_columns)
-#define ston_ht_start(_HT) (((uint8_t*)(_HT)) + sizeof(*(_HT)))
+#define ston_ht_start(_HT) ((uint8_t*)((_HT) + 1))
#define ston_ht_keyrow(_HT,_KEY) ((_KEY) & (ston_ht_rows(ht) - 1))
#define ston_ht32_start(_HT) ((uint32_t*)ston_ht_start(_HT))
#define ston_ht32_end(_HT) (ston_ht32_start(_HT) + ston_ht_size(_HT))
/** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */
STON_FUNC
-size_t ston_up2pow
-( size_t val )
+uint32_t ston_up2pow
+( uint32_t val )
{ val = (val << 1) - 1;
val |= val >> 1;
val |= val >> 2;
return ++val;
}
+/** @see https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel */
+STON_FUNC
+uint8_t ston_trailing0
+( uint32_t v )
+{ uint8_t c = 32;
+ v &= -(int32_t)v;
+ if (v) c--;
+ if (v & 0x0000FFFF) c -= 16;
+ if (v & 0x00FF00FF) c -= 8;
+ if (v & 0x0F0F0F0F) c -= 4;
+ if (v & 0x33333333) c -= 2;
+ if (v & 0x55555555) c -= 1;
+ return c;
+}
+
/* Creates a new hash table, provided a memory allocation function that takes a
single size_t bytes, a column count, and a row count which determines the
size of the table.
*/
STON_FUNC
ston_ht ston_ht32_create
-( uint16_t ht_columns,
- size_t ht_rows,
- uint8_t ht_flags,
- void* (*alloc_fn)(size_t)
+( struct ston_ht_header_t ht_header,
+ void* (*alloc_fn)(size_t)
)
-{ size_t ht_size = ht_rows * ht_columns * sizeof(uint32_t);
- ston_ht ht = (ston_ht) alloc_fn(sizeof(struct ston_ht_header_t) + ht_size);
+{ size_t ht_bytes = ston_ht32_size(&ht_header);
+ ston_ht ht = (ston_ht) alloc_fn(STON_HT_HEADERSIZE + ht_bytes);
if (ht != NULL)
- { for (ht->ht_2pow = 0; ht_size; ht->ht_2pow++)
- ht_size = ht_size >> 1;
- ht->ht_columns = ht_columns;
- ht->ht_flags = ht_flags;
+ { memcpy(ht,&ht_header,STON_HT_HEADERSIZE);
+ memset(ht + 1, 0, ht_bytes);
}
return ht;
}
entire structure is verified, and all file operations are finished.
Returns NULL with properly set errno on failure.
*/
-STON_FUNC_STATIC
-STON_FUNC_NOINLINE
ston_ht ston_ht32_fread
( FILE* file,
long fpos,
populated:
if (row[0] == key)
goto write_position;
- if (row < row_end)
+ if (row + ht_cols < row_end)
row += ht_cols;
else if (looped)
return NULL;
return old_value;
}
+/* Inserts a row of units into a hashtable, starting with the specified column.
+ Returns the number of elements that were written. This function will not
+ overflow internal buffers, but will return a short count (lower than the
+ provided 'units') when truncation of source data occurs. */
+STON_FUNC
+size_t
+ston_ht32_insertx
+( struct ston_ht_header_t* ht,
+ uint32_t key,
+ uint32_t* data_src,
+ size_t start_column,
+ size_t units
+)
+{ uint32_t* data_row = ston_ht32_row(ht,key);
+ uint32_t* data_limit = data_row + ston_ht_cols(ht);
+ uint32_t* data_trg = data_row + start_column;
+ if (data_row == NULL)
+ return 0;
+ while (units-- && data_trg < data_limit)
+ *data_trg++ = *data_src++;
+ return (size_t)(data_trg - data_row);
+}
+
+
#ifndef STON_DHT_SIZE
#define STON_DHT_SIZE 4096
#endif
projects / henge / apc.git / commitdiff