source: GTP/trunk/Lib/Geom/shared/GTGeometry/src/libs/ntl/Cont.cpp @ 1526

////////////////////////////////////////////////////////////////////////////////
// NTL Nonstandard Template Library for C++
// Copyright (c) 2003 by Miroslav Fidler, Tomas Rylek
//
// Created by Miroslav Fidler, Tomas Rylek, cxl@volny.cz
//
// Permission to use, copy, modify, distribute and sell this software for any 
//     purpose is hereby granted without fee, provided that the above copyright 
//     notice appear in all copies and that both that copyright notice and this 
//     permission notice appear in supporting documentation.
// The author makes no representations about the suitability of this software 
//     for any purpose. It is provided "as is" 
//     without express or implied warranty.
////////////////////////////////////////////////////////////////////////////////

#include <ntl.h>

#ifdef _MSC_VER
#pragma inline_depth(255)
#pragma optimize("t", on)
#endif

int Pow2Bound(int i)
{
        int n = 1;
        while(n < i) {
                n <<= 1;
                ASSERT(n);
        }
        return n;
}

void HashBase::Free() const
{
        if(map)
                NTL_RAW_FREE(map, mask + 1, sizeof(int));
        map = NULL;
        mask = 0;
}

void HashBase::ClearIndex() const
{
        link.Clear();
        unlinked = -1;
        Free();
}

HashBase::HashBase()
{
        unlinked = -1;
        map = NULL;
        mask = 0;
}

HashBase::HashBase(pick_ HashBase& b)
: hash(b.hash),
  link(b.link)
{
        map = b.map;
        mask = b.mask;
        unlinked = b.unlinked;
        b.map = NULL;
}

void HashBase::operator=(pick_ HashBase& b)
{
        hash = b.hash;
        link = b.link;
        Free();
        map = b.map;
        mask = b.mask;
        unlinked = b.unlinked;
        b.map = NULL;
}

HashBase::HashBase(const HashBase& b, int)
: hash(b.hash, 0)
{
        unlinked = -1;
        map = NULL;
        mask = 0;
}

void HashBase::operator<<=(const HashBase& b)
{
        ClearIndex();
        hash <<= b.hash;
}

HashBase::~HashBase()
{
        Free();
}

inline void HashBase::LinkBefore(int i, Link& l, int bi) const
{
        Link& bl = link[bi];
        l.next = bi;
        l.prev = bl.prev;
        bl.prev = i;
        link[l.prev].next = i;
}

void HashBase::Trim(int count)
{
        ASSERT(count <= hash.GetCount() && count >= 0);
        if(map) {
                for(int i = count; i < link.GetCount(); i++)
                        Unlink(i, link[i]);
                link.SetCount(count);
        }
        hash.SetCount(count);
}

void HashBase::Drop(int n)
{
        Trim(hash.GetCount() - n);
}

//inline //!! Fidler: either inline or .cpp
void HashBase::FinishIndex() const
{
        int q = link.GetCount();
        link.Reserve(hash.GetAlloc());
        link.AddN(hash.GetCount() - q);
        for(int i = q; i < hash.GetCount(); i++)
                LinkTo(i, link[i], hash[i] & UNSIGNED_HIBIT ? unlinked : Mapi(i));
}

void HashBase::Reindex(int n) const
{
        ClearIndex();
        Free();
        n = ntl_max(16, Pow2Bound(n));
        map = (int *)NTL_RAW_ALLOC(n * sizeof(int));
        Fill(map, map + n, -1);
        mask = n - 1;
        FinishIndex();
}

void HashBase::Reindex() const
{
        Reindex(hash.GetCount());
}

void HashBase::Add(unsigned _hash)
{
        hash.Add(_hash & ~UNSIGNED_HIBIT);
}

void  HashBase::SetUn(int i, unsigned _hash)
{
        if(map) {
                if(link.GetCount() < hash.GetCount())
                        DoIndex();
                Link& lnk = link[i];
                Unlink(i, lnk);
                LinkTo(i, lnk, Maph(_hash & ~UNSIGNED_HIBIT));
        }
        hash[i] = _hash & ~UNSIGNED_HIBIT;
}

Vector<int> HashBase::GetUnlinked() const
{
        if(link.GetCount() < hash.GetCount())
                DoIndex();
        Vector<int> r;
        int q = unlinked;
        if(q >= 0) {
                do {
                        r.Add(q);
                        q = link[q].next;
                }
                while(q != unlinked);
        }
        return r;
}

int HashBase::Put(unsigned _hash)
{
        if(unlinked < 0) return -1;
        if(link.GetCount() < hash.GetCount())
                DoIndex();
        Link& l = link[unlinked];
        int i = unlinked;
        unlinked = link[unlinked].next;
        if(i == unlinked)
                unlinked = -1;
        else {
                link[l.next].prev = l.prev;
                link[l.prev].next = l.next;
        }
        LinkTo(i, l, Maph(_hash & ~UNSIGNED_HIBIT));
        hash[i] = _hash & ~UNSIGNED_HIBIT;
        return i;
}

void HashBase::Set(int i, unsigned _hash) {
        if(map) {
                if(link.GetCount() < hash.GetCount())
                        DoIndex();
                Link& lnk = link[i];
                Unlink(i, lnk);
                int& mi = Maph(_hash & ~UNSIGNED_HIBIT);
                int ii = mi;
                if(ii < 0)
                        mi = lnk.prev = lnk.next = i;
                else
                if(i < ii) {
                        LinkBefore(i, lnk, ii);
                        mi = i;
                }
                else {
                        int l = ii;
                        int h = link[ii].prev;
                        if(h - i < i - l) {
                                while(i < h) {
                                        h = link[h].prev;
                                }
                                LinkBefore(i, lnk, link[h].next);
                        }
                        else {
                                l = link[l].next;
                                while(i > l && l != ii) {
                                        l = link[l].next;
                                }
                                LinkBefore(i, lnk, l);
                        }
                }
        }
        hash[i] = _hash & ~UNSIGNED_HIBIT;
}

void HashBase::Shrink() {
        hash.Shrink();
        if(Pow2Bound(hash.GetCount()) != mask + 1)
                ClearIndex();
        else
                link.Shrink();
}

void HashBase::Reserve(int n)
{
        hash.Reserve(n);
        link.Reserve(n);
        n = Pow2Bound(n);
        if(n > mask + 1)
                Reindex(n);
}

void HashBase::Remove(int i)
{
        hash.Remove(i);
        ClearIndex();
}

void HashBase::Remove(const int *sorted_list, int count)
{
        hash.Remove(sorted_list, count);
        ClearIndex();
}

void HashBase::Insert(int i, unsigned _hash) {
        hash.Insert(i, _hash & ~UNSIGNED_HIBIT);
        ClearIndex();
}

#ifdef UPP
void HashBase::Serialize(Stream& s) {
        int version = 0;
        s / version;
        if(s.IsLoading())
                ClearIndex();
        hash.Serialize(s);
}
#endif

void HashBase::Swap(HashBase& b) {
        ::Swap(hash, b.hash);
        ::Swap(link, b.link);
        ::Swap(map, b.map);
        ::Swap(mask, b.mask);
        ::Swap(unlinked, b.unlinked);
}


#ifdef CPU_IA32

unsigned memhash(const void *ptr, size_t count)
{
        unsigned hash = 1234567890U;

        const unsigned *ds = (unsigned *)ptr;
        const unsigned *de = ds + (count >> 2);
        while(ds < de)
                hash = ((hash << 5) - hash) ^ *ds++;

        const byte *s = (byte *)ds;
        const byte *e = s + (count & 3);
        while(s < e)
                hash = ((hash << 5) - hash) ^ *s++;

        return hash;
}

#else

unsigned memhash(const void *ptr, size_t count)
{
        unsigned hash = 1234567890U;

        const byte *s = (byte *)ptr;
        const byte *e = s + count;
        while(s < e)
                hash = ((hash << 5) - hash) ^ *s++;

        return hash;
}

#endif

unsigned GetHashValue0(const double& d)
{
        return memhash(&d, sizeof(double));
}