162 lines
2.9 KiB
C++
162 lines
2.9 KiB
C++
/*
|
|
*/
|
|
|
|
|
|
#ifndef __TMPL_PAIRLIST__
|
|
#define __TMPL_PAIRLIST__
|
|
|
|
|
|
#include "data/array_list.h"
|
|
#include "platform_config.h"
|
|
|
|
|
|
//
|
|
template <class PAIR, class TYPE> class ntPairList;
|
|
|
|
|
|
/*
|
|
@short Pair item.
|
|
@author Emmanuel Julien (ejulien@gsworks.fr)
|
|
*/
|
|
template <class TYPE> class ntPairItem : public nArrayEntry
|
|
{
|
|
protected:
|
|
|
|
int hash;
|
|
|
|
public:
|
|
|
|
TYPE *a, *b; ///< Object pair.
|
|
void *pair_data; ///< Pair associated data block.
|
|
|
|
/// Compute pair hash value.
|
|
static int ComputeHash(TYPE *_a, TYPE *_b)
|
|
{
|
|
int hash = (((uintptr_t)_a) & 0xf0f0f0f0) | (((uintptr_t)_b) & 0x0f0f0f0f);
|
|
hash = (hash + 0x7ed55d16) + (hash << 12);
|
|
hash = (hash ^ 0xc761c23c) ^ (hash >> 19);
|
|
hash = (hash + 0x165667b1) + (hash << 5);
|
|
hash = (hash + 0xd3a2646c) ^ (hash << 9);
|
|
hash = (hash + 0xfd7046c5) + (hash << 3);
|
|
hash = (hash ^ 0xb55a4f09) ^ (hash >> 16);
|
|
return hash;
|
|
}
|
|
|
|
/// Get pair hash.
|
|
int Hash() const { return hash; }
|
|
|
|
ntPairItem(TYPE *_a, TYPE *_b)
|
|
{
|
|
a = _a; b = _b;
|
|
hash = ComputeHash(a, b);
|
|
}
|
|
};
|
|
|
|
|
|
/*
|
|
*/
|
|
struct ntPairListPool
|
|
{
|
|
uint bucket,
|
|
entry;
|
|
|
|
void Reset()
|
|
{ bucket = entry = 0; }
|
|
|
|
ntPairListPool()
|
|
{ Reset(); }
|
|
};
|
|
|
|
/*
|
|
@short Pair list.
|
|
@author Emmanuel Julien (ejulien@gsworks.fr)
|
|
*/
|
|
template <class PAIR, class TYPE> class ntPairList
|
|
{
|
|
|
|
#define PairListBucketCount 64
|
|
#define OrderPairItems(_A_, _B_) { if (_A_ > _B_) { TYPE *t = _A_; _A_ = _B_; _B_ = t; } }
|
|
|
|
protected:
|
|
|
|
uint count;
|
|
nArrayList bucket[PairListBucketCount];
|
|
|
|
public:
|
|
|
|
/// Get item count in list.
|
|
uint GetCount() const
|
|
{ return count; }
|
|
|
|
/// Pool list.
|
|
PAIR *Pool(ntPairListPool &pool) const
|
|
{
|
|
while (pool.bucket < PairListBucketCount)
|
|
{
|
|
if (pool.entry < bucket[pool.bucket].GetCount())
|
|
break;
|
|
|
|
pool.entry = 0;
|
|
pool.bucket++;
|
|
}
|
|
if (pool.bucket == PairListBucketCount)
|
|
return 0;
|
|
return (PAIR *)bucket[pool.bucket][pool.entry++];
|
|
}
|
|
|
|
/// Add a pair.
|
|
PAIR *Add(TYPE *a, TYPE *b)
|
|
{
|
|
OrderPairItems(a, b);
|
|
|
|
PAIR *pair = new PAIR(a, b);
|
|
if (pair && !bucket[pair->Hash() & (PairListBucketCount - 1)].Add(pair))
|
|
_safe_delete(pair);
|
|
else
|
|
count++;
|
|
return pair;
|
|
}
|
|
|
|
/// Find a pair.
|
|
PAIR *Find(TYPE *a, TYPE *b)
|
|
{
|
|
OrderPairItems(a, b);
|
|
|
|
int hash = PAIR::ComputeHash(a, b);
|
|
nArrayList &h_bucket = bucket[hash & (PairListBucketCount - 1)];
|
|
|
|
for (uint n = 0; n < h_bucket.GetCount(); ++n)
|
|
{
|
|
PAIR *pair = (PAIR *)h_bucket[n];
|
|
if ((pair->a == a) && (pair->b == b))
|
|
return pair;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
/// Remove pair.
|
|
bool Remove(PAIR *pair)
|
|
{
|
|
if (bucket[pair->Hash() & (PairListBucketCount - 1)].Delete(pair))
|
|
{
|
|
count--;
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/// Delete all pair.
|
|
void DeleteAll(bool freedata = true)
|
|
{
|
|
for (int n = 0; n < PairListBucketCount; ++n)
|
|
bucket[n].DeleteAll(freedata);
|
|
count = 0;
|
|
}
|
|
|
|
ntPairList()
|
|
{ count = 0; }
|
|
};
|
|
|
|
|
|
#endif // __TMPL_PAIRLIST__
|