home *** CD-ROM | disk | FTP | other *** search
/ Aminet 10 / aminetcdnumber101996.iso / Aminet / util / gnu / groff_src.lha / groff-1.10src / include / ptable.h < prev    next >
C/C++ Source or Header  |  1995-06-22  |  5KB  |  169 lines
  1. // -*- C++ -*-
  2. /* Copyright (C) 1989, 1990, 1991, 1992 Free Software Foundation, Inc.
  3.      Written by James Clark (jjc@jclark.com)
  4.  
  5. This file is part of groff.
  6.  
  7. groff is free software; you can redistribute it and/or modify it under
  8. the terms of the GNU General Public License as published by the Free
  9. Software Foundation; either version 2, or (at your option) any later
  10. version.
  11.  
  12. groff is distributed in the hope that it will be useful, but WITHOUT ANY
  13. WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14. FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15. for more details.
  16.  
  17. You should have received a copy of the GNU General Public License along
  18. with groff; see the file COPYING.  If not, write to the Free Software
  19. Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
  20.  
  21. #include <assert.h>
  22. #include <string.h>
  23.  
  24. #ifdef TRADITIONAL_CPP
  25. #define name2(a,b) a/**/b
  26. #else /* not TRADITIONAL_CPP */
  27. #define name2(a,b) name2x(a,b)
  28. #define name2x(a,b) a ## b
  29. #endif /* not TRADITIONAL_CPP */
  30.  
  31. #define PTABLE(T) name2(T,_ptable)
  32. #define PASSOC(T) name2(T,_passoc)
  33. #define PTABLE_ITERATOR(T) name2(T,_ptable_iterator)
  34.  
  35. extern unsigned next_ptable_size(unsigned);
  36. extern unsigned long hash_string(const char *);
  37.  
  38. #define declare_ptable(T)                              \
  39.                                           \
  40. struct PASSOC(T) {                                  \
  41.   char *key;                                            \
  42.   T *val;                                      \
  43.   PASSOC(T)();                                      \
  44. };                                          \
  45.                                           \
  46. struct PTABLE(T);                                  \
  47.                                           \
  48. class PTABLE_ITERATOR(T) {                              \
  49.   PTABLE(T) *p;                                      \
  50.   unsigned i;                                      \
  51. public:                                          \
  52.   PTABLE_ITERATOR(T)(PTABLE(T) *);                          \
  53.   int next(const char **, T **);                          \
  54. };                                          \
  55.                                           \
  56. class PTABLE(T) {                                  \
  57.   PASSOC(T) *v;                                      \
  58.   unsigned size;                                  \
  59.   unsigned used;                                  \
  60.   enum { FULL_NUM = 2, FULL_DEN = 3, INITIAL_SIZE = 17 };              \
  61. public:                                          \
  62.   PTABLE(T)();                                      \
  63.   ~PTABLE(T)();                                      \
  64.   void define(const char *, T *);                          \
  65.   T *lookup(const char *);                              \
  66.   friend class PTABLE_ITERATOR(T);                          \
  67. };
  68.  
  69.  
  70. #define implement_ptable(T)                              \
  71.                                           \
  72. PASSOC(T)::PASSOC(T)()                                  \
  73. : key(0), val(0)                                  \
  74. {                                          \
  75. }                                          \
  76.                                           \
  77. PTABLE(T)::PTABLE(T)()                                  \
  78. {                                          \
  79.   v = new PASSOC(T)[size = INITIAL_SIZE];                      \
  80.   used = 0;                                      \
  81. }                                          \
  82.                                           \
  83. PTABLE(T)::~PTABLE(T)()                                  \
  84. {                                          \
  85.   for (unsigned i = 0; i < size; i++) {                          \
  86.     a_delete v[i].key;                                  \
  87.     delete v[i].val;                                  \
  88.   }                                          \
  89.   a_delete v;                                      \
  90. }                                          \
  91.                                           \
  92. void PTABLE(T)::define(const char *key, T *val)                      \
  93. {                                          \
  94.   assert(key != 0);                                  \
  95.   unsigned long h = hash_string(key);                          \
  96.   unsigned n;                                      \
  97.   for (n = unsigned(h % size);                                    \
  98.        v[n].key != 0;                                  \
  99.        n = (n == 0 ? size - 1 : n - 1))                          \
  100.     if (strcmp(v[n].key, key) == 0) {                          \
  101.       delete v[n].val;                                  \
  102.       v[n].val = val;                                  \
  103.       return;                                      \
  104.     }                                          \
  105.   if (val == 0)                                      \
  106.     return;                                      \
  107.   if (used*FULL_DEN >= size*FULL_NUM) {                          \
  108.     PASSOC(T) *oldv = v;                              \
  109.     unsigned old_size = size;                              \
  110.     size = next_ptable_size(size);                          \
  111.     v = new PASSOC(T)[size];                              \
  112.     for (unsigned i = 0; i < old_size; i++)                      \
  113.       if (oldv[i].key != 0) {                              \
  114.     if (oldv[i].val == 0)                              \
  115.       a_delete oldv[i].key;                              \
  116.     else {                                      \
  117.       unsigned j;                                  \
  118.       for (j = unsigned(hash_string(oldv[i].key) % size);                    \
  119.            v[j].key != 0;                              \
  120.            j = (j == 0 ? size - 1 : j - 1))                      \
  121.          ;                                  \
  122.       v[j].key = oldv[i].key;                          \
  123.       v[j].val = oldv[i].val;                          \
  124.     }                                      \
  125.       }                                          \
  126.     for (n = unsigned(h % size);                          \
  127.      v[n].key != 0;                                  \
  128.      n = (n == 0 ? size - 1 : n - 1))                      \
  129.       ;                                          \
  130.     a_delete oldv;                                  \
  131.   }                                          \
  132.   char *temp = new char[strlen(key)+1];                          \
  133.   strcpy(temp, key);                                  \
  134.   v[n].key = temp;                                  \
  135.   v[n].val = val;                                  \
  136.   used++;                                      \
  137. }                                          \
  138.                                           \
  139. T *PTABLE(T)::lookup(const char *key)                          \
  140. {                                          \
  141.   assert(key != 0);                                  \
  142.   for (unsigned n = unsigned(hash_string(key) % size);                  \
  143.        v[n].key != 0;                                  \
  144.        n = (n == 0 ? size - 1 : n - 1))                          \
  145.     if (strcmp(v[n].key, key) == 0)                          \
  146.       return v[n].val;                                  \
  147.   return 0;                                      \
  148. }                                          \
  149.                                           \
  150. PTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t)                  \
  151. : p(t), i(0)                                      \
  152. {                                          \
  153. }                                          \
  154.                                           \
  155. int PTABLE_ITERATOR(T)::next(const char **keyp, T **valp)              \
  156. {                                          \
  157.   unsigned size = p->size;                              \
  158.   PASSOC(T) *v = p->v;                                  \
  159.   for (; i < size; i++)                                  \
  160.     if (v[i].key != 0) {                              \
  161.       *keyp = v[i].key;                                  \
  162.       *valp = v[i].val;                                  \
  163.       i++;                                      \
  164.       return 1;                                      \
  165.     }                                          \
  166.   return 0;                                      \
  167. }
  168.  
  169.