source: tags/ms_r18q1/PROBE/PT_prefixtree.cxx

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