/* Copyright (C) 2011 G.P. Halkes
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License version 3, as
published by the Free Software Foundation.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see .
*/
#include
#include
#include
#include "definitions.h"
#include "hashtable.h"
#define MEMBLOCK_SIZE 32768
#define ALIGNOF(type) offsetof(struct { char c; type member; }, member)
#define ROUNDUP(x, to) (((x + (to - 1)) / to) * to)
typedef struct MemBlock {
struct MemBlock *next;
size_t size;
size_t idx;
} MemBlock;
static MemBlock *head;
#define HASHTABLE_SIZE 8091
typedef struct Tuple {
ValueType value;
size_t stringLength;
struct Tuple *next;
char string[1];
} Tuple;
static Tuple *hashtable[HASHTABLE_SIZE];
static ValueType nextValue;
ValueType baseHashMax;
static Tuple *allocFromBlock(size_t size) {
Tuple *result;
size = ROUNDUP(size, ALIGNOF(Tuple));
if (head == NULL || size > head->size - head->idx) {
MemBlock *newBlock;
if (size > 2048) {
newBlock = safe_malloc(size + sizeof(MemBlock));
newBlock->size = size + sizeof(MemBlock);
} else {
newBlock = safe_malloc(MEMBLOCK_SIZE);
newBlock->size = MEMBLOCK_SIZE;
}
newBlock->idx = ROUNDUP(sizeof(MemBlock), ALIGNOF(Tuple));
newBlock->next = head;
head = newBlock;
}
result = (Tuple *)(((char *) head) + head->idx);
head->idx += size;
return result;
}
static void freeBlocks(void) {
MemBlock *ptr;
while (head != NULL) {
ptr = head;
head = head->next;
free(ptr);
}
}
#ifdef PROFILE_HASH
static int collisions;
static int hits;
void printHashStatistics(void) {
fprintf(stderr, "Hash statistics: unique words: %d, collisions %d (%.2f%%), hits %d\n",
(int) nextValue, collisions, (double) collisions * 100.0 / nextValue, hits);
collisions = 0;
hits = 0;
}
#endif
/** Calculate a hash value for a string.
@param key The string to hash.
@return The hash value associated with the string.
This function uses the djb2 hash function.
*/
static unsigned int hash(void *data, size_t size) {
const unsigned char *ptr;
size_t i;
unsigned int hashValue = 5381;
ptr = data;
for (i = 0; i < size; i++)
hashValue = (hashValue << 5) + hashValue + (unsigned int) *ptr++;
return hashValue;
}
/** Get the value associated with a word.
@param word The word to get the value for.
This function gets the value associated with a word. If the word has not been
seen before a new value will be given.
*/
ValueType getValueFromContext(CharBuffer *word) {
return getValue(word->data, word->used);
}
ValueType getValue(void *data, size_t size) {
Tuple *tuple;
unsigned int hashValue = hash(data, size) % HASHTABLE_SIZE;
tuple = hashtable[hashValue];
/* Search the singly linked list. */
while (tuple != NULL && !(size == tuple->stringLength && memcmp(data, tuple->string, size) == 0))
tuple = tuple->next;
if (tuple == NULL) {
ASSERT(nextValue != VALUE_MAX);
#ifdef PROFILE_HASH
if (hashtable[hashValue] != NULL)
collisions++;
#endif
tuple = allocFromBlock(sizeof(Tuple) - 1 + size);
tuple->value = nextValue++;
tuple->stringLength = size;
memcpy(tuple->string, data, size);
tuple->next = hashtable[hashValue];
hashtable[hashValue] = tuple;
}
#ifdef PROFILE_HASH
else
hits++;
#endif
return tuple->value;
}
ValueType getHashMax(void) {
ValueType hashMax = nextValue;
int i;
#ifdef PROFILE_HASH
printHashStatistics();
#endif
/* Reset the hashtable for the next iteration. */
for (i = 0; i < HASHTABLE_SIZE; i++)
hashtable[i] = NULL;
freeBlocks();
nextValue = 0;
return hashMax;
}