diff options
Diffstat (limited to 'src/include/ptable.h')
| -rw-r--r-- | src/include/ptable.h | 233 |
1 files changed, 233 insertions, 0 deletions
diff --git a/src/include/ptable.h b/src/include/ptable.h new file mode 100644 index 0000000..fa79293 --- /dev/null +++ b/src/include/ptable.h @@ -0,0 +1,233 @@ +/* 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> +#include <string.h> + +// 'class PTABLE(T)' is the type of a hash table mapping a string +// (const char *) to an object of type T. +// +// 'struct PASSOC(T)' is the type of a association (pair) between a +// string (const char *) and an object of type T. +// +// 'class PTABLE_ITERATOR(T)' is the type of an iterator iterating through a +// 'class PTABLE(T)'. +// +// Nowadays one would use templates for this; this code predates the addition +// of templates to C++. +#define PTABLE(T) T ## _ptable +#define PASSOC(T) T ## _passoc +#define PTABLE_ITERATOR(T) T ## _ptable_iterator + +// itable.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 + +extern unsigned long hash_string(const char *); // Return a hash code of the + // given string. The hash function is + // platform dependent. */ + +// Declare the types 'class PTABLE(T)', 'struct PASSOC(T)', and 'class +// PTABLE_ITERATOR(T)' for the type 'T'. +#define declare_ptable(T) \ + \ +struct PASSOC(T) { \ + char *key; \ + T *val; \ + PASSOC(T)(); \ +}; \ + \ +class PTABLE(T); \ + \ +class PTABLE_ITERATOR(T) { \ + PTABLE(T) *p; \ + unsigned i; \ +public: \ + PTABLE_ITERATOR(T)(PTABLE(T) *); /* Initialize an iterator running \ + through the given table. */ \ + int next(const char **, 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 PTABLE(T) { \ + PASSOC(T) *v; \ + unsigned size; \ + unsigned used; \ + enum { \ + FULL_NUM = 1, \ + FULL_DEN = 4, \ + INITIAL_SIZE = 17 \ + }; \ +public: \ + PTABLE(T)(); /* Create an empty table. */ \ + ~PTABLE(T)(); /* Delete a table, including its \ + values. */ \ + const char *define(const char *, T *);/* Define the value (arg2) for a key \ + (arg1). Return the copy in the \ + table of the key (arg1), or \ + possibly NULL if the value (arg2) \ + is NULL. */ \ + T *lookup(const char *); /* Return a pointer to the value of \ + the given key, if found in the \ + table, or NULL otherwise. */ \ + T *lookupassoc(const char **); /* Return a pointer to the value of \ + the given key, passed by reference,\ + and replace the key argument with \ + the copy found in the table, if \ + the key is found in the table. \ + Return NULL otherwise. */ \ + friend class PTABLE_ITERATOR(T); \ +}; + + +// Keys (which are strings) are allocated and freed by PTABLE. +// Values must be allocated by the caller (always using new[], not new) +// and are freed by PTABLE. + +// Define the implementations of the members of the types 'class PTABLE(T)', +// 'struct PASSOC(T)', 'class PTABLE_ITERATOR(T)' for the type 'T'. +#define implement_ptable(T) \ + \ +PASSOC(T)::PASSOC(T)() \ +: key(0), val(0) \ +{ \ +} \ + \ +PTABLE(T)::PTABLE(T)() \ +{ \ + v = new PASSOC(T)[size = INITIAL_SIZE]; \ + used = 0; \ +} \ + \ +PTABLE(T)::~PTABLE(T)() \ +{ \ + for (unsigned i = 0; i < size; i++) { \ + free(v[i].key); \ + /* XXX leak, because we don't know whether */ \ + /* 'free', 'delete', or 'delete[]' should be used */ \ + /* delete[] v[i].val; */ \ + } \ + delete[] v; \ +} \ + \ +const char *PTABLE(T)::define(const char *key, T *val) \ +{ \ + assert(key != 0); \ + unsigned long h = hash_string(key); \ + unsigned n; \ + for (n = unsigned(h % size); \ + v[n].key != 0; \ + n = (n == 0 ? size - 1 : n - 1)) \ + if (strcmp(v[n].key, key) == 0) { \ + /* XXX leak, because we don't know whether */ \ + /* 'free', 'delete', or 'delete[]' should be used */ \ + /* delete[] v[n].val; */ \ + v[n].val = val; \ + return v[n].key; \ + } \ + if (val == 0) \ + return 0; \ + if (used*FULL_DEN >= size*FULL_NUM) { \ + PASSOC(T) *oldv = v; \ + unsigned old_size = size; \ + size = next_ptable_size(size); \ + v = new PASSOC(T)[size]; \ + for (unsigned i = 0; i < old_size; i++) \ + if (oldv[i].key != 0) { \ + if (oldv[i].val == 0) \ + free(oldv[i].key); \ + else { \ + unsigned j; \ + for (j = unsigned(hash_string(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; \ + } \ + char *temp = (char*)malloc(strlen(key)+1); \ + strcpy(temp, key); \ + v[n].key = temp; \ + v[n].val = val; \ + used++; \ + return temp; \ +} \ + \ +T *PTABLE(T)::lookup(const char *key) \ +{ \ + assert(key != 0); \ + for (unsigned n = unsigned(hash_string(key) % size); \ + v[n].key != 0; \ + n = (n == 0 ? size - 1 : n - 1)) \ + if (strcmp(v[n].key, key) == 0) \ + return v[n].val; \ + return 0; \ +} \ + \ +T *PTABLE(T)::lookupassoc(const char **keyptr) \ +{ \ + const char *key = *keyptr; \ + assert(key != 0); \ + for (unsigned n = unsigned(hash_string(key) % size); \ + v[n].key != 0; \ + n = (n == 0 ? size - 1 : n - 1)) \ + if (strcmp(v[n].key, key) == 0) { \ + *keyptr = v[n].key; \ + return v[n].val; \ + } \ + return 0; \ +} \ + \ +PTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t) \ +: p(t), i(0) \ +{ \ +} \ + \ +int PTABLE_ITERATOR(T)::next(const char **keyp, T **valp) \ +{ \ + unsigned size = p->size; \ + PASSOC(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: |