diff options
Diffstat (limited to 'hash.c')
| -rw-r--r-- | hash.c | 599 |
1 files changed, 312 insertions, 287 deletions
@@ -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; } |