Mercurial > hg > octave-lyh
changeset 728:daeee5bd0cb5
[project @ 1994-09-22 16:19:32 by jwe]
Initial revision
author | jwe |
---|---|
date | Thu, 22 Sep 1994 16:19:42 +0000 |
parents | 70e94717bd92 |
children | 9003f624de8b |
files | src/Map.cc src/Map.h |
diffstat | 2 files changed, 446 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
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
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: *** +*/