175584Sru// -*- C++ -*- 2151497Sru/* Copyright (C) 1989, 1990, 1991, 1992, 2003, 2004 3151497Sru Free Software Foundation, Inc. 475584Sru Written by James Clark (jjc@jclark.com) 575584Sru 675584SruThis file is part of groff. 775584Sru 875584Srugroff is free software; you can redistribute it and/or modify it under 975584Sruthe terms of the GNU General Public License as published by the Free 1075584SruSoftware Foundation; either version 2, or (at your option) any later 1175584Sruversion. 1275584Sru 1375584Srugroff is distributed in the hope that it will be useful, but WITHOUT ANY 1475584SruWARRANTY; without even the implied warranty of MERCHANTABILITY or 1575584SruFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1675584Srufor more details. 1775584Sru 1875584SruYou should have received a copy of the GNU General Public License along 1975584Sruwith groff; see the file COPYING. If not, write to the Free Software 20151497SruFoundation, 51 Franklin St - Fifth Floor, Boston, MA 02110-1301, USA. */ 2175584Sru 2275584Sru#include <assert.h> 2375584Sru#include <string.h> 2475584Sru 2575584Sru#ifdef TRADITIONAL_CPP 2675584Sru#define name2(a,b) a/**/b 2775584Sru#else /* not TRADITIONAL_CPP */ 2875584Sru#define name2(a,b) name2x(a,b) 2975584Sru#define name2x(a,b) a ## b 3075584Sru#endif /* not TRADITIONAL_CPP */ 3175584Sru 3275584Sru#define PTABLE(T) name2(T,_ptable) 3375584Sru#define PASSOC(T) name2(T,_passoc) 3475584Sru#define PTABLE_ITERATOR(T) name2(T,_ptable_iterator) 3575584Sru 3675584Sruextern unsigned next_ptable_size(unsigned); 3775584Sruextern unsigned long hash_string(const char *); 3875584Sru 3975584Sru#define declare_ptable(T) \ 4075584Sru \ 4175584Srustruct PASSOC(T) { \ 4275584Sru char *key; \ 4375584Sru T *val; \ 4475584Sru PASSOC(T)(); \ 4575584Sru}; \ 4675584Sru \ 47151497Sruclass PTABLE(T); \ 4875584Sru \ 4975584Sruclass PTABLE_ITERATOR(T) { \ 5075584Sru PTABLE(T) *p; \ 5175584Sru unsigned i; \ 5275584Srupublic: \ 5375584Sru PTABLE_ITERATOR(T)(PTABLE(T) *); \ 5475584Sru int next(const char **, T **); \ 5575584Sru}; \ 5675584Sru \ 5775584Sruclass PTABLE(T) { \ 5875584Sru PASSOC(T) *v; \ 5975584Sru unsigned size; \ 6075584Sru unsigned used; \ 6175584Sru enum { FULL_NUM = 2, FULL_DEN = 3, INITIAL_SIZE = 17 }; \ 6275584Srupublic: \ 6375584Sru PTABLE(T)(); \ 6475584Sru ~PTABLE(T)(); \ 6575584Sru void define(const char *, T *); \ 6675584Sru T *lookup(const char *); \ 6775584Sru friend class PTABLE_ITERATOR(T); \ 6875584Sru}; 6975584Sru 7075584Sru 71114402Sru// Keys (which are strings) are allocated and freed by PTABLE. 72114402Sru// Values must be allocated by the caller (always using new[], not new) 73114402Sru// and are freed by PTABLE. 74114402Sru 7575584Sru#define implement_ptable(T) \ 7675584Sru \ 7775584SruPASSOC(T)::PASSOC(T)() \ 7875584Sru: key(0), val(0) \ 7975584Sru{ \ 8075584Sru} \ 8175584Sru \ 8275584SruPTABLE(T)::PTABLE(T)() \ 8375584Sru{ \ 8475584Sru v = new PASSOC(T)[size = INITIAL_SIZE]; \ 8575584Sru used = 0; \ 8675584Sru} \ 8775584Sru \ 8875584SruPTABLE(T)::~PTABLE(T)() \ 8975584Sru{ \ 9075584Sru for (unsigned i = 0; i < size; i++) { \ 9175584Sru a_delete v[i].key; \ 92114402Sru a_delete v[i].val; \ 9375584Sru } \ 9475584Sru a_delete v; \ 9575584Sru} \ 9675584Sru \ 9775584Sruvoid PTABLE(T)::define(const char *key, T *val) \ 9875584Sru{ \ 9975584Sru assert(key != 0); \ 10075584Sru unsigned long h = hash_string(key); \ 10175584Sru unsigned n; \ 10275584Sru for (n = unsigned(h % size); \ 10375584Sru v[n].key != 0; \ 10475584Sru n = (n == 0 ? size - 1 : n - 1)) \ 10575584Sru if (strcmp(v[n].key, key) == 0) { \ 106114402Sru a_delete v[n].val; \ 10775584Sru v[n].val = val; \ 10875584Sru return; \ 10975584Sru } \ 11075584Sru if (val == 0) \ 11175584Sru return; \ 11275584Sru if (used*FULL_DEN >= size*FULL_NUM) { \ 11375584Sru PASSOC(T) *oldv = v; \ 11475584Sru unsigned old_size = size; \ 11575584Sru size = next_ptable_size(size); \ 11675584Sru v = new PASSOC(T)[size]; \ 11775584Sru for (unsigned i = 0; i < old_size; i++) \ 11875584Sru if (oldv[i].key != 0) { \ 11975584Sru if (oldv[i].val == 0) \ 12075584Sru a_delete oldv[i].key; \ 12175584Sru else { \ 12275584Sru unsigned j; \ 12375584Sru for (j = unsigned(hash_string(oldv[i].key) % size); \ 12475584Sru v[j].key != 0; \ 12575584Sru j = (j == 0 ? size - 1 : j - 1)) \ 12675584Sru ; \ 12775584Sru v[j].key = oldv[i].key; \ 12875584Sru v[j].val = oldv[i].val; \ 12975584Sru } \ 13075584Sru } \ 13175584Sru for (n = unsigned(h % size); \ 13275584Sru v[n].key != 0; \ 13375584Sru n = (n == 0 ? size - 1 : n - 1)) \ 13475584Sru ; \ 13575584Sru a_delete oldv; \ 13675584Sru } \ 13775584Sru char *temp = new char[strlen(key)+1]; \ 13875584Sru strcpy(temp, key); \ 13975584Sru v[n].key = temp; \ 14075584Sru v[n].val = val; \ 14175584Sru used++; \ 14275584Sru} \ 14375584Sru \ 14475584SruT *PTABLE(T)::lookup(const char *key) \ 14575584Sru{ \ 14675584Sru assert(key != 0); \ 14775584Sru for (unsigned n = unsigned(hash_string(key) % size); \ 14875584Sru v[n].key != 0; \ 14975584Sru n = (n == 0 ? size - 1 : n - 1)) \ 15075584Sru if (strcmp(v[n].key, key) == 0) \ 15175584Sru return v[n].val; \ 15275584Sru return 0; \ 15375584Sru} \ 15475584Sru \ 15575584SruPTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t) \ 15675584Sru: p(t), i(0) \ 15775584Sru{ \ 15875584Sru} \ 15975584Sru \ 16075584Sruint PTABLE_ITERATOR(T)::next(const char **keyp, T **valp) \ 16175584Sru{ \ 16275584Sru unsigned size = p->size; \ 16375584Sru PASSOC(T) *v = p->v; \ 16475584Sru for (; i < size; i++) \ 16575584Sru if (v[i].key != 0) { \ 16675584Sru *keyp = v[i].key; \ 16775584Sru *valp = v[i].val; \ 16875584Sru i++; \ 16975584Sru return 1; \ 17075584Sru } \ 17175584Sru return 0; \ 17275584Sru} 173