ARB
probe_tree.h
Go to the documentation of this file.
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 
31 struct 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 
37 extern 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 
185 enum PT1_TYPE {
186  PT1_LEAF = 0,
188  PT1_NODE = 2,
191 };
192 
193 enum PT2_TYPE {
197 };
198 
199 struct POS_TREE1 { // pos-tree (stage 1)
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 
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 
234 struct POS_TREE2 { // pos-tree (stage 2)
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 
265 
269 };
270 
272  unsigned entries;
273  unsigned memsize;
274  unsigned memused;
275  unsigned refabspos;
276  unsigned lastname;
277  char *entrymem;
278 };
279 
280 STATIC_ASSERT(sizeof(PT_long_chain_header) >= sizeof(PT_short_chain_header)); // SHORT_CHAIN_HEADER_ELEMS is too big
281 STATIC_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 
283 inline 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 
312 template <typename PT> inline PT *PT_read_son(PT *node, PT_base base); // @@@ become member
313 
314 template <> inline POS_TREE2 *PT_read_son<POS_TREE2>(POS_TREE2 *node, PT_base base) { // stage 2 (no father)
316  pt_assert(node->is_node());
317 
318  if (node->flags & IS_SINGLE_BRANCH_NODE) {
319  if (base != (node->flags & 0x7)) return NULp; // 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 NULp;
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 
401 template<> inline POS_TREE1 *PT_read_son<POS_TREE1>(POS_TREE1 *node, PT_base base) {
403  if (!((1<<base) & node->flags)) return NULp; // 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 
408 inline 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 
417 class AbsLoc {
418  int name; // index into psg.data[], aka species id
419  int apos; // absolute position in alignment
420 protected:
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_;
426  }
427 public:
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 
449 class DataLoc : public AbsLoc {
450  int rpos; // relative position in data
451 
452 public:
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 
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;
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 
489 inline bool operator==(const AbsLoc& loc1, const AbsLoc& loc2) { return loc1.is_equal(loc2); }
490 
491 // -------------------------
492 // ReadableDataLoc
493 
494 class ReadableDataLoc : public DataLoc {
495  const probe_input_data& pid;
496  mutable SmartCharPtr seq;
497  const char& qseq;
498 
499 public:
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 
529 inline 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 
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 
542 inline char *PT_WRITE_CHAIN_ENTRY(char *ptr, int refabspos, int name, const int apos) {
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 
554  bool is_short;
555  union _U {
556  struct _S {
559 
560  void set_loc(AbsLoc& location) {
562  location = AbsLoc(header->name[next_entry], header->abspos[next_entry]);
563  ++next_entry;
564  }
565  } S;
566  struct _L {
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 
601 public:
603 
605  : loc(0, 0)
606  {
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 
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 
665 public:
667 
669  : data(node->udata()),
670  loc(0, 0) // init name with 0 (needed for chain reading in STAGE2)
671  {
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 
691 template<typename PT, typename T> int PT_forwhole_chain(PT *node, T& func);
692 
693 template<typename T> int PT_forwhole_chain(POS_TREE1 *node, T& func) {
695  int error = 0;
696  for (ChainIteratorStage1 entry(node); entry && !error; ++entry) {
697  error = func(entry.at());
698  }
699  return error;
700 }
701 
702 template<typename T> int PT_forwhole_chain(POS_TREE2 *node, T& func) {
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)
712 struct 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
struct probe_input_data * data
Definition: probe.h:356
AbsLoc()
Definition: probe_tree.h:428
ReadableDataLoc(int name_, int apos_, int rpos_)
Definition: probe_tree.h:500
#define LONG_SONS
Definition: probe_tree.h:155
size_t PT_leaf_size(POS_TREE2 *node)
Definition: probe_tree.h:408
Definition: probe.h:122
void set_type(TYPE type)
Definition: probe_tree.h:221
GB_TYPES type
static TYPE flag_2_type[256]
Definition: probe_tree.h:239
void * PT_PNTR
Definition: PT_tools.h:24
Definition: probe.h:83
#define SHORT_CHAIN_HEADER_SIZE_MASK
Definition: probe_tree.h:261
DataLoc(const PT *node)
Definition: probe_tree.h:457
void set_type(TYPE type)
Definition: probe_tree.h:245
const char * udata() const
Definition: probe_tree.h:208
unsigned int UINT
ReadableDataLoc(const PT *node)
Definition: probe_tree.h:512
const ChainIteratorStage1 & operator++()
Definition: probe_tree.h:630
virtual ~AbsLoc()
Definition: probe_tree.h:430
int PT_forwhole_chain(PT *node, T &func)
int get_name() const
Definition: probe_tree.h:434
const probe_input_data & get_pid() const
Definition: probe_tree.h:519
POS_TREE1 * get_father() const
Definition: probe_tree.h:211
probe_struct_global psg
Definition: PT_main.cxx:36
void set_position(int abs_pos, int rel_pos)
Definition: probe_tree.h:473
const char * udata() const
Definition: probe_tree.h:46
uchar flags
Definition: probe_tree.h:235
#define FLAG_FREE_BITS
Definition: probe_tree.h:181
const PT_short_chain_header * header
Definition: probe_tree.h:557
PT2_TYPE TYPE
Definition: probe_tree.h:237
void set_abs_pos(int abs_pos)
Definition: probe_tree.h:421
unsigned int uint_32
Definition: PT_tools.h:28
uint_32 PT_read_compact_nat(const char *&fromMem)
Definition: PT_tools.h:196
DataLoc(const AbsLoc &aloc)
Definition: probe_tree.h:466
POS_TREE2 * PT_read_son< POS_TREE2 >(POS_TREE2 *node, PT_base base)
Definition: probe_tree.h:314
PT1_TYPE TYPE
Definition: probe_tree.h:203
bool has_valid_positions() const
Definition: probe_tree.h:453
ReadableDataLoc(const DataLoc &loc)
Definition: probe_tree.h:506
const char * PT_READ_CHAIN_ENTRY_stage_2(const char *ptr, int refabspos, AbsLoc &loc)
Definition: probe_tree.h:529
const probe_input_data & get_pid() const
Definition: probe_tree.h:437
STATIC_ASSERT(SHORT_CHAIN_HEADER_SIZE_MASK >=SHORT_CHAIN_HEADER_ELEMS)
void set_name(int name_)
Definition: probe_tree.h:422
PT2_TYPE
Definition: probe_tree.h:193
char * PT_WRITE_CHAIN_ENTRY(char *ptr, int refabspos, int name, const int apos)
Definition: probe_tree.h:542
void set_loc(AbsLoc &location)
Definition: probe_tree.h:560
void PT_write_compact_nat(char *&toMem, uint_32 nat)
Definition: PT_tools.h:197
int get_abs_pos() const
Definition: probe_tree.h:435
pt_global PT_GLOBAL
TYPE get_type() const
Definition: probe_tree.h:226
bool operator==(const AbsLoc &loc1, const AbsLoc &loc2)
Definition: probe_tree.h:489
Definition: probe.h:122
AbsLoc(int name_, int abs_pos)
Definition: probe_tree.h:429
void GBK_terminate(const char *error) __ATTR__NORETURN
Definition: arb_msg.cxx:509
POS_TREE1 * father
Definition: probe_tree.h:201
#define pt_assert_stage(s)
Definition: probe.h:41
bool is_equal(const DataLoc &other) const
Definition: probe_tree.h:479
bool is_chain() const
Definition: probe_tree.h:230
POS_TREE1 POS_TREE_TYPE
Definition: probe_tree.h:602
PT_base operator[](int offset) const
Definition: probe_tree.h:521
#define SHORT_CHAIN_HEADER_ELEMS
Definition: probe_tree.h:257
void set_father(POS_TREE1 *new_father)
Definition: probe_tree.h:215
static void error(const char *msg)
Definition: mkptypes.cxx:96
bool is_equal(const AbsLoc &other) const
Definition: probe_tree.h:439
DataLoc(int name_, int apos_, int rpos_)
Definition: probe_tree.h:456
const AbsLoc & at() const
Definition: probe_tree.h:685
#define SHORT_CHAIN_HEADER_FLAG_BIT
Definition: probe_tree.h:260
bool is_leaf() const
Definition: probe_tree.h:249
TYPE get_type() const
Definition: probe_tree.h:246
bool is_saved() const
Definition: probe_tree.h:231
#define pt_assert(bed)
Definition: PT_tools.h:22
bool is_leaf() const
Definition: probe_tree.h:229
unsigned name[SHORT_CHAIN_HEADER_ELEMS]
Definition: probe_tree.h:267
char * udata()
Definition: probe_tree.h:243
int get_refabspos() const
Definition: probe_tree.h:634
uchar flags
Definition: probe_tree.h:200
PT * PT_read_son(PT *node, PT_base base)
bool is_node() const
Definition: probe_tree.h:248
#define IS_SINGLE_BRANCH_NODE
Definition: probe_tree.h:150
ChainIteratorStage2(const POS_TREE2 *node)
Definition: probe_tree.h:668
uint_8 PT_read_char(const void *fromMem)
Definition: PT_tools.h:71
PT_base
Definition: probe.h:82
static TYPE flag_2_type[256]
Definition: probe_tree.h:205
bool valid_rel_pos(int rel_pos) const
Definition: probe.h:213
Definition: probe.h:89
char * udata()
Definition: probe_tree.h:209
POS_TREE1 * PT_read_son< POS_TREE1 >(POS_TREE1 *node, PT_base base)
Definition: probe_tree.h:401
unsigned char uchar
Definition: gde.hxx:21
const AbsLoc & at() const
Definition: probe_tree.h:629
int get_rel_pos() const
Definition: probe_tree.h:471
#define NULp
Definition: cxxforward.h:116
uint_32 PT_read_int(const void *fromMem)
Definition: PT_tools.h:73
unsigned char uint_8
Definition: PT_tools.h:26
bool is_node() const
Definition: probe_tree.h:228
#define offset(field)
Definition: GLwDrawA.c:73
void set_loc(AbsLoc &location)
Definition: probe_tree.h:570
uint_16 PT_read_short(const void *fromMem)
Definition: PT_tools.h:72
size_t PT_node_size(POS_TREE2 *node)
Definition: probe_tree.h:283
Definition: trnsprob.h:20
static void init_static()
bool has_valid_name() const
Definition: probe_tree.h:432
static void init_static()
unsigned abspos[SHORT_CHAIN_HEADER_ELEMS]
Definition: probe_tree.h:268
POS_TREE2 POS_TREE_TYPE
Definition: probe_tree.h:666
void clear_fathers()
int get_elements_ahead() const
Definition: probe_tree.h:632
bool is_chain() const
Definition: probe_tree.h:250
const ChainIteratorStage2 & operator++()
Definition: probe_tree.h:686
const char * memptr() const
Definition: probe_tree.h:688
char count_bits[PT_BASES+1][256]
Definition: probe_tree.h:32
struct PT_short_chain_header __attribute__
const char * udata() const
Definition: probe_tree.h:242
ChainIteratorStage1(const POS_TREE1 *node)
Definition: probe_tree.h:604
PT1_TYPE
Definition: probe_tree.h:185