aboutsummaryrefslogtreecommitdiffstats
path: root/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'hash.c')
-rw-r--r--hash.c441
1 files changed, 283 insertions, 158 deletions
diff --git a/hash.c b/hash.c
index f66d6e1..bd3f73c 100644
--- a/hash.c
+++ b/hash.c
@@ -1,4 +1,4 @@
-/* $Id: hash.c,v 1.20 2004/06/13 01:12:52 reinelt Exp $
+/* $Id: hash.c,v 1.21 2004/06/17 06:23:43 reinelt Exp $
*
* hashes (associative arrays)
*
@@ -23,6 +23,10 @@
*
*
* $Log: hash.c,v $
+ * Revision 1.21 2004/06/17 06:23:43 reinelt
+ *
+ * hash handling rewritten to solve performance issues
+ *
* Revision 1.20 2004/06/13 01:12:52 reinelt
*
* debug widgets changed (thanks to Andy Baxter)
@@ -114,15 +118,18 @@
/*
* exported functions:
*
- * void hash_set (HASH *Hash, char *key, char *val);
+ * void hash_create (HASH *Hash);
+ * initializes hash
+ *
+ * int hash_age (HASH *Hash, char *key, char **value);
+ * return time of last hash_put
+ *
+ * void hash_put (HASH *Hash, char *key, char *val);
* set an entry in the hash
*
- * void hash_set_delta (HASH *Hash, char *key, char *val);
+ * void hash_put_delta (HASH *Hash, char *key, char *val);
* set a delta entry in the hash
*
- * int hash_age (HASH *Hash, char *key, char **value);
- * return time of last hash_set
- *
* char *hash_get (HASH *Hash, char *key);
* fetch an entry from the hash
*
@@ -159,55 +166,125 @@
#define CHUNK_SIZE 16
-// bsearch compare function for hash entries
-static int hash_lookup_f (const void *a, const void *b)
+// initialize a new hash table
+void hash_create (HASH *Hash)
{
- char *key=(char*)a;
- HASH_ITEM *item=(HASH_ITEM*)b;
+ Hash->sorted = 0;
- return strcmp(key, item->key);
+ Hash->timestamp.tv_sec = 0;
+ Hash->timestamp.tv_usec = 0;
+
+ Hash->nItems = 0;
+ Hash->Items = NULL;
+
+ Hash->nColumns = 0;
+ Hash->Columns = NULL;
+
+ Hash->delimiter = strdup (" \t\n");
+}
+
+
+// bsearch compare function for hash items
+static int hash_lookup_item (const void *a, const void *b)
+{
+ char *key = (char*)a;
+ HASH_ITEM *item = (HASH_ITEM*)b;
+
+ return strcasecmp(key, item->key);
}
-// qsort compare function for hash tables
-static int hash_sort_f (const void *a, const void *b)
+// qsort compare function for hash items
+static int hash_sort_item (const void *a, const void *b)
{
- HASH_ITEM *ha=(HASH_ITEM*)a;
- HASH_ITEM *hb=(HASH_ITEM*)b;
+ HASH_ITEM *ha = (HASH_ITEM*)a;
+ HASH_ITEM *hb = (HASH_ITEM*)b;
return strcasecmp(ha->key, hb->key);
}
+// bsearch compare function for hash headers
+static int hash_lookup_column (const void *a, const void *b)
+{
+ char *key = (char*)a;
+ HASH_COLUMN *column = (HASH_COLUMN*)b;
+
+ return strcasecmp(key, column->key);
+}
+
+
+// qsort compare function for hash headers
+static int hash_sort_column (const void *a, const void *b)
+{
+ HASH_COLUMN *ha = (HASH_COLUMN*)a;
+ HASH_COLUMN *hb = (HASH_COLUMN*)b;
+
+ return strcasecmp(ha->key, hb->key);
+}
+
+
+// split a value into columns and
+// return the nth column in a string
+// WARNING: does return a pointer to a static string!!
+static char* split (const char *val, int column, const char *delimiter)
+{
+ static char buffer[256];
+ int num, len;
+ const char *beg, *end;
+
+ if (column < 0) return (char*)val;
+ if (val == NULL) return NULL;
+
+ num = 0;
+ len = 0;
+ beg = val;
+ end = beg;
+ while (beg && *beg) {
+ while (strchr(delimiter, *beg)) beg++;
+ end = strpbrk (beg, delimiter);
+ if (num++ == column) break;
+ beg = end ? end+1 : NULL;
+ }
+ if (beg != NULL) {
+ len = end ? end - beg : strlen(beg);
+ if (len >= sizeof(buffer)) len = sizeof(buffer)-1;
+ strncpy (buffer, beg, len);
+ }
+
+ buffer[len] = '\0';
+ return buffer;
+}
+
+
// search an entry in the hash table:
// If the table is flagged "sorted", the entry is looked
// up using the bsearch function. If the table is
// unsorted, it will be searched in a linear way
-
-static HASH_ITEM* hash_lookup (HASH *Hash, char *key, int sortit)
+static HASH_ITEM* hash_lookup (HASH *Hash, const char *key, int do_sort)
{
- HASH_ITEM *Item=NULL;
+ HASH_ITEM *Item = NULL;
// maybe sort the array
- if (sortit && !Hash->sorted) {
- qsort(Hash->Items, Hash->nItems, sizeof(HASH_ITEM), hash_sort_f);
- Hash->sorted=1;
+ if (do_sort && !Hash->sorted) {
+ qsort(Hash->Items, Hash->nItems, sizeof(HASH_ITEM), hash_sort_item);
+ Hash->sorted = 1;
}
// no key was passed
- if (key==NULL) return NULL;
+ if (key == NULL) return NULL;
// lookup using bsearch
if (Hash->sorted) {
- Item=bsearch(key, Hash->Items, Hash->nItems, sizeof(HASH_ITEM), hash_lookup_f);
+ Item = bsearch(key, Hash->Items, Hash->nItems, sizeof(HASH_ITEM), hash_lookup_item);
}
// linear search
- if (Item==NULL) {
+ if (Item == NULL) {
int i;
- for (i=0;i<Hash->nItems; i++) {
- if (strcmp(key, Hash->Items[i].key)==0) {
- Item=&(Hash->Items[i]);
+ for (i = 0; i < Hash->nItems; i++) {
+ if (strcmp(key, Hash->Items[i].key) == 0) {
+ Item = &(Hash->Items[i]);
break;
}
}
@@ -218,176 +295,134 @@ static HASH_ITEM* hash_lookup (HASH *Hash, char *key, int sortit)
}
-// insert a key/val pair into the hash table
-// If the entry does already exist, it will be overwritten,
-// and the table stays sorted (if it has been before).
-// Otherwise, the entry is appended at the end, and
-// the table will be flagged 'unsorted' afterwards
-
-static HASH_ITEM* hash_set_string (HASH *Hash, char *key, char *val)
+// return the age in milliseconds of an entry from the hash table
+// or from the hash table itself if key is NULL
+// returns -1 if entry does not exist
+int hash_age (HASH *Hash, const char *key)
{
HASH_ITEM *Item;
- int len = strlen(val);
+ struct timeval now, *timestamp;
- Item = hash_lookup (Hash, key, 0);
-
- // entry already exists?
- if (Item != NULL) {
- if (len > Item->len) {
- // buffer is either empty or too small
- if (Item->val) free (Item->val);
- // allocate memory in multiples of CHUNK_SIZE
- // note that length does not count the trailing \0
- Item->len = CHUNK_SIZE*(len/CHUNK_SIZE+1)-1;
- Item->val = malloc(Item->len+1);
- }
- strcpy(Item->val, val);
- goto hash_got_string;
+ if (key == NULL) {
+ timestamp = &(Hash->timestamp);
+ } else {
+ Item = hash_lookup(Hash, key, 1);
+ if (Item == NULL) return -1;
+ timestamp = &(Item->Slot[Item->index].timestamp);
}
-
- // add entry
- Hash->sorted = 0;
- Hash->nItems++;
- Hash->Items = realloc(Hash->Items, Hash->nItems*sizeof(HASH_ITEM));
-
- Item = &(Hash->Items[Hash->nItems-1]);
- Item->key = strdup(key);
-
- Item->len = CHUNK_SIZE*(len/CHUNK_SIZE+1)-1;
- Item->val = malloc(Item->len+1);
- strcpy(Item->val, val);
+ gettimeofday(&now, NULL);
- Item->root = 0;
- Item->Slot = NULL;
-
- hash_got_string:
- // set timestamps
- gettimeofday(&Hash->time, NULL);
- Item->time = Hash->time;
-
- return Item;
+ return (now.tv_sec - timestamp->tv_sec)*1000 + (now.tv_usec - timestamp->tv_usec)/1000;
}
-// insert a string into the hash table
-void hash_set (HASH *Hash, char *key, char *val)
+// add an entry to the column header table
+void hash_set_column (HASH *Hash, int number, const char *column)
{
- hash_set_string (Hash, key, val);
+ if (Hash == NULL) return;
+
+ Hash->nColumns++;
+ Hash->Columns = realloc(Hash->Columns, Hash->nColumns * sizeof(HASH_COLUMN));
+ Hash->Columns[Hash->nColumns-1].key = strdup(column);
+ Hash->Columns[Hash->nColumns-1].val = number;
+
+ qsort(Hash->Columns, Hash->nColumns, sizeof(HASH_COLUMN), hash_sort_column);
+
}
-// insert a string into the hash table
-// convert it into a number, and store it in the
-// delta table, too
-void hash_set_delta (HASH *Hash, char *key, char *val)
+// fetch a column number by column header
+static int hash_get_column (HASH *Hash, const char *key)
{
- double number=atof(val);
- HASH_ITEM *Item;
-
- Item=hash_set_string (Hash, key, val);
-
- // allocate delta table
- if (Item->Slot==NULL) {
- Item->root = 0;
- Item->Slot = malloc(DELTA_SLOTS*sizeof(HASH_SLOT));
- memset(Item->Slot, 0, DELTA_SLOTS*sizeof(HASH_SLOT));
- }
-
- // move the pointer to the next free slot, wrap around if necessary
- if (--Item->root < 0) Item->root = DELTA_SLOTS-1;
+ HASH_COLUMN *Column;
- // set first entry
- gettimeofday(&(Item->Slot[Item->root].time), NULL);
- Item->Slot[Item->root].val=number;
+ if (key == NULL || *key == '\0') return -1;
+
+ Column = bsearch(key, Hash->Columns, Hash->nColumns, sizeof(HASH_COLUMN), hash_lookup_column);
+ if (Column == NULL) return -1;
+ return Column->val;
}
-// get a string from the hash table
-char *hash_get (HASH *Hash, char *key)
+// set column delimiters
+void hash_set_delimiter (HASH *Hash, const char *delimiter)
{
- HASH_ITEM *Item=hash_lookup(Hash, key, 1);
- return Item?Item->val:NULL;
+ if (Hash->delimiter != NULL) free (Hash->delimiter);
+ Hash->delimiter = strdup(delimiter);
}
-// return the age in milliseconds of an entry from the hash table
-// or from the hash table itself if key is NULL
-// returns -1 if entry does not exist
-// if **value is set, return the value, too
-int hash_age (HASH *Hash, char *key, char **value)
+// get a string from the hash table
+char *hash_get (HASH *Hash, const char *key, const char *column)
{
HASH_ITEM *Item;
- timeval now, *stamp;
- int age;
+ int c;
- if (key!=NULL) {
- Item=hash_lookup(Hash, key, 1);
- if (value) *value=Item?Item->val:NULL;
- if (Item==NULL) {
- return -1;
- }
- stamp=&Item->time;
- } else {
- stamp=&Hash->time;
- }
-
- gettimeofday(&now, NULL);
-
- age = (now.tv_sec - stamp->tv_sec)*1000 + (now.tv_usec - stamp->tv_usec)/1000;
+ Item = hash_lookup(Hash, key, 1);
+ if (Item == NULL) return NULL;
- return age;
+ c = hash_get_column(Hash, column);
+ return split(Item->Slot[Item->index].value, c, Hash->delimiter);
}
// get a delta value from the delta table
-double hash_get_delta (HASH *Hash, char *key, int delay)
+double hash_get_delta (HASH *Hash, const char *key, const char *column, int delay)
{
HASH_ITEM *Item;
- timeval now, end;
- int i;
+ HASH_SLOT *Slot1, *Slot2;
+ int i, c;
+ double v1, v2;
double dv, dt;
- HASH_SLOT *pSlot;
+ struct timeval now, end;
// lookup item
- Item=hash_lookup(Hash, key, 1);
- if (Item==NULL) return 0.0;
- if (Item->Slot==NULL) return 0.0;
+ Item = hash_lookup(Hash, key, 1);
+ if (Item == NULL) return 0.0;
+ // this is the "current" Slot
+ Slot1 = &(Item->Slot[Item->index]);
+
+ // fetch column number
+ c = hash_get_column(Hash, column);
+
// if delay is zero, return absolute value
- if (delay==0) return Item->Slot[Item->root].val;
+ if (delay == 0) return atof(split(Slot1->value, c, Hash->delimiter));
// prepare timing values
- now=Item->Slot[Item->root].time;
+ now = Slot1->timestamp;
end.tv_sec = now.tv_sec;
- end.tv_usec = now.tv_usec-1000*delay;
- if (end.tv_usec<0) {
+ end.tv_usec = now.tv_usec - 1000*delay;
+ while (end.tv_usec < 0) {
end.tv_sec--;
end.tv_usec += 1000000;
}
// search delta slot
- for (i=1; i<DELTA_SLOTS; i++) {
- pSlot = &(Item->Slot[(Item->root+i) % DELTA_SLOTS]);
- if (pSlot->time.tv_sec==0) break;
- if (timercmp(&(pSlot->time), &end, <)) break;
- dt = (now.tv_sec - pSlot->time.tv_sec) + (now.tv_usec - pSlot->time.tv_usec)/1000000.0;
+ Slot2 = &(Item->Slot[Item->index]);
+ for (i = 1; i < Item->nSlot; i++) {
+ Slot2 = &(Item->Slot[(Item->index + i) % Item->nSlot]);
+ if (Slot2->timestamp.tv_sec == 0) break;
+ if (timercmp(&(Slot2->timestamp), &end, <)) break;
}
-
- // empty slot => use the one before
- if (pSlot->time.tv_sec==0) {
+ // empty slot => try the one before
+ if (Slot2->timestamp.tv_sec == 0) {
i--;
- pSlot = &(Item->Slot[(Item->root+i) % DELTA_SLOTS]);
+ Slot2 = &(Item->Slot[(Item->index + i) % Item->nSlot]);
}
// not enough slots available...
- if (i==0) return 0.0;
+ if (i == 0) return 0.0;
// delta value, delta time
- dv = Item->Slot[Item->root].val - pSlot->val;
- dt = (now.tv_sec - pSlot->time.tv_sec) + (now.tv_usec - pSlot->time.tv_usec)/1000000.0;
+ v1 = atof(split(Slot1->value, c, Hash->delimiter));
+ v2 = atof(split(Slot2->value, c, Hash->delimiter));
+ dv = v1 - v2;
+ dt = (Slot1->timestamp.tv_sec - Slot2->timestamp.tv_sec)
+ + (Slot1->timestamp.tv_usec - Slot2->timestamp.tv_usec)/1000000.0;
if (dt > 0.0 && dv >= 0.0) return dv/dt;
return 0.0;
@@ -397,27 +432,28 @@ double hash_get_delta (HASH *Hash, char *key, int delay)
// get a delta value from the delta table
// key may contain regular expressions, and the sum
// of all matching entries is returned.
-double hash_get_regex (HASH *Hash, char *key, int delay)
+double hash_get_regex (HASH *Hash, const char *key, const char *column, int delay)
{
- double sum=0.0;
+ double sum;
regex_t preg;
int i, err;
- err=regcomp(&preg, key, REG_ICASE|REG_NOSUB);
- if (err!=0) {
+ err = regcomp(&preg, key, REG_ICASE|REG_NOSUB);
+ if (err != 0) {
char buffer[32];
regerror(err, &preg, buffer, sizeof(buffer));
error ("error in regular expression: %s", buffer);
regfree(&preg);
return 0.0;
}
-
+
// force the table to be sorted by requesting anything
hash_lookup(Hash, NULL, 1);
- for (i=0;i<Hash->nItems; i++) {
- if (regexec(&preg, Hash->Items[i].key, 0, NULL, 0)==0) {
- sum+=hash_get_delta(Hash, Hash->Items[i].key, delay);
+ sum = 0.0;
+ for (i = 0; i < Hash->nItems; i++) {
+ if (regexec(&preg, Hash->Items[i].key, 0, NULL, 0) == 0) {
+ sum += hash_get_delta(Hash, Hash->Items[i].key, column, delay);
}
}
regfree(&preg);
@@ -425,24 +461,113 @@ double hash_get_regex (HASH *Hash, char *key, int delay)
}
+// insert a key/val pair into the hash table
+// If the entry does already exist, it will be overwritten,
+// and the table stays sorted (if it has been before).
+// Otherwise, the entry is appended at the end, and
+// the table will be flagged 'unsorted' afterwards
+
+static HASH_ITEM* hash_set (HASH *Hash, const char *key, const char *value, int delta)
+{
+ HASH_ITEM *Item;
+ HASH_SLOT *Slot;
+ int size;
+
+ Item = hash_lookup (Hash, key, 0);
+
+ if (Item == NULL) {
+
+ // add entry
+ Hash->sorted = 0;
+ Hash->nItems++;
+ Hash->Items = realloc(Hash->Items, Hash->nItems * sizeof(HASH_ITEM));
+
+ Item = &(Hash->Items[Hash->nItems-1]);
+ Item->key = strdup(key);
+ Item->index = 0;
+ Item->nSlot = delta;
+ Item->Slot = malloc (Item->nSlot * sizeof(HASH_SLOT));
+ memset(Item->Slot, 0, Item->nSlot * sizeof(HASH_SLOT));
+
+ } else {
+
+ // maybe enlarge delta table
+ if (Item->nSlot < delta) {
+ Item->nSlot = delta;
+ Item->Slot = realloc (Item->Slot, Item->nSlot * sizeof(HASH_SLOT));
+ }
+
+ }
+
+ if (Item->nSlot > 1) {
+ // move the pointer to the next free slot, wrap around if necessary
+ if (--Item->index < 0) Item->index = Item->nSlot-1;
+ }
+
+ // create entry
+ Slot = &(Item->Slot[Item->index]);
+ size = strlen(value) + 1;
+
+ // maybe enlarge value buffer
+ if (size > Slot->size) {
+ // buffer is either empty or too small
+ // allocate memory in multiples of CHUNK_SIZE
+ Slot->size = CHUNK_SIZE * (size / CHUNK_SIZE + 1);
+ Slot->value = realloc(Slot->value, Slot->size);
+ }
+
+ // set value
+ strcpy(Slot->value, value);
+
+ // set timestamps
+ gettimeofday(&(Hash->timestamp), NULL);
+ Slot->timestamp = Hash->timestamp;
+
+ return Item;
+}
+
+
+// insert a string into the hash table
+// without delta processing
+void hash_put (HASH *Hash, const char *key, const char *value)
+{
+ hash_set (Hash, key, value, 1);
+}
+
+
+// insert a string into the hash table
+// with delta processing
+void hash_put_delta (HASH *Hash, const char *key, const char *value)
+{
+ hash_set (Hash, key, value, DELTA_SLOTS);
+}
+
+
void hash_destroy (HASH *Hash)
{
int i;
if (Hash->Items) {
- // free all entries
- for (i=0;i<Hash->nItems; i++) {
+ // free all headers
+ for (i = 0; i < Hash->nColumns; i++) {
+ if (Hash->Columns[i].key) free (Hash->Columns[i].key);
+ }
+
+ // free header table
+ free (Hash->Columns);
+
+ // free all items
+ for (i = 0; i < Hash->nItems; i++) {
if (Hash->Items[i].key) free (Hash->Items[i].key);
- if (Hash->Items[i].val) free (Hash->Items[i].val);
if (Hash->Items[i].Slot) free (Hash->Items[i].Slot);
}
- // free hash table
+ // free items table
free (Hash->Items);
}
- Hash->nItems=0;
- Hash->sorted=0;
- Hash->Items=NULL;
+ Hash->sorted = 0;
+ Hash->nItems = 0;
+ Hash->Items = NULL;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-15 21:43:43 +0000