source: trunk/PROBE/PT_prefixtree.cxx

Last change on this file was 18730, checked in by westram, 4 years ago
  • remove trailing whitespace from c source.
  • 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
459static int 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 += 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
591#if defined(PTM_DEBUG_NODES)
592void PTD_debug_nodes() {
593    printf ("Inner Node Statistic:\n");
594    printf ("   Single Nodes:   %6i\n", psg.stat.single_node);
595    printf ("   Short  Nodes:   %6i\n", psg.stat.short_node);
596    printf ("       Chars:      %6i\n", psg.stat.chars);
597    printf ("       Shorts:     %6i\n", psg.stat.shorts2);
598
599#ifdef ARB_64
600    printf ("   Int    Nodes:   %6i\n", psg.stat.int_node);
601    printf ("       Shorts:     %6i\n", psg.stat.shorts);
602    printf ("       Ints:       %6i\n", psg.stat.ints2);
603#endif
604
605    printf ("   Long   Nodes:   %6i\n", psg.stat.long_node);
606#ifdef ARB_64
607    printf ("       Ints:       %6i\n", psg.stat.ints);
608#else
609    printf ("       Shorts:     %6i\n", psg.stat.shorts);
610#endif
611    printf ("       Longs:      %6i\n", psg.stat.longs);
612
613#ifdef ARB_64
614    printf ("   maxdiff:        %6li\n", psg.stat.maxdiff);
615#endif
616}
617#endif
618
619void PTD_delete_saved_node(POS_TREE1*& node) {
620    MEM.put(node, get_memsize_of_saved(node));
621    node = NULp;
622}
623
624static long PTD_write_node_to_disk(FILE *out, POS_TREE1 *node, long *r_poss, const long oldpos) {
625    // Save node after all descendends are already saved
626
627    pt_assert_stage(STAGE1);
628
629    long max_diff = 0;
630    int  lasti    = 0;
631    int  count    = 0;
632    int  size     = PT1_EMPTY_NODE_SIZE;
633    int  mysize   = PT1_EMPTY_NODE_SIZE;
634
635    for (int i = PT_QU; i < PT_BASES; i++) {    // free all sons
636        POS_TREE1 *son = PT_read_son(node, (PT_base)i);
637        if (son) {
638            long diff = oldpos - r_poss[i];
639            pt_assert(diff >= 0);
640            if (diff>max_diff) {
641                max_diff = diff;
642                lasti = i;
643#ifdef ARB_64
644                if (max_diff > psg.stat.maxdiff) {
645                    psg.stat.maxdiff = max_diff;
646                }
647#endif
648            }
649            mysize += sizeof(PT_PNTR);
650            if (!son->is_saved()) GBK_terminate("Internal Error: Son not saved");
651            MEM.put(son, get_memsize_of_saved(son));
652            count ++;
653        }
654    }
655    if ((count == 1) && (max_diff<=9) && (max_diff != 2)) { // nodesingle
656        if (max_diff>2) max_diff -= 2; else max_diff -= 1;
657        long flags = 0xc0 | lasti | (max_diff << 3);
658        fputc((int)flags, out);
659        psg.stat.single_node++;
660    }
661    else {                          // multinode
662        fputc(node->flags, out);
663        int flags2 = 0;
664        int level;
665#ifdef ARB_64
666        if (max_diff > 0xffffffff) {        // long node
667            printf("Warning: max_diff > 0xffffffff is not tested.\n");
668            flags2 |= 0x40;
669            level = 0xffffffff;
670            psg.stat.long_node++;
671        }
672        else if (max_diff > 0xffff) {       // int node
673            flags2 |= 0x80;
674            level = 0xffff;
675            psg.stat.int_node++;
676        }
677        else {                              // short node
678            level = 0xff;
679            psg.stat.short_node++;
680        }
681#else
682        if (max_diff > 0xffff) {
683            flags2 |= 0x80;
684            level = 0xffff;
685            psg.stat.long_node++;
686        }
687        else {
688            max_diff = 0;
689            level = 0xff;
690            psg.stat.short_node++;
691        }
692#endif
693        for (int i = PT_QU; i < PT_BASES; i++) {    // set the flag2
694            if (r_poss[i]) {
695                long diff = oldpos - r_poss[i];
696                pt_assert(diff >= 0);
697
698                if (diff>level) flags2 |= 1<<i;
699            }
700        }
701        fputc(flags2, out);
702        size++;
703        for (int i = PT_QU; i < PT_BASES; i++) {    // write the data
704            if (r_poss[i]) {
705                long diff = oldpos - r_poss[i];
706                pt_assert(diff >= 0);
707#ifdef ARB_64
708                if (max_diff > 0xffffffff) {        // long long / int  (bit[6] in flags2 is set; bit[7] is unset)
709                    printf("Warning: max_diff > 0xffffffff is not tested.\n");
710                    if (diff>level) {               // long long (64 bit)  (bit[i] in flags2 is set)
711                        PTD_put_longlong(out, diff);
712                        size += 8;
713                        psg.stat.longs++;
714                    }
715                    else {                          // int              (bit[i] in flags2 is unset)
716                        PTD_put_int(out, diff);
717                        size += 4;
718                        psg.stat.ints++;
719                    }
720                }
721                else if (max_diff > 0xffff) {       // int/short        (bit[6] in flags2 is unset; bit[7] is set)
722                    if (diff>level) {               // int              (bit[i] in flags2 is set)
723                        PTD_put_int(out, diff);
724                        size += 4;
725                        psg.stat.ints2++;
726                    }
727                    else {                          // short            (bit[i] in flags2 is unset)
728                        PTD_put_short(out, diff);
729                        size += 2;
730                        psg.stat.shorts++;
731                    }
732                }
733                else {                              // short/char       (bit[6] in flags2 is unset; bit[7] is unset)
734                    if (diff>level) {               // short            (bit[i] in flags2 is set)
735                        PTD_put_short(out, diff);
736                        size += 2;
737                        psg.stat.shorts2++;
738                    }
739                    else {                          // char             (bit[i] in flags2 is unset)
740                        PTD_put_byte(out, diff);
741                        size += 1;
742                        psg.stat.chars++;
743                    }
744                }
745#else
746                if (max_diff) {                     // int/short (bit[7] in flags2 set)
747                    if (diff>level) {               // int
748                        PTD_put_int(out, diff);
749                        size += 4;
750                        psg.stat.longs++;
751                    }
752                    else {                          // short
753                        PTD_put_short(out, diff);
754                        size += 2;
755                        psg.stat.shorts++;
756                    }
757                }
758                else {                              // short/char  (bit[7] in flags2 not set)
759                    if (diff>level) {               // short
760                        PTD_put_short(out, diff);
761                        size += 2;
762                        psg.stat.shorts2++;
763                    }
764                    else {                          // char
765                        PTD_put_byte(out, diff);
766                        size += 1;
767                        psg.stat.chars++;
768                    }
769                }
770#endif
771            }
772        }
773    }
774
775    long pos = oldpos+size-sizeof(PT_PNTR);                // no father
776    pt_assert(pos >= 0);
777    PTD_set_object_to_saved_status(node, oldpos, mysize);
778    return pos;
779}
780
781long PTD_write_leafs_to_disk(FILE *out, POS_TREE1 * const node, long pos, long *node_pos, ARB_ERROR& error) {
782    // returns new position in index-file (unchanged for type PT1_SAVED)
783    // *node_pos is set to the start-position of the most recent object written
784
785    pt_assert_stage(STAGE1);
786
787    switch (node->get_type()) {
788        case PT1_SAVED:
789            *node_pos = PT_read_big(&node->father);
790            break;
791
792        case PT1_LEAF:
793            *node_pos = pos;
794            pos       = PTD_write_tip_to_disk(out, node, pos);
795            break;
796
797        case PT1_CHAIN:
798            *node_pos = pos;
799            pos       = PTD_write_chain_to_disk(out, node, pos, error);
800            pt_assert(node->is_saved());
801            break;
802
803        case PT1_NODE: {
804            long son_pos[PT_BASES];
805            for (int i = PT_QU; i < PT_BASES && !error; i++) { // save all sons
806                POS_TREE1 *son = PT_read_son(node, (PT_base)i);
807                son_pos[i] = 0;
808                if (son) {
809                    pos = PTD_write_leafs_to_disk(out, son, pos, &(son_pos[i]), error);
810                    pt_assert(son->is_saved());
811                }
812            }
813
814            if (!error) {
815                *node_pos = pos;
816                pos = PTD_write_node_to_disk(out, node, son_pos, pos);
817            }
818            break;
819        }
820        case PT1_UNDEF:
821            pt_assert(0);
822            break;
823    }
824
825    pt_assert(error || node->is_saved());
826    return pos;
827}
828
829ARB_ERROR PTD_read_leafs_from_disk(const char *fname, POS_TREE2*& root_ptr) { // __ATTR__USERESULT
830    pt_assert_stage(STAGE2);
831
832    GB_ERROR  error  = NULp;
833    char     *buffer = GB_map_file(fname, 0);
834
835    if (!buffer) {
836        error = GBS_global_string("mmap failed (%s)", GB_await_error());
837    }
838    else {
839        long  size = GB_size_of_file(fname);
840        char *main = &(buffer[size-4]);
841
842        psg.big_db = false;
843
844        long i = PT_read_int(main);
845#ifdef ARB_64
846        if (i == 0xffffffff) {                    // 0xffffffff signalizes that "last_obj" is stored
847            main -= 8;                            // in the previous 8 byte (in a long long)
848            STATIC_ASSERT(sizeof(PT_PNTR) == 8);  // 0xffffffff is used to signalize to be compatible with older pt-servers
849            i      = PT_read_big(main);           // this search tree can only be loaded at 64 Bit
850            psg.big_db = true;
851        }
852#else
853        if (i<0) {
854            pt_assert(i == -1);                     // aka 0xffffffff
855            psg.big_db = true;                          // not usable in 32-bit version (fails below)
856        }
857        pt_assert(i <= INT_MAX);
858#endif
859
860        // try to find info_area
861        main -= 2;
862
863        short info_size = PT_read_short(main);
864
865#ifndef ARB_64
866        bool info_detected = false;
867#endif
868
869        if (info_size>0 && info_size<(main-buffer)) {   // otherwise impossible size
870            main -= info_size;
871
872            long magic   = PT_read_int(main); main += 4;
873            int  version = PT_read_char(main); main++;
874
875            pt_assert(PT_SERVER_MAGIC>0 && PT_SERVER_MAGIC<INT_MAX);
876
877            if (magic == PT_SERVER_MAGIC) {
878#ifndef ARB_64
879                info_detected = true;
880#endif
881                if (version != PT_SERVER_VERSION) {
882                    error = "PT-server database has different version (rebuild necessary)";
883                }
884            }
885        }
886
887#ifndef ARB_64
888        // 32bit version:
889        if (!error && psg.big_db) {
890            error = "PT-server database can only be used with 64bit-PT-Server";
891        }
892        if (!error && !info_detected) {
893            printf("Warning: ptserver DB has old format (no problem)\n");
894        }
895#endif
896
897        if (!error) {
898            pt_assert(i >= 0);
899            root_ptr  = (POS_TREE2*)(i+buffer);
900        }
901    }
902
903    return error;
904}
905
906// --------------------------------------------------------------------------------
907
908#if defined(PTM_MEM_DUMP_STATS)
909const char *get_blocksize_description(int blocksize) {
910    const char *known = NULp;
911    switch (blocksize) {
912        case PT1_EMPTY_NODE_SIZE:       known = "PT1_EMPTY_NODE_SIZE"; break;
913        case PT1_MIN_CHAIN_ENTRY_SIZE:  known = "PT1_MIN_CHAIN_ENTRY_SIZE"; break;
914        case PT1_MAX_CHAIN_ENTRY_SIZE:  known = "PT1_MAX_CHAIN_ENTRY_SIZE"; break;
915#if defined(ARB_64)
916        case PT1_EMPTY_LEAF_SIZE:       known = "PT1_EMPTY_LEAF_SIZE"; break;
917        case PT1_CHAIN_SHORT_HEAD_SIZE: known = "PT1_CHAIN_SHORT_HEAD_SIZE"; break;
918        case PT1_CHAIN_LONG_HEAD_SIZE:  known = "PT1_CHAIN_LONG_HEAD_SIZE"; break;
919        case PT1_NODE_WITHSONS_SIZE(2): known = "PT1_NODE_WITHSONS_SIZE(2)"; break;
920#else // 32bit:
921        case PT1_EMPTY_LEAF_SIZE:       known = "PT1_EMPTY_LEAF_SIZE      and PT1_CHAIN_SHORT_HEAD_SIZE"; break;
922        case PT1_NODE_WITHSONS_SIZE(2): known = "PT1_NODE_WITHSONS_SIZE(2) and PT1_CHAIN_LONG_HEAD_SIZE"; break;
923
924        STATIC_ASSERT(PT1_CHAIN_SHORT_HEAD_SIZE == PT1_EMPTY_LEAF_SIZE);
925        STATIC_ASSERT(PT1_CHAIN_LONG_HEAD_SIZE == PT1_NODE_WITHSONS_SIZE(2));
926#endif
927        case PT1_NODE_WITHSONS_SIZE(1): known = "PT1_NODE_WITHSONS_SIZE(1)"; break;
928        case PT1_NODE_WITHSONS_SIZE(3): known = "PT1_NODE_WITHSONS_SIZE(3)"; break;
929        case PT1_NODE_WITHSONS_SIZE(4): known = "PT1_NODE_WITHSONS_SIZE(4)"; break;
930        case PT1_NODE_WITHSONS_SIZE(5): known = "PT1_NODE_WITHSONS_SIZE(5)"; break;
931        case PT1_NODE_WITHSONS_SIZE(6): known = "PT1_NODE_WITHSONS_SIZE(6)"; break;
932    }
933    return known;
934}
935#endif
936
937// --------------------------------------------------------------------------------
938
939#ifdef UNIT_TESTS
940#ifndef TEST_UNIT_H
941#include <test_unit.h>
942#endif
943
944static arb_test::match_expectation has_proper_saved_state(POS_TREE1 *node, int size, bool expect_in_flags) {
945    using namespace arb_test;
946
947    uint_32 unmodified = 0xffffffff;
948    PT_write_int(node->udata(), unmodified);
949
950    PTD_set_object_to_saved_status(node, 0, size);
951
952    expectation_group expected;
953    expected.add(that(node->get_type()).is_equal_to(PT1_SAVED));
954    expected.add(that(get_memsize_of_saved(node)).is_equal_to(size));
955
956    uint_32 data_after = PT_read_int(node->udata());
957
958    if (expect_in_flags) {
959        expected.add(that(data_after).is_equal_to(unmodified));
960    }
961    else {
962        expected.add(that(data_after).does_differ_from(unmodified));
963    }
964
965    return all().ofgroup(expected);
966}
967
968#define TEST_SIZE_SAVED_IN_FLAGS(pt,size)         TEST_EXPECTATION(has_proper_saved_state(pt,size,true))
969#define TEST_SIZE_SAVED_EXTERNAL(pt,size)         TEST_EXPECTATION(has_proper_saved_state(pt,size,false))
970#define TEST_SIZE_SAVED_IN_FLAGS__BROKEN(pt,size) TEST_EXPECTATION__BROKEN(has_proper_saved_state(pt,size,true))
971#define TEST_SIZE_SAVED_EXTERNAL__BROKEN(pt,size) TEST_EXPECTATION__BROKEN(has_proper_saved_state(pt,size,false))
972
973struct EnterStage1 {
974    static bool initialized;
975    EnterStage1() {
976        if (initialized) PT_exit_psg();
977        PT_init_psg();
978        psg.enter_stage(STAGE1);
979        initialized = true;
980    }
981    ~EnterStage1() {
982        pt_assert(initialized);
983        PT_exit_psg();
984        initialized = false;
985    }
986};
987bool EnterStage1::initialized = false;
988
989void TEST_saved_state() {
990    EnterStage1 env;
991
992    const size_t SIZE = PT1_BASE_SIZE+6;
993    STATIC_ASSERT(SIZE >= (1+sizeof(uint_big)+sizeof(int)));
994
995    POS_TREE1 *node = (POS_TREE1*)ARB_alloc<char>(SIZE);
996
997    TEST_SIZE_SAVED_IN_FLAGS(node, PT1_BASE_SIZE);
998
999    TEST_SIZE_SAVED_IN_FLAGS(node, MIN_SIZE_IN_FLAGS);
1000    TEST_SIZE_SAVED_IN_FLAGS(node, MAX_SIZE_IN_FLAGS);
1001
1002    TEST_SIZE_SAVED_EXTERNAL(node, 5000);
1003    TEST_SIZE_SAVED_EXTERNAL(node, 40);
1004
1005#ifdef ARB_64
1006    TEST_SIZE_SAVED_EXTERNAL(node, 24);
1007    TEST_SIZE_SAVED_IN_FLAGS(node, 23);
1008#else
1009    TEST_SIZE_SAVED_EXTERNAL(node, 20);
1010    TEST_SIZE_SAVED_IN_FLAGS(node, 19);
1011#endif
1012
1013    TEST_SIZE_SAVED_IN_FLAGS(node, 10);
1014    TEST_SIZE_SAVED_IN_FLAGS(node, 9);
1015
1016#ifdef ARB_64
1017    STATIC_ASSERT(PT1_BASE_SIZE == 9);
1018#else
1019    TEST_SIZE_SAVED_IN_FLAGS(node, 8);
1020    TEST_SIZE_SAVED_IN_FLAGS(node, 7);
1021    TEST_SIZE_SAVED_IN_FLAGS(node, 6);
1022    TEST_SIZE_SAVED_IN_FLAGS(node, 5);
1023
1024    STATIC_ASSERT(PT1_BASE_SIZE == 5);
1025#endif
1026
1027    free(node);
1028}
1029
1030#if defined(ENABLE_CRASH_TESTS)
1031// # define TEST_BAD_CHAINS // TEST_chains fails in PTD_save_partial_tree if uncommented (as expected)
1032#endif
1033
1034#if defined(TEST_BAD_CHAINS)
1035
1036static POS_TREE1 *theChain = NULp;
1037static DataLoc   *theLoc   = NULp;
1038
1039static void bad_add_to_chain() {
1040    PT_add_to_chain(theChain, *theLoc);
1041#if !defined(PTM_DEBUG_VALIDATE_CHAINS)
1042    pt_assert(PT_chain_has_valid_entries<ChainIteratorStage1>(theChain));
1043#endif
1044    theChain = NULp;
1045    theLoc   = NULp;
1046}
1047#endif
1048
1049void TEST_chains() {
1050    EnterStage1 env;
1051    psg.data_count = 3;
1052
1053    POS_TREE1 *root = PT_create_leaf(NULp, PT_N, DataLoc(0, 0, 0));
1054    TEST_EXPECT_EQUAL(root->get_type(), PT1_LEAF);
1055
1056    root = PT_change_leaf_to_node(root);
1057    TEST_EXPECT_EQUAL(root->get_type(), PT1_NODE);
1058
1059    DataLoc loc0a(0, 500, 500);
1060    DataLoc loc0b(0, 555, 555);
1061
1062    DataLoc loc1a(1, 200, 200);
1063    DataLoc loc1b(1, 500, 500);
1064
1065    DataLoc loc2a(2, 300, 300);
1066    DataLoc loc2b(2, 700, 700);
1067    DataLoc loc2c(2, 701, 701);
1068
1069    for (int base = PT_A; base <= PT_G; ++base) {
1070        POS_TREE1 *leaf = PT_create_leaf(&root, PT_base(base), loc0b);
1071        TEST_EXPECT_EQUAL(leaf->get_type(), PT1_LEAF);
1072
1073        POS_TREE1 *chain = PT_leaf_to_chain(leaf);
1074        TEST_EXPECT_EQUAL(chain->get_type(), PT1_CHAIN);
1075        TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1076
1077        PT_add_to_chain(chain, loc0a); TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1078        PT_add_to_chain(chain, loc1b); TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1079        PT_add_to_chain(chain, loc1a); TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1080        PT_add_to_chain(chain, loc2c); TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1081        PT_add_to_chain(chain, loc2b); TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1082        PT_add_to_chain(chain, loc2a); TEST_EXPECT(PT_chain_has_valid_entries<ChainIteratorStage1>(chain));
1083
1084        // now chain is 'loc0b,loc0a,loc1b,loc1a,loc2b,loc2a'
1085
1086        if (base == PT_A) { // test only once
1087            ChainIteratorStage1 entry(chain);
1088
1089            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc0b); ++entry;
1090            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc0a); ++entry;
1091            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc1b); ++entry;
1092            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc1a); ++entry;
1093            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc2c); ++entry;
1094            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc2b); ++entry;
1095            TEST_EXPECT_EQUAL(bool(entry), true); TEST_EXPECT(entry.at() == loc2a); ++entry;
1096            TEST_EXPECT_EQUAL(bool(entry), false);
1097        }
1098
1099#if defined(TEST_BAD_CHAINS)
1100        // out-of-date
1101        switch (base) {
1102            case PT_A: theChain = chain; theLoc = &loc2a; TEST_EXPECT_CODE_ASSERTION_FAILS(bad_add_to_chain); break; // add same location twice -> fail
1103            case PT_C: theChain = chain; theLoc = &loc1b; TEST_EXPECT_CODE_ASSERTION_FAILS(bad_add_to_chain); break; // add species in wrong order -> fail
1104            case PT_G: theChain = chain; theLoc = &loc2b; TEST_EXPECT_CODE_ASSERTION_FAILS(bad_add_to_chain); break; // add positions in wrong order (should fail)
1105            default: TEST_EXPECT(0); break;
1106        }
1107#endif
1108    }
1109    {
1110        POS_TREE1 *leaf = PT_create_leaf(&root, PT_QU, loc1a); // PT_QU always produces chain
1111        TEST_EXPECT_EQUAL(leaf->get_type(), PT1_CHAIN);
1112    }
1113
1114    // since there is no explicit code to free POS_TREE-memory, spool it into /dev/null
1115    {
1116        FILE      *out = fopen("/dev/null", "wb");
1117        ARB_ERROR  error;
1118        long       root_pos;
1119
1120        long pos = PTD_save_lower_tree(out, root, 0, error);
1121        pos      = PTD_save_upper_tree(out, root, pos, root_pos, error);
1122
1123        TEST_EXPECT_NO_ERROR(error.deliver());
1124        TEST_EXPECTATION(all().of(that(root_pos).is_equal_to(74), that(pos).is_equal_to(79)));
1125        TEST_EXPECT_NULL(root); // nulled by PTD_save_upper_tree
1126
1127        fclose(out);
1128    }
1129}
1130
1131void TEST_mem() {
1132    EnterStage1 env;
1133
1134#if defined(PTM_MEM_DUMP_STATS)
1135    MEM.dump_stats(false);
1136#endif
1137
1138    const int  MAXSIZE = 1024;
1139    char      *ptr[MAXSIZE+1];
1140
1141    for (int size = PTM_MIN_SIZE; size <= MAXSIZE; ++size) {
1142        ptr[size] = (char*)MEM.get(size);
1143    }
1144    for (int size = PTM_MIN_SIZE; size <= MAXSIZE; ++size) {
1145#if defined(PTM_MEM_CHECKED_FREE)
1146        if (size <= PTM_MAX_SIZE) {
1147            TEST_EXPECT_EQUAL(MEM.block_has_size(ptr[size], size), true);
1148        }
1149#endif
1150        MEM.put(ptr[size], size);
1151    }
1152
1153    MEM.clear();
1154#if defined(PTM_MEM_DUMP_STATS)
1155    MEM.dump_stats(true);
1156#endif
1157
1158}
1159
1160template<int R>
1161static arb_test::match_expectation nat_stored_as_expected(uint_32 written_nat, int expected_bytes) {
1162    char buffer[5];
1163
1164    static uint_8 reserved_bits = 0;
1165
1166    reserved_bits = (reserved_bits+1) & BitsBelowBit<R>::value;
1167    uint_8 reserved_bits_read;
1168
1169    char       *wp = buffer;
1170    const char *rp = buffer;
1171
1172    write_nat_with_reserved_bits<R>(wp, written_nat, reserved_bits);
1173    uint_32 read_nat = read_nat_with_reserved_bits<R>(rp, reserved_bits_read);
1174
1175    int written_bytes = wp-buffer;
1176    int read_bytes    = rp-buffer;
1177
1178    using namespace   arb_test;
1179    expectation_group expected;
1180    expected.add(that(read_nat).is_equal_to(written_nat));
1181    expected.add(that(written_bytes).is_equal_to(expected_bytes));
1182    expected.add(that(read_bytes).is_equal_to(written_bytes));
1183    expected.add(that(reserved_bits_read).is_equal_to(reserved_bits));
1184
1185    return all().ofgroup(expected);
1186}
1187
1188template<int R>
1189static arb_test::match_expectation int_stored_as_expected(int32_t written_int, int expected_bytes) {
1190    char buffer[5];
1191
1192    static uint_8 reserved_bits = 0;
1193
1194    reserved_bits = (reserved_bits+1) & BitsBelowBit<R>::value;
1195    uint_8 reserved_bits_read;
1196
1197    char       *wp = buffer;
1198    const char *rp = buffer;
1199
1200    write_int_with_reserved_bits<R>(wp, written_int, reserved_bits);
1201    int32_t read_int = read_int_with_reserved_bits<R>(rp, reserved_bits_read);
1202
1203    int written_bytes = wp-buffer;
1204    int read_bytes    = rp-buffer;
1205
1206    using namespace   arb_test;
1207    expectation_group expected;
1208    expected.add(that(read_int).is_equal_to(written_int));
1209    expected.add(that(written_bytes).is_equal_to(expected_bytes));
1210    expected.add(that(read_bytes).is_equal_to(written_bytes));
1211    expected.add(that(reserved_bits_read).is_equal_to(reserved_bits));
1212
1213    return all().ofgroup(expected);
1214}
1215
1216
1217#define TEST_COMPACT_NAT_STORAGE(nat,inBytes)          TEST_EXPECTATION(nat_stored_as_expected<0>(nat, inBytes))
1218#define TEST_COMPACT_NAT_STORAGE_RESERVE1(nat,inBytes) TEST_EXPECTATION(nat_stored_as_expected<1>(nat, inBytes))
1219#define TEST_COMPACT_NAT_STORAGE_RESERVE2(nat,inBytes) TEST_EXPECTATION(nat_stored_as_expected<2>(nat, inBytes))
1220#define TEST_COMPACT_NAT_STORAGE_RESERVE3(nat,inBytes) TEST_EXPECTATION(nat_stored_as_expected<3>(nat, inBytes))
1221#define TEST_COMPACT_NAT_STORAGE_RESERVE4(nat,inBytes) TEST_EXPECTATION(nat_stored_as_expected<4>(nat, inBytes))
1222#define TEST_COMPACT_NAT_STORAGE_RESERVE5(nat,inBytes) TEST_EXPECTATION(nat_stored_as_expected<5>(nat, inBytes))
1223
1224#define TEST_COMPACT_INT_STORAGE(i,inBytes)          TEST_EXPECTATION(int_stored_as_expected<0>(i, inBytes))
1225#define TEST_COMPACT_INT_STORAGE_RESERVE3(i,inBytes) TEST_EXPECTATION(int_stored_as_expected<3>(i, inBytes))
1226
1227void TEST_compact_storage() {
1228    // test natural numbers (w/o reserved bits)
1229
1230    TEST_COMPACT_NAT_STORAGE(0, 1);
1231    TEST_COMPACT_NAT_STORAGE(0x7f, 1);
1232
1233    TEST_COMPACT_NAT_STORAGE(0x80, 2);
1234    TEST_COMPACT_NAT_STORAGE(0x407F, 2);
1235
1236    TEST_COMPACT_NAT_STORAGE(0x4080, 3);
1237    TEST_COMPACT_NAT_STORAGE(0x20407F, 3);
1238
1239    TEST_COMPACT_NAT_STORAGE(0x204080, 4);
1240    TEST_COMPACT_NAT_STORAGE(0x1020407F, 4);
1241
1242    TEST_COMPACT_NAT_STORAGE(0x10204080, 5);
1243    TEST_COMPACT_NAT_STORAGE(0xffffffff, 5);
1244
1245    // test 1 reserved bit (bit7 is reserved)
1246    TEST_COMPACT_NAT_STORAGE_RESERVE1(0, 1);
1247    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x3f, 1);
1248
1249    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x40, 2);
1250    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x203f, 2);
1251
1252    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x2040, 3);
1253    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x10203f, 3);
1254
1255    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x102040, 4);
1256    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x0810203f, 4);
1257
1258    TEST_COMPACT_NAT_STORAGE_RESERVE1(0x08102040, 5);
1259    TEST_COMPACT_NAT_STORAGE_RESERVE1(0xffffffff, 5);
1260
1261    // test integers (same as natural numbers with 1 bit reserved for sign)
1262    TEST_COMPACT_INT_STORAGE( 0, 1);
1263    TEST_COMPACT_INT_STORAGE( 0x3f, 1);
1264    TEST_COMPACT_INT_STORAGE(-0x40, 1);
1265
1266    TEST_COMPACT_INT_STORAGE( 0x40, 2);
1267    TEST_COMPACT_INT_STORAGE(-0x41, 2);
1268    TEST_COMPACT_INT_STORAGE( 0x203f, 2);
1269    TEST_COMPACT_INT_STORAGE(-0x2040, 2);
1270
1271    TEST_COMPACT_INT_STORAGE( 0x2040, 3);
1272    TEST_COMPACT_INT_STORAGE(-0x2041, 3);
1273    TEST_COMPACT_INT_STORAGE( 0x10203f, 3);
1274    TEST_COMPACT_INT_STORAGE(-0x102040, 3);
1275
1276    TEST_COMPACT_INT_STORAGE( 0x102040, 4);
1277    TEST_COMPACT_INT_STORAGE(-0x102041, 4);
1278    TEST_COMPACT_INT_STORAGE( 0x0810203f, 4);
1279    TEST_COMPACT_INT_STORAGE(-0x08102040, 4);
1280
1281    TEST_COMPACT_INT_STORAGE( 0x08102040, 5);
1282    TEST_COMPACT_INT_STORAGE(-0x08102041, 5);
1283    TEST_COMPACT_INT_STORAGE(INT_MAX, 5);
1284    TEST_COMPACT_INT_STORAGE(INT_MIN, 5);
1285
1286    // test 2 reserved bits (bit7 and bit6 are reserved)
1287    TEST_COMPACT_NAT_STORAGE_RESERVE2(0, 1);
1288    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x1f, 1);
1289
1290    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x20, 2);
1291    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x101f, 2);
1292
1293    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x1020, 3);
1294    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x08101f, 3);
1295
1296    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x081020, 4);
1297    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x0408101f, 4);
1298
1299    TEST_COMPACT_NAT_STORAGE_RESERVE2(0x04081020, 5);
1300    TEST_COMPACT_NAT_STORAGE_RESERVE2(0xffffffff, 5);
1301
1302    // test 3 reserved bits (bit7 .. bit5 are reserved)
1303    TEST_COMPACT_NAT_STORAGE_RESERVE3(0, 1);
1304    TEST_COMPACT_NAT_STORAGE_RESERVE3(0xf, 1);
1305
1306    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x10, 2);
1307    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x080f, 2);
1308
1309    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x0810, 3);
1310    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x04080f, 3);
1311
1312    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x040810, 4);
1313    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x0204080f, 4);
1314
1315    TEST_COMPACT_NAT_STORAGE_RESERVE3(0x02040810, 5);
1316    TEST_COMPACT_NAT_STORAGE_RESERVE3(0xffffffff, 5);
1317
1318    // test 4 reserved bits (bit7 .. bit4 are reserved)
1319    TEST_COMPACT_NAT_STORAGE_RESERVE4(0, 1);
1320    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x07, 1);
1321
1322    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x08, 2);
1323    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x0407, 2);
1324
1325    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x0408, 3);
1326    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x020407, 3);
1327
1328    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x020408, 4);
1329    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x01020407, 4);
1330
1331    TEST_COMPACT_NAT_STORAGE_RESERVE4(0x01020408, 5);
1332    TEST_COMPACT_NAT_STORAGE_RESERVE4(0xffffffff, 5);
1333
1334    // test integers with 3 reserved bits
1335    TEST_COMPACT_INT_STORAGE_RESERVE3( 0, 1);
1336    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x07, 1);
1337    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x08, 1);
1338
1339    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x08, 2);
1340    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x09, 2);
1341    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x0407, 2);
1342    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x0408, 2);
1343
1344    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x0408, 3);
1345    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x0409, 3);
1346    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x020407, 3);
1347    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x020408, 3);
1348
1349    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x020408, 4);
1350    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x020409, 4);
1351    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x01020407, 4);
1352    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x01020408, 4);
1353
1354    TEST_COMPACT_INT_STORAGE_RESERVE3( 0x01020408, 5);
1355    TEST_COMPACT_INT_STORAGE_RESERVE3(-0x01020409, 5);
1356    TEST_COMPACT_INT_STORAGE_RESERVE3(INT_MAX, 5);
1357    TEST_COMPACT_INT_STORAGE_RESERVE3(INT_MIN, 5);
1358
1359#if 0
1360    // reserving more than 4 bits does not work (compacting also uses 4 bits)
1361    // (compiles, but spits warnings)
1362    TEST_COMPACT_NAT_STORAGE_RESERVE5(0, 1);
1363#endif
1364}
1365
1366#endif // UNIT_TESTS
1367
1368// --------------------------------------------------------------------------------
Note: See TracBrowser for help on using the repository browser.