dtv-scan-tables.git - dtv-scan-tables Debian packaging

diff options

Diffstat (limited to '')

-rw-r--r--

1 files changed, 28 insertions, 9 deletions

/* $Id: hash.c,v 1.17 2004/03/11 06:39:59 reinelt Exp $ * * hashes (associative arrays) * * Copyright 1999-2003 Michael Reinelt <reinelt@eunet.at> * Copyright 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.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: * * hash_anything * Fixme: document me! * */ #include "config.h" #include <stdlib.h> #include <stdio.h> #include <string.h> #include <regex.h> //#include <sys/types.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 // bsearch compare function for hash entries static int hash_lookup_f (const void *a, const void *b) { char *key=(char*)a; HASH_ITEM *item=(HASH_ITEM*)b; return strcmp(key, item->key); } // qsort compare function for hash tables static int hash_sort_f (const void *a, const void *b) { HASH_ITEM *ha=(HASH_ITEM*)a; HASH_ITEM *hb=(HASH_ITEM*)b; return strcasecmp(ha->key, hb->key); } // 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) { 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; } // lookup using bsearch if (Hash->sorted) { Item=bsearch(key, Hash->Items, Hash->nItems, sizeof(HASH_ITEM), hash_lookup_f); } // 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; } // 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) { HASH_ITEM *Item; int len = strlen(val); 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; } // 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); Item->root = 0; Item->Slot = NULL; hash_got_string: // set timestamps gettimeofday(&Hash->time, NULL); Item->time = Hash->time; return Item; } // insert a string into the hash table void hash_set (HASH *Hash, char *key, char *val) { hash_set_string (Hash, key, val); } // 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) { 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; // set first entry gettimeofday(&(Item->Slot[Item->root].time), NULL); Item->Slot[Item->root].val=number; } // get a string from the hash table char *hash_get (HASH *Hash, char *key) { HASH_ITEM *Item=hash_lookup(Hash, key, 1); return Item?Item->val:NULL; } // 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) { HASH_ITEM *Item; timeval now, *stamp; int age; 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; return age; } // get a delta value from the delta table double hash_get_delta (HASH *Hash, char *key, int delay) { HASH_ITEM *Item; timeval now, end; int i; double dv, dt; HASH_SLOT *pSlot; // lookup item Item=hash_lookup(Hash, key, 1); if (Item==NULL) return 0.0; if (Item->Slot==NULL) return 0.0; // if delay is zero, return absolute value if (delay==0) return Item->Slot[Item->root].val; // prepare timing values now=Item->Slot[Item->root].time; end.tv_sec = now.tv_sec; end.tv_usec = now.tv_usec-1000*delay; if (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; } // empty slot => use the one before if (pSlot->time.tv_sec==0) { i--; pSlot = &(Item->Slot[(Item->root+i) % DELTA_SLOTS]); } // not enough slots available... 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; 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, char *key, int delay) { double sum=0.0; 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, "", 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); } } regfree(&preg); return sum; } void hash_destroy (HASH *Hash) { int i; if (Hash->Items) { // free all entries 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 (Hash->Items); } Hash->nItems=0; Hash->sorted=0; Hash->Items=NULL; }


context:
space:
mode: