1 /*
2  * Copyright (c) 2024 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #ifndef NETMANAGER_BASE_SUFFIX_MATCH_TRIE_H
17 #define NETMANAGER_BASE_SUFFIX_MATCH_TRIE_H
18 
19 #include <string>
20 #include <cctype>
21 
22 #include <securec.h>
23 
24 namespace OHOS::NetManagerStandard {
25 static constexpr const int DOMAIN_NUM_SIZE = 10;     // [0-9]
26 static constexpr const int DOMAIN_DOT_INDEX = 36;    // [.]
27 static constexpr const int DOMAIN_DASH_INDEX = 37;   // [-]
28 static constexpr const int DOMAIN_CHAR_RANGE = 38;   // [a-z][0-9][-][.]
29 
30 /**
31  * @brief Longest suffix match trie
32  *
33  * @tparam T trie node value type
34  */
35 template <class T> class SuffixMatchTrie {
36 private:
37     /**
38      * @brief TrieNode define
39      */
40     struct TrieNode {
41         // suffix terminal flag
42         bool terminal;
43         // children pointers
44         struct TrieNode *children[DOMAIN_CHAR_RANGE];
45         // node value
46         T val;
47     };
48 
49 public:
SuffixMatchTrie()50     SuffixMatchTrie()
51     {
52         root_ = CreateNode();
53     }
54 
~SuffixMatchTrie()55     ~SuffixMatchTrie()
56     {
57         FreeTrie(root_);
58     }
59 
60     /**
61      * @brief Check trie is empty or not
62      *
63      * @return true if empty, otherwise false
64      */
Empty()65     bool Empty()
66     {
67         return (size_ == 0);
68     }
69 
70     /**
71      * @brief Insert a node to trie
72      *
73      * @param key tire node key
74      * @param val tire node value
75      * @return true if success, otherwise false
76      */
Insert(const std::string & key,const T & val)77     bool Insert(const std::string &key, const T &val)
78     {
79         if (key.empty()) {
80             return false;
81         }
82         TrieNode *pCrawl = root_;
83         for (auto it = key.rbegin(); it != key.rend(); it++) {
84             int i = GetChildIndex(*it);
85             if (i < 0) {
86                 return false;
87             }
88             if (!pCrawl->children[i])
89                 pCrawl->children[i] = CreateNode();
90             pCrawl = pCrawl->children[i];
91         }
92         pCrawl->terminal = true;
93         pCrawl->val = val;
94         size_++;
95         return true;
96     }
97 
98     /**
99      * @brief Update trie node
100      *
101      * @param key tire node key
102      * @param val tire node value to be update
103      * @return true if success, otherwise false
104      */
Update(const std::string & key,const T & val)105     bool Update(const std::string &key, const T &val)
106     {
107         if (key.empty()) {
108             return false;
109         }
110         TrieNode *pCrawl = root_;
111         TrieNode *found = nullptr;
112         for (auto it = key.rbegin(); pCrawl && it != key.rend(); it++) {
113             int i = GetChildIndex(*it);
114             if (i < 0) {
115                 return false;
116             }
117             pCrawl = pCrawl->children[i];
118             if (pCrawl && pCrawl->terminal) {
119                 found = pCrawl;
120             }
121         }
122         if (found) {
123             found->val = val;
124             return true;
125         }
126         return false;
127     }
128 
129     /**
130      * @brief match key with longest suffix
131      *
132      * @param key tire node key
133      * @param out tire node value
134      * @return >0 if success, otherwise =0
135      */
LongestSuffixMatch(const std::string & key,T & out)136     int LongestSuffixMatch(const std::string &key, T &out)
137     {
138         if (key.empty()) {
139             return 0;
140         }
141         TrieNode *pCrawl = root_;
142         TrieNode *found = nullptr;
143         int index = 0;
144         int matchLen = 0;
145         for (auto it = key.rbegin(); pCrawl && it != key.rend(); it++) {
146             int i = GetChildIndex(*it);
147             if (i < 0) {
148                 return matchLen;
149             }
150             pCrawl = pCrawl->children[i];
151             index++;
152 
153             if (pCrawl && pCrawl->terminal) {
154                 found = pCrawl;
155                 matchLen = index;
156             }
157         }
158         if (found) {
159             out = found->val;
160         }
161         return matchLen;
162     }
163 
164 private:
165     TrieNode *root_;
166     uint32_t size_ = 0;
CreateNode()167     TrieNode *CreateNode()
168     {
169         TrieNode *node = new TrieNode;
170         memset_s(node, sizeof(TrieNode), 0, sizeof(TrieNode));
171         return node;
172     }
FreeTrie(TrieNode * root)173     void FreeTrie(TrieNode *root)
174     {
175         if (root) {
176             for (int i = 0; i < DOMAIN_CHAR_RANGE; i++) {
177                 FreeTrie(root->children[i]);
178             }
179 
180             delete root;
181             root = nullptr;
182         }
183     }
GetChildIndex(char c)184     int GetChildIndex(char c)
185     {
186         int ch = c;
187         if (isupper(c)) {
188             ch = tolower(c);
189         }
190         if (ch >= '0' && ch <= '9') {
191             return ch - '0';
192         } else if (ch >= 'a' && ch <= 'z') {
193             return ch - 'a' + DOMAIN_NUM_SIZE;
194         } else if (ch == '.') {
195             return DOMAIN_DOT_INDEX;
196         } else if (ch == '-') {
197             return DOMAIN_DASH_INDEX;
198         }
199         return -1;
200     }
201 };
202 } // namespace OHOS::NetManagerStandard
203 #endif // NETMANAGER_BASE_SUFFIX_MATCH_TRIE_H