1 #ifndef MARISA_GRIMOIRE_TRIE_LOUDS_TRIE_H_ 2 #define MARISA_GRIMOIRE_TRIE_LOUDS_TRIE_H_ 3 4 #include "marisa/keyset.h" 5 #include "marisa/agent.h" 6 #include "marisa/grimoire/vector.h" 7 #include "marisa/grimoire/trie/config.h" 8 #include "marisa/grimoire/trie/key.h" 9 #include "marisa/grimoire/trie/tail.h" 10 #include "marisa/grimoire/trie/cache.h" 11 12 namespace marisa { 13 namespace grimoire { 14 namespace trie { 15 16 class LoudsTrie { 17 public: 18 LoudsTrie(); 19 ~LoudsTrie(); 20 21 void build(Keyset &keyset, int flags); 22 23 void map(Mapper &mapper); 24 void read(Reader &reader); 25 void write(Writer &writer) const; 26 27 bool lookup(Agent &agent) const; 28 void reverse_lookup(Agent &agent) const; 29 bool common_prefix_search(Agent &agent) const; 30 bool predictive_search(Agent &agent) const; 31 num_tries()32 std::size_t num_tries() const { 33 return config_.num_tries(); 34 } num_keys()35 std::size_t num_keys() const { 36 return size(); 37 } num_nodes()38 std::size_t num_nodes() const { 39 return (louds_.size() / 2) - 1; 40 } 41 cache_level()42 CacheLevel cache_level() const { 43 return config_.cache_level(); 44 } tail_mode()45 TailMode tail_mode() const { 46 return config_.tail_mode(); 47 } node_order()48 NodeOrder node_order() const { 49 return config_.node_order(); 50 } 51 empty()52 bool empty() const { 53 return size() == 0; 54 } size()55 std::size_t size() const { 56 return terminal_flags_.num_1s(); 57 } 58 std::size_t total_size() const; 59 std::size_t io_size() const; 60 61 void clear(); 62 void swap(LoudsTrie &rhs); 63 64 private: 65 BitVector louds_; 66 BitVector terminal_flags_; 67 BitVector link_flags_; 68 Vector<UInt8> bases_; 69 FlatVector extras_; 70 Tail tail_; 71 scoped_ptr<LoudsTrie> next_trie_; 72 Vector<Cache> cache_; 73 std::size_t cache_mask_; 74 std::size_t num_l1_nodes_; 75 Config config_; 76 Mapper mapper_; 77 78 void build_(Keyset &keyset, const Config &config); 79 80 template <typename T> 81 void build_trie(Vector<T> &keys, 82 Vector<UInt32> *terminals, const Config &config, std::size_t trie_id); 83 template <typename T> 84 void build_current_trie(Vector<T> &keys, 85 Vector<UInt32> *terminals, const Config &config, std::size_t trie_id); 86 template <typename T> 87 void build_next_trie(Vector<T> &keys, 88 Vector<UInt32> *terminals, const Config &config, std::size_t trie_id); 89 template <typename T> 90 void build_terminals(const Vector<T> &keys, 91 Vector<UInt32> *terminals) const; 92 93 void reserve_cache(const Config &config, std::size_t trie_id, 94 std::size_t num_keys); 95 template <typename T> 96 void cache(std::size_t parent, std::size_t child, 97 float weight, char label); 98 void fill_cache(); 99 100 void map_(Mapper &mapper); 101 void read_(Reader &reader); 102 void write_(Writer &writer) const; 103 104 inline bool find_child(Agent &agent) const; 105 inline bool predictive_find_child(Agent &agent) const; 106 107 inline void restore(Agent &agent, std::size_t node_id) const; 108 inline bool match(Agent &agent, std::size_t node_id) const; 109 inline bool prefix_match(Agent &agent, std::size_t node_id) const; 110 111 void restore_(Agent &agent, std::size_t node_id) const; 112 bool match_(Agent &agent, std::size_t node_id) const; 113 bool prefix_match_(Agent &agent, std::size_t node_id) const; 114 115 inline std::size_t get_cache_id(std::size_t node_id, char label) const; 116 inline std::size_t get_cache_id(std::size_t node_id) const; 117 118 inline std::size_t get_link(std::size_t node_id) const; 119 inline std::size_t get_link(std::size_t node_id, 120 std::size_t link_id) const; 121 122 inline std::size_t update_link_id(std::size_t link_id, 123 std::size_t node_id) const; 124 125 // Disallows copy and assignment. 126 LoudsTrie(const LoudsTrie &); 127 LoudsTrie &operator=(const LoudsTrie &); 128 }; 129 130 } // namespace trie 131 } // namespace grimoire 132 } // namespace marisa 133 134 #endif // MARISA_GRIMOIRE_TRIE_LOUDS_TRIE_H_ 135