git.gag.com Git - fw/sdcc/blob - src/SDCChasht.h

   1 /*-----------------------------------------------------------------
   2     SDCChast.h - contains support routines for hashtables/sets .
   3
   4     Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
   5
   6     This program is free software; you can redistribute it and/or modify it
   7     under the terms of the GNU General Public License as published by the
   8     Free Software Foundation; either version 2, or (at your option) any
   9     later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  19
  20     In other words, you are welcome to use, share and improve this program.
  21     You are forbidden to forbid anyone else to use, share and improve
  22     what you give them.   Help stamp out software-hoarding!
  23 -------------------------------------------------------------------------*/
  24
  25
  26 #ifndef SDCCHASHT_H
  27 #define SDCCHASHT_H
  28
  29 #ifdef _NO_GC
  30
  31 #include <stdlib.h>
  32 #define GC_malloc malloc
  33 #define GC_free free
  34 #define GC_realloc realloc
  35 #define GC_malloc_atomic malloc
  36
  37 #else
  38
  39 #include "./gc/gc.h"
  40
  41 #endif
  42
  43 #ifndef ALLOC
  44
  45 #define  ALLOC(x,sz) if (!(x = GC_malloc(sz)))                          \
  46          {                                                           \
  47             fprintf(stderr,"out of virtual memory %s , %d",__FILE__,__LINE__);\
  48             exit (1);                                                \
  49          }
  50
  51 #define  ALLOC_ATOMIC(x,sz) if (!(x = GC_malloc_atomic(sz)))                          \
  52          {                                                           \
  53             fprintf(stderr,"out of virtual memory %s , %d",__FILE__,__LINE__);\
  54             exit (1);                                                \
  55          }
  56
  57
  58
  59 #endif
  60
  61
  62 /* hashtable item */
  63 typedef struct hashtItem
  64 {
  65     int key;
  66     /* Pointer to the key that was hashed for key.
  67        Used for a hash table with unique keys. */
  68     void *pkey;
  69     void *item;
  70     struct hashtItem *next ;
  71 } hashtItem ;
  72
  73 /* hashtable */
  74 typedef struct hTab
  75 {
  76     int size  ;             /* max number of items */
  77     int minKey;             /* minimum key value   */
  78     int maxKey ;            /* maximum key value */
  79     hashtItem **table ;     /* the actual table  */
  80     int currKey  ;          /* used for iteration */
  81     hashtItem *currItem ;   /* current item within the list */
  82     int nItems ;
  83 } hTab ;
  84
  85 typedef enum {
  86     DELETE_CHAIN = 1,
  87     DELETE_ITEM
  88 } DELETE_ACTION;
  89
  90
  91 /*-----------------------------------------------------------------*/
  92 /*           Forward   definition    for   functions               */
  93 /*-----------------------------------------------------------------*/
  94
  95 /* hashtable related functions */
  96 hTab        *newHashTable      (int);
  97 void         hTabAddItem (hTab **, int key, void *item);
  98 /** Adds a new item to the hash table.
  99     @param h            The hash table to add to
 100     @param key          A hashed version of pkey
 101     @param pkey         A copy of the key.  Owned by the
 102                         hash table after this function.
 103     @param item         Value for this key.
 104 */
 105 void         hTabAddItemLong(hTab **h, int key, void *pkey, void *item);
 106 /** Finds a item by exact key.
 107     Searches all items in the key 'key' for a key that
 108     according to 'compare' matches pkey.
 109     @param h            The hash table to search
 110     @param key          A hashed version of pkey.
 111     @param pkey         The key to search for
 112     @param compare      Returns 0 if pkey == this
 113 */
 114 void *       hTabFindByKey(hTab *h, int key, const void *pkey, int (*compare)(const void *, const void *));
 115 /** Deletes an item with the exact key 'pkey'
 116     @see hTabFindByKey
 117 */
 118 int          hTabDeleteByKey(hTab **h, int key, const void *pkey, int (*compare)(const void *, const void *));
 119
 120 void         hTabDeleteItem (hTab **, int key,
 121                              const void *item, DELETE_ACTION action,
 122                              int (*compareFunc)(const void *,const void *));
 123 int          hTabIsInTable (hTab *, int , void * ,
 124                                  int (*compareFunc)(void *,void *));
 125 void         *hTabFirstItem (hTab *, int *);
 126 void         *hTabNextItem (hTab *, int *);
 127 hTab         *hTabFromTable (hTab *);
 128 int          isHtabsEqual (hTab *,hTab *, int (*compareFunc)(void *,void *));
 129 hashtItem    *hTabSearch  (hTab *, int );
 130 void         *hTabItemWithKey(hTab *,int );
 131 void         hTabAddItemIfNotP(hTab **,int, void *);
 132 void         hTabDeleteAll(hTab *);
 133 void        *hTabFirstItemWK (hTab *htab, int wk);
 134 void        *hTabNextItemWK (hTab *htab );
 135 void         hTabClearAll (hTab *htab);
 136
 137 /** Find the first item that either is 'item' or which
 138     according to 'compareFunc' is the same as item.
 139     @param compareFunc          strcmp like compare function, may be null.
 140 */
 141 void *hTabFindItem(hTab *htab, int key,
 142                    void *item, int (*compareFunc)(void *,void *));
 143
 144 void shash_add(hTab **h, const char *szKey, const char *szValue);
 145 const char *shash_find(hTab *h, const char *szKey);
 146
 147 #endif