mirror of
https://github.com/ultimatepp/ultimatepp.git
synced 2026-05-15 22:02:49 -06:00
394 lines
No EOL
7.5 KiB
C++
394 lines
No EOL
7.5 KiB
C++
force_inline
|
|
void IndexCommon::Link(int& m, Hash& hh, int ii)
|
|
{
|
|
if(m < 0)
|
|
m = hh.prev = hh.next = ii;
|
|
else {
|
|
hh.next = m;
|
|
hh.prev = hash[m].prev;
|
|
hash[hh.prev].next = ii;
|
|
hash[m].prev = ii;
|
|
}
|
|
}
|
|
|
|
force_inline
|
|
void IndexCommon::Link(int ii, dword sh)
|
|
{
|
|
Link(map[sh & mask], hash[ii], ii);
|
|
}
|
|
|
|
force_inline
|
|
void IndexCommon::Del(int& m, Hash& hh, int ii)
|
|
{ // unlink from m
|
|
if(ii == m) { // this is item pointed by map
|
|
if(hh.next == ii) { // this is the only item in the bucket
|
|
m = -1; // bucket is now empty
|
|
return;
|
|
}
|
|
m = hh.next; // move bucket pointer to the next item
|
|
}
|
|
hash[hh.next].prev = hh.prev; // unlink
|
|
hash[hh.prev].next = hh.next;
|
|
}
|
|
|
|
template <typename T>
|
|
never_inline
|
|
void Index<T>::ReallocHash(int n)
|
|
{ // realloc hash to have the same capacity as key, copy n elements from previous alloc
|
|
if(key.GetAlloc()) {
|
|
size_t sz = key.GetAlloc() * sizeof(Hash);
|
|
if(!MemoryTryRealloc(hash, sz)) {
|
|
Hash *h = (Hash *)MemoryAlloc(sz);
|
|
if(hash) {
|
|
if(n)
|
|
memcpy_t(h, hash, n);
|
|
MemoryFree(hash);
|
|
}
|
|
hash = h;
|
|
}
|
|
}
|
|
else {
|
|
MemoryFree(hash);
|
|
hash = NULL;
|
|
}
|
|
}
|
|
|
|
template <typename T>
|
|
never_inline
|
|
void Index<T>::FixHash(bool makemap)
|
|
{
|
|
ReallocHash(0);
|
|
unlinked = -1;
|
|
for(int i = 0; i < key.GetCount(); i++)
|
|
hash[i].hash = Smear(key[i]);
|
|
if(makemap)
|
|
MakeMap(key.GetCount());
|
|
else
|
|
Remap(key.GetCount());
|
|
}
|
|
|
|
template <typename T>
|
|
template <typename U>
|
|
never_inline
|
|
void Index<T>::GrowAdd(U&& k, dword sh)
|
|
{
|
|
int n = key.GetCount();
|
|
key.GrowAdd(std::forward<U>(k));
|
|
ReallocHash(n);
|
|
}
|
|
|
|
template <typename T>
|
|
template <typename U>
|
|
void Index<T>::AddS(int& m, U&& k, dword sh)
|
|
{
|
|
int ii = key.GetCount();
|
|
if(ii >= key.GetAlloc())
|
|
GrowAdd(std::forward<U>(k), sh);
|
|
else
|
|
new(key.Rdd()) T(std::forward<U>(k));
|
|
Hash& hh = hash[ii];
|
|
hh.hash = sh;
|
|
if(ii >= (int)mask)
|
|
GrowMap(key.GetCount());
|
|
else
|
|
Link(m, hh, ii);
|
|
}
|
|
|
|
template <typename T>
|
|
template <typename U>
|
|
void Index<T>::AddS(U&& k, dword sh)
|
|
{
|
|
AddS(map[sh & mask], std::forward<U>(k), sh);
|
|
}
|
|
|
|
template <typename T>
|
|
force_inline
|
|
int Index<T>::FindFrom(int i, dword sh, const T& k, int end) const
|
|
{
|
|
if(i >= 0)
|
|
do {
|
|
if(key[i] == k)
|
|
return i;
|
|
i = hash[i].next;
|
|
}
|
|
while(i != end);
|
|
return -1;
|
|
}
|
|
|
|
template <class T>
|
|
int Index<T>::Find(const T& k) const
|
|
{
|
|
dword sh = Smear(k);
|
|
int& m = map[sh & mask];
|
|
return FindFrom(m, sh, k, m);
|
|
}
|
|
|
|
template <class T>
|
|
int Index<T>::FindNext(int i) const
|
|
{
|
|
const Hash& hh = hash[i];
|
|
int end = map[hash[i].hash & mask];
|
|
return hh.next == end ? -1 : FindFrom(hh.next, hh.hash, key[i], end);
|
|
}
|
|
|
|
template <typename T>
|
|
force_inline
|
|
int Index<T>::FindBack(int i, dword sh, const T& k, int end) const
|
|
{
|
|
do {
|
|
const Hash& ih = hash[i];
|
|
if(key[i] == k)
|
|
return i;
|
|
i = ih.prev;
|
|
}
|
|
while(i != end);
|
|
return -1;
|
|
}
|
|
|
|
template <class T>
|
|
int Index<T>::FindLast(const T& k) const
|
|
{
|
|
dword sh = Smear(k);
|
|
int& m = map[sh & mask];
|
|
return m < 0 ? -1 : FindBack(hash[m].prev, sh, k, hash[m].prev);
|
|
}
|
|
|
|
template <class T>
|
|
int Index<T>::FindPrev(int i) const
|
|
{
|
|
const Hash& hh = hash[i];
|
|
int end = map[hash[i].hash & mask];
|
|
return hh.prev == hash[end].prev ? -1 : FindBack(hh.prev, hh.hash, key[i], hash[end].prev);
|
|
}
|
|
|
|
template <class T>
|
|
template <class OP, class U>
|
|
force_inline
|
|
int Index<T>::FindAdd(U&& k, OP op) {
|
|
dword sh = Smear(k);
|
|
int& m = map[sh & mask];
|
|
int i = m;
|
|
if(i >= 0)
|
|
do {
|
|
if(key[i] == k)
|
|
return i;
|
|
i = hash[i].next;
|
|
}
|
|
while(i != m);
|
|
i = key.GetCount();
|
|
AddS(m, std::forward<U>(k), sh);
|
|
op();
|
|
return i;
|
|
}
|
|
|
|
template <typename T>
|
|
void Index<T>::Unlink(int ii)
|
|
{
|
|
Hash& hh = hash[ii];
|
|
Del(map[hh.hash & mask], hh, ii);
|
|
Link(unlinked, hh, ii);
|
|
hh.hash = 0;
|
|
}
|
|
|
|
template <typename T>
|
|
int Index<T>::UnlinkKey(const T& k)
|
|
{
|
|
dword sh = Smear(k);
|
|
int& m = map[sh & mask];
|
|
int i = m;
|
|
int n = 0;
|
|
if(i >= 0)
|
|
for(;;) {
|
|
Hash& hh = hash[i];
|
|
int ni = hh.next;
|
|
if(key[i] == k) {
|
|
Del(m, hh, i);
|
|
Link(unlinked, hh, i);
|
|
n++;
|
|
hh.hash = 0;
|
|
if(ni == i) // last item removed
|
|
break;
|
|
i = ni;
|
|
}
|
|
else {
|
|
i = ni;
|
|
if(i == m)
|
|
break;
|
|
}
|
|
}
|
|
return n;
|
|
}
|
|
|
|
template <typename T>
|
|
template <typename U>
|
|
int Index<T>::Put0(U&& k, dword sh)
|
|
{
|
|
int i;
|
|
if(HasUnlinked()) {
|
|
i = hash[unlinked].prev;
|
|
Hash& hh = hash[i];
|
|
Del(unlinked, hh, i);
|
|
Link(map[sh & mask], hh, i);
|
|
hh.hash = sh;
|
|
key[i] = std::forward<U>(k);
|
|
}
|
|
else {
|
|
i = GetCount();
|
|
AddS(std::forward<U>(k), sh);
|
|
}
|
|
return i;
|
|
}
|
|
|
|
template <class T>
|
|
template <class U>
|
|
force_inline
|
|
int Index<T>::FindPut0(U&& k) {
|
|
dword sh = Smear(k);
|
|
int& m = map[sh & mask];
|
|
int i = m;
|
|
if(i >= 0)
|
|
do {
|
|
if(key[i] == k)
|
|
return i;
|
|
i = hash[i].next;
|
|
}
|
|
while(i != m);
|
|
return Put0(std::forward<U>(k), sh);
|
|
}
|
|
|
|
template <typename T>
|
|
template <typename U>
|
|
void Index<T>::Set0(int ii, U&& k)
|
|
{
|
|
Hash& hh = hash[ii];
|
|
if(IsUnlinked(ii))
|
|
Del(unlinked, hh, ii);
|
|
else
|
|
Del(map[hh.hash & mask], hh, ii);
|
|
|
|
dword sh = Smear(k);
|
|
hh.hash = sh;
|
|
Link(map[sh & mask], hh, ii);
|
|
key[ii] = std::forward<U>(k);
|
|
}
|
|
|
|
template <typename T>
|
|
never_inline
|
|
void Index<T>::Sweep()
|
|
{
|
|
if(unlinked >= 0) {
|
|
int n = key.GetCount();
|
|
key.RemoveIf([&](int i) { return hash[i].hash == 0; });
|
|
IndexCommon::Sweep(n);
|
|
}
|
|
}
|
|
|
|
template <typename T>
|
|
never_inline
|
|
void Index<T>::Reserve(int n)
|
|
{
|
|
int a = key.GetAlloc();
|
|
key.Reserve(n);
|
|
if(a != key.GetAlloc()) {
|
|
ReallocHash(key.GetCount());
|
|
AdjustMap(key.GetCount(), n);
|
|
}
|
|
}
|
|
|
|
template <typename T>
|
|
never_inline
|
|
void Index<T>::Shrink()
|
|
{
|
|
int a = key.GetAlloc();
|
|
key.Shrink();
|
|
if(a != key.GetAlloc()) {
|
|
ReallocHash(key.GetCount());
|
|
AdjustMap(key.GetCount(), key.GetCount());
|
|
}
|
|
}
|
|
|
|
template <typename T>
|
|
void Index<T>::Remove(const int *sorted_list, int count)
|
|
{
|
|
if(HasUnlinked()) {
|
|
Vector<bool> u;
|
|
u.SetCount(GetCount());
|
|
for(int i = 0; i < GetCount(); i++)
|
|
u[i] = IsUnlinked(i);
|
|
key.Remove(sorted_list, count);
|
|
u.Remove(sorted_list, count);
|
|
FixHash(false);
|
|
for(int i = 0; i < GetCount(); i++)
|
|
if(u[i])
|
|
Unlink(i);
|
|
}
|
|
else {
|
|
key.Remove(sorted_list, count);
|
|
FixHash(false);
|
|
}
|
|
}
|
|
|
|
template <typename T>
|
|
never_inline
|
|
void Index<T>::Serialize(Stream& s)
|
|
{
|
|
key.Serialize(s);
|
|
if(s.IsLoading())
|
|
FixHash();
|
|
|
|
int version = 1;
|
|
s / version;
|
|
if(version == 0) { // support previous version
|
|
Vector<unsigned> h;
|
|
h.Serialize(s);
|
|
if(s.IsLoading())
|
|
for(int i = 0; i < h.GetCount(); i++)
|
|
if(i < GetCount() && h[i] & 0x80000000)
|
|
Unlink(i);
|
|
}
|
|
else {
|
|
Vector<int> u = GetUnlinked();
|
|
u.Serialize(s);
|
|
if(s.IsLoading())
|
|
for(int i : ReverseRange(u)) { // Reverse range to ensure the correct order of Put
|
|
if(i >= 0 && i < GetCount())
|
|
Unlink(i);
|
|
else
|
|
s.LoadError();
|
|
}
|
|
}
|
|
}
|
|
|
|
template <class T>
|
|
void Index<T>::Xmlize(XmlIO& xio, const char *itemtag)
|
|
{
|
|
XmlizeIndex<T, Index<T> >(xio, itemtag, *this);
|
|
}
|
|
|
|
template <class T>
|
|
void Index<T>::Jsonize(JsonIO& jio)
|
|
{
|
|
JsonizeIndex<Index<T>, T>(jio, *this);
|
|
}
|
|
|
|
template <class T>
|
|
String Index<T>::ToString() const
|
|
{
|
|
return AsStringArray(*this);
|
|
}
|
|
|
|
#ifdef _DEBUG
|
|
template <typename T>
|
|
String Index<T>::Dump() const
|
|
{
|
|
String h;
|
|
for(int i = 0; i < key.GetCount(); i++) {
|
|
if(i)
|
|
h << "; ";
|
|
if(IsUnlinked(i))
|
|
h << "#";
|
|
h << i << ": " << key[i] << '/' << (hash[i].hash & mask) << " -> " << hash[i].prev << ":" << hash[i].next;
|
|
}
|
|
return h;
|
|
}
|
|
#endif |