include/ptable.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 _PTABLE_H
  23 #define _PTABLE_H
  24
  25 #include "config.h"
  26
  27 #include <assert.h>
  28 #include <string.h>
  29
  30 // `class PTABLE(T)' is the type of a hash table mapping a string
  31 // (const char *) to an object of type T.
  32 //
  33 // `struct PASSOC(T)' is the type of a association (pair) between a
  34 // string (const char *) and an object of type T.
  35 //
  36 // `class PTABLE_ITERATOR(T)' is the type of an iterator iterating through a
  37 // `class PTABLE(T)'.
  38 //
  39 // Nowadays one would use templates for this; this code predates the addition
  40 // of templates to C++.
  41 #define PTABLE(T) CONCAT(T,_ptable)
  42 #define PASSOC(T) CONCAT(T,_passoc)
  43 #define PTABLE_ITERATOR(T) CONCAT(T,_ptable_iterator)
  44
  45 // itable.h declares this too
  46 #ifndef NEXT_PTABLE_SIZE_DEFINED
  47 # define NEXT_PTABLE_SIZE_DEFINED
  48 extern unsigned next_ptable_size(unsigned);     // Return the first suitable
  49                                 // hash table size greater than the given
  50                                 // value.
  51 #endif
  52
  53 extern unsigned long hash_string(const char *); // Return a hash code of the
  54                                 // given string.  The hash function is
  55                                 // platform dependent.  */
  56
  57 // Declare the types `class PTABLE(T)', `struct PASSOC(T)', and `class
  58 // PTABLE_ITERATOR(T)' for the type `T'.
  59 #define declare_ptable(T)                                                     \
  60                                                                               \
  61 struct PASSOC(T) {                                                            \
  62   char *key;                                                                  \
  63   T *val;                                                                     \
  64   PASSOC(T)();                                                                \
  65 };                                                                            \
  66                                                                               \
  67 class PTABLE(T);                                                              \
  68                                                                               \
  69 class PTABLE_ITERATOR(T) {                                                    \
  70   PTABLE(T) *p;                                                               \
  71   unsigned i;                                                                 \
  72 public:                                                                       \
  73   PTABLE_ITERATOR(T)(PTABLE(T) *);      /* Initialize an iterator running     \
  74                                            through the given table.  */       \
  75   int next(const char **, T **);        /* Fetch the next pair, store the key \
  76                                            and value in arg1 and arg2,        \
  77                                            respectively, and return 1.  If    \
  78                                            there is no more pair in the       \
  79                                            table, return 0.  */               \
  80 };                                                                            \
  81                                                                               \
  82 class PTABLE(T) {                                                             \
  83   PASSOC(T) *v;                                                               \
  84   unsigned size;                                                              \
  85   unsigned used;                                                              \
  86   enum {                                                                      \
  87     FULL_NUM = 2,                                                             \
  88     FULL_DEN = 3,                                                             \
  89     INITIAL_SIZE = 17                                                         \
  90   };                                                                          \
  91 public:                                                                       \
  92   PTABLE(T)();                          /* Create an empty table.  */         \
  93   ~PTABLE(T)();                         /* Delete a table, including its      \
  94                                            values.  */                        \
  95   const char *define(const char *, T *);/* Define the value (arg2) for a key  \
  96                                            (arg1).  Return the copy in the    \
  97                                            table of the key (arg1), or        \
  98                                            possibly NULL if the value (arg2)  \
  99                                            is NULL.  */                       \
 100   T *lookup(const char *);              /* Return a pointer to the value of   \
 101                                            the given key, if found in the     \
 102                                            table, or NULL otherwise.  */      \
 103   T *lookupassoc(const char **);        /* Return a pointer to the value of   \
 104                                            the given key, passed by reference,\
 105                                            and replace the key argument with  \
 106                                            the copy found in the table, if    \
 107                                            the key is found in the table.     \
 108                                            Return NULL otherwise.  */         \
 109   friend class PTABLE_ITERATOR(T);                                            \
 110 };
 111
 112
 113 // Keys (which are strings) are allocated and freed by PTABLE.
 114 // Values must be allocated by the caller (always using new[], not new)
 115 // and are freed by PTABLE.
 116
 117 // Define the implementations of the members of the types `class PTABLE(T)',
 118 // `struct PASSOC(T)', `class PTABLE_ITERATOR(T)' for the type `T'.
 119 #define implement_ptable(T)                                                   \
 120                                                                               \
 121 PASSOC(T)::PASSOC(T)()                                                        \
 122 : key(0), val(0)                                                              \
 123 {                                                                             \
 124 }                                                                             \
 125                                                                               \
 126 PTABLE(T)::PTABLE(T)()                                                        \
 127 {                                                                             \
 128   v = new PASSOC(T)[size = INITIAL_SIZE];                                     \
 129   used = 0;                                                                   \
 130 }                                                                             \
 131                                                                               \
 132 PTABLE(T)::~PTABLE(T)()                                                       \
 133 {                                                                             \
 134   for (unsigned i = 0; i < size; i++) {                                       \
 135     a_delete v[i].key;                                                        \
 136     a_delete v[i].val;                                                        \
 137   }                                                                           \
 138   a_delete v;                                                                 \
 139 }                                                                             \
 140                                                                               \
 141 const char *PTABLE(T)::define(const char *key, T *val)                        \
 142 {                                                                             \
 143   assert(key != 0);                                                           \
 144   unsigned long h = hash_string(key);                                         \
 145   unsigned n;                                                                 \
 146   for (n = unsigned(h % size);                                                \
 147        v[n].key != 0;                                                         \
 148        n = (n == 0 ? size - 1 : n - 1))                                       \
 149     if (strcmp(v[n].key, key) == 0) {                                         \
 150       a_delete v[n].val;                                                      \
 151       v[n].val = val;                                                         \
 152       return v[n].key;                                                        \
 153     }                                                                         \
 154   if (val == 0)                                                               \
 155     return 0;                                                                 \
 156   if (used*FULL_DEN >= size*FULL_NUM) {                                       \
 157     PASSOC(T) *oldv = v;                                                      \
 158     unsigned old_size = size;                                                 \
 159     size = next_ptable_size(size);                                            \
 160     v = new PASSOC(T)[size];                                                  \
 161     for (unsigned i = 0; i < old_size; i++)                                   \
 162       if (oldv[i].key != 0) {                                                 \
 163         if (oldv[i].val == 0)                                                 \
 164           a_delete oldv[i].key;                                               \
 165         else {                                                                \
 166           unsigned j;                                                         \
 167           for (j = unsigned(hash_string(oldv[i].key) % size);                 \
 168                v[j].key != 0;                                                 \
 169                j = (j == 0 ? size - 1 : j - 1))                               \
 170                  ;                                                            \
 171           v[j].key = oldv[i].key;                                             \
 172           v[j].val = oldv[i].val;                                             \
 173         }                                                                     \
 174       }                                                                       \
 175     for (n = unsigned(h % size);                                              \
 176          v[n].key != 0;                                                       \
 177          n = (n == 0 ? size - 1 : n - 1))                                     \
 178       ;                                                                       \
 179     a_delete oldv;                                                            \
 180   }                                                                           \
 181   char *temp = new char[strlen(key)+1];                                       \
 182   strcpy(temp, key);                                                          \
 183   v[n].key = temp;                                                            \
 184   v[n].val = val;                                                             \
 185   used++;                                                                     \
 186   return temp;                                                                \
 187 }                                                                             \
 188                                                                               \
 189 T *PTABLE(T)::lookup(const char *key)                                         \
 190 {                                                                             \
 191   assert(key != 0);                                                           \
 192   for (unsigned n = unsigned(hash_string(key) % size);                        \
 193        v[n].key != 0;                                                         \
 194        n = (n == 0 ? size - 1 : n - 1))                                       \
 195     if (strcmp(v[n].key, key) == 0)                                           \
 196       return v[n].val;                                                        \
 197   return 0;                                                                   \
 198 }                                                                             \
 199                                                                               \
 200 T *PTABLE(T)::lookupassoc(const char **keyptr)                                \
 201 {                                                                             \
 202   const char *key = *keyptr;                                                  \
 203   assert(key != 0);                                                           \
 204   for (unsigned n = unsigned(hash_string(key) % size);                        \
 205        v[n].key != 0;                                                         \
 206        n = (n == 0 ? size - 1 : n - 1))                                       \
 207     if (strcmp(v[n].key, key) == 0) {                                         \
 208       *keyptr = v[n].key;                                                     \
 209       return v[n].val;                                                        \
 210     }                                                                         \
 211   return 0;                                                                   \
 212 }                                                                             \
 213                                                                               \
 214 PTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t)                          \
 215 : p(t), i(0)                                                                  \
 216 {                                                                             \
 217 }                                                                             \
 218                                                                               \
 219 int PTABLE_ITERATOR(T)::next(const char **keyp, T **valp)                     \
 220 {                                                                             \
 221   unsigned size = p->size;                                                    \
 222   PASSOC(T) *v = p->v;                                                        \
 223   for (; i < size; i++)                                                       \
 224     if (v[i].key != 0) {                                                      \
 225       *keyp = v[i].key;                                                       \
 226       *valp = v[i].val;                                                       \
 227       i++;                                                                    \
 228       return 1;                                                               \
 229     }                                                                         \
 230   return 0;                                                                   \
 231 }
 232
 233 #endif // _PTABLE_H
 234 // s-it2-mode