summaryrefslogtreecommitdiff
path: root/Build/source/utils/sam2p/mapping.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/utils/sam2p/mapping.cpp')
-rw-r--r--Build/source/utils/sam2p/mapping.cpp302
1 files changed, 0 insertions, 302 deletions
diff --git a/Build/source/utils/sam2p/mapping.cpp b/Build/source/utils/sam2p/mapping.cpp
deleted file mode 100644
index 118d6d32ef5..00000000000
--- a/Build/source/utils/sam2p/mapping.cpp
+++ /dev/null
@@ -1,302 +0,0 @@
-/*
- * mapping.cpp -- associative array implementations
- * by pts@fazekas.hu at Fri Mar 15 21:13:47 CET 2002
- */
-
-#ifdef __GNUC__
-#pragma implementation
-#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 */
- 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() {
- clear();
- delete [] ary;
-}
-
-/* __END__ */