path: root/hash.c

/* $Id: hash.c,v 1.25 2005/01/18 06:30:23 reinelt Exp $
 *
 * hashes (associative arrays)
 *
 * Copyright (C) 2003 Michael Reinelt <reinelt@eunet.at>
 * Copyright (C) 2004 The LCD4Linux Team <lcd4linux-devel@users.sourceforge.net>
 *
 * This file is part of LCD4Linux.
 *
 * LCD4Linux is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2, or (at your option)
 * any later version.
 *
 * LCD4Linux 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, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 *
 * $Log: hash.c,v $
 * Revision 1.25  2005/01/18 06:30:23  reinelt
 * added (C) to all copyright statements
 *
 * Revision 1.24  2004/06/26 12:04:59  reinelt
 *
 * uh-oh... the last CVS log message messed up things a lot...
 *
 * Revision 1.23  2004/06/26 09:27:21  reinelt
 *
 * added '-W' to CFLAGS
 * changed all C++ comments to C ones
 * cleaned up a lot of signed/unsigned mistakes
 *
 * Revision 1.22  2004/06/20 10:09:56  reinelt
 *
 * 'const'ified the whole source
 *
 * 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)
 *
 * Revision 1.19  2004/06/01 06:45:30  reinelt
 *
 * some Fixme's processed
 * documented some code
 *
 * Revision 1.18  2004/05/31 16:39:06  reinelt
 *
 * added NULL display driver (for debugging/profiling purposes)
 * added backlight/contrast initialisation for matrixOrbital
 * added Backlight initialisation for Cwlinux
 *
 * Revision 1.17  2004/03/11 06:39:59  reinelt
 * big patch from Martin:
 * - reuse filehandles
 * - memory leaks fixed
 * - earlier busy-flag checking with HD44780
 * - reuse memory for strings in RESULT and hash
 * - netdev_fast to wavid time-consuming regex
 *
 * Revision 1.16  2004/03/03 08:40:07  hejl
 * Fixed memory leak in hash_get_regex
 *
 * Revision 1.15  2004/03/03 04:44:16  reinelt
 * changes (cosmetics?) to the big patch from Martin
 * hash patch un-applied
 *
 * Revision 1.14  2004/03/03 03:47:04  reinelt
 * big patch from Martin Hejl:
 * - use qprintf() where appropriate
 * - save CPU cycles on gettimeofday()
 * - add quit() functions to free allocated memory
 * - fixed lots of memory leaks
 *
 * Revision 1.13  2004/02/27 06:07:55  reinelt
 * hash improvements from Martin
 *
 * Revision 1.12  2004/01/30 20:57:56  reinelt
 * HD44780 patch from Martin Hejl
 * dmalloc integrated
 *
 * Revision 1.11  2004/01/29 04:40:02  reinelt
 * every .c file includes "config.h" now
 *
 * Revision 1.10  2004/01/27 04:48:57  reinelt
 * bug with hash_age() fixed (thanks to Markus Keil for pointing this out)
 *
 * Revision 1.9  2004/01/22 07:57:45  reinelt
 * several bugs fixed where segfaulting on layout>display
 * Crystalfontz driver optimized, 632 display already works
 *
 * Revision 1.8  2004/01/21 14:29:03  reinelt
 * new helper 'hash_get_regex' which delivers the sum over regex matched items
 * new function 'disk()' which uses this regex matching
 *
 * Revision 1.7  2004/01/21 10:48:17  reinelt
 * hash_age function added
 *
 * Revision 1.6  2004/01/20 05:36:59  reinelt
 * moved text-display-specific stuff to drv_generic_text
 * moved all the bar stuff from drv_generic_bar to generic_text
 *
 * Revision 1.5  2004/01/18 09:01:45  reinelt
 * /proc/stat parsing finished
 *
 * Revision 1.4  2004/01/18 06:54:08  reinelt
 * bug in expr.c fixed (thanks to Xavier)
 * some progress with /proc/stat parsing
 *
 * Revision 1.3  2004/01/16 07:26:25  reinelt
 * moved various /proc parsing to own functions
 * made some progress with /proc/stat parsing
 *
 * Revision 1.2  2004/01/16 05:04:53  reinelt
 * started plugin proc_stat which should parse /proc/stat
 * which again is a paint in the a**
 * thinking over implementation methods of delta functions
 * (CPU load, ...)
 *
 * Revision 1.1  2004/01/13 10:03:01  reinelt
 * new util 'hash' for associative arrays
 * new plugin 'cpuinfo'
 *
 */

/* 
 * exported functions:
 *
 * 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_put_delta (HASH *Hash, char *key, char *val);
 *   set a delta entry in the hash
 *
 * char *hash_get (HASH *Hash, char *key);
 *   fetch an entry from the hash
 *
 * double hash_get_delta (HASH *Hash, char *key, int delay);
 *   fetch a delta antry from the hash
 *
 * double hash_get_regex (HASH *Hash, char *key, int delay);
 *   fetch one or more entries from the hash
 *
 * void hash_destroy (HASH *Hash);
 *   releases hash
 *
 */


#include "config.h"

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <regex.h>

#include "debug.h"
#include "hash.h"

#ifdef WITH_DMALLOC
#include <dmalloc.h>
#endif

/* number of slots for delta processing */
#define DELTA_SLOTS 64

/* string buffer chunk size */
#define CHUNK_SIZE 16


/* initialize a new hash table */
void hash_create (HASH *Hash)
{
  Hash->sorted = 0;

  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 items */
static int hash_sort_item (const void *a, const void *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, 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;
}


/* 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, 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;
      }
    }
  }
  
  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)
{
  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)
{
  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)
{
  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;

  return Column->val;
}


/* set column delimiters */
void hash_set_delimiter (HASH *Hash, const char *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)
{
  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)
{
  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 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);
    }
  }
  regfree(&preg);
  return sum;
}


/* 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, 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));
    }

  }
  
  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 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].Slot) free (Hash->Items[i].Slot);
    }
    
    /* free items table */
    free (Hash->Items);
  }
  
  Hash->sorted = 0;
  Hash->nItems = 0;
  Hash->Items  = NULL;
}