// This may look like C code, but it is really -*- C++ -*- /* Copyright (C) 1988 Free Software Foundation written by Doug Lea (dl@rocky.oswego.edu) This file is part of the GNU C++ Library. This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This library 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 Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; if not, write to the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ #ifdef __GNUG__ #pragma implementation #endif #include "..CHMap.h" // 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 static inline int goodCHptr(CHNode* t) { return ((((unsigned)t) & 1) == 0); } static inline CHNode* index_to_CHptr(int i) { return (CHNode*)((i << 1) + 1); } static inline int CHptr_to_index(CHNode* t) { return ( ((unsigned) t) >> 1); } CHMap::CHMap( dflt, unsigned int sz) :Map(dflt) { tab = (CHNode**)(new CHNodePtr[size = sz]); for (unsigned int i = 0; i < size; ++i) tab[i] = index_to_CHptr(i+1); count = 0; } CHMap::CHMap(CHMap& a) :Map(a.def) { tab = (CHNode**)(new CHNodePtr[size = a.size]); for (unsigned int i = 0; i < size; ++i) tab[i] = index_to_CHptr(i+1); count = 0; for (Pix p = a.first(); p; a.next(p)) (*this)[a.key(p)] = a.contents(p); } Pix CHMap::seek( key) { unsigned int h = HASH(key) % size; for (CHNode* t = tab[h]; goodCHptr(t); t = t->tl) if (EQ(key, t->hd)) return Pix(t); return 0; } & CHMap::operator []( item) { unsigned int h = HASH(item) % size; for (CHNode* t = tab[h]; goodCHptr(t); t = t->tl) if (EQ(item, t->hd)) return t->cont; t = new CHNode(item, def, tab[h]); tab[h] = t; ++count; return t->cont; } void CHMap::del( key) { unsigned int h = HASH(key) % size; CHNode* t = tab[h]; CHNode* trail = t; while (goodCHptr(t)) { if (EQ(key, t->hd)) { if (trail == t) tab[h] = t->tl; else trail->tl = t->tl; delete t; --count; return; } trail = t; t = t->tl; } } void CHMap::clear() { for (unsigned int i = 0; i < size; ++i) { CHNode* p = tab[i]; tab[i] = index_to_CHptr(i+1); while (goodCHptr(p)) { CHNode* nxt = p->tl; delete(p); p = nxt; } } count = 0; } Pix CHMap::first() { for (unsigned int i = 0; i < size; ++i) if (goodCHptr(tab[i])) return Pix(tab[i]); return 0; } void CHMap::next(Pix& p) { CHNode* t = ((CHNode*)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; } } int CHMap::OK() { int v = tab != 0; int n = 0; for (unsigned int i = 0; i < size; ++i) { for (CHNode* 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; }