1.1.2.3 Static BST Internal And Array Organized Leaf Nodes Sequence

The B-tree external nodes are organized as plain arrays.

The B-tree internal nodes are organized as self balancing, array based BSTs. The editing of the array based BSTs has linear complexity, whereas the editing of the dynamic AVL BSTs has logarithmic complexity. Nonetheless, for their regular memory layout the array based BSTs may outperform the AVL BSTs for small enough sizes. The retrieval complexity is for the arrays based BSTs (as is for the AVL BSTs) logarithmic.

Types:

typedef struct x1f4_qsrate_type {
    unsigned quarter, rate, size;
    void *trans;
} x1f4_qsrate_type;

See Fixed Size Data Sequence Types.

The extra features in the struct x1f4_qsrate_type are the quarter and rate unsigned fields, specifying quarter the maximal population count to be stored in external B-tree nodes and log 2 the maximal population count to be stored in internal B-tree nodes, respectively. Both fields usage is restricted to express request and sensible default values are provided for them.

Construction definitions:

X1f4_QSRATE_FOUR_FRAME

indicates the sequence constructor routines that the quarter the maximal population count to be stored in external B-tree nodes specified by the quarter field of their struct x1f4_qsrate_type * argument is to be observed.

X1f4_QSRATE_RATE_FRAME

indicates the sequence constructor routines that the log 2 the maximal population count to be stored in internal B-tree nodes specified by the rate field of their struct x1f4_qsrate_type * argument is to be observed.

General library:

See Fixed Size Data Sequence Library.

• The call data structure size retriever:

  extern int x1f4_call_qsrate(unsigned *);
  

• The case data structure state retriever:

  extern int x1f4_case_qsrate(void *);
  

• The dash data deletion routine:

  extern int x1f4_dash_qsrate(void *, unsigned, unsigned);
  

• The ever record retriever:

  extern int x1f4_ever_qsrate(void *, void **);
  

• The fast sequence constructor routine:

  extern int x1f4_fast_qsrate(void *, unsigned, struct x1f4_qsrate_type *);
  

• The fini sequence regular destructor routine:

  extern int x1f4_fini_qsrate(void **);
  

• The flat sequence destructor routine:

  extern int x1f4_flat_qsrate(void *);
  

• The flip order reversal routine:

  extern int x1f4_flip_qsrate(void *);
  

• The flow data structure consistency check routine:

  extern int x1f4_flow_qsrate(void *);
  

• The head plain data insertion routine:

  extern int x1f4_head_qsrate(void *, void **);
  

• The high data purge routine:

  extern int x1f4_high_qsrate(void *);
  

• The init sequence regular constructor routine:

  extern int x1f4_init_qsrate(void **, unsigned, struct x1f4_qsrate_type *);
  

• The join sequence consolidation routine:

  extern int x1f4_join_qsrate(void *, void *);
  

• The lead record retriever:

  extern int x1f4_lead_qsrate(void *, void **);
  

• The lime data traversal routine:

  extern int x1f4_lime_qsrate(void *, void *, int (*)(void *, void *));
  

• The line data copy routine:

  extern int x1f4_line_qsrate
      (void *, void *, int (*)(void *, void *, const void *),
       int (*)(void *, void *), void *);
  

• The mind data deletion routine:

  extern int x1f4_mind_qsrate(void *);
  

• The miss plain data deletion routine:

  extern int x1f4_miss_qsrate(void *, unsigned);
  

• The over data traversal routine:

  extern int x1f4_over_qsrate
      (void *, unsigned, unsigned, void *, int (*)(void *, void *));
  

• The peek plain data retrieval routine:

  extern int x1f4_peek_qsrate(void *, unsigned, void **);
  

• The pull data deletetion routine:

  extern int x1f4_pull_qsrate
      (void *, unsigned, void *, int (*)(void *, void *));
  

• The push plain data insertion routine:

  extern int x1f4_push_qsrate(void *, unsigned, void **);
  

• The rand data shuffling routine:

  extern int x1f4_rand_qsrate(void *);
  

• The size size retriever:

  extern int x1f4_size_qsrate(void *, unsigned *);
  

• The slip data deletion routine:

  extern int x1f4_slip_qsrate(void *);
  

• The star sequence resizer routine:

  extern int x1f4_star_qsrate(void *, unsigned);
  

• The swap data swap routine:

  extern int x1f4_swap_qsrate(void *, void *);
  

• The tail plain data insertion routine:

  extern int x1f4_tail_qsrate(void *, void **);
  

• The tear sequence partition routine:

  extern int x1f4_tear_qsrate(void *, unsigned, void *);
  

• The text plain copy routine:

  extern int x1f4_text_qsrate
      (void **, void *, int (*)(void *, void *, const void *),
       int (*)(void *, void *), void *);