| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /*! | ||
| 2 | @file | ||
| 3 | @brief The Om_Tree function definitions. | ||
| 4 | */ | ||
| 5 | |||
| 6 | #include <om/tree.h> | ||
| 7 | |||
| 8 | #include <om/tree/branch_node.h> | ||
| 9 | #include <om/tree/lookup.h> | ||
| 10 | |||
| 11 | #include <assert.h> | ||
| 12 | #include <string.h> | ||
| 13 | |||
| 14 | 45 | void Om_Tree_Initialize( | |
| 15 | Om_Tree * const theTree, | ||
| 16 | Om_Tree_LeafNode_Interface const * const theLeafNodeInterface | ||
| 17 | ) { | ||
| 18 | − | assert(theTree); | |
| 19 | |||
| 20 | 45 | theTree->thisLeafNodeInterface = theLeafNodeInterface; | |
| 21 | 45 | theTree->thisRootNode = (Om_Tree_BranchNode)NULL; | |
| 22 | 45 | theTree->thisLeafCount = 0U; | |
| 23 | 45 | theTree->thisMaximumStringLength = 0U; | |
| 24 | 45 | } | |
| 25 | |||
| 26 | 54 | bool Om_Tree_InitializeCopy( | |
| 27 | Om_Tree * const theTree, | ||
| 28 | Om_Tree const * const theTreeToCopy | ||
| 29 | ) { | ||
| 30 | − | assert(theTree); | |
| 31 | − | assert(theTreeToCopy); | |
| 32 | |||
| 33 | 54 | theTree->thisRootNode = (Om_Tree_BranchNode)NULL; | |
| 34 |
2/2✓ Branch 1 taken 53 times.
✓ Branch 2 taken 1 times.
|
54 | if(!Om_Tree_IsEmpty(theTreeToCopy)) { |
| 35 | // The depth cannot be greater than the leaf count. | ||
| 36 | 53 | Om_Tree_NodeStack * const theStack = Om_Tree_NodeStack_Create( | |
| 37 | 53 | theTreeToCopy->thisLeafCount | |
| 38 | ); | ||
| 39 |
2/2✓ Branch 0 taken 51 times.
✓ Branch 1 taken 2 times.
|
53 | if(theStack) { |
| 40 | Om_Tree_NodePointerStack * const theCopyStack = ( | ||
| 41 | 51 | Om_Tree_NodePointerStack_Create(theTreeToCopy->thisLeafCount) | |
| 42 | ); | ||
| 43 |
2/2✓ Branch 0 taken 49 times.
✓ Branch 1 taken 2 times.
|
51 | if(theCopyStack) { |
| 44 | 98 | theTree->thisRootNode = Om_Tree_BranchNode_CreateCopy( | |
| 45 | 49 | theTreeToCopy->thisRootNode, theTreeToCopy->thisLeafNodeInterface, | |
| 46 | theStack, theCopyStack | ||
| 47 | ); | ||
| 48 | 49 | Om_Tree_NodePointerStack_Destroy(theCopyStack); | |
| 49 | } | ||
| 50 | 51 | Om_Tree_NodeStack_Destroy(theStack); | |
| 51 | } | ||
| 52 |
2/2✓ Branch 0 taken 13 times.
✓ Branch 1 taken 40 times.
|
53 | if(theTree->thisRootNode == (Om_Tree_BranchNode)NULL) { |
| 53 | 13 | return false; | |
| 54 | } | ||
| 55 | } | ||
| 56 | 41 | theTree->thisLeafNodeInterface = theTreeToCopy->thisLeafNodeInterface; | |
| 57 | 41 | theTree->thisLeafCount = theTreeToCopy->thisLeafCount; | |
| 58 | 41 | theTree->thisMaximumStringLength = theTreeToCopy->thisMaximumStringLength; | |
| 59 | 41 | return true; | |
| 60 | } | ||
| 61 | |||
| 62 | 323 | bool Om_Tree_IsEmpty( | |
| 63 | Om_Tree const * const theTree | ||
| 64 | ) { | ||
| 65 | − | assert(theTree); | |
| 66 | − | assert( | |
| 67 | (theTree->thisRootNode != (Om_Tree_BranchNode)NULL) || | ||
| 68 | !theTree->thisLeafCount | ||
| 69 | ); | ||
| 70 | |||
| 71 | 323 | return (theTree->thisRootNode == (Om_Tree_BranchNode)NULL); | |
| 72 | } | ||
| 73 | |||
| 74 | 35 | size_t Om_Tree_GetCount( | |
| 75 | Om_Tree const * const theTree | ||
| 76 | ) { | ||
| 77 | − | assert(theTree); | |
| 78 | |||
| 79 | 35 | return theTree->thisLeafCount; | |
| 80 | } | ||
| 81 | |||
| 82 | 141 | Om_Tree_LeafNode * Om_Tree_Get( | |
| 83 | Om_Tree const * const theTree, | ||
| 84 | size_t theStringLength, | ||
| 85 | char const * const theString | ||
| 86 | ) { | ||
| 87 | − | assert(theTree); | |
| 88 | − | assert(theString); | |
| 89 | − | assert(theStringLength == strlen(theString)); | |
| 90 | |||
| 91 |
2/2✓ Branch 1 taken 2 times.
✓ Branch 2 taken 139 times.
|
141 | if(Om_Tree_IsEmpty(theTree)) { |
| 92 | 2 | return NULL; | |
| 93 | } | ||
| 94 | Om_Tree_Lookup theLookup; | ||
| 95 | 139 | Om_Tree_Lookup_Initialize(&theLookup, theTree); | |
| 96 | − | assert(Om_Tree_Lookup_CanAdvance(&theLookup)); | |
| 97 | 139 | Om_Tree_Lookup_Advance(&theLookup, theStringLength + 1U, theString); | |
| 98 | 139 | return Om_Tree_Lookup_GetLeafNode(&theLookup); | |
| 99 | } | ||
| 100 | |||
| 101 | 175 | int Om_Tree_Set( | |
| 102 | Om_Tree * const theTree, | ||
| 103 | size_t const theStringLength, | ||
| 104 | char const * const theString, | ||
| 105 | Om_Tree_LeafNode const theValue | ||
| 106 | ) { | ||
| 107 | − | assert(theTree); | |
| 108 | |||
| 109 | 175 | Om_Tree_LeafNode * theLeafNode = NULL; | |
| 110 | 175 | int const theResult = Om_Tree_Insert( | |
| 111 | theTree, theStringLength, theString, &theLeafNode | ||
| 112 | ); | ||
| 113 |
2/2✓ Branch 0 taken 167 times.
✓ Branch 1 taken 8 times.
|
175 | if(theResult) { |
| 114 | − | assert(theLeafNode); | |
| 115 |
4/4✓ Branch 0 taken 2 times.
✓ Branch 1 taken 165 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 1 times.
|
167 | if((theResult == -1) && theTree->thisLeafNodeInterface) { |
| 116 | − | assert(theTree->thisLeafNodeInterface->Deinitialize); | |
| 117 | 1 | theTree->thisLeafNodeInterface->Deinitialize(*theLeafNode); | |
| 118 | } | ||
| 119 | 167 | *theLeafNode = theValue; | |
| 120 | } | ||
| 121 | 175 | return theResult; | |
| 122 | } | ||
| 123 | |||
| 124 | 114 | int Om_Tree_Unset( | |
| 125 | Om_Tree * const theTree, | ||
| 126 | size_t const theStringLength, | ||
| 127 | char const * const theString | ||
| 128 | ) { | ||
| 129 | − | assert(theTree); | |
| 130 | |||
| 131 | // NOLINTNEXTLINE(cppcoreguidelines-init-variables) | ||
| 132 | Om_Tree_LeafNode theLeafNode; | ||
| 133 | 114 | int const theResult = Om_Tree_Remove( | |
| 134 | theTree, theStringLength, theString, &theLeafNode | ||
| 135 | ); | ||
| 136 |
4/4✓ Branch 0 taken 110 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 109 times.
|
114 | if((theResult == 1) && theTree->thisLeafNodeInterface) { |
| 137 | − | assert(theTree->thisLeafNodeInterface->Deinitialize); | |
| 138 | 1 | theTree->thisLeafNodeInterface->Deinitialize(theLeafNode); | |
| 139 | } | ||
| 140 | 114 | return theResult; | |
| 141 | } | ||
| 142 | |||
| 143 | 212 | int Om_Tree_Insert( | |
| 144 | Om_Tree * const theTree, | ||
| 145 | size_t theStringLength, | ||
| 146 | char const * const theString, | ||
| 147 | Om_Tree_LeafNode * * const theLeafNode | ||
| 148 | ) { | ||
| 149 | − | assert(theTree); | |
| 150 | − | assert(theLeafNode); | |
| 151 | |||
| 152 | // LCOV_EXCL_START | ||
| 153 | − | if(theTree->thisLeafCount == SIZE_MAX) { | |
| 154 | − | return 0; | |
| 155 | } | ||
| 156 | // LCOV_EXCL_STOP | ||
| 157 | 212 | int const theResult = Om_Tree_BranchNode_Insert( | |
| 158 | &theTree->thisRootNode, theStringLength, theString, theLeafNode | ||
| 159 | ); | ||
| 160 |
2/2✓ Branch 0 taken 190 times.
✓ Branch 1 taken 22 times.
|
212 | if(theResult == 1) { |
| 161 | − | assert(theTree->thisLeafCount < SIZE_MAX); | |
| 162 | 190 | ++theTree->thisLeafCount; | |
| 163 |
2/2✓ Branch 0 taken 50 times.
✓ Branch 1 taken 140 times.
|
190 | if(theStringLength > theTree->thisMaximumStringLength) { |
| 164 | 50 | theTree->thisMaximumStringLength = theStringLength; | |
| 165 | } | ||
| 166 | } | ||
| 167 | 212 | return theResult; | |
| 168 | } | ||
| 169 | |||
| 170 | 138 | int Om_Tree_Remove( | |
| 171 | Om_Tree * const theTree, | ||
| 172 | size_t const theStringLength, | ||
| 173 | char const * const theString, | ||
| 174 | Om_Tree_LeafNode * const theLeafNode | ||
| 175 | ) { | ||
| 176 | − | assert(theTree); | |
| 177 | − | assert(theLeafNode); | |
| 178 | |||
| 179 | 138 | int const theResult = Om_Tree_BranchNode_Remove( | |
| 180 | &theTree->thisRootNode, theStringLength, theString, theLeafNode | ||
| 181 | ); | ||
| 182 |
2/2✓ Branch 0 taken 122 times.
✓ Branch 1 taken 16 times.
|
138 | if(theResult == 1) { |
| 183 | − | assert(theTree->thisLeafCount); | |
| 184 | 122 | --theTree->thisLeafCount; | |
| 185 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 118 times.
|
122 | if(!theTree->thisLeafCount) { |
| 186 | 4 | theTree->thisMaximumStringLength = 0U; | |
| 187 | } | ||
| 188 | } | ||
| 189 | 138 | return theResult; | |
| 190 | } | ||
| 191 | |||
| 192 | 62 | bool Om_Tree_Match( | |
| 193 | Om_Tree const * const theTree, | ||
| 194 | Om_Tree const * const theOtherTree | ||
| 195 | ) { | ||
| 196 | − | assert(theTree); | |
| 197 | − | assert(theOtherTree); | |
| 198 | |||
| 199 | 62 | if( | |
| 200 |
2/2✓ Branch 0 taken 60 times.
✓ Branch 1 taken 2 times.
|
62 | (theTree->thisLeafNodeInterface != theOtherTree->thisLeafNodeInterface) || |
| 201 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 58 times.
|
60 | (theTree->thisLeafCount != theOtherTree->thisLeafCount) |
| 202 | ) { | ||
| 203 | 4 | return false; | |
| 204 | } | ||
| 205 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 57 times.
|
58 | if(theTree->thisRootNode == theOtherTree->thisRootNode) { |
| 206 | 1 | return true; | |
| 207 | } | ||
| 208 | 57 | if( | |
| 209 |
2/2✓ Branch 0 taken 56 times.
✓ Branch 1 taken 1 times.
|
57 | (theTree->thisRootNode == (Om_Tree_BranchNode)NULL) || |
| 210 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 55 times.
|
56 | (theOtherTree->thisRootNode == (Om_Tree_BranchNode)NULL) |
| 211 | ) { | ||
| 212 | 2 | return false; | |
| 213 | } | ||
| 214 | // The depth cannot be greater than the leaf count. | ||
| 215 | 55 | Om_Tree_NodeStack * const theStack = Om_Tree_NodeStack_Create( | |
| 216 | 55 | theTree->thisLeafCount | |
| 217 | ); | ||
| 218 | 55 | Om_Tree_NodeStack * const theOtherStack = Om_Tree_NodeStack_Create( | |
| 219 | 55 | theTree->thisLeafCount | |
| 220 | ); | ||
| 221 | 55 | bool const isMatch = Om_Tree_BranchNode_Match( | |
| 222 | 55 | theTree->thisRootNode, theOtherTree->thisRootNode, | |
| 223 | 55 | theTree->thisLeafNodeInterface, theStack, theOtherStack | |
| 224 | ); | ||
| 225 | 55 | Om_Tree_NodeStack_Destroy(theOtherStack); | |
| 226 | 55 | Om_Tree_NodeStack_Destroy(theStack); | |
| 227 | 55 | return isMatch; | |
| 228 | } | ||
| 229 | |||
| 230 | #if Om_Tree_IsPrintEnabled | ||
| 231 | 104 | bool Om_Tree_Print( | |
| 232 | Om_Tree const * const theTree, | ||
| 233 | FILE * const theStream | ||
| 234 | ) { | ||
| 235 | − | assert(theTree); | |
| 236 | − | assert(theStream); | |
| 237 | |||
| 238 | return ( | ||
| 239 | − | (fputs("- : ", theStream) != EOF) && // LCOV_EXCL_LINE | |
| 240 | 104 | Om_Tree_BranchNode_Print( | |
| 241 | 104 | theTree->thisRootNode, theStream, 1U, theTree->thisLeafNodeInterface | |
| 242 | ) | ||
| 243 | ); | ||
| 244 | } | ||
| 245 | #endif | ||
| 246 | |||
| 247 | 40 | void Om_Tree_Reinitialize( | |
| 248 | Om_Tree * const theTree | ||
| 249 | ) { | ||
| 250 | − | assert(theTree); | |
| 251 | |||
| 252 | 40 | Om_Tree_Deinitialize(theTree); | |
| 253 | 40 | theTree->thisRootNode = (Om_Tree_BranchNode)NULL; | |
| 254 | 40 | theTree->thisLeafCount = 0U; | |
| 255 | 40 | theTree->thisMaximumStringLength = 0U; | |
| 256 | 40 | } | |
| 257 | |||
| 258 | 79 | void Om_Tree_Deinitialize( | |
| 259 | Om_Tree * const theTree | ||
| 260 | ) { | ||
| 261 |
2/2✓ Branch 1 taken 76 times.
✓ Branch 2 taken 3 times.
|
79 | if(!Om_Tree_IsEmpty(theTree)) { |
| 262 | // The depth cannot be greater than the leaf count. | ||
| 263 | 76 | Om_Tree_NodeStack * const theStack = Om_Tree_NodeStack_Create( | |
| 264 | theTree->thisLeafCount | ||
| 265 | ); | ||
| 266 | 76 | Om_Tree_BranchNode_Destroy( | |
| 267 | theTree->thisRootNode, theTree->thisLeafNodeInterface, theStack | ||
| 268 | ); | ||
| 269 | 76 | Om_Tree_NodeStack_Destroy(theStack); | |
| 270 | } | ||
| 271 | 79 | } | |
| 272 |