home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / usr.bin / groff / libgroff / ptable.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-04-30  |  5.0 KB  |  160 lines
  1. // -*- C++ -*-
  2. /* Copyright (C) 1989, 1990 Free Software Foundation, Inc.
  3.      Written by James Clark (jjc@jclark.uucp)
  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 1, 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 LICENSE.  If not, write to the Free Software
  19. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  20.  
  21. #include <assert.h>
  22. #include <generic.h>
  23. #include <string.h>
  24.  
  25. #define PTABLE(T) name2(T,_ptable)
  26. #define PASSOC(T) name2(T,_passoc)
  27. #define PTABLE_ITERATOR(T) name2(T,_ptable_iterator)
  28.  
  29. extern int next_ptable_size(int);
  30. extern unsigned hash_string(const char *);
  31.  
  32. #define declare_ptable(T)                              \
  33.                                           \
  34. struct PASSOC(T) {                                  \
  35.   char *key;                                            \
  36.   T *val;                                      \
  37.   PASSOC(T)();                                      \
  38. };                                          \
  39.                                           \
  40. struct PTABLE(T);                                  \
  41.                                           \
  42. class PTABLE_ITERATOR(T) {                              \
  43.   PTABLE(T) *p;                                      \
  44.   int i;                                      \
  45. public:                                          \
  46.   PTABLE_ITERATOR(T)(PTABLE(T) *);                          \
  47.   int next(const char **, T **);                          \
  48. };                                          \
  49.                                           \
  50. class PTABLE(T) {                                  \
  51.   PASSOC(T) *v;                                      \
  52.   int size;                                      \
  53.   int used;                                      \
  54.   enum { FULL_NUM = 2, FULL_DEN = 3, INITIAL_SIZE = 17 };              \
  55. public:                                          \
  56.   PTABLE(T)();                                      \
  57.   ~PTABLE(T)();                                      \
  58.   void define(const char *, T *);                          \
  59.   T *lookup(const char *);                              \
  60.   friend class PTABLE_ITERATOR(T);                          \
  61. };
  62.  
  63.  
  64. #define implement_ptable(T)                              \
  65.                                           \
  66. PASSOC(T)::PASSOC(T)()                                  \
  67. : key(0), val(0)                                  \
  68. {                                          \
  69. }                                          \
  70.                                           \
  71. PTABLE(T)::PTABLE(T)()                                  \
  72. {                                          \
  73.   v = new PASSOC(T)[size = INITIAL_SIZE];                      \
  74.   used = 0;                                      \
  75. }                                          \
  76.                                           \
  77. PTABLE(T)::~PTABLE(T)()                                  \
  78. {                                          \
  79.   for (int i = 0; i < size; i++) {                          \
  80.     delete v[i].key;                                  \
  81.     delete v[i].val;                                  \
  82.   }                                          \
  83. }                                          \
  84.                                           \
  85. void PTABLE(T)::define(const char *key, T *val)                      \
  86. {                                          \
  87.   assert(key != 0);                                  \
  88.   int h = hash_string(key);                              \
  89.   for (int n = h % size;                              \
  90.        v[n].key != 0;                                  \
  91.        n = (n == 0 ? size - 1 : n - 1))                          \
  92.     if (strcmp(v[n].key, key) == 0) {                          \
  93.       delete v[n].val;                                  \
  94.       v[n].val = val;                                  \
  95.       return;                                      \
  96.     }                                          \
  97.   if (val == 0)                                      \
  98.     return;                                      \
  99.   if (used*FULL_DEN >= size*FULL_NUM) {                          \
  100.     PASSOC(T) *oldv = v;                              \
  101.     int old_size = size;                              \
  102.     size = next_ptable_size(size);                          \
  103.     v = new PASSOC(T)[size];                              \
  104.     for (int i = 0; i < old_size; i++)                          \
  105.       if (oldv[i].key != 0) {                              \
  106.     if (oldv[i].val == 0)                              \
  107.       delete oldv[i].key;                              \
  108.     else {                                      \
  109.       for (int j = hash_string(oldv[i].key) % size;                  \
  110.            v[j].key != 0;                              \
  111.            j = (j == 0 ? size - 1 : j - 1))                      \
  112.          ;                                  \
  113.       v[j].key = oldv[i].key;                          \
  114.       v[j].val = oldv[i].val;                          \
  115.     }                                      \
  116.       }                                          \
  117.     for (n = h % size;                                  \
  118.      v[n].key != 0;                                  \
  119.      n = (n == 0 ? size - 1 : n - 1))                      \
  120.       ;                                          \
  121.     delete oldv;                                  \
  122.   }                                          \
  123.   char *temp = new char[strlen(key)+1];                          \
  124.   strcpy(temp, key);                                  \
  125.   v[n].key = temp;                                  \
  126.   v[n].val = val;                                  \
  127.   used++;                                      \
  128. }                                          \
  129.                                           \
  130. T *PTABLE(T)::lookup(const char *key)                          \
  131. {                                          \
  132.   assert(key != 0);                                  \
  133.   for (int n = hash_string(key) % size;                          \
  134.        v[n].key != 0;                                  \
  135.        n = (n == 0 ? size - 1 : n - 1))                          \
  136.     if (strcmp(v[n].key, key) == 0)                          \
  137.       return v[n].val;                                  \
  138.   return 0;                                      \
  139. }                                          \
  140.                                           \
  141. PTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t)                  \
  142. : p(t), i(0)                                      \
  143. {                                          \
  144. }                                          \
  145.                                           \
  146. int PTABLE_ITERATOR(T)::next(const char **keyp, T **valp)              \
  147. {                                          \
  148.   int size = p->size;                                  \
  149.   PASSOC(T) *v = p->v;                                  \
  150.   for (; i < size; i++)                                  \
  151.     if (v[i].key != 0) {                              \
  152.       *keyp = v[i].key;                                  \
  153.       *valp = v[i].val;                                  \
  154.       i++;                                      \
  155.       return 1;                                      \
  156.     }                                          \
  157.   return 0;                                      \
  158. }
  159.  
  160.