1 /** @file 2 3 A brief file description 4 5 @section license License 6 7 Licensed to the Apache Software Foundation (ASF) under one 8 or more contributor license agreements. See the NOTICE file 9 distributed with this work for additional information 10 regarding copyright ownership. The ASF licenses this file 11 to you under the Apache License, Version 2.0 (the 12 "License"); you may not use this file except in compliance 13 with the License. You may obtain a copy of the License at 14 15 http://www.apache.org/licenses/LICENSE-2.0 16 17 Unless required by applicable law or agreed to in writing, software 18 distributed under the License is distributed on an "AS IS" BASIS, 19 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 20 See the License for the specific language governing permissions and 21 limitations under the License. 22 */ 23 24 /***************************************************************************** 25 * 26 * HostLookup.h - Interface to general purpose matcher 27 * 28 * 29 ****************************************************************************/ 30 31 #pragma once 32 33 #include <vector> 34 #include <string> 35 #include <string_view> 36 #include <functional> 37 #include <unordered_map> 38 39 // HostLookup constants 40 constexpr int HOST_TABLE_DEPTH = 3; // Controls the max number of levels in the logical tree 41 constexpr int HOST_ARRAY_MAX = 8; // Sets the fixed array size 42 43 class CharIndex; 44 class HostArray; 45 46 // The data in the HostMatcher tree is pointers to HostBranches. No duplicates keys permitted in the tree. To handle 47 // multiple data items bound the same key, the HostBranch has the lead_indexs array which stores pointers (in the form 48 // of array indexes) to HostLeaf structs 49 // 50 // There is HostLeaf struct for each data item put into the table 51 // 52 struct HostLeaf { 53 /// Type of leaf. 54 enum Type { 55 LEAF_INVALID, 56 HOST_PARTIAL, 57 HOST_COMPLETE, 58 DOMAIN_COMPLETE, 59 DOMAIN_PARTIAL, 60 }; 61 Type type{LEAF_INVALID}; ///< Type of this leaf instance. 62 std::string match; // Contains a copy of the match data 63 bool isNot{false}; // used by any fasssst path ... 64 void *opaque_data{nullptr}; // Data associated with this leaf 65 HostLeafHostLeaf66 HostLeaf() {} HostLeafHostLeaf67 HostLeaf(std::string_view name, void *data) : opaque_data(data) 68 { 69 if (!name.empty() && name.front() == '!') { 70 name.remove_prefix(1); 71 isNot = true; 72 } 73 match.assign(name); 74 } 75 }; 76 77 struct HostBranch { 78 /// Branch type. 79 enum Type { 80 HOST_TERMINAL, 81 HOST_HASH, 82 HOST_INDEX, 83 HOST_ARRAY, 84 }; 85 86 using HostTable = std::unordered_map<std::string_view, HostBranch *>; 87 88 using LeafIndices = std::vector<int>; 89 90 /// Type of data in this branch. 91 union Level { 92 std::nullptr_t _nil; ///< HOST_TERMINAL 93 HostTable *_table; ///< HOST_HASH 94 CharIndex *_index; ///< HOST_INDEX 95 HostArray *_array; ///< HOST_ARRAY 96 void *_ptr; ///< As generic pointer. 97 }; 98 99 ~HostBranch(); 100 int level_idx{0}; // what level in the tree. the root is level 0 101 Type type{HOST_TERMINAL}; // tells what kind of data structure is next_level is 102 Level next_level{nullptr}; // opaque pointer to lookup structure 103 LeafIndices leaf_indices; // HostLeaf indices. 104 std::string key; 105 }; 106 107 // 108 // End Host Lookup Helper types 109 // 110 111 struct HostLookupState { 112 HostBranch *cur{nullptr}; 113 int table_level{0}; 114 int array_index{0}; 115 std::string_view hostname; ///< Original host name. 116 std::string_view hostname_stub; ///< Remaining host name to search. 117 }; 118 119 class HostLookup 120 { 121 public: 122 using LeafArray = std::vector<HostLeaf>; 123 using PrintFunc = std::function<void(void *)>; 124 125 HostLookup(std::string_view name); 126 void NewEntry(std::string_view match_data, bool domain_record, void *opaque_data_in); 127 void AllocateSpace(int num_entries); 128 bool Match(std::string_view host); 129 bool Match(std::string_view host, void **opaque_ptr); 130 bool MatchFirst(std::string_view host, HostLookupState *s, void **opaque_ptr); 131 bool MatchNext(HostLookupState *s, void **opaque_ptr); 132 133 void Print(PrintFunc const &f) const; 134 void Print() const; 135 136 LeafArray * get_leaf_array()137 get_leaf_array() 138 { 139 return &leaf_array; 140 } 141 142 private: 143 using HostTable = HostBranch::HostTable; 144 using LeafIndices = HostBranch::LeafIndices; 145 146 void TableInsert(std::string_view match_data, int index, bool domain_record); 147 HostBranch *TableNewLevel(HostBranch *from, std::string_view level_data); 148 HostBranch *InsertBranch(HostBranch *insert_in, std::string_view level_data); 149 HostBranch *FindNextLevel(HostBranch *from, std::string_view level_data, bool bNotProcess = false); 150 bool MatchArray(HostLookupState *s, void **opaque_ptr, LeafIndices &array, bool host_done); 151 152 void PrintHostBranch(const HostBranch *hb, PrintFunc const &f) const; 153 154 HostBranch root; // The top of the search tree 155 LeafArray leaf_array; // array of all leaves in tree 156 std::string matcher_name; // Used for Debug/Warning/Error messages 157 }; 158