[dragonfly.git] / contrib / groff / src / include / ptable.h

// -*- C++ -*-
/* Copyright (C) 1989, 1990, 1991, 1992, 2003, 2004, 2006, 2009
   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>

// name2(a,b) concatenates two C identifiers.
#ifdef TRADITIONAL_CPP
# define name2(a,b) a/**/b
#else /* not TRADITIONAL_CPP */
# define name2(a,b) name2x(a,b)
# define name2x(a,b) a ## b
#endif /* not TRADITIONAL_CPP */

// `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) name2(T,_ptable)
#define PASSOC(T) name2(T,_passoc)
#define PTABLE_ITERATOR(T) name2(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 = 2,							      \
    FULL_DEN = 3,							      \
    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++) {					      \
    a_delete v[i].key;							      \
    a_delete v[i].val;							      \
  }									      \
  a_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) {					      \
      a_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)						      \
	  a_delete 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))				      \
      ;									      \
    a_delete oldv;							      \
  }									      \
  char *temp = new char[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;								      \
}

// end of ptable.h
Commit	Line	Data
92d0a6a6	1	// -- C++ --
4d3e9548	2	/* Copyright (C) 1989, 1990, 1991, 1992, 2003, 2004, 2006, 2009
92d0a6a6 JR	3	Free Software Foundation, Inc.
	4	Written by James Clark (jjc@jclark.com)
	5
	6	This file is part of groff.
	7
	8	groff is free software; you can redistribute it and/or modify it under
	9	the terms of the GNU General Public License as published by the Free
4d3e9548 JL	10	Software Foundation, either version 3 of the License, or
4d3e9548 JL	11	(at your option) any later version.
92d0a6a6 JR	12
	13	groff is distributed in the hope that it will be useful, but WITHOUT ANY
	14	WARRANTY; without even the implied warranty of MERCHANTABILITY or
	15	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	16	for more details.
	17
4d3e9548 JL	18	You should have received a copy of the GNU General Public License
4d3e9548 JL	19	along with this program. If not, see <http://www.gnu.org/licenses/>. */
92d0a6a6 JR	20
	21	#include <assert.h>
	22	#include <string.h>
	23
4d3e9548	24	// name2(a,b) concatenates two C identifiers.
92d0a6a6	25	#ifdef TRADITIONAL_CPP
4d3e9548	26	# define name2(a,b) a/**/b
92d0a6a6	27	#else /* not TRADITIONAL_CPP */
4d3e9548 JL	28	# define name2(a,b) name2x(a,b)
4d3e9548 JL	29	# define name2x(a,b) a ## b
92d0a6a6 JR	30	#endif /* not TRADITIONAL_CPP */
92d0a6a6 JR	31
4d3e9548 JL	32	// `class PTABLE(T)' is the type of a hash table mapping a string
	33	// (const char *) to an object of type T.
	34	//
	35	// `struct PASSOC(T)' is the type of a association (pair) between a
	36	// string (const char *) and an object of type T.
	37	//
	38	// `class PTABLE_ITERATOR(T)' is the type of an iterator iterating through a
	39	// `class PTABLE(T)'.
	40	//
	41	// Nowadays one would use templates for this; this code predates the addition
	42	// of templates to C++.
92d0a6a6 JR	43	#define PTABLE(T) name2(T,_ptable)
	44	#define PASSOC(T) name2(T,_passoc)
	45	#define PTABLE_ITERATOR(T) name2(T,_ptable_iterator)
	46
4d3e9548 JL	47	// itable.h declares this too
	48	#ifndef NEXT_PTABLE_SIZE_DEFINED
	49	# define NEXT_PTABLE_SIZE_DEFINED
	50	extern unsigned next_ptable_size(unsigned); // Return the first suitable
	51	// hash table size greater than the given
	52	// value.
	53	#endif
92d0a6a6	54
4d3e9548 JL	55	extern unsigned long hash_string(const char *); // Return a hash code of the
	56	// given string. The hash function is
	57	// platform dependent. */
	58
	59	// Declare the types `class PTABLE(T)', `struct PASSOC(T)', and `class
	60	// PTABLE_ITERATOR(T)' for the type `T'.
92d0a6a6 JR	61	#define declare_ptable(T) \
	62	\
	63	struct PASSOC(T) { \
	64	char *key; \
	65	T *val; \
	66	PASSOC(T)(); \
	67	}; \
	68	\
	69	class PTABLE(T); \
	70	\
	71	class PTABLE_ITERATOR(T) { \
	72	PTABLE(T) *p; \
	73	unsigned i; \
	74	public: \
4d3e9548 JL	75	PTABLE_ITERATOR(T)(PTABLE(T) ); / Initialize an iterator running \
	76	through the given table. */ \
	77	int next(const char , T ); /* Fetch the next pair, store the key \
	78	and value in arg1 and arg2, \
	79	respectively, and return 1. If \
	80	there is no more pair in the \
	81	table, return 0. */ \
92d0a6a6 JR	82	}; \
	83	\
	84	class PTABLE(T) { \
	85	PASSOC(T) *v; \
	86	unsigned size; \
	87	unsigned used; \
4d3e9548 JL	88	enum { \
	89	FULL_NUM = 2, \
	90	FULL_DEN = 3, \
	91	INITIAL_SIZE = 17 \
	92	}; \
92d0a6a6	93	public: \
4d3e9548 JL	94	PTABLE(T)(); /* Create an empty table. */ \
	95	~PTABLE(T)(); /* Delete a table, including its \
	96	values. */ \
	97	const char define(const char , T );/ Define the value (arg2) for a key \
	98	(arg1). Return the copy in the \
	99	table of the key (arg1), or \
	100	possibly NULL if the value (arg2) \
	101	is NULL. */ \
	102	T lookup(const char ); /* Return a pointer to the value of \
	103	the given key, if found in the \
	104	table, or NULL otherwise. */ \
	105	T lookupassoc(const char ); / Return a pointer to the value of \
	106	the given key, passed by reference,\
	107	and replace the key argument with \
	108	the copy found in the table, if \
	109	the key is found in the table. \
	110	Return NULL otherwise. */ \
92d0a6a6 JR	111	friend class PTABLE_ITERATOR(T); \
	112	};
	113
	114
	115	// Keys (which are strings) are allocated and freed by PTABLE.
	116	// Values must be allocated by the caller (always using new[], not new)
	117	// and are freed by PTABLE.
	118
4d3e9548 JL	119	// Define the implementations of the members of the types `class PTABLE(T)',
4d3e9548 JL	120	// `struct PASSOC(T)', `class PTABLE_ITERATOR(T)' for the type `T'.
92d0a6a6 JR	121	#define implement_ptable(T) \
	122	\
	123	PASSOC(T)::PASSOC(T)() \
	124	: key(0), val(0) \
	125	{ \
	126	} \
	127	\
	128	PTABLE(T)::PTABLE(T)() \
	129	{ \
	130	v = new PASSOC(T)[size = INITIAL_SIZE]; \
	131	used = 0; \
	132	} \
	133	\
	134	PTABLE(T)::~PTABLE(T)() \
	135	{ \
	136	for (unsigned i = 0; i < size; i++) { \
	137	a_delete v[i].key; \
	138	a_delete v[i].val; \
	139	} \
	140	a_delete v; \
	141	} \
	142	\
4d3e9548	143	const char PTABLE(T)::define(const char key, T *val) \
92d0a6a6 JR	144	{ \
	145	assert(key != 0); \
	146	unsigned long h = hash_string(key); \
	147	unsigned n; \
	148	for (n = unsigned(h % size); \
	149	v[n].key != 0; \
	150	n = (n == 0 ? size - 1 : n - 1)) \
	151	if (strcmp(v[n].key, key) == 0) { \
	152	a_delete v[n].val; \
	153	v[n].val = val; \
4d3e9548	154	return v[n].key; \
92d0a6a6 JR	155	} \
92d0a6a6 JR	156	if (val == 0) \
4d3e9548	157	return 0; \
92d0a6a6 JR	158	if (usedFULL_DEN >= sizeFULL_NUM) { \
	159	PASSOC(T) *oldv = v; \
	160	unsigned old_size = size; \
	161	size = next_ptable_size(size); \
	162	v = new PASSOC(T)[size]; \
	163	for (unsigned i = 0; i < old_size; i++) \
	164	if (oldv[i].key != 0) { \
	165	if (oldv[i].val == 0) \
	166	a_delete oldv[i].key; \
	167	else { \
	168	unsigned j; \
	169	for (j = unsigned(hash_string(oldv[i].key) % size); \
	170	v[j].key != 0; \
	171	j = (j == 0 ? size - 1 : j - 1)) \
	172	; \
	173	v[j].key = oldv[i].key; \
	174	v[j].val = oldv[i].val; \
	175	} \
	176	} \
	177	for (n = unsigned(h % size); \
	178	v[n].key != 0; \
	179	n = (n == 0 ? size - 1 : n - 1)) \
	180	; \
	181	a_delete oldv; \
	182	} \
	183	char *temp = new char[strlen(key)+1]; \
	184	strcpy(temp, key); \
	185	v[n].key = temp; \
	186	v[n].val = val; \
	187	used++; \
4d3e9548	188	return temp; \
92d0a6a6 JR	189	} \
	190	\
	191	T PTABLE(T)::lookup(const char key) \
	192	{ \
	193	assert(key != 0); \
	194	for (unsigned n = unsigned(hash_string(key) % size); \
	195	v[n].key != 0; \
	196	n = (n == 0 ? size - 1 : n - 1)) \
	197	if (strcmp(v[n].key, key) == 0) \
	198	return v[n].val; \
	199	return 0; \
	200	} \
	201	\
4d3e9548 JL	202	T PTABLE(T)::lookupassoc(const char *keyptr) \
	203	{ \
	204	const char key = keyptr; \
	205	assert(key != 0); \
	206	for (unsigned n = unsigned(hash_string(key) % size); \
	207	v[n].key != 0; \
	208	n = (n == 0 ? size - 1 : n - 1)) \
	209	if (strcmp(v[n].key, key) == 0) { \
	210	*keyptr = v[n].key; \
	211	return v[n].val; \
	212	} \
	213	return 0; \
	214	} \
	215	\
92d0a6a6 JR	216	PTABLE_ITERATOR(T)::PTABLE_ITERATOR(T)(PTABLE(T) *t) \
	217	: p(t), i(0) \
	218	{ \
	219	} \
	220	\
	221	int PTABLE_ITERATOR(T)::next(const char keyp, T valp) \
	222	{ \
	223	unsigned size = p->size; \
	224	PASSOC(T) *v = p->v; \
	225	for (; i < size; i++) \
	226	if (v[i].key != 0) { \
	227	*keyp = v[i].key; \
	228	*valp = v[i].val; \
	229	i++; \
	230	return 1; \
	231	} \
	232	return 0; \
	233	}
4d3e9548 JL	234
4d3e9548 JL	235	// end of ptable.h