17 #include <bits/wordsize.h>
20 #ifndef STATIC_ASSERT_H
27 #define PT_CHAIN_NTERM 250
28 #define PT_SHORT_SIZE 0xffff
29 #define PT_INIT_CHAIN_SIZE 20
150 #define IS_SINGLE_BRANCH_NODE 0x40
152 # define INT_SONS 0x80
153 # define LONG_SONS 0x40
155 # define LONG_SONS 0x80
161 #define PT1_BASE_SIZE sizeof(POS_TREE1) // flag + father
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
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))
172 #define PT1_NODE_WITHSONS_SIZE(sons) (PT1_EMPTY_NODE_SIZE+sizeof(PT_PNTR)*(sons))
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))
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)
208 const char *
udata()
const {
return ((
const char*)
this)+
sizeof(*this); }
209 char *
udata() {
return ((
char*)
this)+
sizeof(*this); }
242 const char *
udata()
const {
return ((
const char*)
this)+
sizeof(*this); }
243 char *
udata() {
return ((
char*)
this)+
sizeof(*this); }
255 #define SHORT_CHAIN_HEADER_ELEMS 4
256 #else // !defined(ARB_64)
257 #define SHORT_CHAIN_HEADER_ELEMS 3
260 #define SHORT_CHAIN_HEADER_FLAG_BIT (1<<4)
261 #define SHORT_CHAIN_HEADER_SIZE_MASK 0x07
294 else if (sec & INT_SONS) {
301 if (sec & LONG_SONS) {
319 if (base != (node->flags & 0x7))
return NULp;
320 long i = (node->flags >> 3)&0x7;
321 if (!i) i = 1;
else i+=2;
325 if (!((1<<base) & node->flags)) {
330 long i = PT_GLOBAL.
count_bits[base][node->flags];
333 char *sons = node->udata()+1;
337 if (sec & INT_SONS) {
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");
344 printf(
"Warning: A search tree of this size is not tested.\n");
345 printf(
" (sec & LONG_SON) == true\n");
348 if ((1<<base) & sec) {
349 i = PT_read_long(sons+offset);
358 if (sec & INT_SONS) {
360 if ((1<<base) & sec) {
369 if ((1<<base) & sec) {
378 if (sec & LONG_SONS) {
380 if ((1<<base) & sec) {
389 if ((1<<base) & sec) {
403 if (!((1<<base) & node->flags))
return NULp;
405 return PT_read_pointer<POS_TREE1>(node->udata() +
sizeof(
PT_PNTR)*base);
429 AbsLoc(
int name_,
int abs_pos) : name(name_), apos(abs_pos) {}
439 bool is_equal(
const AbsLoc& other)
const {
return apos == other.apos && name == other.name; }
442 void dump(FILE *fp)
const {
443 fprintf(fp,
" apos=%6i name=%6i='%s'\n",
457 template <
typename PT>
explicit DataLoc(
const PT *node) {
459 const char *data = node->udata();
482 void dump(FILE *fp)
const {
483 fprintf(fp,
" apos=%6i rpos=%6i name=%6i='%s'\n",
496 mutable SmartCharPtr seq;
501 :
DataLoc(name_, apos_, rpos_),
503 seq(pid.get_dataPtr()),
509 seq(pid.get_dataPtr()),
515 seq(pid.get_dataPtr()),
535 uint_32 name = loc.
get_name() + read_nat_with_reserved_bits<1>(ptr, has_main_apos);
544 bool has_main_apos = (apos == refabspos);
545 write_nat_with_reserved_bits<1>(ptr, name, has_main_apos);
574 location =
AbsLoc(name, abspos);
582 bool at_end_of_chain()
const {
return elements_ahead<0; }
583 void set_loc_from_chain() {
585 if (elements_ahead>0) {
586 if (is_short) iter.S.set_loc(loc);
587 else iter.L.set_loc(loc);
598 set_loc_from_chain();
613 iter.S.next_entry = 0;
619 elements_ahead = header->
entries;
625 set_loc_from_chain();
628 operator bool()
const {
return !at_end_of_chain(); }
636 ? iter.S.header->abspos[0]
648 bool at_end_of_chain()
const {
return elements_ahead<0; }
649 void set_loc_from_chain() {
650 if (elements_ahead>0) {
662 set_loc_from_chain();
669 : data(node->
udata()),
681 set_loc_from_chain();
684 operator bool()
const {
return !at_end_of_chain(); }
688 const char *
memptr()
const {
return data; }
697 error = func(entry.at());
706 error = func(entry.at());
712 struct PTD_chain_print {
713 int operator()(
const AbsLoc& loc) { loc.dump(stdout);
return 0; }
718 #error probe_tree.h included twice
719 #endif // PROBE_TREE_H
struct probe_input_data * data
ReadableDataLoc(int name_, int apos_, int rpos_)
size_t PT_leaf_size(POS_TREE2 *node)
static TYPE flag_2_type[256]
#define SHORT_CHAIN_HEADER_SIZE_MASK
const char * udata() const
ReadableDataLoc(const PT *node)
const ChainIteratorStage1 & operator++()
int PT_forwhole_chain(PT *node, T &func)
const probe_input_data & get_pid() const
POS_TREE1 * get_father() const
void set_position(int abs_pos, int rel_pos)
const char * udata() const
const PT_short_chain_header * header
void set_abs_pos(int abs_pos)
DataLoc(const AbsLoc &aloc)
POS_TREE2 * PT_read_son< POS_TREE2 >(POS_TREE2 *node, PT_base base)
bool has_valid_positions() const
ReadableDataLoc(const DataLoc &loc)
const char * PT_READ_CHAIN_ENTRY_stage_2(const char *ptr, int refabspos, AbsLoc &loc)
const probe_input_data & get_pid() const
STATIC_ASSERT(SHORT_CHAIN_HEADER_SIZE_MASK >=SHORT_CHAIN_HEADER_ELEMS)
char * PT_WRITE_CHAIN_ENTRY(char *ptr, int refabspos, int name, const int apos)
void set_loc(AbsLoc &location)
bool operator==(const AbsLoc &loc1, const AbsLoc &loc2)
AbsLoc(int name_, int abs_pos)
void GBK_terminate(const char *error) __ATTR__NORETURN
#define pt_assert_stage(s)
bool is_equal(const DataLoc &other) const
PT_base operator[](int offset) const
#define SHORT_CHAIN_HEADER_ELEMS
void set_father(POS_TREE1 *new_father)
static void error(const char *msg)
bool is_equal(const AbsLoc &other) const
DataLoc(int name_, int apos_, int rpos_)
const AbsLoc & at() const
#define SHORT_CHAIN_HEADER_FLAG_BIT
int get_refabspos() const
PT * PT_read_son(PT *node, PT_base base)
#define IS_SINGLE_BRANCH_NODE
ChainIteratorStage2(const POS_TREE2 *node)
static TYPE flag_2_type[256]
POS_TREE1 * PT_read_son< POS_TREE1 >(POS_TREE1 *node, PT_base base)
const AbsLoc & at() const
void set_loc(AbsLoc &location)
size_t PT_node_size(POS_TREE2 *node)
static void init_static()
bool has_valid_name() const
static void init_static()
int get_elements_ahead() const
const ChainIteratorStage2 & operator++()
const char * memptr() const
char count_bits[PT_BASES+1][256]
struct PT_short_chain_header __attribute__
const char * udata() const
ChainIteratorStage1(const POS_TREE1 *node)