1 /*
2 * Copyright (c) 2023 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 #include "sehap_contexts_trie.h"
16 #include <deque>
17
18 #include "src/callbacks.h"
19 #include "selinux/selinux.h"
20 #include "selinux_log.h"
21
SplitString(const std::string & paraName)22 std::vector<std::string> SehapContextsTrie::SplitString(const std::string& paraName)
23 {
24 std::vector<std::string> words;
25 std::string delimiter = ".";
26 size_t len = paraName.length();
27 size_t index = 0;
28 while (index < len) {
29 size_t pos;
30 if ((pos = paraName.substr(index).find(delimiter)) == std::string::npos) {
31 break;
32 }
33 std::string element = paraName.substr(index, pos);
34 if (!element.empty()) {
35 words.emplace_back(element);
36 }
37 index += pos + delimiter.length();
38 }
39 if (!paraName.substr(index).empty()) {
40 words.emplace_back(paraName.substr(index));
41 }
42 return words;
43 }
44
FindChild(const std::string & element)45 SehapContextsTrie* SehapContextsTrie::FindChild(const std::string& element)
46 {
47 SehapContextsTrie* node = this;
48 auto iter = node->children.find(element);
49 if (iter != node->children.end()) {
50 return iter->second;
51 }
52 return nullptr;
53 }
54
Insert(const std::string & paraName,const std::string & domain,const std::string & type)55 bool SehapContextsTrie::Insert(const std::string& paraName, const std::string& domain, const std::string& type)
56 {
57 SehapContextsTrie* node = this;
58 std::vector<std::string> words = SplitString(paraName);
59 for (const std::string& word : words) {
60 if (word == "*") {
61 break;
62 }
63 if (node->children[word] == nullptr) {
64 node->children[word] = new (std::nothrow) SehapContextsTrie();
65 if (node->children[word] == nullptr) {
66 selinux_log(SELINUX_ERROR, "new child sehapcontextstrie failed!");
67 return false;
68 }
69 }
70 node = node->children[word];
71 }
72 if ((paraName.back() == '.') || (paraName.back() == '*')) {
73 node->prefixInfo.isEnd = true;
74 node->prefixInfo.domain = domain;
75 node->prefixInfo.type = type;
76 return true;
77 }
78 node->matchedInfo.isEnd = true;
79 node->matchedInfo.domain = domain;
80 node->matchedInfo.type = type;
81 return true;
82 }
83
Search(const std::string & paraName,bool isDomain)84 std::string SehapContextsTrie::Search(const std::string& paraName, bool isDomain)
85 {
86 std::vector<std::string> words = SplitString(paraName);
87 std::string type = "";
88 SehapContextsTrie* root = this;
89 for (size_t i = 0; i < words.size(); i++) {
90 const std::string& word = words[i];
91 auto child = root->FindChild(word);
92 if (child == nullptr) {
93 break;
94 }
95 root = child;
96 if ((root->prefixInfo.isEnd) && (i != words.size() - 1)) {
97 if (isDomain) {
98 type = root->prefixInfo.domain;
99 } else {
100 type = root->prefixInfo.type;
101 }
102 }
103 if ((root->matchedInfo.isEnd) && (i == words.size() - 1)) {
104 if (isDomain) {
105 type = root->matchedInfo.domain;
106 } else {
107 type = root->matchedInfo.type;
108 }
109 }
110 }
111 return type;
112 }
113
Clear()114 void SehapContextsTrie::Clear()
115 {
116 SehapContextsTrie* root = this;
117 std::deque<SehapContextsTrie*> nodeDeque;
118 for (auto child : root->children) {
119 nodeDeque.emplace_back(child.second);
120 }
121 while (!nodeDeque.empty()) {
122 root = nodeDeque.front();
123 nodeDeque.pop_front();
124 if (root != nullptr) {
125 for (auto child : root->children) {
126 nodeDeque.emplace_back(child.second);
127 }
128 delete root;
129 }
130 }
131 }