/usr/include/sp/PointerTable.cxx is in libsp1-dev 1.3.4-1.2.1-47.3ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | // Copyright (c) 1994 James Clark
// See the file COPYING for copying permission.
#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 */
|