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