Mercurial > illumos > onarm
view usr/src/cmd/man/src/util/nsgmls.src/include/PointerTable.cxx @ 4:1a15d5aaf794
synchronized with onnv_86 (6202) in onnv-gate
author | Koji Uno <koji.uno@sun.com> |
---|---|
date | Mon, 31 Aug 2009 14:38:03 +0900 |
parents | c9caec207d52 |
children |
line wrap: on
line source
// Copyright (c) 1994 James Clark // See the file COPYING for copying permission. #pragma ident "%Z%%M% %I% %E% SMI" #ifndef PointerTable_DEF_INCLUDED #define PointerTable_DEF_INCLUDED 1 #include <stdlib.h> #ifdef SP_NAMESPACE namespace SP_NAMESPACE { #endif template<class P, class K, class HF, class KF> PointerTable<P, K, HF, KF>::PointerTable() : used_(0), usedLimit_(0), null_(0) { } template<class P, class K, class HF, class KF> void PointerTable<P, K, HF, KF>::clear() { vec_.clear(); used_ = 0; usedLimit_ = 0; } template<class P, class K, class HF, class KF> P PointerTable<P, K, HF, KF>::insert(P p, Boolean replace) { size_t h; if (vec_.size() == 0) { vec_.assign(8, P(0)); usedLimit_ = 4; h = startIndex(KF::key(*p)); } else { for (h = startIndex(KF::key(*p)); vec_[h] != 0 ; h = nextIndex(h)) if (KF::key(*vec_[h]) == KF::key(*p)) { if (replace) { P tem(vec_[h]); vec_[h] = p; return tem; } else return vec_[h]; } if (used_ >= usedLimit_) { if (vec_.size() > size_t(-1)/2) { if (usedLimit_ == vec_.size() - 1) abort(); // FIXME throw an exception else usedLimit_ = vec_.size() - 1; } else { // rehash Vector<P> oldVec(vec_.size()*2, P(0)); vec_.swap(oldVec); usedLimit_ = vec_.size() / 2; for (size_t i = 0; i < oldVec.size(); i++) if (oldVec[i] != 0) { size_t j; for (j = startIndex(KF::key(*oldVec[i])); vec_[j] != 0; j = nextIndex(j)) ; vec_[j] = oldVec[i]; } for (h = startIndex(KF::key(*p)); vec_[h] != 0; h = nextIndex(h)) ; } } } used_++; vec_[h] = p; return 0; } template<class P, class K, class HF, class KF> const P &PointerTable<P, K, HF, KF>::lookup(const K &k) const { if (used_ > 0) { for (size_t i = startIndex(k); vec_[i] != 0; i = nextIndex(i)) if (KF::key(*vec_[i]) == k) return vec_[i]; } return null_; } template<class P, class K, class HF, class KF> P PointerTable<P, K, HF, KF>::remove(const K &k) { if (used_ > 0) { for (size_t i = startIndex(k); vec_[i] != 0; i = nextIndex(i)) if (KF::key(*vec_[i]) == k) { P p = vec_[i]; do { vec_[i] = P(0); size_t j = i; size_t r; do { i = nextIndex(i); if (vec_[i] == 0) break; r = startIndex(KF::key(*vec_[i])); } while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r)); vec_[j] = vec_[i]; } while (vec_[i] != 0); --used_; return p; } } return 0; } template<class P, class K, class HF, class KF> void PointerTable<P, K, HF, KF>::swap(PointerTable<P, K, HF, KF> &to) { vec_.swap(to.vec_); size_t tem = to.used_; to.used_ = used_; used_ = tem; tem = to.usedLimit_; to.usedLimit_ = usedLimit_; usedLimit_ = tem; } template<class P, class K, class HF, class KF> PointerTableIter<P, K, HF, KF>::PointerTableIter(const PointerTable<P, K, HF, KF> &table) : tablePtr_(&table), i_(0) { } template<class P, class K, class HF, class KF> const P &PointerTableIter<P, K, HF, KF>::next() { for (; i_ < tablePtr_->vec_.size(); i_++) if (tablePtr_->vec_[i_] != 0) return tablePtr_->vec_[i_++]; return tablePtr_->null_; } #ifdef SP_NAMESPACE } #endif #endif /* not PointerTable_DEF_INCLUDED */