--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/Map.cc	Thu Sep 22 16:19:42 1994 +0000
@@ -0,0 +1,293 @@
+// octave-map.cc                                   -*- C++ -*-
+/*
+
+Copyright (C) 1992, 1993, 1994 John W. Eaton
+
+This file is part of Octave.
+
+Octave 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.
+
+Octave 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 Octave; see the file COPYING.  If not, write to the Free
+Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
+
+*/
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#if defined (__GNUG__) && defined (USE_EXTERNAL_TEMPLATES)
+#pragma implementation
+#endif
+
+#include <iostream.h>
+
+#include "Map.h"
+
+static unsigned int
+hash (const char *str)
+{
+  unsigned h = 0;
+  while (*str)
+    h = h * 33 + *str++;
+  return h;
+}
+
+template <class C>
+Pix
+Map<C>::seek (const char *item) const
+{
+  for (Pix i = first (); i != 0 && strcmp (key (i), item) != 0; next (i))
+    ; // Skip items until match found.
+
+  return i;
+}
+
+template <class C>
+int
+Map<C>::owns (Pix idx) const
+{
+  if (idx == 0)
+    return 0;
+
+  for (Pix i = first (); i != 0; next (i))
+    if (i == idx)
+      return 1;
+
+  return 0;
+}
+
+template <class C>
+void
+Map<C>::clear (void)
+{
+  Pix i = first ();
+  while (i != 0)
+    {
+      del (key (i));
+      i = first ();
+    }
+}
+
+template <class C>
+int
+Map<C>::contains (const char *item) const
+{
+  return seek (item) != 0;
+}
+
+template <class C>
+void
+Map<C>::error (const char* msg) const
+{
+  cerr << "Map: " << msg << "\n";
+}
+
+// CHMap class.
+
+// The nodes are linked together serially via a version of a trick
+// used in some vtables: odd pointers are actually links to the next
+// table entry.  Not terrible, but not wonderful either.
+
+template <class C>
+static inline
+int
+goodCHptr (CHNode<C> *t)
+{
+  return ((((unsigned) t) & 1) == 0);
+}
+
+// This sucks, but avoids g++ 2.6.0 `type unification failed' errors.
+
+void *
+index_to_CHptr (int i)
+{
+  return (void *) ((i << 1) + 1);
+}
+
+template <class C>
+static inline
+int
+CHptr_to_index (CHNode<C> *t)
+{
+  return ((unsigned) t) >> 1;
+}
+
+template <class C>
+CHMap<C>::CHMap (const C& dflt, unsigned int sz) : Map<C> (dflt)
+{
+  tab = new CHNode<C>* [size = sz];
+  for (unsigned int i = 0; i < size; ++i)
+    tab[i] = (CHNode<C> *) index_to_CHptr (i+1);
+  count = 0;
+}
+
+template <class C>
+CHMap<C>::CHMap (const CHMap& a) : Map<C> (a.def)
+{
+  tab = new CHNode<C>* [size = a.size];
+  for (unsigned int i = 0; i < size; ++i)
+    tab[i] = (CHNode<C> *) index_to_CHptr (i+1);
+  count = 0;
+  for (Pix p = a.first (); p; a.next (p))
+    (*this) [a.key (p)] = a.contents (p);
+}
+
+template <class C>
+Pix
+CHMap<C>::seek (const char *key) const
+{
+  unsigned int h = hash (key) % size;
+
+  for (CHNode<C> *t = tab[h]; goodCHptr (t); t = t->tl)
+    if (strcmp (key, t->hd) == 0)
+      return Pix (t);
+
+  return 0;
+}
+
+template <class C>
+C&
+CHMap<C>::operator [] (const char *item)
+{
+  unsigned int h = hash (item) % size;
+
+  for (CHNode<C> *t = tab[h]; goodCHptr (t); t = t->tl)
+    if (strcmp (item, t->hd) == 0)
+      return t->cont;
+
+  t = new CHNode<C> (item, def, tab[h]);
+  tab[h] = t;
+  ++count;
+  return t->cont;
+}
+
+template <class C>
+void
+CHMap<C>::del (const char *key)
+{
+  unsigned int h = hash (key) % size;
+
+  CHNode<C> *t = tab[h];
+  CHNode<C> *trail = t;
+  while (goodCHptr (t))
+    {
+      if (strcmp (key, t->hd) == 0)
+	{
+	  if (trail == t)
+	    tab[h] = t->tl;
+	  else
+	    trail->tl = t->tl;
+	  delete t;
+	  --count;
+	  return;
+	}
+      trail = t;
+      t = t->tl;
+    }
+}
+
+template <class C>
+void
+CHMap<C>::clear (void)
+{
+  for (unsigned int i = 0; i < size; ++i)
+    {
+      CHNode<C> *p = tab[i];
+      tab[i] = (CHNode<C> *) index_to_CHptr (i+1);
+      while (goodCHptr (p))
+	{
+	  CHNode<C> *nxt = p->tl;
+	  delete p;
+	  p = nxt;
+	}
+    }
+  count = 0;
+}
+
+template <class C>
+Pix
+CHMap<C>::first (void) const
+{
+  for (unsigned int i = 0; i < size; ++i)
+    if (goodCHptr (tab[i]))
+      return Pix (tab[i]);
+  return 0;
+}
+
+template <class C>
+void
+CHMap<C>::next (Pix& p) const
+{
+  CHNode<C> *t = ((CHNode<C> *) p)->tl;
+  if (goodCHptr (t))
+    p = Pix (t);
+  else
+    {
+      for (unsigned int i = CHptr_to_index (t); i < size; ++i)
+	{
+	  if (goodCHptr (tab[i]))
+	    {
+	      p =  Pix (tab[i]);
+	      return;
+	    }
+	}
+      p = 0;
+    }
+}
+
+template <class C>
+int
+CHMap<C>::OK (void) const
+{
+  int v = tab != 0;
+  int n = 0;
+
+  for (unsigned int i = 0; i < size; ++i)
+    {
+      for (CHNode<C> *p = tab[i]; goodCHptr (p); p = p->tl)
+	++n;
+
+      v &= CHptr_to_index (p) == i + 1;
+    }
+
+  v &= count == n;
+
+  if (! v)
+    error ("invariant failure");
+
+  return v;
+}
+
+#if defined (__GNUG__) && defined (USE_EXTERNAL_TEMPLATES)
+#if defined (OCTAVE_SOURCE)
+
+//typedef Map<double> map_type_double;
+//typedef CHNode<double> chnode_type_double;
+typedef CHMap<double> chmap_type_double;
+
+#elif defined (USER_TYPEDEFS)
+
+// Users can generate their own .o files with their own types, as many
+// times as they like.  USER_TYPEDEFS should be defined to be the name
+// of an include file that contains typdefs for the desired types.
+//
+// For example, if my-types.h contains typedefs for the Map types
+// you are interested in, you might compile this file with the command
+//
+//   g++ -fexternal-templates -DUSE_EXTERNAL_TEMPLATES \
+//       -DUSER_TYPEDEFS=\"my-types.h\"
+
+#include USER_TYPEDEFS
+
+#endif
+#endif