* src/include/ptable.h, src/include/itable.h

(NEXT_PTABLE_SIZE_DEFINED): Use it to avoid multiple declaration
of external symbol `next_ptable_size' (used by both header files).

3 files changed, 211 insertions, 0 deletions

diff --git a/ChangeLog b/ChangeLog
index fafe3eeb..8470b0c0 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2006-02-17  Werner LEMBERG  <wl@gnu.org>
+
+	* src/include/ptable.h, src/include/itable.h
+	(NEXT_PTABLE_SIZE_DEFINED): Use it to avoid multiple declaration
+	of external symbol `next_ptable_size' (used by both header files).
+
 2006-02-15  Bruno Haible  <bruno@clisp.org>
 
 	* src/include/font.h (struct glyphinfo): New class.
diff --git a/src/include/itable.h b/src/include/itable.h
new file mode 100644
index 00000000..e8a79d94
--- /dev/null
+++ b/src/include/itable.h
@@ -0,0 +1,200 @@
+// -*- C++ -*-
+/* Copyright (C) 1989, 1990, 1991, 1992, 2003, 2004, 2006
+   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 2, 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 groff; see the file COPYING.  If not, write to the Free Software
+Foundation, 51 Franklin St - Fifth Floor, Boston, MA 02110-1301, USA. */
+
+#include <assert.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 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) name2(T,_itable)
+#define IASSOC(T) name2(T,_iassoc)
+#define ITABLE_ITERATOR(T) name2(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++)					      \
+    a_delete v[i].val;							      \
+  a_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) {						      \
+      a_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))				      \
+      ;									      \
+    a_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;								      \
+}
+
+// end of itable.h
diff --git a/src/include/ptable.h b/src/include/ptable.h
index 6b0998e1..7a67527a 100644
--- a/src/include/ptable.h
+++ b/src/include/ptable.h
@@ -45,9 +45,14 @@ Foundation, 51 Franklin St - Fifth Floor, Boston, MA 02110-1301, USA. */
 #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.  */