[lcd4linux @ 2004-06-17 06:23:39 by reinelt]

hash handling rewritten to solve performance issues

git-svn-id: https://ssl.bulix.org/svn/lcd4linux/trunk@473 3ae390bd-cb1e-0410-b409-cd5a39f66f1f

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;
 }