aboutsummaryrefslogtreecommitdiffstats
path: root/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'hash.c')
-rw-r--r--hash.c599
1 files changed, 312 insertions, 287 deletions
diff --git a/hash.c b/hash.c
index e55e9c4..9eff1a0 100644
--- a/hash.c
+++ b/hash.c
@@ -1,4 +1,4 @@
-/* $Id: hash.c,v 1.25 2005/01/18 06:30:23 reinelt Exp $
+/* $Id: hash.c,v 1.26 2005/05/08 04:32:44 reinelt Exp $
*
* hashes (associative arrays)
*
@@ -23,6 +23,9 @@
*
*
* $Log: hash.c,v $
+ * Revision 1.26 2005/05/08 04:32:44 reinelt
+ * CodingStyle added and applied
+ *
* Revision 1.25 2005/01/18 06:30:23 reinelt
* added (C) to all copyright statements
*
@@ -184,94 +187,99 @@
/* initialize a new hash table */
-void hash_create (HASH *Hash)
+void hash_create(HASH * Hash)
{
- Hash->sorted = 0;
+ Hash->sorted = 0;
+
+ Hash->timestamp.tv_sec = 0;
+ Hash->timestamp.tv_usec = 0;
- Hash->timestamp.tv_sec = 0;
- Hash->timestamp.tv_usec = 0;
-
- Hash->nItems = 0;
- Hash->Items = NULL;
+ Hash->nItems = 0;
+ Hash->Items = NULL;
- Hash->nColumns = 0;
- Hash->Columns = NULL;
+ Hash->nColumns = 0;
+ Hash->Columns = NULL;
- Hash->delimiter = strdup (" \t\n");
+ Hash->delimiter = strdup(" \t\n");
}
/* bsearch compare function for hash items */
-static int hash_lookup_item (const void *a, const void *b)
+static int hash_lookup_item(const void *a, const void *b)
{
- char *key = (char*)a;
- HASH_ITEM *item = (HASH_ITEM*)b;
+ char *key = (char *) a;
+ HASH_ITEM *item = (HASH_ITEM *) b;
- return strcasecmp(key, item->key);
+ return strcasecmp(key, item->key);
}
/* qsort compare function for hash items */
-static int hash_sort_item (const void *a, const void *b)
+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);
+ return strcasecmp(ha->key, hb->key);
}
/* bsearch compare function for hash headers */
-static int hash_lookup_column (const void *a, const void *b)
+static int hash_lookup_column(const void *a, const void *b)
{
- char *key = (char*)a;
- HASH_COLUMN *column = (HASH_COLUMN*)b;
+ char *key = (char *) a;
+ HASH_COLUMN *column = (HASH_COLUMN *) b;
- return strcasecmp(key, column->key);
+ return strcasecmp(key, column->key);
}
/* qsort compare function for hash headers */
-static int hash_sort_column (const void *a, const void *b)
+static int hash_sort_column(const void *a, const void *b)
{
- HASH_COLUMN *ha = (HASH_COLUMN*)a;
- HASH_COLUMN *hb = (HASH_COLUMN*)b;
+ HASH_COLUMN *ha = (HASH_COLUMN *) a;
+ HASH_COLUMN *hb = (HASH_COLUMN *) b;
- return strcasecmp(ha->key, hb->key);
+ 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, const int column, const char *delimiter)
+static char *split(const char *val, const int column, const char *delimiter)
{
- static char buffer[256];
- int num;
- size_t 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 ? (size_t)(end - beg) : strlen(beg);
- if (len >= sizeof(buffer)) len = sizeof(buffer)-1;
- strncpy (buffer, beg, len);
- }
-
- buffer[len] = '\0';
- return buffer;
+ static char buffer[256];
+ int num;
+ size_t 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 ? (size_t) (end - beg) : strlen(beg);
+ if (len >= sizeof(buffer))
+ len = sizeof(buffer) - 1;
+ strncpy(buffer, beg, len);
+ }
+
+ buffer[len] = '\0';
+ return buffer;
}
@@ -279,203 +287,216 @@ static char* split (const char *val, const int column, const char *delimiter)
/* 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, const char *key, const int do_sort)
+static HASH_ITEM *hash_lookup(HASH * Hash, const char *key, const int do_sort)
{
- HASH_ITEM *Item = NULL;
-
- /* maybe sort the array */
- 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;
-
- /* lookup using bsearch */
- if (Hash->sorted) {
- Item = bsearch(key, Hash->Items, Hash->nItems, sizeof(HASH_ITEM), hash_lookup_item);
- }
-
- /* linear search */
- if (Item == NULL) {
- int i;
- for (i = 0; i < Hash->nItems; i++) {
- if (strcmp(key, Hash->Items[i].key) == 0) {
- Item = &(Hash->Items[i]);
- break;
- }
+ HASH_ITEM *Item = NULL;
+
+ /* maybe sort the array */
+ if (do_sort && !Hash->sorted) {
+ qsort(Hash->Items, Hash->nItems, sizeof(HASH_ITEM), hash_sort_item);
+ Hash->sorted = 1;
}
- }
-
- return Item;
-
+
+ /* no key was passed */
+ if (key == NULL)
+ return NULL;
+
+ /* lookup using bsearch */
+ if (Hash->sorted) {
+ Item = bsearch(key, Hash->Items, Hash->nItems, sizeof(HASH_ITEM), hash_lookup_item);
+ }
+
+ /* linear search */
+ if (Item == NULL) {
+ int i;
+ for (i = 0; i < Hash->nItems; i++) {
+ if (strcmp(key, Hash->Items[i].key) == 0) {
+ Item = &(Hash->Items[i]);
+ break;
+ }
+ }
+ }
+
+ return Item;
+
}
/* 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)
+int hash_age(HASH * Hash, const char *key)
{
- HASH_ITEM *Item;
- struct timeval now, *timestamp;
-
- if (key == NULL) {
- timestamp = &(Hash->timestamp);
- } else {
- Item = hash_lookup(Hash, key, 1);
- if (Item == NULL) return -1;
- timestamp = &(Item->Slot[Item->index].timestamp);
- }
-
- gettimeofday(&now, NULL);
-
- return (now.tv_sec - timestamp->tv_sec)*1000 + (now.tv_usec - timestamp->tv_usec)/1000;
+ HASH_ITEM *Item;
+ struct timeval now, *timestamp;
+
+ if (key == NULL) {
+ timestamp = &(Hash->timestamp);
+ } else {
+ Item = hash_lookup(Hash, key, 1);
+ if (Item == NULL)
+ return -1;
+ timestamp = &(Item->Slot[Item->index].timestamp);
+ }
+
+ gettimeofday(&now, NULL);
+
+ return (now.tv_sec - timestamp->tv_sec) * 1000 + (now.tv_usec - timestamp->tv_usec) / 1000;
}
/* add an entry to the column header table */
-void hash_set_column (HASH *Hash, const int number, const char *column)
+void hash_set_column(HASH * Hash, const int number, const char *column)
{
- 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);
-
+ 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);
+
}
/* fetch a column number by column header */
-static int hash_get_column (HASH *Hash, const char *key)
+static int hash_get_column(HASH * Hash, const char *key)
{
- HASH_COLUMN *Column;
+ HASH_COLUMN *Column;
- 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;
+ if (key == NULL || *key == '\0')
+ return -1;
- return Column->val;
+ Column = bsearch(key, Hash->Columns, Hash->nColumns, sizeof(HASH_COLUMN), hash_lookup_column);
+ if (Column == NULL)
+ return -1;
+
+ return Column->val;
}
/* set column delimiters */
-void hash_set_delimiter (HASH *Hash, const char *delimiter)
+void hash_set_delimiter(HASH * Hash, const char *delimiter)
{
- if (Hash->delimiter != NULL) free (Hash->delimiter);
- Hash->delimiter = strdup(delimiter);
+ if (Hash->delimiter != NULL)
+ free(Hash->delimiter);
+ Hash->delimiter = strdup(delimiter);
}
/* get a string from the hash table */
-char *hash_get (HASH *Hash, const char *key, const char *column)
+char *hash_get(HASH * Hash, const char *key, const char *column)
{
- HASH_ITEM *Item;
- int c;
-
- Item = hash_lookup(Hash, key, 1);
- if (Item == NULL) return NULL;
-
- c = hash_get_column(Hash, column);
- return split(Item->Slot[Item->index].value, c, Hash->delimiter);
+ HASH_ITEM *Item;
+ int c;
+
+ Item = hash_lookup(Hash, key, 1);
+ if (Item == NULL)
+ return NULL;
+
+ 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, const char *key, const char *column, const int delay)
+double hash_get_delta(HASH * Hash, const char *key, const char *column, const int delay)
{
- HASH_ITEM *Item;
- HASH_SLOT *Slot1, *Slot2;
- int i, c;
- double v1, v2;
- double dv, dt;
- struct timeval now, end;
-
- /* lookup item */
- 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 atof(split(Slot1->value, c, Hash->delimiter));
-
- /* prepare timing values */
- now = Slot1->timestamp;
- end.tv_sec = now.tv_sec;
- end.tv_usec = now.tv_usec - 1000*delay;
- while (end.tv_usec < 0) {
- end.tv_sec--;
- end.tv_usec += 1000000;
- }
-
- /* search delta slot */
- 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 => try the one before */
- if (Slot2->timestamp.tv_sec == 0) {
- i--;
- Slot2 = &(Item->Slot[(Item->index + i) % Item->nSlot]);
- }
-
- /* not enough slots available... */
- if (i == 0) return 0.0;
-
- /* delta value, delta time */
- 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;
+ HASH_ITEM *Item;
+ HASH_SLOT *Slot1, *Slot2;
+ int i, c;
+ double v1, v2;
+ double dv, dt;
+ struct timeval now, end;
+
+ /* lookup item */
+ 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 atof(split(Slot1->value, c, Hash->delimiter));
+
+ /* prepare timing values */
+ now = Slot1->timestamp;
+ end.tv_sec = now.tv_sec;
+ end.tv_usec = now.tv_usec - 1000 * delay;
+ while (end.tv_usec < 0) {
+ end.tv_sec--;
+ end.tv_usec += 1000000;
+ }
+
+ /* search delta slot */
+ 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 => try the one before */
+ if (Slot2->timestamp.tv_sec == 0) {
+ i--;
+ Slot2 = &(Item->Slot[(Item->index + i) % Item->nSlot]);
+ }
+
+ /* not enough slots available... */
+ if (i == 0)
+ return 0.0;
+
+ /* delta value, delta time */
+ 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;
}
/* 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, const char *key, const char *column, const int delay)
+double hash_get_regex(HASH * Hash, const char *key, const char *column, const int delay)
{
- double sum;
- regex_t preg;
- int i, err;
-
- 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);
-
- 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);
+ double sum;
+ regex_t preg;
+ int i, err;
+
+ 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;
}
- }
- regfree(&preg);
- return sum;
+
+ /* force the table to be sorted by requesting anything */
+ hash_lookup(Hash, NULL, 1);
+
+ 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);
+ return sum;
}
@@ -485,107 +506,111 @@ double hash_get_regex (HASH *Hash, const char *key, const char *column, const in
/* 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, const int delta)
+static HASH_ITEM *hash_set(HASH * Hash, const char *key, const char *value, const 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));
+ 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;
}
- }
-
- 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;
+ /* 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)
+void hash_put(HASH * Hash, const char *key, const char *value)
{
- hash_set (Hash, key, value, 1);
+ 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)
+void hash_put_delta(HASH * Hash, const char *key, const char *value)
{
- hash_set (Hash, key, value, DELTA_SLOTS);
+ hash_set(Hash, key, value, DELTA_SLOTS);
}
-void hash_destroy (HASH *Hash)
+void hash_destroy(HASH * Hash)
{
- int i;
+ int i;
- if (Hash->Items) {
-
- /* free all headers */
- for (i = 0; i < Hash->nColumns; i++) {
- if (Hash->Columns[i].key) free (Hash->Columns[i].key);
- }
+ if (Hash->Items) {
- /* free header table */
- free (Hash->Columns);
+ /* free all headers */
+ for (i = 0; i < Hash->nColumns; i++) {
+ if (Hash->Columns[i].key)
+ free(Hash->Columns[i].key);
+ }
- /* free all items */
- for (i = 0; i < Hash->nItems; i++) {
- if (Hash->Items[i].key) free (Hash->Items[i].key);
- if (Hash->Items[i].Slot) free (Hash->Items[i].Slot);
+ /* 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].Slot)
+ free(Hash->Items[i].Slot);
+ }
+
+ /* free items table */
+ free(Hash->Items);
}
-
- /* free items table */
- free (Hash->Items);
- }
-
- Hash->sorted = 0;
- Hash->nItems = 0;
- Hash->Items = NULL;
+
+ Hash->sorted = 0;
+ Hash->nItems = 0;
+ Hash->Items = NULL;
}