2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
6 * These libraries and programs are free software; you can
7 * redistribute them and/or modify them under the terms of the GNU
8 * Lesser General Public License as published by the Free Software
9 * Foundation; either version 2 of the License, or (at your option)
12 * These libraries and programs are distributed in the hope that
13 * they will be useful, but WITHOUT ANY WARRANTY; without even the
14 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU Lesser General Public License for more
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with these librararies and programs; if not, write
20 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
21 * Floor, Boston, MA 02110-1301 USA
23 /* $XConsortium: PointerTable.C /main/1 1996/07/29 17:01:40 cde-hp $ */
24 // Copyright (c) 1994 James Clark
25 // See the file COPYING for copying permission.
27 #ifndef PointerTable_DEF_INCLUDED
28 #define PointerTable_DEF_INCLUDED 1
33 namespace SP_NAMESPACE {
36 template<class P, class K, class HF, class KF>
37 PointerTable<P, K, HF, KF>::PointerTable()
38 : used_(0), usedLimit_(0), null_(0)
42 template<class P, class K, class HF, class KF>
43 void PointerTable<P, K, HF, KF>::clear()
50 template<class P, class K, class HF, class KF>
51 P PointerTable<P, K, HF, KF>::insert(P p, Boolean replace)
54 if (vec_.size() == 0) {
57 h = startIndex(KF::key(*p));
60 for (h = startIndex(KF::key(*p)); vec_[h] != 0 ; h = nextIndex(h))
61 if (KF::key(*vec_[h]) == KF::key(*p)) {
70 if (used_ >= usedLimit_) {
71 if (vec_.size() > size_t(-1)/2) {
72 if (usedLimit_ == vec_.size() - 1)
73 abort(); // FIXME throw an exception
75 usedLimit_ = vec_.size() - 1;
79 Vector<P> oldVec(vec_.size()*2, P(0));
81 usedLimit_ = vec_.size() / 2;
82 for (size_t i = 0; i < oldVec.size(); i++)
85 for (j = startIndex(KF::key(*oldVec[i]));
91 for (h = startIndex(KF::key(*p)); vec_[h] != 0; h = nextIndex(h))
101 template<class P, class K, class HF, class KF>
102 const P &PointerTable<P, K, HF, KF>::lookup(const K &k) const
105 for (size_t i = startIndex(k); vec_[i] != 0; i = nextIndex(i))
106 if (KF::key(*vec_[i]) == k)
112 template<class P, class K, class HF, class KF>
113 P PointerTable<P, K, HF, KF>::remove(const K &k)
116 for (size_t i = startIndex(k); vec_[i] != 0; i = nextIndex(i))
117 if (KF::key(*vec_[i]) == k) {
127 r = startIndex(KF::key(*vec_[i]));
128 } while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
130 } while (vec_[i] != 0);
138 template<class P, class K, class HF, class KF>
139 void PointerTable<P, K, HF, KF>::swap(PointerTable<P, K, HF, KF> &to)
142 size_t tem = to.used_;
146 to.usedLimit_ = usedLimit_;
150 template<class P, class K, class HF, class KF>
151 PointerTableIter<P, K, HF, KF>::PointerTableIter(const PointerTable<P, K, HF, KF> &table)
152 : tablePtr_(&table), i_(0)
156 template<class P, class K, class HF, class KF>
157 const P &PointerTableIter<P, K, HF, KF>::next()
159 for (; i_ < tablePtr_->vec_.size(); i_++)
160 if (tablePtr_->vec_[i_] != 0)
161 return tablePtr_->vec_[i_++];
162 return tablePtr_->null_;
169 #endif /* not PointerTable_DEF_INCLUDED */