source: branches/profile/PROBE/PT_prefixtree.cxx

Last change on this file was 11826, checked in by westram, 12 years ago
  • fix NULL ptr conversions
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 45.4 KB
Line 
1// =============================================================== //
2//                                                                 //
3//   File      : PT_prefixtree.cxx                                 //
4//   Purpose   :                                                   //
5//                                                                 //
6//   Institute of Microbiology (Technical University Munich)       //
7//   http://www.arb-home.de/                                       //
8//                                                                 //
9// =============================================================== //
10
11#include "probe.h"
12#include "probe_tree.h"
13#include "pt_prototypes.h"
14#include "PT_mem.h"
15
16#include <arb_file.h>
17
18#include <sys/types.h>
19#include <sys/mman.h>
20#include <climits>
21
22struct pt_global PT_GLOBAL;
23
24inline bool locs_in_chain_order(const AbsLoc& loc1, const AbsLoc& loc2) { 
25    if (loc1.get_name() > loc2.get_name()) {
26#if defined(DEBUG)
27        fprintf(stderr, "invalid chain: loc1.name>loc2.name (%i>%i)\n", loc1.get_name(), loc2.get_name());
28#endif
29        return false;
30    }
31    if (loc1.get_name() == loc2.get_name()) {
32        if (loc1.get_abs_pos() <= loc2.get_abs_pos()) {
33#if defined(DEBUG)
34            fprintf(stderr, "invalid chain: loc1.apos<=loc2.apos (%i<=%i)\n", loc1.get_abs_pos(), loc2.get_abs_pos());
35#endif
36            return false;
37        }
38    }
39    return true;
40}
41
42#if defined(PTM_DEBUG_VALIDATE_CHAINS)
43template <typename CHAINITER>
44inline bool PT_is_empty_chain(const typename CHAINITER::POS_TREE_TYPE * const node) { 
45    pt_assert(node->is_chain());
46    return !CHAINITER(node);
47}
48#endif
49
50template <typename CHAINITER>
51bool PT_chain_has_valid_entries(const typename CHAINITER::POS_TREE_TYPE * const node) {
52    pt_assert(node->is_chain());
53
54    bool ok = true;
55
56    CHAINITER entry(node);
57    if (!entry) return false;
58
59    AbsLoc last(entry.at());
60
61    ++entry;
62    while (entry && ok) {
63        ok   = locs_in_chain_order(last, entry.at());
64        last = entry.at();
65        ++entry;
66    }
67
68    return ok;
69}
70
71PT1_TYPE POS_TREE1::flag_2_type[256];
72PT2_TYPE POS_TREE2::flag_2_type[256];
73
74void POS_TREE1::init_static() {
75    for (int i=0; i<256; i++) {
76        if (i&0x80) { // bit 8 marks a node
77            flag_2_type[i] = PT1_NODE;
78        }
79        else if (i&0x20) { // in STAGE1 bit 6 is used to mark PT1_SAVED (in STAGE2 that bit may be used otherwise)
80            flag_2_type[i] = (i&0x40) ? PT1_UNDEF : PT1_SAVED;
81        }
82        else { // bit 7 distinguishes between chain and leaf
83            flag_2_type[i] = (i&0x40) ? PT1_CHAIN : PT1_LEAF;
84        }
85    }
86}
87void POS_TREE2::init_static() {
88    for (int i=0; i<256; i++) {
89        if (i&0x80) { // bit 8 marks a node
90            flag_2_type[i] = PT2_NODE;
91        }
92        else { // bit 7 distinguishes between chain and leaf
93            flag_2_type[i] = (i&0x40) ? PT2_CHAIN : PT2_LEAF;
94        }
95    }
96}
97
98void pt_global::init() {
99    POS_TREE1::init_static();
100    POS_TREE2::init_static();
101
102    for (unsigned base = PT_QU; base <= PT_BASES; base++) {
103        for (unsigned i=0; i<256; i++) {
104            unsigned h = 0xff >> (8-base);
105            h &= i;
106            unsigned count = 0;
107            for (unsigned j=0; j<8; j++) {
108                if (h&1) count++;
109                h = h>>1;
110            }
111            count_bits[base][i] = count;
112        }
113    }
114}
115
116void PT_init_cache_sizes(Stage stage) {
117    size_t species_count = psg.data_count;
118    pt_assert(species_count>0);
119
120#define CACHE_SEQ_PERCENT 50 // @@@ make global def and use in mem est.
121
122    if (stage == STAGE1) {
123        probe_input_data::set_cache_sizes(species_count*CACHE_SEQ_PERCENT/100+5, // cache about CACHE_SEQ_PERCENT% of seq data
124                                          1);                                    // don't cache - only need abspos of currently inserted species
125    }
126    else {
127        probe_input_data::set_cache_sizes(species_count, species_count); // cache all seq and positional data
128    }
129}
130
131void probe_struct_global::enter_stage(Stage stage_) {
132    stage = stage_;
133    PT_GLOBAL.init();
134    pt_assert(MEM.is_clear());
135}
136
137// ------------------------------
138//      functions for stage 1
139
140static void PT_change_link_in_father(POS_TREE1 *father, POS_TREE1 *old_link, POS_TREE1 *new_link) {
141    pt_assert_stage(STAGE1);
142    long i = PT_GLOBAL.count_bits[PT_BASES][father->flags]-1;
143    for (; i >= 0; i--) {
144        POS_TREE1 *link = PT_read_pointer<POS_TREE1>(father->udata()+sizeof(PT_PNTR)*i);
145        if (link==old_link) {
146            PT_write_pointer(father->udata()+sizeof(PT_PNTR)*i, new_link);
147            return;
148        }
149    }
150    pt_assert(0); // father did not contain 'old_link'
151}
152
153class ChainEntryBuffer : virtual Noncopyable {
154    const size_t size;
155    char *const  mem;
156    const int    refabspos;
157
158    char *write_pos;
159    int   lastname;
160
161    static const int MAXSIZEPERELEMENT = 2*5; // size for 2 compactNAT's
162public:
163    ChainEntryBuffer(int forElements, int refabspos_, int lastname_)
164        : size(forElements*MAXSIZEPERELEMENT),
165          mem((char*)MEM.get(size)),
166          refabspos(refabspos_),
167          write_pos(mem),
168          lastname(lastname_)
169    {}
170    ~ChainEntryBuffer() { MEM.put(mem, size); }
171
172    void add(const AbsLoc& loc) {
173        int namediff = loc.get_name()-lastname;
174        pt_assert(namediff >= 0);
175
176        uint_8 has_refabspos = (loc.get_abs_pos() == refabspos);
177        write_nat_with_reserved_bits<1>(write_pos, namediff, has_refabspos);
178        if (!has_refabspos) PT_write_compact_nat(write_pos, loc.get_abs_pos());
179
180        lastname = loc.get_name();
181    }
182
183    size_t get_size() const { return write_pos-mem; }
184    const char *get_mem() const { return mem; }
185    int get_refabspos() const { return refabspos; }
186    int get_lastname() const { return lastname; }
187};
188
189void PT_add_to_chain(POS_TREE1 *node, const DataLoc& loc) {
190    pt_assert_stage(STAGE1);
191#if defined(PTM_DEBUG_VALIDATE_CHAINS)
192    pt_assert(PT_is_empty_chain<ChainIteratorStage1>(node) ||
193              PT_chain_has_valid_entries<ChainIteratorStage1>(node));
194#endif
195
196    if (node->flags & SHORT_CHAIN_HEADER_FLAG_BIT) {
197        PT_short_chain_header *sheader = reinterpret_cast<PT_short_chain_header*>(node->udata());
198        int                    entries = node->flags & SHORT_CHAIN_HEADER_SIZE_MASK;
199
200        if (entries<SHORT_CHAIN_HEADER_ELEMS) { // store entries in header
201            sheader->name[entries]   = loc.get_name();
202            sheader->abspos[entries] = loc.get_abs_pos();
203
204            node->flags = (node->flags & (~SHORT_CHAIN_HEADER_SIZE_MASK)) | (entries+1);
205        }
206        else {
207            // short header is filled -> convert into long header
208            // @@@ detect most used abspos!
209            ChainEntryBuffer buf(entries+1, sheader->abspos[0], 0);
210
211            for (int e = 0; e<entries; ++e) {
212                buf.add(AbsLoc(sheader->name[e], sheader->abspos[e]));
213            }
214            buf.add(loc);
215
216            sheader                       = NULL; // no further access possible (is reused as lheader)
217            PT_long_chain_header *lheader = reinterpret_cast<PT_long_chain_header*>(node->udata());
218
219            lheader->entries   = entries+1;
220            lheader->memused   = buf.get_size();
221            lheader->memsize   = std::max(size_t(PTM_MIN_SIZE), buf.get_size());
222            lheader->refabspos = buf.get_refabspos();
223            lheader->lastname  = buf.get_lastname();
224            lheader->entrymem  = (char*)MEM.get(lheader->memsize);
225
226            memcpy(lheader->entrymem, buf.get_mem(), buf.get_size());
227
228            node->flags = (node->flags & ~(SHORT_CHAIN_HEADER_SIZE_MASK|SHORT_CHAIN_HEADER_FLAG_BIT));
229        }
230    }
231    else {
232        PT_long_chain_header *header = reinterpret_cast<PT_long_chain_header*>(node->udata());
233
234        ChainEntryBuffer buf(1, header->refabspos, header->lastname);
235        buf.add(loc);
236        header->lastname = buf.get_lastname();
237
238        unsigned memfree = header->memsize-header->memused;
239        if (memfree >= buf.get_size()) {
240            memcpy(header->entrymem+header->memused, buf.get_mem(), buf.get_size());
241        }
242        else {
243            unsigned new_memsize = header->memused+buf.get_size();
244
245            if (header->entries>10) new_memsize *= 1.25; // alloctate 25% more memory than needed // @@@ test with diff percentages
246
247            // @@@ check for better refabspos if memsize per entry is too high
248
249            char *new_mem = (char*)MEM.get(new_memsize);
250            memcpy(new_mem, header->entrymem, header->memused);
251            memcpy(new_mem+header->memused, buf.get_mem(), buf.get_size());
252
253            MEM.put(header->entrymem, header->memsize);
254
255            header->entrymem = new_mem;
256            header->memsize  = new_memsize;
257        }
258        header->memused += buf.get_size();
259        header->entries++;
260    }
261
262#if defined(PTM_DEBUG_VALIDATE_CHAINS)
263    pt_assert(!PT_is_empty_chain<ChainIteratorStage1>(node));
264    pt_assert(PT_chain_has_valid_entries<ChainIteratorStage1>(node));
265#endif
266}
267
268POS_TREE1 *PT_change_leaf_to_node(POS_TREE1 *node) { // @@@ become member
269    pt_assert_stage(STAGE1);
270    pt_assert(node->is_leaf());
271
272    POS_TREE1 *father = node->get_father();
273
274    POS_TREE1 *new_elem = (POS_TREE1 *)MEM.get(PT1_EMPTY_NODE_SIZE);
275    if (father) PT_change_link_in_father(father, node, new_elem);
276    MEM.put(node, PT1_LEAF_SIZE(node));
277    new_elem->set_type(PT1_NODE);
278    new_elem->set_father(father);
279
280    return new_elem;
281}
282
283POS_TREE1 *PT_leaf_to_chain(POS_TREE1 *node) { // @@@ become member
284    pt_assert_stage(STAGE1);
285    pt_assert(node->is_leaf());
286
287    POS_TREE1     *father = node->get_father();
288    const DataLoc  loc(node);
289
290    const size_t  chain_size = sizeof(POS_TREE1)+sizeof(PT_short_chain_header);
291    POS_TREE1    *new_elem   = (POS_TREE1 *)MEM.get(chain_size);
292
293    PT_change_link_in_father(father, node, new_elem);
294    MEM.put(node, PT1_LEAF_SIZE(node));
295
296    new_elem->set_type(PT1_CHAIN);
297    new_elem->set_father(father);
298
299    new_elem->flags |= SHORT_CHAIN_HEADER_FLAG_BIT; // "has short header"
300
301    pt_assert((new_elem->flags & SHORT_CHAIN_HEADER_SIZE_MASK) == 0); // zero elements
302
303    PT_add_to_chain(new_elem, loc);
304
305    return new_elem;
306}
307
308POS_TREE1 *PT_create_leaf(POS_TREE1 **pfather, PT_base base, const DataLoc& loc) {
309    pt_assert_stage(STAGE1);
310    pt_assert(base<PT_BASES);
311
312    int leafsize = PT1_EMPTY_LEAF_SIZE;
313
314    if (loc.get_rel_pos()>PT_SHORT_SIZE) leafsize += 2;
315    if (loc.get_abs_pos()>PT_SHORT_SIZE) leafsize += 2;
316    if (loc.get_name()   >PT_SHORT_SIZE) leafsize += 2;
317
318    POS_TREE1 *node = (POS_TREE1 *)MEM.get(leafsize);
319
320    pt_assert(node->get_father() == NULL); // cause memory is cleared
321
322    if (pfather) {
323        POS_TREE1 *father = *pfather;
324
325        int        oldfathersize  = PT1_NODE_SIZE(father);
326        POS_TREE1 *new_elemfather = (POS_TREE1 *)MEM.get(oldfathersize + sizeof(PT_PNTR));
327        new_elemfather->set_type(PT1_NODE);
328
329        POS_TREE1 *gfather = father->get_father();
330        if (gfather) {
331            PT_change_link_in_father(gfather, father, new_elemfather);
332            new_elemfather->set_father(gfather);
333        }
334
335        long sbase   = 0;
336        long dbase   = 0;
337        int  basebit = 1 << base;
338
339        pt_assert((father->flags&basebit) == 0); // son already exists!
340
341        for (int i = 1; i < (1<<FLAG_FREE_BITS); i = i << 1) {
342            if (i & father->flags) { // existing son
343                POS_TREE1 *son = PT_read_pointer<POS_TREE1>(father->udata()+sbase);
344                if (!son->is_saved()) son->set_father(new_elemfather);
345
346                PT_write_pointer(new_elemfather->udata()+dbase, son);
347
348                sbase += sizeof(PT_PNTR);
349                dbase += sizeof(PT_PNTR);
350            }
351            else if (i & basebit) { // newly created leaf
352                PT_write_pointer(new_elemfather->udata()+dbase, node);
353                node->set_father(new_elemfather);
354                dbase += sizeof(PT_PNTR);
355            }
356        }
357
358        new_elemfather->flags = father->flags | basebit;
359        MEM.put(father, oldfathersize);
360        *pfather = new_elemfather;
361    }
362    node->set_type(PT1_LEAF);
363
364    char *dest = node->udata();
365    if (loc.get_name()>PT_SHORT_SIZE) {
366        PT_write_int(dest, loc.get_name());
367        node->flags |= 1;
368        dest += 4;
369    }
370    else {
371        PT_write_short(dest, loc.get_name());
372        dest += 2;
373    }
374    if (loc.get_rel_pos()>PT_SHORT_SIZE) {
375        PT_write_int(dest, loc.get_rel_pos());
376        node->flags |= 2;
377        dest += 4;
378    }
379    else {
380        PT_write_short(dest, loc.get_rel_pos());
381        dest += 2;
382    }
383    if (loc.get_abs_pos()>PT_SHORT_SIZE) {
384        PT_write_int(dest, loc.get_abs_pos());
385        node->flags |= 4;
386        dest += 4;
387    }
388    else {
389        PT_write_short(dest, loc.get_abs_pos());
390        dest += 2;
391    }
392
393    return base == PT_QU ? PT_leaf_to_chain(node) : node;
394}
395
396// ------------------------------------
397//      functions for stage 1: save
398
399void POS_TREE1::clear_fathers() {
400    if (!is_saved()) {
401        set_father(NULL);
402        if (is_node()) {
403            for (int i = PT_QU; i < PT_BASES; i++) {
404                POS_TREE1 *son = PT_read_son(this, (PT_base)i);
405                if (son) son->clear_fathers();
406            }
407        }
408    }
409}
410
411#ifdef ARB_64
412void PTD_put_longlong(FILE *out, ULONG i) {
413    pt_assert(i == (unsigned long) i);
414    const size_t SIZE = 8;
415    STATIC_ASSERT(sizeof(uint_big) == SIZE); // this function only works and only gets called at 64-bit
416
417    unsigned char buf[SIZE];
418    PT_write_long(buf, i);
419    ASSERT_RESULT(size_t, SIZE, fwrite(buf, 1, SIZE, out));
420}
421#endif
422
423void PTD_put_int(FILE *out, ULONG i) {
424    pt_assert(i == (unsigned int) i);
425    const size_t SIZE = 4;
426#ifndef ARB_64
427    STATIC_ASSERT(sizeof(PT_PNTR) == SIZE); // in 32bit mode ints are used to store pointers
428#endif
429    unsigned char buf[SIZE];
430    PT_write_int(buf, i);
431    ASSERT_RESULT(size_t, SIZE, fwrite(buf, 1, SIZE, out));
432}
433
434void PTD_put_short(FILE *out, ULONG i) {
435    pt_assert(i == (unsigned short) i);
436    const size_t SIZE = 2;
437    unsigned char buf[SIZE];
438    PT_write_short(buf, i);
439    ASSERT_RESULT(size_t, SIZE, fwrite(buf, 1, SIZE, out));
440}
441
442void PTD_put_byte(FILE *out, ULONG i) {
443    pt_assert(i == (unsigned char) i);
444    unsigned char ch;
445    PT_write_char(&ch, i);
446    fputc(ch, out);
447}
448
449int PTD_put_compact_nat(FILE *out, uint_32 nat) {
450    // returns number of bytes written
451    const size_t MAXSIZE = 5;
452
453    char  buf[MAXSIZE];
454    char *bp = buf;
455
456    PT_write_compact_nat(bp, nat);
457    size_t size = bp-buf;
458    pt_assert(size <= MAXSIZE);
459    ASSERT_RESULT(size_t, size, fwrite(buf, 1, size, out));
460    return size;
461}
462
463const int BITS_FOR_SIZE = 4; // size is stored inside POS_TREEx->flags, if it fits into lower 4 bits
464const int SIZE_MASK     = (1<<BITS_FOR_SIZE)-1;
465
466STATIC_ASSERT(PT1_BASE_SIZE <= PT1_EMPTY_LEAF_SIZE);
467STATIC_ASSERT(PT1_BASE_SIZE <= PT1_CHAIN_SHORT_HEAD_SIZE);
468STATIC_ASSERT(PT1_BASE_SIZE <= PT1_EMPTY_NODE_SIZE);
469
470const uint_32 MIN_SIZE_IN_FLAGS = PT1_BASE_SIZE;
471const uint_32 MAX_SIZE_IN_FLAGS = PT1_BASE_SIZE+SIZE_MASK-1;
472
473const int FLAG_SIZE_REDUCTION = MIN_SIZE_IN_FLAGS-1;
474
475static void PTD_set_object_to_saved_status(POS_TREE1 *node, long pos_start, uint_32 former_size) {
476    pt_assert_stage(STAGE1);
477    node->flags = 0x20; // sets node type to PT1_SAVED; see PT_prefixtree.cxx@PT1_SAVED
478
479    char *no_father = (char*)(&node->father);
480
481    PT_write_big(no_father, pos_start);
482
483    pt_assert(former_size >= PT1_BASE_SIZE);
484
485    STATIC_ASSERT((MAX_SIZE_IN_FLAGS-MIN_SIZE_IN_FLAGS+1) == SIZE_MASK); // ????0000 means "size not stored in flags"
486
487    if (former_size >= MIN_SIZE_IN_FLAGS && former_size <= MAX_SIZE_IN_FLAGS) {
488        pt_assert(former_size >= int(sizeof(uint_big)));
489        node->flags |= former_size-FLAG_SIZE_REDUCTION;
490    }
491    else {
492        pt_assert(former_size >= int(sizeof(uint_big)+sizeof(int)));
493        PT_write_int(no_father+sizeof(uint_big), former_size);
494    }
495}
496
497inline int get_memsize_of_saved(const POS_TREE1 *node) {
498    int memsize = node->flags & SIZE_MASK;
499    if (memsize) {
500        memsize += FLAG_SIZE_REDUCTION;
501    }
502    else {
503        memsize = PT_read_int(node->udata());
504    }
505    return memsize;
506}
507
508static long PTD_write_tip_to_disk(FILE *out, POS_TREE1 *node, const long oldpos) {
509    fputc(node->flags, out);         // save type
510    int size = PT1_LEAF_SIZE(node);
511    // write 4 bytes when not in stage 2 save mode
512
513    size_t cnt = size-sizeof(PT_PNTR)-1;               // no father; type already saved
514    ASSERT_RESULT(size_t, cnt, fwrite(node->udata(), 1, cnt, out)); // write name rpos apos
515
516    long pos = oldpos+size-sizeof(PT_PNTR);                // no father
517    pt_assert(pos >= 0);
518    PTD_set_object_to_saved_status(node, oldpos, size);
519    return pos;
520}
521
522static long PTD_write_chain_to_disk(FILE *out, POS_TREE1 * const node, const long oldpos, ARB_ERROR& error) {
523    pt_assert_valid_chain_stage1(node);
524
525    long                pos          = oldpos;
526    ChainIteratorStage1 entry(node);
527    uint_32             chain_length = 1+entry.get_elements_ahead();
528
529    pt_assert(chain_length>0);
530
531    int    refabspos     = entry.get_refabspos(); // @@@ search for better apos?
532    uint_8 has_long_apos = refabspos>0xffff;
533
534    PTD_put_byte(out, (node->flags & 0xc0) | has_long_apos); // save type
535    pos++;
536
537    if (has_long_apos) { PTD_put_int  (out, refabspos); pos += 4; }
538    else               { PTD_put_short(out, refabspos); pos += 2; }
539
540    pos += PTD_put_compact_nat(out, chain_length);
541
542    ChainEntryBuffer buf(chain_length, refabspos, 0);
543    uint_32 entries  = 0;
544
545    while (entry && !error) {
546        const AbsLoc& loc = entry.at();
547        if (loc.get_name()<buf.get_lastname()) {
548            error = GBS_global_string("Chain Error: name order error (%i < %i)", loc.get_name(), buf.get_lastname());
549        }
550        else {
551            buf.add(loc);
552            ++entry;
553        }
554        ++entries;
555    }
556
557    if (buf.get_size() != fwrite(buf.get_mem(), 1, buf.get_size(), out)) {
558        error = GB_IO_error("writing chains to", "ptserver-index");
559    }
560    pos += buf.get_size();
561
562    pt_assert(entries == chain_length);
563    pt_assert(pos >= 0);
564
565    {
566        bool is_short        = node->flags&SHORT_CHAIN_HEADER_FLAG_BIT;
567        int  chain_head_size = sizeof(POS_TREE1)+(is_short ? sizeof(PT_short_chain_header) : sizeof(PT_long_chain_header));
568
569        if (!is_short) {
570            PT_long_chain_header *header = reinterpret_cast<PT_long_chain_header*>(node->udata());
571            MEM.put(header->entrymem, header->memsize);
572        }
573
574        PTD_set_object_to_saved_status(node, oldpos, chain_head_size);
575        pt_assert(node->is_saved());
576    }
577
578    return pos;
579}
580
581void PTD_debug_nodes() {
582    printf ("Inner Node Statistic:\n");
583    printf ("   Single Nodes:   %6i\n", psg.stat.single_node);
584    printf ("   Short  Nodes:   %6i\n", psg.stat.short_node);
585    printf ("       Chars:      %6i\n", psg.stat.chars);
586    printf ("       Shorts:     %6i\n", psg.stat.shorts2);
587
588#ifdef ARB_64
589    printf ("   Int    Nodes:   %6i\n", psg.stat.int_node);
590    printf ("       Shorts:     %6i\n", psg.stat.shorts);
591    printf ("       Ints:       %6i\n", psg.stat.ints2);
592#endif
593
594    printf ("   Long   Nodes:   %6i\n", psg.stat.long_node);
595#ifdef ARB_64
596    printf ("       Ints:       %6i\n", psg.stat.ints);
597#else   
598    printf ("       Shorts:     %6i\n", psg.stat.shorts);
599#endif
600    printf ("       Longs:      %6i\n", psg.stat.longs);
601
602#ifdef ARB_64
603    printf ("   maxdiff:        %6li\n", psg.stat.maxdiff);
604#endif
605}
606
607void PTD_delete_saved_node(POS_TREE1*& node) {
608    MEM.put(node, get_memsize_of_saved(node));
609    node = NULL;
610}
611
612static long PTD_write_node_to_disk(FILE *out, POS_TREE1 *node, long *r_poss, const long oldpos) {
613    // Save node after all descendends are already saved
614
615    pt_assert_stage(STAGE1);
616
617    long max_diff = 0;
618    int  lasti    = 0;
619    int  count    = 0;
620    int  size     = PT1_EMPTY_NODE_SIZE;
621    int  mysize   = PT1_EMPTY_NODE_SIZE;
622
623    for (int i = PT_QU; i < PT_BASES; i++) {    // free all sons
624        POS_TREE1 *son = PT_read_son(node, (PT_base)i);
625        if (son) {
626            long diff = oldpos - r_poss[i];
627            pt_assert(diff >= 0);
628            if (diff>max_diff) {
629                max_diff = diff;
630                lasti = i;
631#ifdef ARB_64
632                if (max_diff > psg.stat.maxdiff) {
633                    psg.stat.maxdiff = max_diff;
634                }
635#endif
636            }
637            mysize += sizeof(PT_PNTR);
638            if (!son->is_saved()) GBK_terminate("Internal Error: Son not saved");
639            MEM.put(son, get_memsize_of_saved(son));
640            count ++;
641        }
642    }
643    if ((count == 1) && (max_diff<=9) && (max_diff != 2)) { // nodesingle
644        if (max_diff>2) max_diff -= 2; else max_diff -= 1;
645        long flags = 0xc0 | lasti | (max_diff << 3);
646        fputc((int)flags, out);
647        psg.stat.single_node++;
648    }
649    else {                          // multinode
650        fputc(node->flags, out);
651        int flags2 = 0;
652        int level;
653#ifdef ARB_64
654        if (max_diff > 0xffffffff) {        // long node
655            printf("Warning: max_diff > 0xffffffff is not tested.\n");
656            flags2 |= 0x40;
657            level = 0xffffffff;
658            psg.stat.long_node++;
659        }
660        else if (max_diff > 0xffff) {       // int node
661            flags2 |= 0x80;
662            level = 0xffff;
663            psg.stat.int_node++;
664        }
665        else {                              // short node
666            level = 0xff;
667            psg.stat.short_node++;
668        }
669#else
670        if (max_diff > 0xffff) {
671            flags2 |= 0x80;
672            level = 0xffff;
673            psg.stat.long_node++;
674        }
675        else {
676            max_diff = 0;
677            level = 0xff;
678            psg.stat.short_node++;
679        }
680#endif
681        for (int i = PT_QU; i < PT_BASES; i++) {    // set the flag2
682            if (r_poss[i]) {
683                long diff = oldpos - r_poss[i];
684                pt_assert(diff >= 0);
685
686                if (diff>level) flags2 |= 1<<i;
687            }
688        }
689        fputc(flags2, out);
690        size++;
691        for (int i = PT_QU; i < PT_BASES; i++) {    // write the data
692            if (r_poss[i]) {
693                long diff = oldpos - r_poss[i];
694                pt_assert(diff >= 0);
695#ifdef ARB_64
696                if (max_diff > 0xffffffff) {        // long long / int  (bit[6] in flags2 is set; bit[7] is unset)
697                    printf("Warning: max_diff > 0xffffffff is not tested.\n");
698                    if (diff>level) {               // long long (64 bit)  (bit[i] in flags2 is set)
699                        PTD_put_longlong(out, diff);
700                        size += 8;
701                        psg.stat.longs++;
702                    }
703                    else {                          // int              (bit[i] in flags2 is unset)
704                        PTD_put_int(out, diff);
705                        size += 4;
706                        psg.stat.ints++;
707                    }
708                }
709                else if (max_diff > 0xffff) {       // int/short        (bit[6] in flags2 is unset; bit[7] is set)
710                    if (diff>level) {               // int              (bit[i] in flags2 is set)
711                        PTD_put_int(out, diff);
712                        size += 4;
713                        psg.stat.ints2++;
714                    }
715                    else {                          // short            (bit[i] in flags2 is unset)
716                        PTD_put_short(out, diff);
717                        size += 2;
718                        psg.stat.shorts++;
719                    }
720                }
721                else {                              // short/char       (bit[6] in flags2 is unset; bit[7] is unset)
722                    if (diff>level) {               // short            (bit[i] in flags2 is set)
723                        PTD_put_short(out, diff);
724                        size += 2;
725                        psg.stat.shorts2++;
726                    }
727                    else {                          // char             (bit[i] in flags2 is unset)
728                        PTD_put_byte(out, diff);
729                        size += 1;
730                        psg.stat.chars++;
731                    }
732                }
733#else
734                if (max_diff) {                     // int/short (bit[7] in flags2 set)
735                    if (diff>level) {               // int
736                        PTD_put_int(out, diff);
737                        size += 4;
738                        psg.stat.longs++;
739                    }
740                    else {                          // short
741                        PTD_put_short(out, diff);
742                        size += 2;
743                        psg.stat.shorts++;
744                    }
745                }
746                else {                              // short/char  (bit[7] in flags2 not set)
747                    if (diff>level) {               // short
748                        PTD_put_short(out, diff);
749                        size += 2;
750                        psg.stat.shorts2++;
751                    }
752                    else {                          // char
753                        PTD_put_byte(out, diff);
754                        size += 1;
755                        psg.stat.chars++;
756                    }
757                }
758#endif
759            }
760        }
761    }
762
763    long pos = oldpos+size-sizeof(PT_PNTR);                // no father
764    pt_assert(pos >= 0);
765    PTD_set_object_to_saved_status(node, oldpos, mysize);
766    return pos;
767}
768
769long PTD_write_leafs_to_disk(FILE *out, POS_TREE1 * const node, long pos, long *node_pos, ARB_ERROR& error) { 
770    // returns new position in index-file (unchanged for type PT1_SAVED)
771    // *node_pos is set to the start-position of the most recent object written
772
773    pt_assert_stage(STAGE1);
774
775    switch (node->get_type()) {
776        case PT1_SAVED:
777            *node_pos = PT_read_big(&node->father);
778            break;
779
780        case PT1_LEAF:
781            *node_pos = pos;
782            pos       = PTD_write_tip_to_disk(out, node, pos);
783            break;
784
785        case PT1_CHAIN:
786            *node_pos = pos;
787            pos       = PTD_write_chain_to_disk(out, node, pos, error);
788            pt_assert(node->is_saved());
789            break;
790
791        case PT1_NODE: {
792            long son_pos[PT_BASES];
793            for (int i = PT_QU; i < PT_BASES && !error; i++) { // save all sons
794                POS_TREE1 *son = PT_read_son(node, (PT_base)i);
795                son_pos[i] = 0;
796                if (son) {
797                    pos = PTD_write_leafs_to_disk(out, son, pos, &(son_pos[i]), error);
798                    pt_assert(son->is_saved());
799                }
800            }
801
802            if (!error) {
803                *node_pos = pos;
804                pos = PTD_write_node_to_disk(out, node, son_pos, pos);
805            }
806            break;
807        }
808        case PT1_UNDEF:
809            pt_assert(0);
810            break;
811    }
812
813    pt_assert(error || node->is_saved());
814    return pos;
815}
816
817ARB_ERROR PTD_read_leafs_from_disk(const char *fname, POS_TREE2*& root_ptr) { // __ATTR__USERESULT
818    pt_assert_stage(STAGE2);
819
820    GB_ERROR  error  = NULL;
821    char     *buffer = GB_map_file(fname, 0);
822
823    if (!buffer) {
824        error = GBS_global_string("mmap failed (%s)", GB_await_error());
825    }
826    else {
827        long  size = GB_size_of_file(fname);
828        char *main = &(buffer[size-4]);
829
830        psg.big_db = false;
831
832        long i = PT_read_int(main);
833#ifdef ARB_64
834        if (i == 0xffffffff) {                    // 0xffffffff signalizes that "last_obj" is stored
835            main -= 8;                            // in the previous 8 byte (in a long long)
836            STATIC_ASSERT(sizeof(PT_PNTR) == 8);  // 0xffffffff is used to signalize to be compatible with older pt-servers
837            i      = PT_read_big(main);           // this search tree can only be loaded at 64 Bit
838            psg.big_db = true;
839        }
840#else
841        if (i<0) {
842            pt_assert(i == -1);                     // aka 0xffffffff
843            psg.big_db = true;                          // not usable in 32-bit version (fails below)
844        }
845        pt_assert(i <= INT_MAX);
846#endif
847
848        // try to find info_area
849        main -= 2;
850
851        short info_size = PT_read_short(main);
852
853#ifndef ARB_64
854        bool info_detected = false;
855#endif
856
857        if (info_size>0 && info_size<(main-buffer)) {   // otherwise impossible size
858            main -= info_size;
859
860            long magic   = PT_read_int(main); main += 4;
861            int  version = PT_read_char(main); main++;
862
863            pt_assert(PT_SERVER_MAGIC>0 && PT_SERVER_MAGIC<INT_MAX);
864
865            if (magic == PT_SERVER_MAGIC) {
866#ifndef ARB_64
867                info_detected = true;
868#endif
869                if (version != PT_SERVER_VERSION) {
870                    error = "PT-server database has different version (rebuild necessary)";
871                }
872            }
873        }
874
875#ifndef ARB_64
876        // 32bit version:
877        if (!error && psg.big_db) {
878            error = "PT-server database can only be used with 64bit-PT-Server";
879        }
880        if (!error && !info_detected) {
881            printf("Warning: ptserver DB has old format (no problem)\n");
882        }
883#endif
884
885        if (!error) {
886            pt_assert(i >= 0);
887            root_ptr  = (POS_TREE2*)(i+buffer);
888        }
889    }
890
891    return error;
892}
893
894// --------------------------------------------------------------------------------
895
896#if defined(PTM_MEM_DUMP_STATS)
897const char *get_blocksize_description(int blocksize) {
898    const char *known = NULL;
899    switch (blocksize) {
900        case PT1_EMPTY_NODE_SIZE:       known = "PT1_EMPTY_NODE_SIZE"; break;
901        case PT1_MIN_CHAIN_ENTRY_SIZE:  known = "PT1_MIN_CHAIN_ENTRY_SIZE"; break;
902        case PT1_MAX_CHAIN_ENTRY_SIZE:  known = "PT1_MAX_CHAIN_ENTRY_SIZE"; break;
903#if defined(ARB_64)
904        case PT1_EMPTY_LEAF_SIZE:       known = "PT1_EMPTY_LEAF_SIZE"; break;
905        case PT1_CHAIN_SHORT_HEAD_SIZE: known = "PT1_CHAIN_SHORT_HEAD_SIZE"; break;
906        case PT1_CHAIN_LONG_HEAD_SIZE:  known = "PT1_CHAIN_LONG_HEAD_SIZE"; break;
907        case PT1_NODE_WITHSONS_SIZE(2): known = "PT1_NODE_WITHSONS_SIZE(2)"; break;
908#else // 32bit:
909        case PT1_EMPTY_LEAF_SIZE:       known = "PT1_EMPTY_LEAF_SIZE      and PT1_CHAIN_SHORT_HEAD_SIZE"; break;
910        case PT1_NODE_WITHSONS_SIZE(2): known = "PT1_NODE_WITHSONS_SIZE(2) and PT1_CHAIN_LONG_HEAD_SIZE"; break;
911
912        STATIC_ASSERT(PT1_CHAIN_SHORT_HEAD_SIZE == PT1_EMPTY_LEAF_SIZE);
913        STATIC_ASSERT(PT1_CHAIN_LONG_HEAD_SIZE == PT1_NODE_WITHSONS_SIZE(2));
914#endif
915        case PT1_NODE_WITHSONS_SIZE(1): known = "PT1_NODE_WITHSONS_SIZE(1)"; break;
916        case PT1_NODE_WITHSONS_SIZE(3): known = "PT1_NODE_WITHSONS_SIZE(3)"; break;
917        case PT1_NODE_WITHSONS_SIZE(4): known = "PT1_NODE_WITHSONS_SIZE(4)"; break;
918        case PT1_NODE_WITHSONS_SIZE(5): known = "PT1_NODE_WITHSONS_SIZE(5)"; break;
919        case PT1_NODE_WITHSONS_SIZE(6): known = "PT1_NODE_WITHSONS_SIZE(6)"; break;
920    }
921    return known;
922}
923#endif
924
925// --------------------------------------------------------------------------------
926
927#ifdef UNIT_TESTS
928#ifndef TEST_UNIT_H
929#include <test_unit.h>
930#endif
931
932static arb_test::match_expectation has_proper_saved_state(POS_TREE1 *node, int size, bool expect_in_flags) {
933    using namespace arb_test;
934
935    uint_32 unmodified = 0xffffffff;
936    PT_write_int(node->udata(), unmodified);
937
938    PTD_set_object_to_saved_status(node, 0, size);
939
940    expectation_group expected;
941    expected.add(that(node->get_type()).is_equal_to(PT1_SAVED));
942    expected.add(that(get_memsize_of_saved(node)).is_equal_to(size));
943
944    uint_32 data_after = PT_read_int(node->udata());
945
946    if (expect_in_flags) {
947        expected.add(that(data_after).is_equal_to(unmodified));
948    }
949    else {
950        expected.add(that(data_after).does_differ_from(unmodified));
951    }
952
953    return all().ofgroup(expected);
954}
955
956#define TEST_SIZE_SAVED_IN_FLAGS(pt,size)         TEST_EXPECTATION(has_proper_saved_state(pt,size,true))
957#define TEST_SIZE_SAVED_EXTERNAL(pt,size)         TEST_EXPECTATION(has_proper_saved_state(pt,size,false))
958#define TEST_SIZE_SAVED_IN_FLAGS__BROKEN(pt,size) TEST_EXPECTATION__BROKEN(has_proper_saved_state(pt,size,true))
959#define TEST_SIZE_SAVED_EXTERNAL__BROKEN(pt,size) TEST_EXPECTATION__BROKEN(has_proper_saved_state(pt,size,false))
960
961struct EnterStage1 {
962    static bool initialized;
963    EnterStage1() {
964        if (initialized) PT_exit_psg();
965        PT_init_psg();
966        psg.enter_stage(STAGE1);
967        initialized = true;
968    }
969    ~EnterStage1() {
970        pt_assert(initialized);
971        PT_exit_psg();
972        initialized = false;
973    }
974};
975bool EnterStage1::initialized = false;
976
977void TEST_saved_state() {
978    EnterStage1 env;
979
980    const size_t SIZE = PT1_BASE_SIZE+6;
981    STATIC_ASSERT(SIZE >= (1+sizeof(uint_big)+sizeof(int)));
982
983    POS_TREE1 *node = (POS_TREE1*)malloc(SIZE);
984
985    TEST_SIZE_SAVED_IN_FLAGS(node, PT1_BASE_SIZE);
986
987    TEST_SIZE_SAVED_IN_FLAGS(node, MIN_SIZE_IN_FLAGS);
988    TEST_SIZE_SAVED_IN_FLAGS(node, MAX_SIZE_IN_FLAGS);
989
990    TEST_SIZE_SAVED_EXTERNAL(node, 5000);
991    TEST_SIZE_SAVED_EXTERNAL(node, 40);
992
993#ifdef ARB_64
994    TEST_SIZE_SAVED_EXTERNAL(node, 24);
995    TEST_SIZE_SAVED_IN_FLAGS(node, 23);
996#else
997    TEST_SIZE_SAVED_EXTERNAL(node, 20);
998    TEST_SIZE_SAVED_IN_FLAGS(node, 19);
999#endif
1000
1001    TEST_SIZE_SAVED_IN_FLAGS(node, 10);
1002    TEST_SIZE_SAVED_IN_FLAGS(node, 9);
1003
1004#ifdef ARB_64
1005    STATIC_ASSERT(PT1_BASE_SIZE == 9);
1006#else
1007    TEST_SIZE_SAVED_IN_FLAGS(node, 8);
1008    TEST_SIZE_SAVED_IN_FLAGS(node, 7);
1009    TEST_SIZE_SAVED_IN_FLAGS(node, 6);
1010    TEST_SIZE_SAVED_IN_FLAGS(node, 5);
1011
1012    STATIC_ASSERT(PT1_BASE_SIZE == 5);
1013#endif
1014
1015    free(node);
1016}
1017
1018#if defined(ENABLE_CRASH_TESTS)
1019// # define TEST_BAD_CHAINS // TEST_chains fails in PTD_save_partial_tree if uncommented (as expected)
1020#endif
1021
1022#if defined(TEST_BAD_CHAINS)
1023
1024static POS_TREE1 *theChain = NULL;
1025static DataLoc   *theLoc   = NULL;
1026
1027static void bad_add_to_chain() {
1028    PT_add_to_chain(theChain, *theLoc);
1029#if !defined(PTM_DEBUG_VALIDATE_CHAINS)
1030    pt_assert(PT_chain_has_valid_entries<ChainIteratorStage1>(theChain));
1031#endif
1032    theChain = NULL;
1033    theLoc   = NULL;
1034}
1035#endif
1036
1037void TEST_chains() {
1038    EnterStage1 env;
1039    psg.data_count = 3;
1040
1041    POS_TREE1 *root = PT_create_leaf(NULL, PT_N, DataLoc(0, 0, 0));
1042    TEST_EXPECT_EQUAL(root->get_type(), PT1_LEAF);
1043
1044    root = PT_change_leaf_to_node(root);
1045    TEST_EXPECT_EQUAL(root->get_type(), PT1_NODE);
1046
1047    DataLoc loc0a(0, 500, 500);
1048    DataLoc loc0b(0, 555, 555);
1049
1050    DataLoc loc1a(1, 200, 200);
1051    DataLoc loc1b(1, 500, 500);
1052
1053    DataLoc loc2a(2, 300, 300);
1054    DataLoc loc2b(2, 700, 700);
1055    DataLoc loc2c(2, 701, 701);
1056
1057    for (int base = PT_A; base <= PT_G; ++base) {
1058        POS_TREE1 *leaf = PT_create_leaf(&root, PT_base(base), loc0b);
1059        TEST_EXPECT_EQUAL(leaf->get_type(), PT1_LEAF);
1060
1061        POS_TREE1 *chain = PT_leaf_to_chain(leaf);
1062        TEST_EXPECT_EQUAL(chain->get_type(), PT1_CHAIN);
1063        TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1064
1065        PT_add_to_chain(chain, loc0a); TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1066        PT_add_to_chain(chain, loc1b); TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1067        PT_add_to_chain(chain, loc1a); TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1068        PT_add_to_chain(chain, loc2c); TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1069        PT_add_to_chain(chain, loc2b); TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1070        PT_add_to_chain(chain, loc2a); TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1071
1072        // now chain is 'loc0b,loc0a,loc1b,loc1a,loc2b,loc2a'
1073
1074        if (base == PT_A) { // test only once
1075            ChainIteratorStage1 entry(chain);
1076
1077            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc0b); ++entry;
1078            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc0a); ++entry;
1079            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc1b); ++entry;
1080            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc1a); ++entry;
1081            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc2c); ++entry;
1082            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc2b); ++entry;
1083            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc2a); ++entry;
1084            TEST_EXPECT_EQUAL(bool(entry), false);
1085        }
1086
1087#if defined(TEST_BAD_CHAINS)
1088        // out-of-date
1089        switch (base) {
1090            case PT_A: theChain = chain; theLoc = &loc2a; TEST_EXPECT_CODE_ASSERTION_FAILS(bad_add_to_chain); break; // add same location twice -> fail
1091            case PT_C: theChain = chain; theLoc = &loc1b; TEST_EXPECT_CODE_ASSERTION_FAILS(bad_add_to_chain); break; // add species in wrong order -> fail
1092            case PT_G: theChain = chain; theLoc = &loc2b; TEST_EXPECT_CODE_ASSERTION_FAILS(bad_add_to_chain); break; // add positions in wrong order (should fail)
1093            default: TEST_EXPECT(0); break;
1094        }
1095#endif
1096    }
1097    {
1098        POS_TREE1 *leaf = PT_create_leaf(&root, PT_QU, loc1a); // PT_QU always produces chain
1099        TEST_EXPECT_EQUAL(leaf->get_type(), PT1_CHAIN);
1100    }
1101
1102    // since there is no explicit code to free POS_TREE-memory, spool it into /dev/null
1103    {
1104        FILE      *out = fopen("/dev/null", "wb");
1105        ARB_ERROR  error;
1106        long       root_pos;
1107
1108        long pos = PTD_save_lower_tree(out, root, 0, error);
1109        pos      = PTD_save_upper_tree(out, root, pos, root_pos, error);
1110
1111        TEST_EXPECT_NO_ERROR(error.deliver());
1112        TEST_EXPECTATION(all().of(that(root_pos).is_equal_to(74), that(pos).is_equal_to(79)));
1113        TEST_EXPECT_NULL(root); // nulled by PTD_save_upper_tree
1114
1115        fclose(out);
1116    }
1117}
1118
1119void TEST_mem() {
1120    EnterStage1 env;
1121
1122#if defined(PTM_MEM_DUMP_STATS)
1123    MEM.dump_stats(false);
1124#endif
1125
1126    const int  MAXSIZE = 1024;
1127    char      *ptr[MAXSIZE+1];
1128
1129    for (int size = PTM_MIN_SIZE; size <= MAXSIZE; ++size) {
1130        ptr[size] = (char*)MEM.get(size);
1131    }
1132    for (int size = PTM_MIN_SIZE; size <= MAXSIZE; ++size) {
1133#if defined(PTM_MEM_CHECKED_FREE)
1134        if (size <= PTM_MAX_SIZE) {
1135            TEST_EXPECT_EQUAL(MEM.block_has_size(ptr[size], size), true);
1136        }
1137#endif
1138        MEM.put(ptr[size], size);
1139    }
1140
1141    MEM.clear();
1142#if defined(PTM_MEM_DUMP_STATS)
1143    MEM.dump_stats(true);
1144#endif
1145
1146}
1147
1148template<int R>
1149static arb_test::match_expectation nat_stored_as_expected(uint_32 written_nat, int expected_bytes) {
1150    char buffer[5];
1151
1152    static uint_8 reserved_bits = 0;
1153
1154    reserved_bits = (reserved_bits+1) & BitsBelowBit<R>::value;
1155    uint_8 reserved_bits_read;
1156
1157    char       *wp = buffer;
1158    const char *rp = buffer;
1159
1160    write_nat_with_reserved_bits<R>(wp, written_nat, reserved_bits);
1161    uint_32 read_nat = read_nat_with_reserved_bits<R>(rp, reserved_bits_read);
1162
1163    int written_bytes = wp-buffer;
1164    int read_bytes    = rp-buffer;
1165
1166    using namespace   arb_test;
1167    expectation_group expected;
1168    expected.add(that(read_nat).is_equal_to(written_nat));
1169    expected.add(that(written_bytes).is_equal_to(expected_bytes));
1170    expected.add(that(read_bytes).is_equal_to(written_bytes));
1171    expected.add(that(reserved_bits_read).is_equal_to(reserved_bits));
1172
1173    return all().ofgroup(expected);
1174}
1175
1176template<int R>
1177static arb_test::match_expectation int_stored_as_expected(int32_t written_int, int expected_bytes) {
1178    char buffer[5];
1179
1180    static uint_8 reserved_bits = 0;
1181
1182    reserved_bits = (reserved_bits+1) & BitsBelowBit<R>::value;
1183    uint_8 reserved_bits_read;
1184
1185    char       *wp = buffer;
1186    const char *rp = buffer;
1187
1188    write_int_with_reserved_bits<R>(wp, written_int, reserved_bits);
1189    int32_t read_int = read_int_with_reserved_bits<R>(rp, reserved_bits_read);
1190
1191    int written_bytes = wp-buffer;
1192    int read_bytes    = rp-buffer;
1193
1194    using namespace   arb_test;
1195    expectation_group expected;
1196    expected.add(that(read_int).is_equal_to(written_int));
1197    expected.add(that(written_bytes).is_equal_to(expected_bytes));
1198    expected.add(that(read_bytes).is_equal_to(written_bytes));
1199    expected.add(that(reserved_bits_read).is_equal_to(reserved_bits));
1200
1201    return all().ofgroup(expected);
1202}
1203
1204
1205#define TEST_COMPACT_NAT_STORAGE(nat,inBytes)          TEST_EXPECTATION(nat_stored_as_expected<0>(nat, inBytes))
1206#define TEST_COMPACT_NAT_STORAGE_RESERVE1(nat,inBytes) TEST_EXPECTATION(nat_stored_as_expected<1>(nat, inBytes))
1207#define TEST_COMPACT_NAT_STORAGE_RESERVE2(nat,inBytes) TEST_EXPECTATION(nat_stored_as_expected<2>(nat, inBytes))
1208#define TEST_COMPACT_NAT_STORAGE_RESERVE3(nat,inBytes) TEST_EXPECTATION(nat_stored_as_expected<3>(nat, inBytes))
1209#define TEST_COMPACT_NAT_STORAGE_RESERVE4(nat,inBytes) TEST_EXPECTATION(nat_stored_as_expected<4>(nat, inBytes))
1210#define TEST_COMPACT_NAT_STORAGE_RESERVE5(nat,inBytes) TEST_EXPECTATION(nat_stored_as_expected<5>(nat, inBytes))
1211
1212#define TEST_COMPACT_INT_STORAGE(i,inBytes)          TEST_EXPECTATION(int_stored_as_expected<0>(i, inBytes))
1213#define TEST_COMPACT_INT_STORAGE_RESERVE3(i,inBytes) TEST_EXPECTATION(int_stored_as_expected<3>(i, inBytes))
1214
1215void TEST_compact_storage() {
1216    // test natural numbers (w/o reserved bits)
1217
1218    TEST_COMPACT_NAT_STORAGE(0, 1);
1219    TEST_COMPACT_NAT_STORAGE(0x7f, 1);
1220
1221    TEST_COMPACT_NAT_STORAGE(0x80, 2);
1222    TEST_COMPACT_NAT_STORAGE(0x407F, 2);
1223
1224    TEST_COMPACT_NAT_STORAGE(0x4080, 3);
1225    TEST_COMPACT_NAT_STORAGE(0x20407F, 3);
1226
1227    TEST_COMPACT_NAT_STORAGE(0x204080, 4);
1228    TEST_COMPACT_NAT_STORAGE(0x1020407F, 4);
1229
1230    TEST_COMPACT_NAT_STORAGE(0x10204080, 5);
1231    TEST_COMPACT_NAT_STORAGE(0xffffffff, 5);
1232
1233    // test 1 reserved bit (bit7 is reserved)
1234    TEST_COMPACT_NAT_STORAGE_RESERVE1(0, 1);
1235    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x3f, 1);
1236
1237    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x40, 2);
1238    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x203f, 2);
1239
1240    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x2040, 3);
1241    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x10203f, 3);
1242
1243    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x102040, 4);
1244    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x0810203f, 4);
1245
1246    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x08102040, 5);
1247    TEST_COMPACT_NAT_STORAGE_RESERVE1(0xffffffff, 5);
1248
1249    // test integers (same as natural numbers with 1 bit reserved for sign)
1250    TEST_COMPACT_INT_STORAGE( 0, 1);
1251    TEST_COMPACT_INT_STORAGE( 0x3f, 1);
1252    TEST_COMPACT_INT_STORAGE(-0x40, 1);
1253
1254    TEST_COMPACT_INT_STORAGE( 0x40, 2);
1255    TEST_COMPACT_INT_STORAGE(-0x41, 2);
1256    TEST_COMPACT_INT_STORAGE( 0x203f, 2);
1257    TEST_COMPACT_INT_STORAGE(-0x2040, 2);
1258
1259    TEST_COMPACT_INT_STORAGE( 0x2040, 3);
1260    TEST_COMPACT_INT_STORAGE(-0x2041, 3);
1261    TEST_COMPACT_INT_STORAGE( 0x10203f, 3);
1262    TEST_COMPACT_INT_STORAGE(-0x102040, 3);
1263
1264    TEST_COMPACT_INT_STORAGE( 0x102040, 4);
1265    TEST_COMPACT_INT_STORAGE(-0x102041, 4);
1266    TEST_COMPACT_INT_STORAGE( 0x0810203f, 4);
1267    TEST_COMPACT_INT_STORAGE(-0x08102040, 4);
1268
1269    TEST_COMPACT_INT_STORAGE( 0x08102040, 5);
1270    TEST_COMPACT_INT_STORAGE(-0x08102041, 5);
1271    TEST_COMPACT_INT_STORAGE(INT_MAX, 5);
1272    TEST_COMPACT_INT_STORAGE(INT_MIN, 5);
1273
1274    // test 2 reserved bits (bit7 and bit6 are reserved)
1275    TEST_COMPACT_NAT_STORAGE_RESERVE2(0, 1);
1276    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x1f, 1);
1277
1278    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x20, 2);
1279    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x101f, 2);
1280
1281    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x1020, 3);
1282    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x08101f, 3);
1283
1284    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x081020, 4);
1285    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x0408101f, 4);
1286
1287    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x04081020, 5);
1288    TEST_COMPACT_NAT_STORAGE_RESERVE2(0xffffffff, 5);
1289
1290    // test 3 reserved bits (bit7 .. bit5 are reserved)
1291    TEST_COMPACT_NAT_STORAGE_RESERVE3(0, 1);
1292    TEST_COMPACT_NAT_STORAGE_RESERVE3(0xf, 1);
1293
1294    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x10, 2);
1295    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x080f, 2);
1296
1297    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x0810, 3);
1298    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x04080f, 3);
1299
1300    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x040810, 4);
1301    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x0204080f, 4);
1302
1303    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x02040810, 5);
1304    TEST_COMPACT_NAT_STORAGE_RESERVE3(0xffffffff, 5);
1305
1306    // test 4 reserved bits (bit7 .. bit4 are reserved)
1307    TEST_COMPACT_NAT_STORAGE_RESERVE4(0, 1);
1308    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x07, 1);
1309
1310    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x08, 2);
1311    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x0407, 2);
1312
1313    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x0408, 3);
1314    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x020407, 3);
1315
1316    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x020408, 4);
1317    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x01020407, 4);
1318
1319    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x01020408, 5);
1320    TEST_COMPACT_NAT_STORAGE_RESERVE4(0xffffffff, 5);
1321
1322    // test integers with 3 reserved bits
1323    TEST_COMPACT_INT_STORAGE_RESERVE3( 0, 1);
1324    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x07, 1);
1325    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x08, 1);
1326
1327    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x08, 2);
1328    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x09, 2);
1329    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x0407, 2);
1330    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x0408, 2);
1331
1332    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x0408, 3);
1333    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x0409, 3);
1334    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x020407, 3);
1335    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x020408, 3);
1336
1337    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x020408, 4);
1338    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x020409, 4);
1339    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x01020407, 4);
1340    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x01020408, 4);
1341
1342    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x01020408, 5);
1343    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x01020409, 5);
1344    TEST_COMPACT_INT_STORAGE_RESERVE3(INT_MAX, 5);
1345    TEST_COMPACT_INT_STORAGE_RESERVE3(INT_MIN, 5);
1346
1347#if 0
1348    // reserving more than 4 bits does not work (compacting also uses 4 bits)
1349    // (compiles, but spits warnings)
1350    TEST_COMPACT_NAT_STORAGE_RESERVE5(0, 1);
1351#endif
1352}
1353
1354#endif // UNIT_TESTS
1355
1356// --------------------------------------------------------------------------------
Note: See TracBrowser for help on using the repository browser.