home *** CD-ROM | disk | FTP | other *** search
/ Xentax forum attachments archive / xentax.7z / 7662 / gttool_src_bin.7z / gttool / src / btree.cpp next >
Encoding:
C/C++ Source or Header  |  2014-02-21  |  6.1 KB  |  152 lines
  1. #include "btree.h"
  2.  
  3. void BTreeBase::traverse(TraverseCallback* callback, void* const arg) const
  4. {
  5.     const uint16_t num_nodes = data_at<uint16_t>(table_data_, sizeof(uint32_t));
  6.     const void* node_data = advance_pointer(table_data_, sizeof(uint32_t) + sizeof(num_nodes));
  7.     for (uint32_t i = 0; i < num_nodes; ++i) {
  8.         const uint32_t num_keys = extract_twelve_bits(node_data, 0) & 0x7FF;
  9.         const uint32_t next_node_data_offset = extract_twelve_bits(node_data, num_keys + 1);
  10.         for (uint32_t j = 0; j < num_keys; ++j) {
  11.             const uint32_t node_offset = extract_twelve_bits(node_data, j + 1);
  12.             const void* node = advance_pointer(node_data, node_offset);
  13.             if (callback) {
  14.                 if ((*callback)(node, arg) < 0)
  15.                     return;
  16.             }
  17.         }
  18.         node_data = advance_pointer(node_data, next_node_data_offset);
  19.     }
  20. }
  21.  
  22. const void* BTreeBase::search(const uint32_t index) const
  23. {
  24.     const uint32_t num_child_nodes = data_at<uint8_t>(table_data_, 0);
  25.     uint32_t node_data_offset = data_at<uint32_t>(table_data_, 0) & 0xFFFFFF;
  26.     const void* node_data = advance_pointer(table_data_, node_data_offset);
  27.     uint32_t key_index_start = 0;
  28.     bool found = false;
  29.     for (uint32_t i = num_child_nodes; i != 0 && !found; --i) {
  30.         const void* node = nullptr;
  31.         const uint32_t num_keys = extract_twelve_bits(node_data, 0) & 0x7FF;
  32.         for (uint32_t j = 0; j < num_keys; ++j) {
  33.             const uint32_t node_offset = extract_twelve_bits(node_data, j + 1);
  34.             node = advance_pointer(node_data, node_offset);
  35.             const uint32_t next_key_index = extract_value_and_advance(&node);
  36.             if (index < next_key_index) {
  37.                 found = true;
  38.                 break;
  39.             }
  40.             key_index_start = next_key_index;
  41.         }
  42.         if (!node)
  43.             break;
  44.         node = skip_node_data(node);
  45.         node_data_offset = extract_value_and_advance(&node);
  46.         node_data = advance_pointer(table_data_, node_data_offset);
  47.     }
  48.     if (true /* found */) { // FIXME: check this
  49.         const uint32_t num_keys = extract_twelve_bits(node_data, 0) & 0x7FF;
  50.         const uint32_t node_offset = extract_twelve_bits(node_data, (index - key_index_start) + 1);
  51.         const void* const node = advance_pointer(node_data, node_offset);
  52.         return node;
  53.     }
  54.     return nullptr;
  55. }
  56.  
  57. const void* BTreeBase::search(const void* const key, uint32_t* const index) const
  58. {
  59.     uint32_t lower_bound = 0;
  60.     uint32_t upper_bound = 0;
  61.     uint32_t max_key_index = 0;
  62.  
  63.     const uint32_t num_child_nodes = data_at<uint8_t>(table_data_, 0);
  64.     uint32_t node_data_offset = data_at<uint32_t>(table_data_, 0) & 0xFFFFFF;
  65.     const void* node_data = advance_pointer(table_data_, node_data_offset);
  66.     for (uint32_t i = num_child_nodes; i != 0; --i) {
  67.         const void* node = search_with_cmp(node_data, key, less_than_op_, &lower_bound, &upper_bound, true);
  68.         if (!node) {
  69.             if (lower_bound != upper_bound) {
  70.                 const uint32_t node_offset = extract_twelve_bits(node_data, lower_bound + 1);
  71.                 node = advance_pointer(node_data, node_offset);
  72.             }
  73.             if (!node)
  74.                 return nullptr;
  75.         }
  76.         max_key_index = extract_value_and_advance(&node);
  77.         node = skip_node_data(node);
  78.         node_data_offset = extract_value_and_advance(&node);
  79.         node_data = advance_pointer(table_data_, node_data_offset);
  80.     }
  81.  
  82.     const void* const node = search_with_cmp(node_data, key, equal_op_, &lower_bound, &upper_bound, false);
  83.     if (index) {
  84.         if (!num_child_nodes)
  85.             upper_bound = 0;
  86.         *index = node ? (max_key_index - upper_bound + lower_bound) : kINVALID_INDEX;
  87.     }
  88.  
  89.     return node;
  90. }
  91.  
  92. //    ╤ ∩ε∞ε∙ⁿ■ ßΦφα≡φεπε ∩εΦ±Ωα ∩ε ≥αßδΦ÷σ ±∞σ∙σφΦΘ φα⌡εΣΦ∞ ≥ε, ΩαΩεσ ≤Ωατ√Γασ≥ φα φα° Ωδ■≈
  93. // Φ ΓετΓ≡α∙ασ∞ σπε ΦφΣσΩ±.
  94. //    ╚φΣσΩ±√ ΩαµΣεπε ΦΣ≤≥ ∩ε±δσΣεΓα≥σδⁿφε, φα≈Φφα  ± 0, high ≤Ωατ√Γασ≥ φα ΦφΣσΩ±, φα⌡εΣ ∙ΦΘ±  τα
  95. // ∩ε±δσΣφΦ∞, ≥.σ.:
  96. //      high-low=num_indices ΦδΦ high=num_indices, ≥.Ω. low=0 ΦδΦ high=last_index+1
  97. //    ─αφφ√σ ∩ε±δσΣ≤■∙σπε ≤τδα (α Φ∞σφφε - ≥αßδΦ÷α ±∞σ∙σφΦΘ Φ ±α∞Φ Ωδ■≈Φ) ΦΣ≤≥ ±≡ατ≤ τα ∩≡σΣ√Σ≤∙Φ∞
  98. // ≤τδε∞, Ω≡ε∞σ ≥επε, ΦφΣσΩ±√ Γ φεΓε∞ ≤τδσ φα≈Φφα■≥±  ±ε τφα≈σφΦ  high (ΦδΦ last_index+1) Γ ∩≡σΣ√Σ≤∙σ∞.
  99. //    max_key_index Σδ  ∩ε±δσΣ≤■∙σπε ≤τδα  Γ√±≈Φ≥√Γασ≥±  ∩ε ⌠ε≡∞≤δσ: max_key_index=prev_high+(high-low),
  100. //  ≥.σ. ΩαΩ ±≤∞∞α τφα≈σφΦ  ΦφΣσΩ±α, ±δσΣ≤■∙σπε τα ∩ε±δσΣφΦ∞ ²δσ∞σφ≥ε∞ ∩≡ε°δεπε ≤τδα, Φ ≡ατφΦ÷√
  101. //  ∞σµΣ≤ ≥αΩΦ∞ µσ ΦφΣσΩ±ε∞ Φ ±≥α≡≥εΓ√∞ φεΓεπε ≤τδα.
  102. //    ─ε∩≤±≥Φ∞, ≈≥ε Φ∞σ■≥±  ΣΓα ≤τδα ± ΦφΣσΩ±α∞Φ 0-9 Φ 10-15 ±εε≥Γσ≥±≥Γσφφε.
  103. //    ─δ  ∩σ≡Γεπε ≤τδα ∩εδ≤≈Φ∞ τφα≈σφΦ : low=0, high=10, Σδ  Γ≥ε≡επε ≤τδα: low=0, high=7.
  104. //    ╥αΩΦ∞ εß≡ατε∞, max_key_index Γ≥ε≡επε ≤τδα ß≤Σσ≥ ≡αΓσφ: max_key_index=10+(7-0)=17.
  105. //    ╩αµΣεσ ±∞σ∙σφΦσ ταφΦ∞ασ≥ 12 ßΦ≥, ∩ε±δσ ∩ε±δσΣφσπε ±∞σ∙σφΦ  φα Ωδ■≈ ΦΣσ≥ ±∞σ∙σφΦσ Ω ±δσΣ≤■∙σ∞≤
  106. // ≤τδ≤. ┬±σ ±∞σ∙σφΦ  ταΣα■≥±  ε≥φε±Φ≥σδⁿφεπε φα≈αδε Σαφφ√⌡ ßδεΩα, Ωε≥ε≡√Θ Γ Σαφφ√Θ ∞ε∞σφ≥ εß≡αßα≥√Γασ∞.
  107. //    ╧σ≡Γεσ ±∞σ∙σφΦσ Γ °α∩Ωσ ⌠αΘδα ≤Ωατ√Γασ≥ φα φα≈αδε Σαφφ√⌡ Ωε≡φσΓεπε ≤τδα, Γ °α∩Ωσ Ωε≥ε≡επε
  108. // τα∩Φ±αφε ΩεδΦ≈σ±≥Γε Σε≈σ≡φΦ⌡ ≤τδεΓ Φ ±∞σ∙σφΦσ Ω Σαφφ√∞ ±α∞επε Ωε≡φσΓεπε ≤τδα. !!![─αδσσ ≡α±∩εδεµσφ√
  109. // Σαφφ√σ Σε≈σ≡φΦ⌡ ≤τδεΓ, Γ φα≈αδσ Ωε≥ε≡√⌡ ε∩ ≥ⁿ ΦΣσ≥ ≈Φ±δε Σε≈σ≡φΦ⌡ ≤τδεΓ Φ ±∞σ∙σφΦσ Ω Σαφφ√∞ ²≥επε
  110. // ≤τδα, ∩ε±δσ ≈σπε ε∩ ≥ⁿ Σαφφ√σ Σε≈σ≡φΦ⌡ ≤τδεΓ Φ ≥.Σ.]!!!
  111. const void* BTreeBase::search_with_cmp(const void* const node_data, const void* const key, KeyComparsionOp* const op, uint32_t* const lower_bound, uint32_t* const upper_bound, const bool is_internal) const
  112. {
  113.     uint32_t low = 0;
  114.     uint32_t high = extract_twelve_bits(node_data, 0) & 0x7FF;
  115.  
  116.      *upper_bound = high;
  117.     if (high != 0) {
  118.         do {
  119.             const uint32_t mid = low + (high - low) / 2;
  120.             const uint32_t node_offset = extract_twelve_bits(node_data, mid + 1);
  121.             const void* const node = advance_pointer(node_data, node_offset);
  122.             int cmp = (*op)(key, node);
  123.             if (!cmp) {
  124.                 *lower_bound = mid;
  125.                 return node;
  126.             } else if (cmp < 0) {
  127.                 high = mid;
  128.             } else if (cmp > 0) {
  129.                 low = mid + 1;
  130.             }
  131.         } while (low < high);
  132.     }
  133.     *lower_bound = low;
  134.  
  135.     return nullptr;
  136. }
  137.  
  138. uint32_t extract_value_and_advance(const void** const ptr)
  139. {
  140.     const uint8_t* p = static_cast<const uint8_t*>(*ptr);
  141.     uint32_t value = *p++;
  142.     if ((value & 0x80) != 0) {
  143.         uint32_t mask = 0x80;
  144.         do {
  145.             value = ((value - mask) << 8) + *p++;
  146.             mask = mask << 7;
  147.         } while ((value & mask) != 0);
  148.     }
  149.     *ptr = p;
  150.     return value;
  151. }
  152.