diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /graphics/sam2p/mapping.cpp |
Initial commit
Diffstat (limited to 'graphics/sam2p/mapping.cpp')
-rw-r--r-- | graphics/sam2p/mapping.cpp | 309 |
1 files changed, 309 insertions, 0 deletions
diff --git a/graphics/sam2p/mapping.cpp b/graphics/sam2p/mapping.cpp new file mode 100644 index 0000000000..4c3844ec77 --- /dev/null +++ b/graphics/sam2p/mapping.cpp @@ -0,0 +1,309 @@ +/* + * mapping.cpp -- associative array implementations + * by pts@fazekas.hu at Fri Mar 15 21:13:47 CET 2002 + */ + +#ifdef __GNUC__ +#ifndef __clang__ +#pragma implementation +#endif +#endif + +#include "mapping.hpp" +#include "error.hpp" +#include <string.h> +#include <stdlib.h> /* abort() */ + +/* --- */ + +bool Mapping::Gen::update(char const*key, slen_t keylen, char const*data) { + char *found_data=get(key, keylen); + if (found_data==NULLP) return true; + memcpy(found_data, data, datalen); + return false; +} + +/* --- */ + +bool Mapping::DoubleHash::obj_assert() { + assert(len <= used); + assert(minlen <= len); + assert(used <= maxused); + assert(maxused < alloced); + assert(alloced < (slen_t)-2); + /* Imp: re-count used and len */ + return true; +} + +bool Mapping::DoubleHash::set (char const* key, slen_t keylen, char const*data) { + assert(obj_assert()); + slen_t h1=vi_h1(key,keylen); + assert(h1<alloced); + Ary *p=ary+h1; + if (p->keylen==NEVER_USED) { added: + /* Dat: we shouldn't stop on p->keylen==DELETED */ + /* This will be deleted by `delete [] (pp->keydata-datalen);' called from + * Mapping::DoubleHash::clear() called from the destructor of + * Mapping::DoubleHash15, also known as Mapping::H. + */ + memcpy(p->keydata=new char[keylen+datalen], data, datalen); + memcpy(p->keydata+=datalen, key, p->keylen=keylen); len++; + //if (p->keylen==NEVER_USED && used++==maxused) { p->keylen=keylen; rehash(); } + // else { p->keylen=keylen; } + if (used++==maxused) rehash(); + assert(obj_assert()); + return true; /* new value added */ + } + if (p->keylen==keylen && 0==memcmp(p->keydata, key, keylen)) { updated: + memcpy(p->keydata-datalen, data, datalen); + return false; /* value updated */ + } + /* Not found for the 1st try. We have to walk. */ + slen_t h2=vi_h2(key,keylen); + assert(1<=h2 && h1<alloced); + while (1) { /* Dat: maxlen < alloced, so this can safely be an infinite loop. */ + if (h1>=h2) { h1-=h2; p-=h2; } + else { h1+=alloced-h2; p+=alloced-h2; } + if (p->keylen==NEVER_USED) goto added; + if (p->keylen==keylen && 0==memcmp(p->keydata, key, keylen)) goto updated; + } +} +char*Mapping::DoubleHash::get (char const* key, slen_t keylen) { + assert(obj_assert()); + slen_t h1=vi_h1(key,keylen); + assert(h1<alloced); + Ary *p=ary+h1; + if (p->keylen==NEVER_USED) return (char*)NULLP; + if (p->keylen==keylen && 0==memcmp(p->keydata, key, keylen)) return p->keydata-datalen; + /* Not found for the 1st try. We have to walk. */ + slen_t h2=vi_h2(key,keylen); + assert(1<=h2 && h1<alloced); + /* Dat: assert(lnko(...)) better in vi_h2 */ + while (1) { /* Dat: maxlen < alloced, so this can safely be an infinite loop. */ + if (h1>=h2) { h1-=h2; p-=h2; } + else { h1+=alloced-h2; p+=alloced-h2; } + if (p->keylen==NEVER_USED) return (char*)NULLP; + if (p->keylen==keylen && 0==memcmp(p->keydata, key, keylen)) return p->keydata-datalen; + } +} +bool Mapping::DoubleHash::deletee (char const* key, slen_t keylen) { + /* We must not set `p->keylen=NEVER_USED' in this method because this would + * ruin searches jumping on `p', but not coming from `p+h2'. So we just set + * `p->keylen=DELETED'. + */ + assert(obj_assert()); + slen_t h1=vi_h1(key,keylen); + assert(h1<alloced); + Ary *p=ary+h1; + if (p->keylen==NEVER_USED) return true; /* key to be deleted does not exist */ + if (p->keylen==keylen && 0==memcmp(p->keydata, key, keylen)) { found: + vi_dtor(p->keydata-datalen); + delete [] (p->keydata-datalen); + p->keylen=(slen_t)DELETED; + // p->keydata=(char*)NULLP; + if (len--==minlen) rehash(); + assert(obj_assert()); + return false; /* key-value pair deleted */ + } + /* Not found for the 1st try. We have to walk. */ + slen_t h2=vi_h2(key,keylen); + assert(1<=h2 && h1<alloced); + while (1) { /* Dat: maxlen < alloced, so this can safely be an infinite loop. */ + if (h1>=h2) { h1-=h2; p-=h2; } + else { h1+=alloced-h2; p+=alloced-h2; } + if (p->keylen==(slen_t)NEVER_USED) return true; /* key to be deleted does not exist */ + if (p->keylen==keylen && 0==memcmp(p->keydata, key, keylen)) goto found; + } +} +void Mapping::DoubleHash::getFirst(char const*const*& key, slen_t &keylen, char *& data) { + assert(obj_assert()); + Ary *p=ary, *pend=p+alloced; + while (p!=pend && p->keylen>=(slen_t)-2) p++; + if (p==pend) { key=(char const*const*)NULLP; } + else { key=&p->keydata; data=p->keydata-datalen; keylen=p->keylen; } +} +void Mapping::DoubleHash::getNext (char const*const*& key, slen_t &keylen, char *& data) { + assert(obj_assert()); + /* vvv Dat: this operation is safe despite of the fact that it increases + * signedness off pointer target type ((char*) -> (Ary*)). + */ + Ary *p=PTS_align_cast(Ary*, + ( (char*)const_cast<char**>(key) + - ((char*)&((Ary*)0)->keydata-(char*)0) )), *pend=ary+alloced; + p++; + while (p!=pend && p->keylen>=(slen_t)-2) p++; + if (p==pend) { key=(char const*const*)NULLP; } + else { key=&p->keydata; data=p->keydata-datalen; keylen=p->keylen; } +} +void Mapping::DoubleHash::rehash() { + unsigned old_scale=scale; + slen_t old_alloced=alloced; +#ifndef NDEBUG + slen_t old_len=len; + slen_t old_used=used; +#endif + Ary *old_ary=ary; + // printf("rehash minlen=%u len=%u used=%u maxused=%u alloced=%u\n", minlen, len, used, maxused, alloced); + vi_scale(); + // printf("scaled minlen=%u len=%u used=%u maxused=%u alloced=%u\n", minlen, len, used, maxused, alloced); + // assert( minlen <= len); + if (scale==old_scale && used<=maxused) { assert(obj_assert()); return; } + Ary *pp=old_ary, *ppend=pp+old_alloced; + slen_t calclen=0, calcused=0; + ary=new Ary[alloced]; + // printf("alloced=%u\n", alloced); + memset(ary, '\377', sizeof(Ary)*alloced); /* fill with NEVER_USED */ + /* insert the old values to the new hash */ + for (; pp!=ppend; pp++) { + if (pp->keylen!=NEVER_USED) calcused++; + if (pp->keylen<(slen_t)-2) { + // printf("%u %u\n", (unsigned char)pp->keydata[0], (unsigned char)pp->keydata[1]); + calclen++; + slen_t h1=vi_h1(pp->keydata,pp->keylen); + assert(h1<alloced); + Ary *p=ary+h1; + assert(p->keylen!=DELETED); + if (p->keylen==NEVER_USED) { found: + p->keylen=pp->keylen; + p->keydata=pp->keydata; + continue; + } + assert(!(p->keylen==pp->keylen && 0==memcmp(p->keydata, pp->keydata, pp->keylen)) && "dupicate key"); + /* Not found for the 1st try. We have to walk. */ + slen_t h2=vi_h2(pp->keydata,pp->keylen); + assert(1<=h2 && h1<alloced); + while (1) { /* Dat: maxlen < alloced, so this can safely be an infinite loop. */ + if (h1>=h2) { h1-=h2; p-=h2; } + else { h1+=alloced-h2; p+=alloced-h2; } + assert(p->keylen!=DELETED); + if (p->keylen==NEVER_USED) goto found; + assert(!(p->keylen==pp->keylen && 0==memcmp(p->keydata, pp->keydata, pp->keylen)) && "dupicate key"); + } /* WHILE */ + } + } /* NEXT */ + used=len=calclen; + assert(calclen==old_len); + assert(calcused==old_used); + assert(old_len==len); + assert(old_len==used); + assert(obj_assert()); + delete [] old_ary; +} +void Mapping::DoubleHash::clear() { + assert(obj_assert()); + Ary *pp=ary, *ppend=pp+alloced; + for (; pp!=ppend; pp++) if (pp->keylen<(slen_t)-2) { + vi_dtor(pp->keydata-datalen); /* this is quite fast */ + delete [] (pp->keydata-datalen); /* this is really slow for millions of values */ + pp->keylen=(slen_t)DELETED; + len--; + } + assert(len==0); + if (minlen!=0) rehash(); +} + +/* --- */ + +static slen_t const d15_primes[]= { + 0, 10, 13, 23, 37, 59, 89, 137, 211, 317, 479, 719, 1087, 1637, 2459, 3691, + 5557, 8353, 12539, 18839, 28277, 42433, 63659, + 95507UL, 143261UL, 214913UL, 322397UL, 483611UL, 725423UL, 1088159UL, 1632259UL, 2448389UL, + 3672593UL, 5508913UL, 8263373UL, 12395069UL, 18592631UL, 27888947UL, 41833427UL, + 62750147UL, 94125247UL, 141187901UL, 211781873UL, 317672813UL, 476509223UL, + 714763843UL, 1072145771UL, 1608218669UL, 2412328031UL, 3618492049UL, +#if SIZEOF_SLEN_T>=8 + 5427738097UL, 8141607167UL, 12212410753UL, 18318616157UL, 27477924239UL, + 41216886467UL, 61825329719UL, 92737994593UL, 139106991917UL, 208660487887UL, + 312990731839UL, 469486097807UL, 704229146717UL, 1056343720093UL, + 1584515580187UL, 2376773370313UL, 3565160055487UL, 5347740083243UL, + 8021610124867UL, 12032415187319UL, 18048622780987UL, 27072934171487UL, + 40609401257291UL, 60914101885951UL, 91371152828947UL, 137056729243439UL, + 205585093865189UL, 308377640797829UL, 462566461196803UL, + 693849691795229UL, 1040774537692907UL, 1561161806539393UL, + 2341742709809177UL, 3512614064713777UL, 5268921097070759UL, + 7903381645606193UL, 11855072468409349UL, 17782608702614033UL, + 26673913053921061UL, 40010869580881603UL, 60016304371322423UL, + 90024456556983643UL, 135036684835475519UL, 202555027253213279UL, + 303832540879819943UL, 455748811319729951UL, 683623216979594929UL, + 1025434825469392417UL, 1538152238204088631UL, 2307228357306132983UL, + 3460842535959199481UL, 5191263803938799269UL, +#endif + 0 +}; + +void Mapping::DoubleHash15::vi_scale() { +#if 0 + // <lloced=63659 used=59671 maxused=59670 + // alloced=1637 used=59671 maxused=1534 + + // <lloced=1637 used=1535 maxused=1534 + // |lloced=2459 used=1535 maxused=1534 + // |lloced=1637 used=1535 maxused=1534 + // alloced=1637 used=1535 maxused=1534 + + + printf("<lloced=%u used=%u maxused=%u\n", alloced, used, maxused); + if (len<minlen) { again: + /* assert(used==minlen-1); */ + assert(scale>=1); + alloced=(d15_primes+2)[--scale]; + if (scale>1) minlen=(d15_primes+2)[scale-2]; + else if (scale==1) minlen=10; + else minlen=0; + if (len<minlen) goto again; + } else if (used>maxused) { + assert(used==maxused+1); + if ((alloced=(d15_primes+2)[++scale])==0) abort(); /* Imp: better overflow reporting */ + if (scale>1) minlen=(d15_primes+2)[scale-2]; + else if (scale==1) minlen=10; + else minlen=0; + // if (len<minlen) minlen=len; + } else assert(0); + printf("|lloced=%u used=%u maxused=%u\n", alloced, used, maxused); + if (alloced<=4000U) maxused=(alloced*15)>>4; + else maxused=(alloced>>4)*15; + if (used>maxused) printf("alloced=%u used=%u maxused=%u\n", alloced, used, maxused); +#endif + + /* Dat: we respect only `len', not used. */ + /* Imp: make calculation of scale relative to previous one */ + + scale=0; while (1) { + // printf("xscale=%u\n", scale); + if (0==(alloced=(d15_primes+2)[scale])) { assert(0); abort(); } /* Imp: better overflow reporting */ + if (alloced<=4000U) maxused=(alloced*15)>>4; + else maxused=(alloced>>4)*15; /* avoid overflows */ + if (len<=maxused) break; /* _not_ used<=maxused, because of rehash() */ + scale++; + } + minlen=(d15_primes)[scale]; + // printf("ret alloced=%u used=%u maxused=%u\n", alloced, used, maxused); +} +slen_t Mapping::DoubleHash15::vi_h1(register char const*key, register slen_t keylen) { + register slen_t hval=0, m=alloced; + while (keylen--!=0) hval=((hval<<8)+*key++)%m; + /* Imp: make this accurate and faster (the `%' operation is rather slow) */ + return hval; +} +slen_t Mapping::DoubleHash15::vi_h2(char const*key, slen_t keylen) { + register slen_t hval=0, m=alloced-1; + while (keylen--!=0) hval=((hval<<8)+*key++)%m; + /* Imp: make this accurate and faster (the `%' operation is rather slow) */ + return hval+1; +} +void Mapping::DoubleHash15::vi_dtor(char *) {} + +Mapping::DoubleHash15::DoubleHash15(slen_t datalen_) { + ary=new Ary[alloced=(d15_primes+2)[scale=0]]; + memset(ary, '\377', sizeof(Ary)*alloced); /* fill with NEVER_USED */ + datalen=datalen_; + len=used=minlen=0; + maxused=(alloced>>4)*15; +} +Mapping::DoubleHash15::~DoubleHash15() { + minlen=0; + clear(); + delete [] ary; +} + +/* __END__ */ |