ARB
PT_prefixtree.cxx
Go to the documentation of this file.
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 
23 
24 inline 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)
43 template <typename CHAINITER>
44 inline 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 
50 template <typename CHAINITER>
51 bool 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 
73 
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 
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 
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 
142  stage = stage_;
143  PT_GLOBAL.init();
145 }
146 
147 // ------------------------------
148 // functions for stage 1
149 
150 static void PT_change_link_in_father(POS_TREE1 *father, POS_TREE1 *old_link, POS_TREE1 *new_link) {
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 
163 class 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
172 public:
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 
199 void PT_add_to_chain(POS_TREE1 *node, const DataLoc& loc) {
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 
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 
278 POS_TREE1 *PT_change_leaf_to_node(POS_TREE1 *node) { // @@@ become member
280  pt_assert(node->is_leaf());
281 
282  POS_TREE1 *father = node->get_father();
283 
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 
293 POS_TREE1 *PT_leaf_to_chain(POS_TREE1 *node) { // @@@ become member
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 
318 POS_TREE1 *PT_create_leaf(POS_TREE1 **pfather, PT_base base, const DataLoc& loc) {
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 
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
422 void 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 
433 void 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 
444 void 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 
452 void 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 
459 static 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 
473 const int BITS_FOR_SIZE = 4; // size is stored inside POS_TREEx->flags, if it fits into lower 4 bits
474 const int SIZE_MASK = (1<<BITS_FOR_SIZE)-1;
475 
479 
482 
483 const int FLAG_SIZE_REDUCTION = MIN_SIZE_IN_FLAGS-1;
484 
485 static void PTD_set_object_to_saved_status(POS_TREE1 *node, long pos_start, uint_32 former_size) {
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 
507 inline 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 
518 static 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 
532 static long PTD_write_chain_to_disk(FILE *out, POS_TREE1 * const node, const long oldpos, ARB_ERROR& error) {
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)
592 void 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 
620  MEM.put(node, get_memsize_of_saved(node));
621  node = NULp;
622 }
623 
624 static 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 
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 
781 long 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 
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 
829 ARB_ERROR PTD_read_leafs_from_disk(const char *fname, POS_TREE2*& root_ptr) { // __ATTR__USERESULT
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 
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)
909 const 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 
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 
944 static 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 
973 struct EnterStage1 {
974  static bool initialized;
975  EnterStage1() {
976  if (initialized) PT_exit_psg();
977  PT_init_psg();
979  initialized = true;
980  }
981  ~EnterStage1() {
982  pt_assert(initialized);
983  PT_exit_psg();
984  initialized = false;
985  }
986 };
987 bool EnterStage1::initialized = false;
988 
989 void 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
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 
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 
1036 static POS_TREE1 *theChain = NULp;
1037 static DataLoc *theLoc = NULp;
1038 
1039 static 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 
1049 void 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));
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);
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
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 
1131 void 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 
1160 template<int R>
1161 static 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 
1188 template<int R>
1189 static 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 
1227 void 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 // --------------------------------------------------------------------------------
long PTD_save_upper_tree(FILE *out, POS_TREE1 *&node, long pos, long &node_pos, ARB_ERROR &error)
#define PT1_CHAIN_SHORT_HEAD_SIZE
Definition: probe_tree.h:165
const int FLAG_SIZE_REDUCTION
const char * GB_ERROR
Definition: arb_core.h:25
void PT_add_to_chain(POS_TREE1 *node, const DataLoc &loc)
Definition: probe.h:122
#define PT_SERVER_VERSION
Definition: probe.h:28
void set_type(TYPE type)
Definition: probe_tree.h:221
bool PT_chain_has_valid_entries(const typename CHAINITER::POS_TREE_TYPE *const node)
static TYPE flag_2_type[256]
Definition: probe_tree.h:239
const int SIZE_MASK
const char * get_mem() const
void PT_init_psg()
Definition: PT_main.cxx:131
void * PT_PNTR
Definition: PT_tools.h:24
uint_big PT_read_big(const void *fromMem)
Definition: PT_tools.h:78
group_matcher all()
Definition: test_unit.h:1000
#define PTM_MAX_SIZE
Definition: PT_mem.h:44
Definition: probe.h:83
#define SHORT_CHAIN_HEADER_SIZE_MASK
Definition: probe_tree.h:261
const uint_32 MIN_SIZE_IN_FLAGS
const char * udata() const
Definition: probe_tree.h:208
#define PT1_NODE_SIZE(node)
Definition: probe_tree.h:175
STATIC_ASSERT(PT1_BASE_SIZE<=PT1_EMPTY_LEAF_SIZE)
Definition: probe.h:84
void PTD_put_int(FILE *out, ULONG i)
void PTD_delete_saved_node(POS_TREE1 *&node)
#define PT1_EMPTY_NODE_SIZE
Definition: probe_tree.h:167
void PT_write_short(void *toMem, uint_16 i)
Definition: PT_tools.h:82
int get_name() const
Definition: probe_tree.h:434
int main(int argc, char **argv)
Definition: aisc.c:359
POS_TREE1 * get_father() const
Definition: probe_tree.h:211
probe_struct_global psg
Definition: PT_main.cxx:36
#define ASSERT_RESULT(Type, Expected, Expr)
Definition: arb_assert.h:336
GB_ERROR GB_IO_error(const char *action, const char *filename)
Definition: arb_msg.cxx:293
unsigned long ULONG
Definition: probe.h:50
void PTD_put_longlong(FILE *out, ULONG i)
Definition: probe.h:85
int get_memsize_of_saved(const POS_TREE1 *node)
const char * GBS_global_string(const char *templat,...)
Definition: arb_msg.cxx:204
#define FLAG_FREE_BITS
Definition: probe_tree.h:181
ARB_ERROR PTD_read_leafs_from_disk(const char *fname, POS_TREE2 *&root_ptr)
const uint_32 MAX_SIZE_IN_FLAGS
void * get(int size)
Definition: PT_mem.h:248
Stage
Definition: probe.h:122
int get_refabspos() const
probe_statistic_struct stat
Definition: probe.h:379
long GB_size_of_file(const char *path)
Definition: arb_file.cxx:28
unsigned int uint_32
Definition: PT_tools.h:28
char buffer[MESSAGE_BUFFERSIZE]
Definition: seq_search.cxx:34
#define PT_SHORT_SIZE
Definition: probe_tree.h:28
void PT_write_char(void *toMem, uint_8 i)
Definition: PT_tools.h:81
#define PT1_EMPTY_LEAF_SIZE
Definition: probe_tree.h:163
#define PT1_MIN_CHAIN_ENTRY_SIZE
Definition: probe_tree.h:169
static bool initialized
Definition: AW_advice.cxx:36
POS_TREE1 * father
Definition: probe_tree.h:39
void PTD_put_byte(FILE *out, ULONG i)
#define PT1_CHAIN_LONG_HEAD_SIZE
Definition: probe_tree.h:166
void enter_stage(Stage stage_)
static long PTD_write_chain_to_disk(FILE *out, POS_TREE1 *const node, const long oldpos, ARB_ERROR &error)
ChainEntryBuffer(int forElements, int refabspos_, int lastname_)
uchar flags
Definition: probe_tree.h:38
GB_ERROR GB_await_error()
Definition: arb_msg.cxx:353
static int diff(int v1, int v2, int v3, int v4, int st, int en)
Definition: ClustalV.cxx:534
#define TEST_EXPECT(cond)
Definition: test_unit.h:1312
void PT_exit_psg()
Definition: PT_main.cxx:137
PT2_TYPE
Definition: probe_tree.h:193
void PT_write_pointer(void *toMem, const void *thePtr)
Definition: PT_tools.h:206
unsigned int nat
Definition: gb_aci_impl.h:61
#define PT1_MAX_CHAIN_ENTRY_SIZE
Definition: probe_tree.h:170
#define PT1_LEAF_SIZE(leaf)
Definition: probe_tree.h:164
void PT_write_compact_nat(char *&toMem, uint_32 nat)
Definition: PT_tools.h:197
GB_ERROR deliver() const
Definition: arb_error.h:114
int get_abs_pos() const
Definition: probe_tree.h:435
TYPE get_type() const
Definition: probe_tree.h:226
#define does_differ_from(val)
Definition: test_unit.h:1015
long PTD_write_leafs_to_disk(FILE *out, POS_TREE1 *const node, long pos, long *node_pos, ARB_ERROR &error)
static long PTD_write_tip_to_disk(FILE *out, POS_TREE1 *node, const long oldpos)
static void PTD_set_object_to_saved_status(POS_TREE1 *node, long pos_start, uint_32 former_size)
Definition: probe.h:122
void GBK_terminate(const char *error) __ATTR__NORETURN
Definition: arb_msg.cxx:463
POS_TREE1 * father
Definition: probe_tree.h:201
#define pt_assert_stage(s)
Definition: probe.h:41
#define PT1_BASE_SIZE
Definition: probe_tree.h:161
#define SHORT_CHAIN_HEADER_ELEMS
Definition: probe_tree.h:257
void PT_init_cache_sizes(Stage stage)
void set_father(POS_TREE1 *new_father)
Definition: probe_tree.h:215
char * GB_map_file(const char *path, int writeable)
Definition: adsocket.cxx:344
static void error(const char *msg)
Definition: mkptypes.cxx:96
size_t get_size() const
#define SIZE
Definition: date.cxx:7
fputc('\n', stderr)
expectation_group & add(const expectation &e)
Definition: test_unit.h:801
struct pt_global PT_GLOBAL
#define that(thing)
Definition: test_unit.h:1032
static void PT_change_link_in_father(POS_TREE1 *father, POS_TREE1 *old_link, POS_TREE1 *new_link)
#define SHORT_CHAIN_HEADER_FLAG_BIT
Definition: probe_tree.h:260
Definition: probe.h:86
bool is_saved() const
Definition: probe_tree.h:231
bool locs_in_chain_order(const AbsLoc &loc1, const AbsLoc &loc2)
#define pt_assert(bed)
Definition: PT_tools.h:22
bool is_leaf() const
Definition: probe_tree.h:229
POS_TREE1 * PT_leaf_to_chain(POS_TREE1 *node)
#define PT_SERVER_MAGIC
Definition: probe.h:27
POS_TREE1 * PT_create_leaf(POS_TREE1 **pfather, PT_base base, const DataLoc &loc)
void add(const AbsLoc &loc)
unsigned name[SHORT_CHAIN_HEADER_ELEMS]
Definition: probe_tree.h:267
int get_refabspos() const
Definition: probe_tree.h:634
uchar flags
Definition: probe_tree.h:200
#define __ATTR__DONT_VECTORIZE_HERE
PT * PT_read_son(PT *node, PT_base base)
static long PTD_write_node_to_disk(FILE *out, POS_TREE1 *node, long *r_poss, const long oldpos)
#define is_equal_to(val)
Definition: test_unit.h:1014
#define TEST_EXPECTATION(EXPCTN)
Definition: test_unit.h:1037
uint_8 PT_read_char(const void *fromMem)
Definition: PT_tools.h:71
#define PTM_MIN_SIZE
Definition: PT_mem.h:35
PT_base
Definition: probe.h:82
void clear()
Definition: PT_mem.h:298
const char * get_blocksize_description(int blocksize)
#define TEST_EXPECT_NULL(n)
Definition: test_unit.h:1307
Memory MEM
Definition: PT_main.cxx:128
#define TEST_EXPECT_CODE_ASSERTION_FAILS(cb)
Definition: test_unit.h:1241
aisc_com * link
static TYPE flag_2_type[256]
Definition: probe_tree.h:205
#define CACHE_SEQ_PERCENT
static void set_cache_sizes(size_t seq_cache_size, size_t abs_cache_size)
Definition: probe.h:158
uint_32 uint_big
Definition: PT_tools.h:34
const int BITS_FOR_SIZE
void PTD_debug_nodes(void)
Definition: probe.h:89
#define TEST_EXPECT_NO_ERROR(call)
Definition: test_unit.h:1107
void put(void *vblock, int size)
Definition: PT_mem.h:272
const AbsLoc & at() const
Definition: probe_tree.h:629
int get_rel_pos() const
Definition: probe_tree.h:471
#define NULp
Definition: cxxforward.h:97
uint_32 PT_read_int(const void *fromMem)
Definition: PT_tools.h:73
int get_lastname() const
unsigned char uint_8
Definition: PT_tools.h:26
bool is_node() const
Definition: probe_tree.h:228
uint_16 PT_read_short(const void *fromMem)
Definition: PT_tools.h:72
void PT_write_big(void *toMem, uint_big i)
Definition: PT_tools.h:88
#define pt_assert_valid_chain_stage1(node)
Definition: probe.h:47
static void init_static()
bool is_clear() const
Definition: PT_mem.h:297
static void init_static()
unsigned abspos[SHORT_CHAIN_HEADER_ELEMS]
Definition: probe_tree.h:268
#define PT1_NODE_WITHSONS_SIZE(sons)
Definition: probe_tree.h:172
void clear_fathers()
int get_elements_ahead() const
Definition: probe_tree.h:632
char count_bits[PT_BASES+1][256]
Definition: probe_tree.h:32
#define TEST_EXPECT_EQUAL(expr, want)
Definition: test_unit.h:1283
void PTD_put_short(FILE *out, ULONG i)
long PTD_save_lower_tree(FILE *out, POS_TREE1 *node, long pos, ARB_ERROR &error)
Definition: probe.h:87
static int put_compact_nat(FILE *out, uint_32 nat)
void PT_write_int(void *toMem, uint_32 i)
Definition: PT_tools.h:83
POS_TREE1 * PT_change_leaf_to_node(POS_TREE1 *node)
PT1_TYPE
Definition: probe_tree.h:185
#define max(a, b)
Definition: f2c.h:154