X-Git-Url: https://git.gag.com/?a=blobdiff_plain;f=src%2FSDCChasht.c;h=dd6322d451c632b5a70231f1ed0f57b6f979e628;hb=80972b2e54c9b88f11c27b878874fd2a6a681391;hp=df23760b376ba87593ec57e077c3ff0b509aa643;hpb=f4ae1348c3ec937bc78f7c64194dc768cce0838a;p=fw%2Fsdcc diff --git a/src/SDCChasht.c b/src/SDCChasht.c index df23760b..dd6322d4 100644 --- a/src/SDCChasht.c +++ b/src/SDCChasht.c @@ -1,154 +1,175 @@ /*----------------------------------------------------------------- SDCChast.c - contains support routines for hashtables - + Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998) This program 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. - + This program 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. - + In other words, you are welcome to use, share and improve this program. You are forbidden to forbid anyone else to use, share and improve - what you give them. Help stamp out software-hoarding! + what you give them. Help stamp out software-hoarding! -------------------------------------------------------------------------*/ #include #include #include +#include +#include "SDCCglobl.h" #include "SDCChasht.h" - +#include "newalloc.h" #define DEFAULT_HTAB_SIZE 128 /*-----------------------------------------------------------------*/ /* newHashtItem - creates a new hashtable Item */ /*-----------------------------------------------------------------*/ - hashtItem *newHashtItem (int key, void *item) +static hashtItem * +_newHashtItem (int key, void *pkey, void *item) { - hashtItem *htip; - - ALLOC(htip,sizeof(hashtItem)); - - htip->key = key ; - htip->item = item; - htip->next = NULL ; - return htip; + hashtItem *htip; + + htip = Safe_alloc ( sizeof (hashtItem)); + + htip->key = key; + htip->pkey = pkey; + htip->item = item; + htip->next = NULL; + return htip; } /*-----------------------------------------------------------------*/ /* newHashTable - allocates a new hashtable of size */ /*-----------------------------------------------------------------*/ -hTab *newHashTable (int size) +hTab * +newHashTable (int size) { - hTab *htab; - - ALLOC(htab,sizeof(hTab)); - - if (!(htab->table = GC_malloc((size +1)* sizeof(hashtItem *)))) { - fprintf(stderr,"out of virtual memory %s %d\n", - __FILE__,(size +1)* sizeof(hashtItem *)); - exit(1); - } - htab->minKey = htab->size = size ; - return htab; + hTab *htab; + + htab = Safe_alloc ( sizeof (hTab)); + + if (!(htab->table = Safe_alloc ((size + 1) * sizeof (hashtItem *)))) + { + fprintf (stderr, "out of virtual memory %s %d\n", + __FILE__, (size + 1) * (int) sizeof (hashtItem *)); + exit (1); + } + htab->minKey = htab->size = size; + return htab; } +void +hTabAddItemLong (hTab ** htab, int key, void *pkey, void *item) +{ + hashtItem *htip; + hashtItem *last; + + if (!(*htab)) + *htab = newHashTable (DEFAULT_HTAB_SIZE); + + if (key > (*htab)->size) + { + int i; + (*htab)->table = Safe_realloc ((*htab)->table, + (key * 2 + 2) * sizeof (hashtItem *)); + for (i = (*htab)->size + 1; i <= (key * 2 + 1); i++) + (*htab)->table[i] = NULL; + (*htab)->size = key * 2 + 1; + } + + /* update the key */ + if ((*htab)->maxKey < key) + (*htab)->maxKey = key; + + if ((*htab)->minKey > key) + (*htab)->minKey = key; + + /* create the item */ + htip = _newHashtItem (key, pkey, item); + + /* if there is a clash then goto end of chain */ + if ((last = (*htab)->table[key])) + { + while (last->next) + last = last->next; + last->next = htip; + } + else + /* else just add it */ + (*htab)->table[key] = htip; + (*htab)->nItems++; +} + /*-----------------------------------------------------------------*/ /* hTabAddItem - adds an item to the hash table */ /*-----------------------------------------------------------------*/ -void hTabAddItem (hTab **htab, int key, void *item ) -{ - hashtItem *htip ; - hashtItem *last ; - - if (!(*htab) ) - *htab = newHashTable ( DEFAULT_HTAB_SIZE ); - - if (key > (*htab)->size ) { - int i; - (*htab)->table = GC_realloc ((*htab)->table, - (key*2 + 2)*sizeof(hashtItem *)); - for ( i = (*htab)->size +1; i <= (key*2 + 1); i++ ) - (*htab)->table[i] = NULL ; - (*htab)->size = key*2 + 1; - } - - /* update the key */ - if ((*htab)->maxKey < key ) - (*htab)->maxKey = key ; - - if ((*htab)->minKey > key ) - (*htab)->minKey = key ; - - /* create the item */ - htip = newHashtItem (key,item); - - /* if there is a clash then goto end of chain */ - if ((last = (*htab)->table[key])) { - while (last->next) - last = last->next ; - last->next = htip ; - } else - /* else just add it */ - (*htab)->table[key] = htip ; - (*htab)->nItems++ ; +void +hTabAddItem (hTab ** htab, int key, void *item) +{ + hTabAddItemLong (htab, key, NULL, item); } /*-----------------------------------------------------------------*/ /* hTabDeleteItem - either delete an item */ /*-----------------------------------------------------------------*/ -void hTabDeleteItem (hTab **htab, int key , - void *item, int action , - int (*compareFunc)(void *,void *)) +void +hTabDeleteItem (hTab ** htab, int key, + const void *item, DELETE_ACTION action, + int (*compareFunc) (const void *, const void *)) { - hashtItem *htip, **htipp ; - - if (!(*htab)) - return ; - - /* first check if anything exists in the slot */ - if (! (*htab)->table[key] ) - return ; - - /* if delete chain */ - if ( action == DELETE_CHAIN ) - (*htab)->table[key] = NULL ; - else { - - /* delete specific item */ - /* if a compare function is given then use the compare */ - /* function to find the item, else just compare the items */ - - htipp = &((*htab)->table[key]); - htip = (*htab)->table[key]; - for (; htip; htip = htip->next) { - - if (compareFunc ? (*compareFunc)(item,htip->item) : - (item == htip->item) ) { - *htipp=htip->next; - break; - } - - htipp=&(htip->next); - } - + hashtItem *htip, **htipp; + + if (!(*htab)) + return; + + /* first check if anything exists in the slot */ + if (!(*htab)->table[key]) + return; + + /* if delete chain */ + if (action == DELETE_CHAIN) + (*htab)->table[key] = NULL; + else + { + + /* delete specific item */ + /* if a compare function is given then use the compare */ + /* function to find the item, else just compare the items */ + + htipp = &((*htab)->table[key]); + htip = (*htab)->table[key]; + for (; htip; htip = htip->next) + { + + if (compareFunc ? compareFunc (item, htip->item) : + (item == htip->item)) + { + *htipp = htip->next; + break; + } + + htipp = &(htip->next); + } + } - - (*htab)->nItems-- ; - - if (!(*htab)->nItems) { - *htab = NULL; + + (*htab)->nItems--; + + if (!(*htab)->nItems) + { + *htab = NULL; } } @@ -157,241 +178,409 @@ void hTabDeleteItem (hTab **htab, int key , /* leaks written by */ /* "BESSIERE Jerome" */ /*-----------------------------------------------------------------*/ -void hTabDeleteAll(hTab * p) +void +hTabDeleteAll (hTab * p) { - if (p && p->table) { - register int i; - register hashtItem *jc,*jn; - for (i=0;isize;i++) { - - if (!(jc = p->table[i])) continue; - jn = jc->next; - while(jc){ - GC_free(jc); - if((jc=jn)) jn = jc->next; - } - p->table[i] = NULL ; - } - GC_free(p->table); + if (p && p->table) + { + register int i; + register hashtItem *jc, *jn; + for (i = 0; i < p->size; i++) + { + + if (!(jc = p->table[i])) + continue; + jn = jc->next; + while (jc) + { + Safe_free (jc); + if ((jc = jn)) + jn = jc->next; + } + p->table[i] = NULL; + } + Safe_free (p->table); } } /*-----------------------------------------------------------------*/ -/* hTabClearAll - clear all entries inthe table (does not free) */ +/* hTabClearAll - clear all entries in the table (does not free) */ /*-----------------------------------------------------------------*/ -void hTabClearAll (hTab *htab) +void +hTabClearAll (hTab * htab) { - if (!htab || !htab->table) { - printf("null table\n"); - return ; + if (!htab || !htab->table) + { + printf ("null table\n"); + return; } - memset(htab->table, 0, htab->size*sizeof(hashtItem *)); - - htab->minKey = htab->size; - htab->currKey = htab->nItems = htab->maxKey = 0; + memset (htab->table, 0, htab->size * sizeof (hashtItem *)); + + htab->minKey = htab->size; + htab->currKey = htab->nItems = htab->maxKey = 0; } -/*-----------------------------------------------------------------*/ -/* hTabIsInTable - will determine if an Item is in the hasht */ -/*-----------------------------------------------------------------*/ -int hTabIsInTable (hTab *htab, int key, - void *item , int (*compareFunc)(void *,void *)) +static const hashtItem * +_findItem (hTab * htab, int key, void *item, int (*compareFunc) (void *, void *)) { - hashtItem *htip ; - - for (htip = htab->table[key] ; htip ; htip = htip->next ) { - /* if a compare function is given use it */ - if (compareFunc && (*compareFunc)(item,htip->item)) - break ; - else - if (item == htip->item) - break; + hashtItem *htip; + + for (htip = htab->table[key]; htip; htip = htip->next) + { + /* if a compare function is given use it */ + if (compareFunc && compareFunc (item, htip->item)) + break; + else if (item == htip->item) + break; } + return htip; +} + +static const hashtItem * +_findByKey (hTab * htab, int key, const void *pkey, int (*compare) (const void *, const void *)) +{ + hashtItem *htip; + + assert (compare); + + if (!htab) + return NULL; + + for (htip = htab->table[key]; htip; htip = htip->next) + { + /* if a compare function is given use it */ + if (compare && compare (pkey, htip->pkey)) + { + break; + } + else + { + if (pkey == htip->pkey) + { + break; + } + } + } + return htip; +} + +void * +hTabFindByKey (hTab * h, int key, const void *pkey, int (*compare) (const void *, const void *)) +{ + const hashtItem *item; + + if ((item = _findByKey (h, key, pkey, compare))) + return item->item; + return NULL; +} + +int +hTabDeleteByKey (hTab ** h, int key, const void *pkey, int (*compare) (const void *, const void *)) +{ + hashtItem *htip, **htipp; + bool found = FALSE; - if ( htip) - return 1; + if (!(*h)) return 0; + + /* first check if anything exists in the slot */ + if (!(*h)->table[key]) + return 0; + + /* delete specific item */ + /* if a compare function is given then use the compare */ + /* function to find the item, else just compare the items */ + + htipp = &((*h)->table[key]); + htip = (*h)->table[key]; + for (; htip; htip = htip->next) + { + if ( + (compare && compare (pkey, htip->pkey)) || + pkey == htip->pkey) + { + *htipp = htip->next; + found = TRUE; + break; + } + htipp = &(htip->next); + } + + if (found == TRUE) + { + (*h)->nItems--; + + if (!(*h)->nItems) + { + *h = NULL; + } + } + + return 1; } /*-----------------------------------------------------------------*/ -/* hTabFirstItem - returns the first Item in the hTab */ +/* hTabIsInTable - will determine if an Item is in the hasht */ /*-----------------------------------------------------------------*/ -void *hTabFirstItem (hTab *htab, int *k) -{ - int key ; - - if (!htab) - return NULL ; +int +hTabIsInTable (hTab * htab, int key, + void *item, int (*compareFunc) (void *, void *)) +{ + if (_findItem (htab, key, item, compareFunc)) + return 1; + return 0; +} - for ( key = htab->minKey ; key <= htab->maxKey ; key++ ) { - if (htab->table[key]) { - htab->currItem = htab->table[key]; - htab->currKey = key ; - *k = key ; - return htab->table[key]->item; +/*-----------------------------------------------------------------*/ +/* hTabFirstItem - returns the first Item in the hTab */ +/*-----------------------------------------------------------------*/ +void * +hTabFirstItem (hTab * htab, int *k) +{ + int key; + + if (!htab) + return NULL; + + for (key = htab->minKey; key <= htab->maxKey; key++) + { + if (htab->table[key]) + { + htab->currItem = htab->table[key]; + htab->currKey = key; + *k = key; + return htab->table[key]->item; } } - return NULL ; + return NULL; } /*-----------------------------------------------------------------*/ /* hTabNextItem - returns the next item in the hTab */ /*-----------------------------------------------------------------*/ -void *hTabNextItem (hTab *htab, int *k) -{ - int key ; +void * +hTabNextItem (hTab * htab, int *k) +{ + int key; - if (!htab) - return NULL; + if (!htab) + return NULL; - /* if this chain not ended then */ - if (htab->currItem->next) { - *k = htab->currItem->key ; - return (htab->currItem = htab->currItem->next)->item ; + /* if this chain not ended then */ + if (htab->currItem->next) + { + *k = htab->currItem->key; + return (htab->currItem = htab->currItem->next)->item; } - /* find the next chain which has something */ - for ( key = htab->currKey + 1; key <= htab->maxKey ; key++ ) { - if (htab->table[key]) { - htab->currItem = htab->table[key]; - *k = htab->currKey = key ; - return htab->table[key]->item; + /* find the next chain which has something */ + for (key = htab->currKey + 1; key <= htab->maxKey; key++) + { + if (htab->table[key]) + { + htab->currItem = htab->table[key]; + *k = htab->currKey = key; + return htab->table[key]->item; } } - return NULL ; + return NULL; } /*-----------------------------------------------------------------*/ /* hTabFirstItemWK - returns the first Item in the hTab for a key */ /*-----------------------------------------------------------------*/ -void *hTabFirstItemWK (hTab *htab, int wk) -{ +void * +hTabFirstItemWK (hTab * htab, int wk) +{ - if (!htab) - return NULL ; - - if (wk < htab->minKey || wk > htab->maxKey ) - return NULL; + if (!htab) + return NULL; - htab->currItem = htab->table[wk] ; - htab->currKey = wk ; + if (wk < htab->minKey || wk > htab->maxKey) + return NULL; - return (htab->table[wk] ? htab->table[wk]->item : NULL); + htab->currItem = htab->table[wk]; + htab->currKey = wk; + + return (htab->table[wk] ? htab->table[wk]->item : NULL); } /*-----------------------------------------------------------------*/ /* hTabNextItem - returns the next item in the hTab for a key */ /*-----------------------------------------------------------------*/ -void *hTabNextItemWK (hTab *htab ) -{ +void * +hTabNextItemWK (hTab * htab) +{ - if (!htab) - return NULL; + if (!htab) + return NULL; - /* if this chain not ended then */ - if (htab->currItem->next) { - return (htab->currItem = htab->currItem->next)->item ; + /* if this chain not ended then */ + if (htab->currItem->next) + { + return (htab->currItem = htab->currItem->next)->item; } - return NULL ; + return NULL; } /*-----------------------------------------------------------------*/ /* hTabFromTable - hash Table from a hash table */ /*-----------------------------------------------------------------*/ -hTab *hTabFromTable (hTab *htab) +hTab * +hTabFromTable (hTab * htab) { - hTab *nhtab ; - hashtItem *htip; - int key ; + hTab *nhtab; + hashtItem *htip; + int key; - if (!htab) - return NULL ; + if (!htab) + return NULL; - nhtab = newHashTable(htab->size); + nhtab = newHashTable (htab->size); - for (key = htab->minKey; key <= htab->maxKey ; key++ ) { - - for (htip = htab->table[key] ; htip ; htip = htip->next) - hTabAddItem (&nhtab, htip->key, htip->item); + for (key = htab->minKey; key <= htab->maxKey; key++) + { + + for (htip = htab->table[key]; htip; htip = htip->next) + hTabAddItem (&nhtab, htip->key, htip->item); } - return nhtab ; + return nhtab; } /*-----------------------------------------------------------------*/ -/* isHtabsEqual - returns 1 if all items in htab1 is found in htab2*/ +/* isHtabsEqual - returns 1 if all items in htab1 is found in htab2 */ /*-----------------------------------------------------------------*/ -int isHtabsEqual (hTab *htab1, hTab *htab2, - int (*compareFunc)(void *,void *)) +int +isHtabsEqual (hTab * htab1, hTab * htab2, + int (*compareFunc) (void *, void *)) { - void *item; - int key; - - if ( htab1 == htab2 ) - return 1; - - if (htab1 == NULL || htab2 == NULL ) - return 0; - - /* if they are different sizes then */ - if ( htab1->nItems != htab2->nItems) - return 0; - - /* now do an item by item check */ - for ( item = hTabFirstItem (htab1,&key) ;item; - item = hTabNextItem (htab1,&key)) - if (!hTabIsInTable (htab2, key, item, compareFunc)) - return 0; + void *item; + int key; + if (htab1 == htab2) return 1; + + if (htab1 == NULL || htab2 == NULL) + return 0; + + /* if they are different sizes then */ + if (htab1->nItems != htab2->nItems) + return 0; + + /* now do an item by item check */ + for (item = hTabFirstItem (htab1, &key); item; + item = hTabNextItem (htab1, &key)) + if (!hTabIsInTable (htab2, key, item, compareFunc)) + return 0; + + return 1; } /*-----------------------------------------------------------------*/ /* hTabSearch - returns the first Item with the specified key */ /*-----------------------------------------------------------------*/ -hashtItem *hTabSearch (hTab *htab, int key ) +hashtItem * +hTabSearch (hTab * htab, int key) { - if (!htab) - return NULL ; + if (!htab) + return NULL; - if ((key < htab->minKey)||(key>htab->maxKey)) - return NULL ; + if ((key < htab->minKey) || (key > htab->maxKey)) + return NULL; - if (!htab->table[key]) - return NULL ; + if (!htab->table[key]) + return NULL; - return htab->table[key] ; + return htab->table[key]; } /*-----------------------------------------------------------------*/ -/* hTabItemWithKey - returns the first item with the gievn key */ +/* hTabItemWithKey - returns the first item with the given key */ /*-----------------------------------------------------------------*/ -void *hTabItemWithKey (hTab *htab, int key ) +void * +hTabItemWithKey (hTab * htab, int key) { - hashtItem *htip; + hashtItem *htip; - if (!(htip = hTabSearch(htab,key))) - return NULL; + if (!(htip = hTabSearch (htab, key))) + return NULL; - return htip->item; + return htip->item; } +/*-----------------------------------------------------------------*/ +/* hTabMaxKey - return the maxKey of item in the hashTable */ +/*-----------------------------------------------------------------*/ +int hTabMaxKey (hTab *htab) +{ + return (htab ? htab->maxKey : 0); +} + /*-----------------------------------------------------------------*/ /*hTabAddItemIfNotP - adds an item with nothing found with key */ /*-----------------------------------------------------------------*/ -void hTabAddItemIfNotP (hTab **htab, int key, void *item) +void +hTabAddItemIfNotP (hTab ** htab, int key, void *item) { - if (!*htab) { - hTabAddItem (htab,key,item); - return; + if (!*htab) + { + hTabAddItem (htab, key, item); + return; } - if (hTabItemWithKey(*htab,key)) - return ; + if (hTabItemWithKey (*htab, key)) + return; - hTabAddItem(htab,key,item); + hTabAddItem (htab, key, item); +} + +/** Simple implementation of a hash table which uses + string (key, value) pairs. If a key already exists in the + table, the newly added value will replace it. + This is used for the assembler token table. The replace existing + condition is used to implement inheritance. +*/ +static int +_compare (const void *s1, const void *s2) +{ + return !strcmp (s1, s2); +} + +static int +_hash (const char *sz) +{ + /* Dumb for now */ + return *sz; +} + +void +shash_add (hTab ** h, const char *szKey, const char *szValue) +{ + char *val; + int key = _hash (szKey); + + /* Find value of the item */ + val = (char *)hTabFindByKey(*h, key, szKey, _compare); + /* Delete any that currently exist */ + hTabDeleteByKey(h, key, szKey, _compare); + /* Deallocate old value in not NULL */ + if (val != NULL) + Safe_free(val); + /* Duplicate new value if not NULL */ + if (szValue != NULL) + szValue = Safe_strdup(szValue); + /* Now add in ours */ + hTabAddItemLong (h, key, Safe_strdup (szKey), (void *)szValue); +} + +const char * +shash_find (hTab * h, const char *szKey) +{ + int key = _hash (szKey); + return (char *) hTabFindByKey (h, key, szKey, _compare); }