# HG changeset patch
# User jwe
# Date 780250782 0
# Node ID daeee5bd0cb53ea894676bc82afa1126962c075f
# Parent  70e94717bd92eebaefe4cbb25b634cf81bed300c
[project @ 1994-09-22 16:19:32 by jwe]
Initial revision

diff --git a/src/Map.cc b/src/Map.cc
new file mode 100644
--- /dev/null
+++ b/src/Map.cc
@@ -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
diff --git a/src/Map.h b/src/Map.h
new file mode 100644
--- /dev/null
+++ b/src/Map.h
@@ -0,0 +1,153 @@
+// octave-map.h                                    -*- 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.
+
+*/
+
+#if ! defined (octave_Map_h)
+#define octave_Map_h 1
+
+#if defined (__GNUG__) && defined (USE_EXTERNAL_TEMPLATES)
+#pragma interface
+#endif
+
+#include <Pix.h>
+
+template <class C>
+class Map
+{
+protected:
+  int count;
+  C def;
+
+public:
+  Map (const C& dflt) : def (dflt) { count = 0; }
+
+  virtual ~Map (void) { }
+
+  int length (void) const { return count; }	// current number of items
+  int empty (void) const { return count == 0; }
+
+  virtual int contains (const char *key) const;	// is key mapped?
+
+  virtual void clear (void);			// delete all items
+	      
+  virtual C& operator [] (const char *key) = 0;	// access contents by key
+	      
+  virtual void del (const char *key) = 0;	// delete entry
+	      
+  virtual Pix first (void) const = 0;		// Pix of first item or 0
+  virtual void next (Pix& i) const = 0;		// advance to next or 0
+  virtual const char *key (Pix i) const = 0;	// access key at i
+  virtual const C& contents (Pix i) const = 0;	// access contents at i
+
+  virtual int owns (Pix i) const;		// is i a valid Pix  ?
+  virtual Pix seek (const char *key) const;	// Pix of key
+
+  C& dflt (void) { return def; }		// access default val
+
+  void  error (const char* msg) const;
+
+  virtual int OK (void) const = 0;		// rep invariant
+};
+
+template <class C>
+struct CHNode
+{
+  CHNode *tl;
+  const char *hd;
+  C cont;
+
+  CHNode (void) { }
+
+  CHNode (const char *h, const C& c, CHNode *t = 0)
+    : hd (h), cont (c), tl (t) { }
+
+  ~CHNode (void) { }
+};
+
+#ifndef DEFAULT_INITIAL_CAPACITY
+#define DEFAULT_INITIAL_CAPACITY 32
+#endif
+
+template <class C>
+class CHMap : public Map<C>
+{
+protected:
+  CHNode<C> **tab;
+  unsigned int size;
+
+public:
+  CHMap (const C& dflt, unsigned int sz = DEFAULT_INITIAL_CAPACITY);
+
+  CHMap (const CHMap& a);
+
+  ~CHMap (void)
+    {
+      clear ();
+      delete tab;
+    }
+
+  C& operator [] (const char *key);
+
+  void del (const char *key);
+
+  Pix first (void) const;
+  void next (Pix& i) const;
+
+  const char *key (Pix p) const
+    {
+      if (p == 0)
+	error ("null Pix");
+
+      return ((CHNode<C> *) p)->hd;
+    }
+
+  const C& contents (Pix p) const
+    {
+      if (p == 0)
+	error ("null Pix");
+
+     return ((CHNode<C> *) p)->cont;
+   }
+
+  Pix seek (const char *key) const;
+
+  int contains (const char *key) const
+    {
+      return seek (key) != 0;
+    }
+
+  void clear (void);
+  int  OK (void) const;
+};
+
+#if defined (__GNUG__) && ! defined (USE_EXTERNAL_TEMPLATES)
+#include "Map.cc"
+#endif
+
+#endif
+
+/*
+;;; Local Variables: ***
+;;; mode: C++ ***
+;;; page-delimiter: "^/\\*" ***
+;;; End: ***
+*/