diff options
Diffstat (limited to 'src/include/itable.h')
| -rw-r--r-- | src/include/itable.h | 193 |
1 files changed, 193 insertions, 0 deletions
diff --git a/src/include/itable.h b/src/include/itable.h new file mode 100644 index 0000000..c97db55 --- /dev/null +++ b/src/include/itable.h @@ -0,0 +1,193 @@ +/* Copyright (C) 1989-2020 Free Software Foundation, Inc. + Written by James Clark (jjc@jclark.com) + +This file is part of groff. + +groff is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation, either version 3 of the License, or +(at your option) any later version. + +groff is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#include <assert.h> + +// 'class ITABLE(T)' is the type of a hash table mapping an integer (int >= 0) +// to an object of type T. +// +// 'struct IASSOC(T)' is the type of a association (pair) between an integer +// (int >= 0) and an object of type T. +// +// 'class ITABLE_ITERATOR(T)' is the type of an iterator iterating through a +// 'class ITABLE(T)'. +// +// Nowadays one would use templates for this; this code predates the addition +// of templates to C++. +#define ITABLE(T) T ## _itable +#define IASSOC(T) T ## _iassoc +#define ITABLE_ITERATOR(T) T ## _itable_iterator + +// ptable.h declares this too +#ifndef NEXT_PTABLE_SIZE_DEFINED +# define NEXT_PTABLE_SIZE_DEFINED +extern unsigned next_ptable_size(unsigned); // Return the first suitable + // hash table size greater than the given + // value. +#endif + +// Declare the types 'class ITABLE(T)', 'struct IASSOC(T)', and 'class +// ITABLE_ITERATOR(T)' for the type 'T'. +#define declare_itable(T) \ + \ +struct IASSOC(T) { \ + int key; \ + T *val; \ + IASSOC(T)(); \ +}; \ + \ +class ITABLE(T); \ + \ +class ITABLE_ITERATOR(T) { \ + ITABLE(T) *p; \ + unsigned i; \ +public: \ + ITABLE_ITERATOR(T)(ITABLE(T) *); /* Initialize an iterator running \ + through the given table. */ \ + int next(int *, T **); /* Fetch the next pair, store the key \ + and value in arg1 and arg2, \ + respectively, and return 1. If \ + there is no more pair in the \ + table, return 0. */ \ +}; \ + \ +class ITABLE(T) { \ + IASSOC(T) *v; \ + unsigned size; \ + unsigned used; \ + enum { \ + FULL_NUM = 2, \ + FULL_DEN = 3, \ + INITIAL_SIZE = 17 \ + }; \ +public: \ + ITABLE(T)(); /* Create an empty table. */ \ + ~ITABLE(T)(); /* Delete a table, including its \ + values. */ \ + void define(int, T *); /* Define the value (arg2) for a key \ + (arg1). */ \ + T *lookup(int); /* Return a pointer to the value of \ + the given key, if found in the \ + table, or NULL otherwise. */ \ + friend class ITABLE_ITERATOR(T); \ +}; + + +// Values must be allocated by the caller (always using new[], not new) +// and are freed by ITABLE. + +// Define the implementations of the members of the types 'class ITABLE(T)', +// 'struct IASSOC(T)', 'class ITABLE_ITERATOR(T)' for the type 'T'. +#define implement_itable(T) \ + \ +IASSOC(T)::IASSOC(T)() \ +: key(-1), val(0) \ +{ \ +} \ + \ +ITABLE(T)::ITABLE(T)() \ +{ \ + v = new IASSOC(T)[size = INITIAL_SIZE]; \ + used = 0; \ +} \ + \ +ITABLE(T)::~ITABLE(T)() \ +{ \ + for (unsigned i = 0; i < size; i++) \ + delete[] v[i].val; \ + delete[] v; \ +} \ + \ +void ITABLE(T)::define(int key, T *val) \ +{ \ + assert(key >= 0); \ + unsigned int h = (unsigned int)(key); \ + unsigned n; \ + for (n = unsigned(h % size); \ + v[n].key >= 0; \ + n = (n == 0 ? size - 1 : n - 1)) \ + if (v[n].key == key) { \ + delete[] v[n].val; \ + v[n].val = val; \ + return; \ + } \ + if (val == 0) \ + return; \ + if (used*FULL_DEN >= size*FULL_NUM) { \ + IASSOC(T) *oldv = v; \ + unsigned old_size = size; \ + size = next_ptable_size(size); \ + v = new IASSOC(T)[size]; \ + for (unsigned i = 0; i < old_size; i++) \ + if (oldv[i].key >= 0) { \ + if (oldv[i].val != 0) { \ + unsigned j; \ + for (j = (unsigned int)(oldv[i].key) % size; \ + v[j].key >= 0; \ + j = (j == 0 ? size - 1 : j - 1)) \ + ; \ + v[j].key = oldv[i].key; \ + v[j].val = oldv[i].val; \ + } \ + } \ + for (n = unsigned(h % size); \ + v[n].key >= 0; \ + n = (n == 0 ? size - 1 : n - 1)) \ + ; \ + delete[] oldv; \ + } \ + v[n].key = key; \ + v[n].val = val; \ + used++; \ +} \ + \ +T *ITABLE(T)::lookup(int key) \ +{ \ + assert(key >= 0); \ + for (unsigned n = (unsigned int)key % size; \ + v[n].key >= 0; \ + n = (n == 0 ? size - 1 : n - 1)) \ + if (v[n].key == key) \ + return v[n].val; \ + return 0; \ +} \ + \ +ITABLE_ITERATOR(T)::ITABLE_ITERATOR(T)(ITABLE(T) *t) \ +: p(t), i(0) \ +{ \ +} \ + \ +int ITABLE_ITERATOR(T)::next(int *keyp, T **valp) \ +{ \ + unsigned size = p->size; \ + IASSOC(T) *v = p->v; \ + for (; i < size; i++) \ + if (v[i].key >= 0) { \ + *keyp = v[i].key; \ + *valp = v[i].val; \ + i++; \ + return 1; \ + } \ + return 0; \ +} + +// Local Variables: +// fill-column: 72 +// mode: C++ +// End: +// vim: set cindent noexpandtab shiftwidth=2 textwidth=72: |