source: branches/profile/PROBE/probe_tree.h

Last change on this file was 11492, checked in by westram, 12 years ago
  • fix several doxygen issues (doxygen 1.6.3)
    • force macro expansion for IF_ASSERTION_USED
    • fixed changed param names
    • named some anonymous (nested) structs
    • remove/quote several '#' (triggering unknown commands)
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 23.5 KB
Line 
1// ============================================================= //
2//                                                               //
3//   File      : probe_tree.h                                    //
4//   Purpose   :                                                 //
5//                                                               //
6//   Institute of Microbiology (Technical University Munich)     //
7//   http://www.arb-home.de/                                     //
8//                                                               //
9// ============================================================= //
10
11#ifndef PROBE_TREE_H
12#define PROBE_TREE_H
13
14#if defined(DARWIN)
15#include <krb5.h>
16#else
17#include <bits/wordsize.h>
18#endif // DARWIN
19
20#ifndef STATIC_ASSERT_H
21#include <static_assert.h>
22#endif
23#ifndef PROBE_H
24#include "probe.h"
25#endif
26
27#define PT_CHAIN_NTERM     250
28#define PT_SHORT_SIZE      0xffff
29#define PT_INIT_CHAIN_SIZE 20
30
31struct pt_global {
32    char count_bits[PT_BASES+1][256];         // returns how many bits are set (e.g. PT_count_bits[3][n] is the number of the 3 lsb bits)
33
34    void init();
35};
36
37extern pt_global PT_GLOBAL;
38
39/* --------------------------------------------------------------------------------
40 *
41 *  Their are 3 stages of data format:
42 *      1st:        Creation of the tree
43 *      2nd:        Tree saved to disk
44 *
45 *  In stage 1 every element has a father pointer directly behind
46 *  the 1st byte (flags). Exception: Nodes of type PT1_SAVED.
47 *
48 * --------------------
49 * Data format:
50 *
51 * for 'compactNAT' see PT_write_compact_nat / PT_read_compact_nat
52 *
53 * ---------- Written object (PT1_SAVED)
54 *
55 *  flags       bit[7]   = 0
56 *              bit[6]   = 0
57 *              bit[5]   = 1
58 *              bit[4]   = unused
59 *              bit[3-0] = size of former entry-4 (if ==0 then size follows)
60 *  PT_PNTR     rel start of the object in the saved index
61 *  [int        size]      (if flagsbit[3-0] == 0)
62 *
63 * ---------- leaf (PT1_LEAF and PT2_LEAF)
64 *
65 *  byte        flags       bit[7]   = 0
66 *                          bit[6]   = 0
67 *                          bit[5]   = 0
68 *                          bit[4-3] = unused
69 *                          bit[2-0] = used to indicate sizes of entries below
70 *  [PT_PNTR    father]     only if type is PT1_LEAF
71 *  short/int   name        int if bit[0]
72 *  short/int   relpos      int if bit[1]
73 *  short/int   abspos      int if bit[2]
74 *
75 * ---------- inner node (PT1_NODE)
76 *
77 *  byte        flags       bit[7]   = 1
78 *                          bit[6]   = 0
79 *                          bit[5-0] = indicate existing sons
80 *  PT_PNTR     father
81 *  [PT_PNTR son0]          if bit[0]
82 *  ...                     ...
83 *  [PT_PNTR son5]          if bit[5]
84 *
85 * ---------- inner node with more than one child (PT2_NODE)
86 *
87 *  byte        flags       bit[7]   = 1
88 *                          bit[6]   = 0
89 *                          bit[5-0] = indicate existing sons
90 *  byte2                   bit2[7] = 0  bit2[6] = 0  -->  short/char
91 *                          bit2[7] = 1  bit2[6] = 0  -->  int/short
92 *                          bit2[7] = 0  bit2[6] = 1  -->  long/int         (only if ARB_64 is set)
93 *                          bit2[7] = 1  bit2[6] = 1  -->  undefined        (only if ARB_64 is set)
94 *
95 *  [char/short/int/long son0]  if bit[0]; uses left (bigger) type if bit2[0] else right (smaller) type
96 *  [char/short/int/long son1]  if bit[1]; uses left (bigger) type if bit2[1] else right (smaller) type
97 *  ...
98 *  [char/short/int/long son5]  if bit[5]; uses left (bigger) type if bit2[5] else right (smaller) type
99 *
100 *  example1:   byte  = 0x8d    --> inner node; son0, son2 and son3 are available
101 *              byte2 = 0x05    --> son0 and son2 are shorts; son3 is a char
102 *
103 *  example2:   byte  = 0x8d    --> inner node; son0, son2 and son3 are available
104 *              byte2 = 0x81    --> son0 is a int; son2 and son3 are shorts
105 *
106 *  [example3 atm only if ARB_64 is set]
107 *  example3:   byte  = 0x8d    --> inner node; son0, son2 and son3 are available
108 *              byte2 = 0x44    --> son2 is a long; son0 and son3 are ints
109 *
110 * ---------- inner node with single child (PT2_NODE)
111 *
112 *  byte        flags       bit[7]   = 1
113 *                          bit[6]   = 1
114 *                          bit[5-3] = offset 0->1 1->3 2->4 3->5 ....
115 *                          bit[2-0] = base
116 *
117 * ---------- chain (PT1_CHAIN)
118 *
119 *  byte        flags       bit[7]   = 0
120 *                          bit[6]   = 1
121 *                          bit[5]   = 0
122 *                          bit[4]   = uses PT_short_chain_header (see SHORT_CHAIN_HEADER_FLAG_BIT)
123 *                          bit[3]   = unused
124 *                          bit[2-0] = entries in PT_short_chain_header, see SHORT_CHAIN_HEADER_SIZE_MASK (unused otherwise)
125 *  PT_PNTR     father
126 *  PT_short_chain_header or PT_long_chain_header
127 *
128 *  if PT_long_chain_header is used, the memory pointed-to by its 'entrymem'
129 *  contains for each chain element:
130 *
131 *  compactNAT  namediff    (1 bit reserved for 'hasrefapos')
132 *  [compactNAT abspos]     (if 'hasrefapos'; otherwise entry has refabspos as in PT_long_chain_header)
133 *
134 * ---------- chain (PT2_CHAIN)
135 *
136 *  byte        flags       bit[7]   = 0
137 *                          bit[6]   = 1
138 *                          bit[5-1] = unused
139 *                          bit[0]   = flag for refabspos
140 *  short/int   refabspos   (int if bit[0])
141 *  compactNAT  chainsize
142 *
143 *  for each chain element:
144 *
145 *  compactNAT  namediff    (relative to previous name in chain; first bit reserved : 1 -> has refabspos )
146 *  [compactNAT abspos]     (only if not has refabspos)
147 *
148 */
149
150#define IS_SINGLE_BRANCH_NODE 0x40
151#ifdef ARB_64
152# define INT_SONS              0x80
153# define LONG_SONS             0x40
154#else
155# define LONG_SONS             0x80
156#endif
157
158// -----------------------------------------------
159//      Get the size of entries (stage 1) only
160
161#define PT1_BASE_SIZE sizeof(POS_TREE1) // flag + father
162
163#define PT1_EMPTY_LEAF_SIZE       (PT1_BASE_SIZE+6)                 // name rel apos
164#define PT1_LEAF_SIZE(leaf)       (PT1_BASE_SIZE+6+2*PT_GLOBAL.count_bits[3][(leaf)->flags])
165#define PT1_CHAIN_SHORT_HEAD_SIZE (PT1_BASE_SIZE+2+sizeof(PT_PNTR)) // apos first_elem
166#define PT1_CHAIN_LONG_HEAD_SIZE  (PT1_CHAIN_SHORT_HEAD_SIZE+2)     // apos uses 4 byte here
167#define PT1_EMPTY_NODE_SIZE       PT1_BASE_SIZE
168
169#define PT1_MIN_CHAIN_ENTRY_SIZE  (sizeof(PT_PNTR)+3*sizeof(char)) // depends on PT_write_compact_nat
170#define PT1_MAX_CHAIN_ENTRY_SIZE  (sizeof(PT_PNTR)+3*(sizeof(int)+1))
171
172#define PT1_NODE_WITHSONS_SIZE(sons) (PT1_EMPTY_NODE_SIZE+sizeof(PT_PNTR)*(sons))
173
174#define PT_NODE_SON_COUNT(node) (PT_GLOBAL.count_bits[PT_BASES][node->flags])
175#define PT1_NODE_SIZE(node)     PT1_NODE_WITHSONS_SIZE(PT_NODE_SON_COUNT(node))
176
177// -----------------
178//      POS TREE
179
180#define FLAG_TYPE_BITS      2
181#define FLAG_FREE_BITS      (8-FLAG_TYPE_BITS)
182#define FLAG_FREE_BITS_MASK ((1<<FLAG_TYPE_BITS)-1)
183#define FLAG_TYPE_BITS_MASK (0xFF^FLAG_FREE_BITS_MASK)
184
185enum PT1_TYPE {
186    PT1_LEAF  = 0,
187    PT1_CHAIN = 1,
188    PT1_NODE  = 2,
189    PT1_SAVED = 3,
190    PT1_UNDEF = 4,
191};
192
193enum PT2_TYPE {
194    PT2_LEAF  = PT1_LEAF,
195    PT2_CHAIN = PT1_CHAIN,
196    PT2_NODE  = PT1_NODE,
197};
198
199struct POS_TREE1 { // pos-tree (stage 1)
200    uchar      flags;
201    POS_TREE1 *father;
202
203    typedef PT1_TYPE TYPE;
204
205    static TYPE flag_2_type[256];
206    static void init_static();
207
208    const char *udata() const { return ((const char*)this)+sizeof(*this); }
209    char *udata() { return ((char*)this)+sizeof(*this); }
210
211    POS_TREE1 *get_father() const {
212        pt_assert(!is_saved());
213        return father;
214    }
215    void set_father(POS_TREE1 *new_father) {
216        pt_assert(!new_father || new_father->is_node());
217        father = new_father;
218    }
219    void clear_fathers();
220
221    void set_type(TYPE type) {
222        // sets user bits to zero
223        pt_assert(type != PT1_UNDEF && type != PT1_SAVED); // does not work for saved nodes (done manually)
224        flags = type<<FLAG_FREE_BITS;
225    }
226    TYPE get_type() const { return flag_2_type[flags]; }
227
228    bool is_node() const { return get_type() == PT1_NODE; }
229    bool is_leaf() const { return get_type() == PT1_LEAF; }
230    bool is_chain() const { return get_type() == PT1_CHAIN; }
231    bool is_saved() const { return get_type() == PT1_SAVED; }
232} __attribute__((packed));
233
234struct POS_TREE2 { // pos-tree (stage 2)
235    uchar flags;
236
237    typedef PT2_TYPE TYPE;
238
239    static TYPE flag_2_type[256];
240    static void init_static();
241
242    const char *udata() const { return ((const char*)this)+sizeof(*this); }
243    char *udata() { return ((char*)this)+sizeof(*this); }
244
245    void set_type(TYPE type) { flags = type<<FLAG_FREE_BITS; } // sets user bits to zero
246    TYPE get_type() const { return flag_2_type[flags]; }
247
248    bool is_node() const { return get_type() == PT2_NODE; }
249    bool is_leaf() const { return get_type() == PT2_LEAF; }
250    bool is_chain() const { return get_type() == PT2_CHAIN; }
251} __attribute__((packed));
252
253
254#if defined(ARB_64)
255#define SHORT_CHAIN_HEADER_ELEMS 4
256#else // !defined(ARB_64)
257#define SHORT_CHAIN_HEADER_ELEMS 3
258#endif
259
260#define SHORT_CHAIN_HEADER_FLAG_BIT  (1<<4)
261#define SHORT_CHAIN_HEADER_SIZE_MASK 0x07
262
263STATIC_ASSERT(SHORT_CHAIN_HEADER_SIZE_MASK >= SHORT_CHAIN_HEADER_ELEMS);
264STATIC_ASSERT((SHORT_CHAIN_HEADER_SIZE_MASK & SHORT_CHAIN_HEADER_FLAG_BIT) == 0);
265
266struct PT_short_chain_header {
267    unsigned name[SHORT_CHAIN_HEADER_ELEMS];
268    unsigned abspos[SHORT_CHAIN_HEADER_ELEMS];
269};
270
271struct PT_long_chain_header {
272    unsigned  entries;
273    unsigned  memsize;
274    unsigned  memused;
275    unsigned  refabspos;
276    unsigned  lastname;
277    char     *entrymem;
278};
279
280STATIC_ASSERT(sizeof(PT_long_chain_header) >= sizeof(PT_short_chain_header)); // SHORT_CHAIN_HEADER_ELEMS is too big
281STATIC_ASSERT((sizeof(PT_short_chain_header)/SHORT_CHAIN_HEADER_ELEMS*(SHORT_CHAIN_HEADER_ELEMS+1)) > sizeof(PT_long_chain_header)); // SHORT_CHAIN_HEADER_ELEMS is too small
282
283inline size_t PT_node_size(POS_TREE2 *node) { // @@@ become member
284    size_t size = 1; // flags
285    if ((node->flags & IS_SINGLE_BRANCH_NODE) == 0) {
286        UINT sec = (uchar)*node->udata(); // read second byte for charshort/shortlong info
287        ++size;
288
289        long i = PT_GLOBAL.count_bits[PT_BASES][node->flags] + PT_GLOBAL.count_bits[PT_BASES][sec];
290#ifdef ARB_64
291        if (sec & LONG_SONS) {
292            size += 4*i;
293        }
294        else if (sec & INT_SONS) {
295            size += 2*i;
296        }
297        else {
298            size += i;
299        }
300#else
301        if (sec & LONG_SONS) {
302            size += 2*i;
303        }
304        else {
305            size += i;
306        }
307#endif
308    }
309    return size;
310}
311
312template <typename PT> inline PT *PT_read_son(PT *node, PT_base base); // @@@ become member
313
314template <> inline POS_TREE2 *PT_read_son<POS_TREE2>(POS_TREE2 *node, PT_base base) { // stage 2 (no father)
315    pt_assert_stage(STAGE2);
316    pt_assert(node->is_node());
317
318    if (node->flags & IS_SINGLE_BRANCH_NODE) {
319        if (base != (node->flags & 0x7)) return NULL; // no son
320        long i    = (node->flags >> 3)&0x7;      // this son
321        if (!i) i = 1; else i+=2;                // offset mapping
322        pt_assert(i >= 0);
323        return (POS_TREE2 *)(((char *)node)-i);
324    }
325    if (!((1<<base) & node->flags)) { // bit not set
326        return NULL;
327    }
328
329    UINT sec  = (uchar)*node->udata();   // read second byte for charshort/shortlong info
330    long i    = PT_GLOBAL.count_bits[base][node->flags];
331    i        += PT_GLOBAL.count_bits[base][sec];
332
333    char *sons = node->udata()+1;
334
335#ifdef ARB_64
336    if (sec & LONG_SONS) {
337        if (sec & INT_SONS) {                                   // undefined -> error
338            GBK_terminate("Your pt-server search tree is corrupt! You can not use it anymore.\n"
339                          "Error: ((sec & LONG_SON) && (sec & INT_SONS)) == true\n"
340                          "       this combination of both flags is not implemented");
341        }
342        else {                                                // long/int
343#ifdef DEBUG
344            printf("Warning: A search tree of this size is not tested.\n");
345            printf("         (sec & LONG_SON) == true\n");
346#endif
347            UINT offset = 4 * i;
348            if ((1<<base) & sec) {              // long
349                i = PT_read_long(sons+offset);
350            }
351            else {                                              // int
352                i = PT_read_int(sons+offset);
353            }
354        }
355
356    }
357    else {
358        if (sec & INT_SONS) {                                   // int/short
359            UINT offset = i+i;
360            if ((1<<base) & sec) {                              // int
361                i = PT_read_int(sons+offset);
362            }
363            else {                                              // short
364                i = PT_read_short(sons+offset);
365            }
366        }
367        else {                                                  // short/char
368            UINT offset = i;
369            if ((1<<base) & sec) {                              // short
370                i = PT_read_short(sons+offset);
371            }
372            else {                                              // char
373                i = PT_read_char(sons+offset);
374            }
375        }
376    }
377#else
378    if (sec & LONG_SONS) {
379        UINT offset = i+i;
380        if ((1<<base) & sec) {
381            i = PT_read_int(sons+offset);
382        }
383        else {
384            i = PT_read_short(sons+offset);
385        }
386    }
387    else {
388        UINT offset = i;
389        if ((1<<base) & sec) {
390            i = PT_read_short(sons+offset);
391        }
392        else {
393            i = PT_read_char(sons+offset);
394        }
395    }
396#endif
397    pt_assert(i >= 0);
398    return (POS_TREE2 *)(((char*)node)-i);
399}
400
401template<> inline POS_TREE1 *PT_read_son<POS_TREE1>(POS_TREE1 *node, PT_base base) {
402    pt_assert_stage(STAGE1);
403    if (!((1<<base) & node->flags)) return NULL;   // bit not set
404    base = (PT_base)PT_GLOBAL.count_bits[base][node->flags];
405    return PT_read_pointer<POS_TREE1>(node->udata() + sizeof(PT_PNTR)*base);
406}
407
408inline size_t PT_leaf_size(POS_TREE2 *node) { // @@@ become member
409    size_t size = 1;  // flags
410    size += (PT_GLOBAL.count_bits[PT_BASES][node->flags]+3)*2;
411    return size;
412}
413
414// --------------------------------------
415//      Different types of locations
416
417class AbsLoc {
418    int name; // index into psg.data[], aka species id
419    int apos; // absolute position in alignment
420protected:
421    void set_abs_pos(int abs_pos) { apos = abs_pos; }
422    void set_name(int name_) {
423        pt_assert(name == -1); // only allowed if instance has been default constructed
424        name = name_;
425        pt_assert(has_valid_name());
426    }
427public:
428    AbsLoc() : name(-1), apos(0) {}
429    AbsLoc(int name_, int abs_pos) : name(name_), apos(abs_pos) {}
430    virtual ~AbsLoc() {}
431
432    bool has_valid_name() const { return name >= 0 && name < psg.data_count; }
433
434    int get_name() const { return name; }
435    int get_abs_pos() const { return apos; }
436
437    const probe_input_data& get_pid() const { pt_assert(has_valid_name()); return psg.data[name]; }
438
439    bool is_equal(const AbsLoc& other) const { return apos == other.apos && name == other.name; }
440
441#if defined(DEBUG)
442    void dump(FILE *fp) const {
443        fprintf(fp, "          apos=%6i  name=%6i='%s'\n",
444                get_abs_pos(), get_name(), has_valid_name() ? get_pid().get_shortname() : "<invalid>");
445    }
446#endif
447};
448
449class DataLoc : public AbsLoc {
450    int rpos; // relative position in data
451
452public:
453    bool has_valid_positions() const { return get_abs_pos() >= 0 && rpos >= 0 && get_abs_pos() >= rpos; }
454
455    DataLoc() : rpos(0) {}
456    DataLoc(int name_, int apos_, int rpos_) : AbsLoc(name_, apos_), rpos(rpos_) { pt_assert(has_valid_positions()); }
457    template <typename PT> explicit DataLoc(const PT *node) {
458        pt_assert(node->is_leaf());
459        const char *data = node->udata();
460        if (node->flags&1) { set_name(PT_read_int(data)); data += 4; } else { set_name(PT_read_short(data)); data += 2; }
461        if (node->flags&2) { rpos = PT_read_int(data); data += 4; } else { rpos = PT_read_short(data); data += 2; }
462        if (node->flags&4) { set_abs_pos(PT_read_int(data)); data += 4; } else { set_abs_pos(PT_read_short(data)); /*data += 2;*/ }
463
464        pt_assert(has_valid_positions());
465    }
466    explicit DataLoc(const AbsLoc& aloc) // expensive!
467        : AbsLoc(aloc),
468          rpos(get_pid().calc_relpos(get_abs_pos()))
469    {}
470
471    int get_rel_pos() const { return rpos; }
472
473    void set_position(int abs_pos, int rel_pos) {
474        set_abs_pos(abs_pos);
475        rpos = rel_pos;
476        pt_assert(has_valid_positions());
477    }
478
479    bool is_equal(const DataLoc& other) const { return rpos == other.rpos && AbsLoc::is_equal(other); }
480
481#if defined(DEBUG)
482    void dump(FILE *fp) const {
483        fprintf(fp, "          apos=%6i  rpos=%6i  name=%6i='%s'\n",
484                get_abs_pos(), rpos, get_name(), has_valid_name() ? get_pid().get_shortname() : "<invalid>");
485    }
486#endif
487};
488
489inline bool operator==(const AbsLoc& loc1, const AbsLoc& loc2) { return loc1.is_equal(loc2); }
490
491// -------------------------
492//      ReadableDataLoc
493
494class ReadableDataLoc : public DataLoc {
495    const probe_input_data& pid;
496    mutable SmartCharPtr    seq;
497    const char&             qseq;
498
499public:
500    ReadableDataLoc(int name_, int apos_, int rpos_)
501        : DataLoc(name_, apos_, rpos_),
502          pid(DataLoc::get_pid()),
503          seq(pid.get_dataPtr()),
504          qseq(*seq)
505    {}
506    explicit ReadableDataLoc(const DataLoc& loc)
507        : DataLoc(loc),
508          pid(DataLoc::get_pid()),
509          seq(pid.get_dataPtr()),
510          qseq(*seq)
511    {}
512    template <typename PT> explicit ReadableDataLoc(const PT *node)
513        : DataLoc(node),
514          pid(DataLoc::get_pid()),
515          seq(pid.get_dataPtr()),
516          qseq(*seq)
517    {}
518
519    const probe_input_data& get_pid() const { return pid; }
520
521    PT_base operator[](int offset) const {
522        int ro_pos = get_rel_pos()+offset;
523        return pid.valid_rel_pos(ro_pos) ? PT_base((&qseq)[ro_pos]) : PT_QU;
524    }
525};
526
527// -----------------------
528
529inline const char *PT_READ_CHAIN_ENTRY_stage_2(const char *ptr, int refabspos, AbsLoc& loc) {
530    // Caution: 'name' (of AbsLoc) has to be initialized before first call and shall not be modified between calls
531
532    pt_assert_stage(STAGE2);
533
534    uint_8  has_main_apos;
535    uint_32 name = loc.get_name() + read_nat_with_reserved_bits<1>(ptr, has_main_apos);
536
537    loc = AbsLoc(name, has_main_apos ? refabspos : PT_read_compact_nat(ptr));
538
539    return ptr;
540}
541
542inline char *PT_WRITE_CHAIN_ENTRY(char *ptr, int refabspos, int name, const int apos) {
543    pt_assert_stage(STAGE1);
544    bool has_main_apos = (apos == refabspos);
545    write_nat_with_reserved_bits<1>(ptr, name, has_main_apos);
546    if (!has_main_apos) PT_write_compact_nat(ptr, apos);
547    return ptr;
548}
549
550// -----------------------
551//      ChainIterators
552
553class ChainIteratorStage1 : virtual Noncopyable {
554    bool is_short;
555    union _U {
556        struct _S {
557            const PT_short_chain_header *header;
558            int                          next_entry;
559
560            void set_loc(AbsLoc& location) {
561                pt_assert(next_entry<SHORT_CHAIN_HEADER_ELEMS);
562                location = AbsLoc(header->name[next_entry], header->abspos[next_entry]);
563                ++next_entry;
564            }
565        } S;
566        struct _L {
567            int         refabspos;
568            const char *read_pos;
569
570            void set_loc(AbsLoc& location) {
571                uint_8  has_refabspos;
572                uint_32 name   = location.get_name()+read_nat_with_reserved_bits<1>(read_pos, has_refabspos);
573                uint_32 abspos = has_refabspos ? refabspos : PT_read_compact_nat(read_pos);
574                location = AbsLoc(name, abspos);
575            }
576        } L;
577    } iter;
578
579    AbsLoc loc;
580    int    elements_ahead;
581
582    bool at_end_of_chain() const { return elements_ahead<0; }
583    void set_loc_from_chain() {
584        pt_assert(!at_end_of_chain());
585        if (elements_ahead>0) {
586            if (is_short) iter.S.set_loc(loc);
587            else          iter.L.set_loc(loc);
588        }
589        else {
590            pt_assert(elements_ahead == 0);
591            loc = AbsLoc();
592        }
593        --elements_ahead;
594        pt_assert(at_end_of_chain() || loc.has_valid_name());
595    }
596    void inc() {
597        pt_assert(!at_end_of_chain());
598        set_loc_from_chain();
599    }
600
601public:
602    typedef POS_TREE1 POS_TREE_TYPE;
603
604    ChainIteratorStage1(const POS_TREE1 *node)
605        : loc(0, 0)
606    {
607        pt_assert_stage(STAGE1);
608        pt_assert(node->is_chain());
609
610        is_short = node->flags & SHORT_CHAIN_HEADER_FLAG_BIT;
611        if (is_short) {
612            elements_ahead    = node->flags & SHORT_CHAIN_HEADER_SIZE_MASK;
613            iter.S.next_entry = 0;
614            iter.S.header     = reinterpret_cast<const PT_short_chain_header*>(node->udata());
615        }
616        else {
617            const PT_long_chain_header *header = reinterpret_cast<const PT_long_chain_header*>(node->udata());
618
619            elements_ahead = header->entries;
620
621            iter.L.refabspos = header->refabspos;
622            iter.L.read_pos  = header->entrymem;
623        }
624
625        set_loc_from_chain();
626    }
627
628    operator bool() const { return !at_end_of_chain(); }
629    const AbsLoc& at() const { return loc; }
630    const ChainIteratorStage1& operator++() { inc(); return *this; } // prefix-inc
631
632    int get_elements_ahead() const { return elements_ahead; }
633
634    int get_refabspos() const {
635        return is_short
636            ? iter.S.header->abspos[0] // @@@ returns any abspos, optimize for SHORT_CHAIN_HEADER_ELEMS >= 3 only
637            : iter.L.refabspos;
638    }
639};
640
641class ChainIteratorStage2 : virtual Noncopyable {
642    const char *data;
643    AbsLoc      loc;
644
645    int refabspos;
646    int elements_ahead;
647
648    bool at_end_of_chain() const { return elements_ahead<0; }
649    void set_loc_from_chain() {
650        if (elements_ahead>0) {
651            data = PT_READ_CHAIN_ENTRY_stage_2(data, refabspos, loc);
652        }
653        else {
654            pt_assert(elements_ahead == 0);
655            loc = AbsLoc();
656        }
657        --elements_ahead;
658        pt_assert(at_end_of_chain() || loc.has_valid_name());
659    }
660    void inc() {
661        pt_assert(!at_end_of_chain());
662        set_loc_from_chain();
663    }
664
665public:
666    typedef POS_TREE2 POS_TREE_TYPE;
667
668    ChainIteratorStage2(const POS_TREE2 *node)
669        : data(node->udata()),
670          loc(0, 0) // init name with 0 (needed for chain reading in STAGE2)
671    {
672        pt_assert_stage(STAGE2);
673        pt_assert(node->is_chain());
674
675        if (node->flags&1) { refabspos = PT_read_int(data);   data += 4; }
676        else               { refabspos = PT_read_short(data); data += 2; }
677
678        elements_ahead = PT_read_compact_nat(data);
679
680        pt_assert(elements_ahead>0); // chain cant be empty
681        set_loc_from_chain();
682    }
683
684    operator bool() const { return !at_end_of_chain(); }
685    const AbsLoc& at() const { return loc; }
686    const ChainIteratorStage2& operator++() { inc(); return *this; } // prefix-inc
687
688    const char *memptr() const { return data; }
689};
690
691template<typename PT, typename T> int PT_forwhole_chain(PT *node, T& func);
692
693template<typename T> int PT_forwhole_chain(POS_TREE1 *node, T& func) {
694    pt_assert_stage(STAGE1);
695    int error = 0;
696    for (ChainIteratorStage1 entry(node); entry && !error; ++entry) {
697        error = func(entry.at());
698    }
699    return error;
700}
701
702template<typename T> int PT_forwhole_chain(POS_TREE2 *node, T& func) {
703    pt_assert_stage(STAGE2);
704    int error = 0;
705    for (ChainIteratorStage2 entry(node); entry && !error; ++entry) {
706        error = func(entry.at());
707    }
708    return error;
709}
710
711#if defined(DEBUG)
712struct PTD_chain_print {
713    int operator()(const AbsLoc& loc) { loc.dump(stdout); return 0; }
714};
715#endif
716
717#else
718#error probe_tree.h included twice
719#endif // PROBE_TREE_H
Note: See TracBrowser for help on using the repository browser.