include/itable.h

   1 /*@
   2  * Copyright (c) 2014 - 2017 Steffen (Daode) Nurpmeso <steffen@sdaoden.eu>.
   3  *
   4  * Copyright (C) 1989 - 1992, 2003, 2004, 2006
   5  *    Free Software Foundation, Inc.
   6  *      Written by James Clark (jjc@jclark.com)
   7  *
   8  * This is free software; you can redistribute it and/or modify it under
   9  * the terms of the GNU General Public License as published by the Free
  10  * Software Foundation; either version 2, or (at your option) any later
  11  * version.
  12  *
  13  * This is distributed in the hope that it will be useful, but WITHOUT ANY
  14  * WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16  * for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License along
  19  * with groff; see the file COPYING.  If not, write to the Free Software
  20  * Foundation, 51 Franklin St - Fifth Floor, Boston, MA 02110-1301, USA.
  21  */
  22 #ifndef _ITABLE_H
  23 #define _ITABLE_H
  24
  25 #include "config.h"
  26
  27 #include <assert.h>
  28
  29 // `class ITABLE(T)' is the type of a hash table mapping an integer (int >= 0)
  30 // to an object of type T.
  31 //
  32 // `struct IASSOC(T)' is the type of a association (pair) between an integer
  33 // (int >= 0) and an object of type T.
  34 //
  35 // `class ITABLE_ITERATOR(T)' is the type of an iterator iterating through a
  36 // `class ITABLE(T)'.
  37 //
  38 // Nowadays one would use templates for this; this code predates the addition
  39 // of templates to C++.
  40 #define ITABLE(T) CONCAT(T,_itable)
  41 #define IASSOC(T) CONCAT(T,_iassoc)
  42 #define ITABLE_ITERATOR(T) CONCAT(T,_itable_iterator)
  43
  44 // ptable.h declares this too
  45 #ifndef NEXT_PTABLE_SIZE_DEFINED
  46 # define NEXT_PTABLE_SIZE_DEFINED
  47 extern unsigned next_ptable_size(unsigned);     // Return the first suitable
  48                                 // hash table size greater than the given
  49                                 // value.
  50 #endif
  51
  52 // Declare the types `class ITABLE(T)', `struct IASSOC(T)', and `class
  53 // ITABLE_ITERATOR(T)' for the type `T'.
  54 #define declare_itable(T)                                                     \
  55                                                                               \
  56 struct IASSOC(T) {                                                            \
  57   int key;                                                                    \
  58   T *val;                                                                     \
  59   IASSOC(T)();                                                                \
  60 };                                                                            \
  61                                                                               \
  62 class ITABLE(T);                                                              \
  63                                                                               \
  64 class ITABLE_ITERATOR(T) {                                                    \
  65   ITABLE(T) *p;                                                               \
  66   unsigned i;                                                                 \
  67 public:                                                                       \
  68   ITABLE_ITERATOR(T)(ITABLE(T) *);      /* Initialize an iterator running     \
  69                                            through the given table.  */       \
  70   int next(int *, T **);                /* Fetch the next pair, store the key \
  71                                            and value in arg1 and arg2,        \
  72                                            respectively, and return 1.  If    \
  73                                            there is no more pair in the       \
  74                                            table, return 0.  */               \
  75 };                                                                            \
  76                                                                               \
  77 class ITABLE(T) {                                                             \
  78   IASSOC(T) *v;                                                               \
  79   unsigned size;                                                              \
  80   unsigned used;                                                              \
  81   enum {                                                                      \
  82     FULL_NUM = 2,                                                             \
  83     FULL_DEN = 3,                                                             \
  84     INITIAL_SIZE = 17                                                         \
  85   };                                                                          \
  86 public:                                                                       \
  87   ITABLE(T)();                          /* Create an empty table.  */         \
  88   ~ITABLE(T)();                         /* Delete a table, including its      \
  89                                            values.  */                        \
  90   void define(int, T *);                /* Define the value (arg2) for a key  \
  91                                            (arg1).  */                        \
  92   T *lookup(int);                       /* Return a pointer to the value of   \
  93                                            the given key, if found in the     \
  94                                            table, or NULL otherwise.  */      \
  95   friend class ITABLE_ITERATOR(T);                                            \
  96 };
  97
  98
  99 // Values must be allocated by the caller (always using new[], not new)
 100 // and are freed by ITABLE.
 101
 102 // Define the implementations of the members of the types `class ITABLE(T)',
 103 // `struct IASSOC(T)', `class ITABLE_ITERATOR(T)' for the type `T'.
 104 #define implement_itable(T)                                                   \
 105                                                                               \
 106 IASSOC(T)::IASSOC(T)()                                                        \
 107 : key(-1), val(0)                                                             \
 108 {                                                                             \
 109 }                                                                             \
 110                                                                               \
 111 ITABLE(T)::ITABLE(T)()                                                        \
 112 {                                                                             \
 113   v = new IASSOC(T)[size = INITIAL_SIZE];                                     \
 114   used = 0;                                                                   \
 115 }                                                                             \
 116                                                                               \
 117 ITABLE(T)::~ITABLE(T)()                                                       \
 118 {                                                                             \
 119   for (unsigned i = 0; i < size; i++)                                         \
 120     a_delete v[i].val;                                                        \
 121   a_delete v;                                                                 \
 122 }                                                                             \
 123                                                                               \
 124 void ITABLE(T)::define(int key, T *val)                                       \
 125 {                                                                             \
 126   assert(key >= 0);                                                           \
 127   unsigned int h = (unsigned int)(key);                                       \
 128   unsigned n;                                                                 \
 129   for (n = unsigned(h % size);                                                \
 130        v[n].key >= 0;                                                         \
 131        n = (n == 0 ? size - 1 : n - 1))                                       \
 132     if (v[n].key == key) {                                                    \
 133       a_delete v[n].val;                                                      \
 134       v[n].val = val;                                                         \
 135       return;                                                                 \
 136     }                                                                         \
 137   if (val == 0)                                                               \
 138     return;                                                                   \
 139   if (used*FULL_DEN >= size*FULL_NUM) {                                       \
 140     IASSOC(T) *oldv = v;                                                      \
 141     unsigned old_size = size;                                                 \
 142     size = next_ptable_size(size);                                            \
 143     v = new IASSOC(T)[size];                                                  \
 144     for (unsigned i = 0; i < old_size; i++)                                   \
 145       if (oldv[i].key >= 0) {                                                 \
 146         if (oldv[i].val != 0) {                                               \
 147           unsigned j;                                                         \
 148           for (j = (unsigned int)(oldv[i].key) % size;                        \
 149                v[j].key >= 0;                                                 \
 150                j = (j == 0 ? size - 1 : j - 1))                               \
 151                  ;                                                            \
 152           v[j].key = oldv[i].key;                                             \
 153           v[j].val = oldv[i].val;                                             \
 154         }                                                                     \
 155       }                                                                       \
 156     for (n = unsigned(h % size);                                              \
 157          v[n].key >= 0;                                                       \
 158          n = (n == 0 ? size - 1 : n - 1))                                     \
 159       ;                                                                       \
 160     a_delete oldv;                                                            \
 161   }                                                                           \
 162   v[n].key = key;                                                             \
 163   v[n].val = val;                                                             \
 164   used++;                                                                     \
 165 }                                                                             \
 166                                                                               \
 167 T *ITABLE(T)::lookup(int key)                                                 \
 168 {                                                                             \
 169   assert(key >= 0);                                                           \
 170   for (unsigned n = (unsigned int)key % size;                                 \
 171        v[n].key >= 0;                                                         \
 172        n = (n == 0 ? size - 1 : n - 1))                                       \
 173     if (v[n].key == key)                                                      \
 174       return v[n].val;                                                        \
 175   return 0;                                                                   \
 176 }                                                                             \
 177                                                                               \
 178 ITABLE_ITERATOR(T)::ITABLE_ITERATOR(T)(ITABLE(T) *t)                          \
 179 : p(t), i(0)                                                                  \
 180 {                                                                             \
 181 }                                                                             \
 182                                                                               \
 183 int ITABLE_ITERATOR(T)::next(int *keyp, T **valp)                             \
 184 {                                                                             \
 185   unsigned size = p->size;                                                    \
 186   IASSOC(T) *v = p->v;                                                        \
 187   for (; i < size; i++)                                                       \
 188     if (v[i].key >= 0) {                                                      \
 189       *keyp = v[i].key;                                                       \
 190       *valp = v[i].val;                                                       \
 191       i++;                                                                    \
 192       return 1;                                                               \
 193     }                                                                         \
 194   return 0;                                                                   \
 195 }
 196
 197 #endif // _ITABLE_H
 198 // s-it2-mode