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