home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / octave-1.1.1p1-base.tgz / octave-1.1.1p1-base.tar / fsf / octave / src / Map.cc < prev    next >
C/C++ Source or Header  |  1995-01-03  |  5KB  |  284 lines
  1. // Map.cc                                               -*- C++ -*-
  2. /*
  3.  
  4. Copyright (C) 1992, 1993, 1994, 1995 John W. Eaton
  5.  
  6. This file is part of Octave.
  7.  
  8. Octave is free software; you can redistribute it and/or modify it
  9. under the terms of the GNU General Public License as published by the
  10. Free Software Foundation; either version 2, or (at your option) any
  11. later version.
  12.  
  13. Octave is distributed in the hope that it will be useful, but WITHOUT
  14. ANY 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.  
  18. You should have received a copy of the GNU General Public License
  19. along with Octave; see the file COPYING.  If not, write to the Free
  20. Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  
  22. */
  23.  
  24. /*
  25.  
  26. The classes in this file are derived from the old `genclass' versions
  27. of Map and CHMap from libg++, originally:
  28.  
  29.   Copyright (C) 1988 Free Software Foundation
  30.     written by Doug Lea (dl@rocky.oswego.edu)
  31.  
  32. and distributed under the terms of the GNU Library General Public
  33. License as published by the Free Software Foundation.
  34.  
  35. */
  36.  
  37. #ifdef HAVE_CONFIG_H
  38. #include "config.h"
  39. #endif
  40.  
  41. #include <iostream.h>
  42.  
  43. #include "Map.h"
  44.  
  45. static unsigned int
  46. hash (const char *str)
  47. {
  48.   unsigned h = 0;
  49.   while (*str)
  50.     h = h * 33 + *str++;
  51.   return h;
  52. }
  53.  
  54. template <class C>
  55. Pix
  56. Map<C>::seek (const char *item) const
  57. {
  58.   for (Pix i = first (); i != 0 && strcmp (key (i), item) != 0; next (i))
  59.     ; // Skip items until match found.
  60.  
  61.   return i;
  62. }
  63.  
  64. template <class C>
  65. int
  66. Map<C>::owns (Pix idx) const
  67. {
  68.   if (idx == 0)
  69.     return 0;
  70.  
  71.   for (Pix i = first (); i != 0; next (i))
  72.     if (i == idx)
  73.       return 1;
  74.  
  75.   return 0;
  76. }
  77.  
  78. template <class C>
  79. void
  80. Map<C>::clear (void)
  81. {
  82.   Pix i = first ();
  83.   while (i != 0)
  84.     {
  85.       del (key (i));
  86.       i = first ();
  87.     }
  88. }
  89.  
  90. template <class C>
  91. int
  92. Map<C>::contains (const char *item) const
  93. {
  94.   return seek (item) != 0;
  95. }
  96.  
  97. template <class C>
  98. void
  99. Map<C>::error (const char* msg) const
  100. {
  101.   cerr << "Map: " << msg << "\n";
  102. }
  103.  
  104. // CHMap class.
  105.  
  106. // The nodes are linked together serially via a version of a trick
  107. // used in some vtables: odd pointers are actually links to the next
  108. // table entry.  Not terrible, but not wonderful either.
  109.  
  110. template <class C>
  111. static int
  112. goodCHptr (CHNode<C> *t)
  113. {
  114.   return ((((unsigned) t) & 1) == 0);
  115. }
  116.  
  117. // This sucks, but avoids g++ 2.6.0 `type unification failed' errors.
  118.  
  119. static void *
  120. index_to_CHptr (int i)
  121. {
  122.   return (void *) ((i << 1) + 1);
  123. }
  124.  
  125. template <class C>
  126. static int
  127. CHptr_to_index (CHNode<C> *t)
  128. {
  129.   return ((unsigned) t) >> 1;
  130. }
  131.  
  132. template <class C>
  133. CHMap<C>::CHMap (const C& dflt, unsigned int sz) : Map<C> (dflt)
  134. {
  135.   tab = new CHNode<C>* [size = sz];
  136.   for (unsigned int i = 0; i < size; ++i)
  137.     tab[i] = (CHNode<C> *) index_to_CHptr (i+1);
  138.   count = 0;
  139. }
  140.  
  141. template <class C>
  142. CHMap<C>::CHMap (const CHMap& a) : Map<C> (a.def)
  143. {
  144.   tab = new CHNode<C>* [size = a.size];
  145.   for (unsigned int i = 0; i < size; ++i)
  146.     tab[i] = (CHNode<C> *) index_to_CHptr (i+1);
  147.   count = 0;
  148.   for (Pix p = a.first (); p; a.next (p))
  149.     (*this) [a.key (p)] = a.contents (p);
  150. }
  151.  
  152. template <class C>
  153. Pix
  154. CHMap<C>::seek (const char *key) const
  155. {
  156.   unsigned int h = hash (key) % size;
  157.  
  158.   for (CHNode<C> *t = tab[h]; goodCHptr (t); t = t->tl)
  159.     if (strcmp (key, t->hd) == 0)
  160.       return Pix (t);
  161.  
  162.   return 0;
  163. }
  164.  
  165. template <class C>
  166. C&
  167. CHMap<C>::operator [] (const char *item)
  168. {
  169.   unsigned int h = hash (item) % size;
  170.  
  171.   for (CHNode<C> *t = tab[h]; goodCHptr (t); t = t->tl)
  172.     if (strcmp (item, t->hd) == 0)
  173.       return t->cont;
  174.  
  175.   t = new CHNode<C> (item, def, tab[h]);
  176.   tab[h] = t;
  177.   ++count;
  178.   return t->cont;
  179. }
  180.  
  181. template <class C>
  182. void
  183. CHMap<C>::del (const char *key)
  184. {
  185.   unsigned int h = hash (key) % size;
  186.  
  187.   CHNode<C> *t = tab[h];
  188.   CHNode<C> *trail = t;
  189.   while (goodCHptr (t))
  190.     {
  191.       if (strcmp (key, t->hd) == 0)
  192.     {
  193.       if (trail == t)
  194.         tab[h] = t->tl;
  195.       else
  196.         trail->tl = t->tl;
  197.       delete t;
  198.       --count;
  199.       return;
  200.     }
  201.       trail = t;
  202.       t = t->tl;
  203.     }
  204. }
  205.  
  206. template <class C>
  207. void
  208. CHMap<C>::clear (void)
  209. {
  210.   for (unsigned int i = 0; i < size; ++i)
  211.     {
  212.       CHNode<C> *p = tab[i];
  213.       tab[i] = (CHNode<C> *) index_to_CHptr (i+1);
  214.       while (goodCHptr (p))
  215.     {
  216.       CHNode<C> *nxt = p->tl;
  217.       delete p;
  218.       p = nxt;
  219.     }
  220.     }
  221.   count = 0;
  222. }
  223.  
  224. template <class C>
  225. Pix
  226. CHMap<C>::first (void) const
  227. {
  228.   for (unsigned int i = 0; i < size; ++i)
  229.     if (goodCHptr (tab[i]))
  230.       return Pix (tab[i]);
  231.   return 0;
  232. }
  233.  
  234. template <class C>
  235. void
  236. CHMap<C>::next (Pix& p) const
  237. {
  238.   CHNode<C> *t = ((CHNode<C> *) p)->tl;
  239.   if (goodCHptr (t))
  240.     p = Pix (t);
  241.   else
  242.     {
  243.       for (unsigned int i = CHptr_to_index (t); i < size; ++i)
  244.     {
  245.       if (goodCHptr (tab[i]))
  246.         {
  247.           p =  Pix (tab[i]);
  248.           return;
  249.         }
  250.     }
  251.       p = 0;
  252.     }
  253. }
  254.  
  255. template <class C>
  256. int
  257. CHMap<C>::OK (void) const
  258. {
  259.   int v = tab != 0;
  260.   int n = 0;
  261.  
  262.   for (unsigned int i = 0; i < size; ++i)
  263.     {
  264.       for (CHNode<C> *p = tab[i]; goodCHptr (p); p = p->tl)
  265.     ++n;
  266.  
  267.       v &= CHptr_to_index (p) == i + 1;
  268.     }
  269.  
  270.   v &= count == n;
  271.  
  272.   if (! v)
  273.     error ("invariant failure");
  274.  
  275.   return v;
  276. }
  277.  
  278. /*
  279. ;;; Local Variables: ***
  280. ;;; mode: C++ ***
  281. ;;; page-delimiter: "^/\\*" ***
  282. ;;; End: ***
  283. */
  284.