{ uint16_t ht_columns;
uint8_t ht_2pow, ht_flags;
}ston_ht_h,* ston_ht;
-#define STON_HT_HEADERSIZE (sizeof(struct ston_ht_header_t))
STON_FUNC
uint32_t ston_up2pow(uint32_t);
STON_FUNC
uint8_t ston_trailing0(uint32_t);
STON_FUNC
-ston_ht ston_ht32_create(struct ston_ht_header_t,void*(*)(size_t));
+ston_ht ston_ht32_create(uint16_t,uint8_t,uint8_t,void*(*)(size_t));
STON_FUNC
uint32_t* ston_ht32_row(ston_ht,uint32_t);
STON_FUNC
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((ston_ht_h){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_FN))
+#define ston_ht32_new(_COL,_N,_F,_FN) (ston_ht32_create(_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)
*/
STON_FUNC
ston_ht ston_ht32_create
-( struct ston_ht_header_t ht_header,
- void* (*alloc_fn)(size_t)
+( uint16_t ht_columns,
+ uint8_t ht_2pow,
+ uint8_t ht_flags,
+ void* (*alloc_fn)(size_t)
)
-{ size_t ht_bytes = ston_ht32_size(&ht_header);
- ston_ht ht = (ston_ht) alloc_fn(STON_HT_HEADERSIZE + ht_bytes);
+{ size_t ht_bytes = (ht_columns << ht_2pow) * sizeof(uint32_t);
+ ston_ht ht = (ston_ht) alloc_fn(sizeof(ston_ht_h) + ht_bytes);
if (ht != NULL)
- { memcpy(ht,&ht_header,STON_HT_HEADERSIZE);
+ { ht->ht_columns = ht_columns;
+ ht->ht_2pow = ht_2pow;
+ ht->ht_flags = ht_flags;
memset(ht + 1, 0, ht_bytes);
}
return ht;
external allocation.
*/
typedef struct ston_dht_header_t
-{ uint16_t ht_columns;
- uint8_t ht_2pow, ht_flags;
- void* (*ht_alloc)(size_t);
- void (*ht_free)(void*);
- void** page_head;
-}ston_dht_h,* ston_dht;
-#define STON_DHT_HEADERSIZE (sizeof(struct ston_dht_header_t))
+{ uint16_t columns;
+ uint8_t unit_bytes;
+ uint8_t start_depth;
+}ston_dht_h;
+
+typedef struct ston_dht_t
+{ ston_dht_h header;
+ void* pages[sizeof(void*) * 8];
+ void* (*ht_alloc)(size_t);
+ void (*ht_free)(void*);
+}* ston_dht;
STON_FUNC
-ston_dht ston_dht32_create(struct ston_ht_header_t,void*(*)(size_t),void(*)(void*));
+ston_dht ston_dht_create(uint16_t,uint8_t,uint8_t,void*(*)(size_t),void(*)(void*));
STON_FUNC
uint32_t* ston_dht32_row(ston_dht,uint32_t);
STON_FUNC
uint32_t ston_dht32_insert(ston_dht,uint32_t,uint16_t,uint32_t);
STON_FUNC
-size_t ston_dht32_insertx(ston_dht,uint32_t,uint32_t*,size_t,size_t);
+size_t ston_dht32_insertx(ston_dht,uint32_t,uint32_t*,uint16_t,size_t);
STON_FUNC
-ston_dht ston_dht32_free(ston_dht);
+ston_dht ston_dht_free(ston_dht);
+
+#define ston_dht_units(_HT,_DEPTH) ((_HT)->header.columns << _DEPTH)
+#define ston_dht_bytes(_HT,_DEPTH) (ston_dht_units(_HT,_DEPTH) * (_HT)->header.unit_bytes)
+#define ston_dht_new(_COL,_ALOC,_FRE) (ston_dht_create(_COL,3,sizeof(int),_ALOC,_FRE))
+#define ston_dht_sized(_COL,_N,_ALOC,_FRE) (ston_dht_create(_COL,ston_trailing0(ston_up2pow(_N),sizeof(int),_ALOC,_FRE)))
+#define ston_dht32_entry(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL)
+#define ston_dht32_new(_COL,_ALOC,_FRE) (ston_dht_create(_COL,0,sizeof(uint32_t),_ALOC,_FRE))
+#define ston_dht32_sized(_COL,_N,_ALOC,_FRE) (ston_dht_create(_COL,ston_trailing0(ston_up2pow(_N)),sizeof(uint32_t),_ALOC,_FRE))
-#define ston_dht32_new(_COL,_N,_F,_ALLOC,_FREE) (ston_dht32_create((ston_ht_h){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_ALLOC,_FREE))
-#define ston_dht32_entry(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL)
-#define ston_dht_size(_HT) (ston_ht_size(_HT))
-#define ston_dht_rows(_HT) (ston_ht_rows(_HT))
-#define ston_dht_cols(_HT) (ston_ht_cols(_HT))
-#define ston_dht_keyrow(_HT,_KEY) (ston_ht_keyrow(_HT,_KEY))
-#define ston_dht_pagestart(_HT) ((void**)(((uint8_t*)(_HT)) + STON_DHT_HEADERSIZE))
-#define ston_dht_pagehead(_HT) ((_HT)->page_head)
-#define ston_dht_pagemax(_HT) ((void**)((uint8_t*)(_HT) + STON_DHT_SIZE - sizeof(void**)))
-#define ston_dht_start(_HT,_DEPTH) ((uint8_t*)*(ston_dht_pagestart(_HT) + _DEPTH))
-#define ston_dht32_start(_HT,_DEPTH) ((uint32_t*)ston_dht_start(_HT,_DEPTH))
-#define ston_dht32_end(_HT,_DEPTH) (ston_ht32_start(_HT,_DEPTH) + ston_ht_size(_HT))
-#define ston_dht32_size(_HT) (ston_dht_size(_HT) * sizeof(uint32_t))
-#define ston_dht32_pagepush(_HT) ((*(++((_HT)->page_head)) = (_HT)->ht_alloc(ston_dht32_size(_HT))))
-#define ston_dht32_pagepop(_HT) ((_HT)->ht_free((_HT)->page_head--))
/* Creates a new bucketted hash table, provided a memory allocation function
that takes a single size_t bytes, a memory free function, a column count, and
a row count which determines the size of the buckets.
*/
STON_FUNC
-ston_dht ston_dht32_create
-( struct ston_ht_header_t ht_header,
- void* (*ht_alloc)(size_t),
- void (*ht_free)(void*)
+ston_dht ston_dht_create
+( uint16_t columns,
+ uint8_t start_depth,
+ uint8_t unit_bytes,
+ void* (*ht_alloc)(size_t),
+ void (*ht_free)(void*)
)
-{ size_t ht_bytes = ston_dht32_size(&ht_header);
- ston_dht ht = (ston_dht) ht_alloc(STON_DHT_SIZE);
+{ ston_dht ht = (ston_dht) ht_alloc(sizeof(struct ston_dht_t));
if (ht != NULL)
- { memcpy(ht, &ht_header, sizeof(ht_header));
+ { ht->header.columns = columns;
+ ht->header.start_depth = start_depth;
+ ht->header.unit_bytes = unit_bytes;
+ memset(ht->pages, 0, sizeof(void*) * sizeof(void*) * 8);
+ ht->pages[start_depth] = ht_alloc(ston_dht_bytes(ht, start_depth));
ht->ht_alloc = ht_alloc;
ht->ht_free = ht_free;
- ht->page_head = ston_dht_pagestart(ht);
- if ((*(ht->page_head) = ht->ht_alloc(ht_bytes)) == NULL)
- if (ht_free != NULL)
- ht_free(ht);
+ if (ht->pages[start_depth] == NULL && ht_free != NULL)
+ ht_free(ht);
+ else
+ memset(ht->pages[start_depth], 0, ston_dht_bytes(ht, start_depth));
}
return ht;
}
*/
STON_FUNC
uint32_t* ston_dht32_row
-( struct ston_dht_header_t* ht,
- uint32_t key
+( struct ston_dht_t* ht,
+ uint32_t key
)
-{ uint16_t ht_cols = ston_dht_cols(ht);
- size_t row_number = ston_dht_keyrow(ht,key);
- uint32_t** page = (uint32_t**)ston_dht_pagestart(ht);
- uint32_t** pagemax = (uint32_t**)ston_dht_pagemax(ht);
- uint8_t loop_x = 0;
- uint8_t loop_y = 0;
- uint32_t* row,* row_end;
+{ uint16_t columns = ht->header.columns;
+ uint8_t depth = ht->header.start_depth;
+ uint32_t mask = ((0x1 << depth) - 1) >> 1;
+ void* page;
+ uint32_t* row;
+ uint32_t row_key;
next_page:
- row = *page + (row_number * ht_cols);
- row_end = *page + (ston_dht_size(ht) - 1);
- next_row:
- if (row[0] != 0)
- goto populated;
- write_position:
- row[0] = key;
- return row;
- populated:
- if (row[0] == key)
- goto write_position;
- if (!loop_x)
- { if (page < pagemax)
- { if (page == (uint32_t**)ston_dht_pagehead(ht))
- if (ston_dht32_pagepush(ht) == NULL)
- { ston_dht32_free(ht);
- return NULL;
- }
- ++page;
- goto next_row;
- }
- loop_x = 1;
- row_number = (row_number + 1) % ston_dht_rows(ht);
- page = (uint32_t**)ston_dht_pagestart(ht);
- goto next_row;
- }
- if (row + ht_cols < row_end)
- { row += ht_cols;
- goto next_row;
- }
- else if (!loop_y)
- { loop_y = 1;
- row = *page;
- goto next_row;
+ if (ht->pages[depth] == NULL)
+ { ht->pages[depth] = ht->ht_alloc(ston_dht_bytes(ht, depth));
+ if (ht->pages[depth] == NULL)
+ return NULL;
+ memset(ht->pages[depth], 0, ston_dht_bytes(ht, depth));
}
- if (page < pagemax)
- { loop_y = 0;
- page++;
- goto next_page;
+ page = ht->pages[depth];
+ row = (uint32_t*)page + ((key & mask) * columns);
+ row_key = *row;
+ if (row_key == key || row_key == 0)
+ { row[0] = key;
+ return row;
}
- return NULL;
+ depth++;
+ mask = (mask << 1) | 0x1;
+ goto next_page;
}
/* Inserts a value into a hashtable at the specified column, returning the
previous value */
STON_FUNC
uint32_t ston_dht32_insert
-( struct ston_dht_header_t* ht,
- uint32_t key,
- uint16_t column,
- uint32_t value
+( struct ston_dht_t* ht,
+ uint32_t key,
+ uint16_t column,
+ uint32_t value
)
{ uint32_t* value_location, old_value;
value_location = ston_dht32_entry(ht,key,column);
return old_value;
}
-/* Free the dynamic hash table */
-STON_FUNC
-struct ston_dht_header_t* ston_dht32_free
-( struct ston_dht_header_t* ht )
-{ void (*ht_free)(void*) = ht->ht_free;
- if (ht_free != NULL)
- { while (ht->page_head >= ston_dht_pagestart(ht))
- { ht_free(*(ht->page_head));
- ht->page_head--;
- }
- ht_free(ht);
- return NULL;
- }
- return ht;
-}
-
/* Insert multiple values, returning the number of bytes written */
STON_FUNC
size_t
ston_dht32_insertx
-( struct ston_dht_header_t* ht,
- uint32_t key,
- uint32_t* data_src,
- size_t start_column,
- size_t units
+( struct ston_dht_t* ht,
+ uint32_t key,
+ uint32_t* data_src,
+ uint16_t start_column,
+ size_t units
)
{ uint32_t* data_row = ston_dht32_row(ht,key);
- uint32_t* data_limit = data_row + ston_dht_cols(ht);
+ uint32_t* data_limit = data_row + ht->header.columns;
uint32_t* data_trg = data_row + start_column;
if (data_row == NULL)
return 0;
return (size_t)(data_trg - data_row);
}
+/* Free the dynamic hash table */
+STON_FUNC
+struct ston_dht_t* ston_dht_free
+( struct ston_dht_t* ht )
+{ void (*ht_free)(void*) = ht->ht_free;
+ uint8_t depth = ht->header.start_depth;
+ void** pages = ht->pages;
+ if (ht_free != NULL)
+ { while (pages[depth] != NULL)
+ ht_free(pages[depth++]);
+ ht_free(ht);
+ return NULL;
+ }
+ return ht;
+}
+
#endif //_STON_HT_H_
projects / henge / apc.git / commitdiff