| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /*! | ||
| 2 | @file | ||
| 3 | @brief The @ref Om_Tree_BranchNode function definitions. | ||
| 4 | */ | ||
| 5 | |||
| 6 | #include <om/tree/branch_node.h> | ||
| 7 | |||
| 8 | #include <om/bit.h> | ||
| 9 | #include <om/memory.h> | ||
| 10 | #if Om_Tree_IsPrintEnabled | ||
| 11 | #include <om/print.h> | ||
| 12 | #endif | ||
| 13 | |||
| 14 | #include <assert.h> | ||
| 15 | #if Om_Tree_IsPrintEnabled | ||
| 16 | #include <errno.h> | ||
| 17 | #endif | ||
| 18 | #include <limits.h> | ||
| 19 | #include <string.h> | ||
| 20 | |||
| 21 | 1101 | static Om_Tree_BranchNode Om_Tree_BranchNode_Create( | |
| 22 | Om_Tree_Branch * const theBranch, | ||
| 23 | uint_fast8_t const theBranchBitCount | ||
| 24 | ) { | ||
| 25 | static_assert(CHAR_BIT > 0U, "The byte size must be positive."); | ||
| 26 | static_assert(Om_Alignment >= CHAR_BIT, | ||
| 27 | "The alignment must be greater than or equal to the byte size." | ||
| 28 | ); | ||
| 29 | − | assert(!((uintptr_t)theBranch % Om_Alignment)); | |
| 30 | − | assert(theBranchBitCount < CHAR_BIT); | |
| 31 | |||
| 32 | 1101 | return ((uintptr_t)theBranch + theBranchBitCount); | |
| 33 | } | ||
| 34 | |||
| 35 | 143 | static Om_Tree_Branch * Om_Tree_BranchNode_Split( | |
| 36 | Om_Tree_Branch * theBranch, | ||
| 37 | uint_fast8_t * const theBranchBitCount, | ||
| 38 | size_t const theNewBranchByteCount, | ||
| 39 | // NOLINTNEXTLINE(bugprone-easily-swappable-parameters) | ||
| 40 | uint_fast8_t const theNewBranchBitCount, | ||
| 41 | Om_Tree_Node const theOtherChild | ||
| 42 | ) { | ||
| 43 | − | assert(theBranch); | |
| 44 | − | assert(theBranchBitCount && (*theBranchBitCount < CHAR_BIT)); | |
| 45 | − | assert( | |
| 46 | theNewBranchByteCount <= | ||
| 47 | Om_Tree_Branch_GetByteCount(theBranch, *theBranchBitCount) | ||
| 48 | ); | ||
| 49 | − | assert(theNewBranchBitCount < CHAR_BIT); | |
| 50 | // Assert that if the new byte count is the same, that the new bit count is | ||
| 51 | // less than the old one. | ||
| 52 | − | assert( | |
| 53 | ( | ||
| 54 | theNewBranchByteCount < | ||
| 55 | Om_Tree_Branch_GetByteCount(theBranch, *theBranchBitCount) | ||
| 56 | ) || (!*theBranchBitCount || (theNewBranchBitCount < *theBranchBitCount)) | ||
| 57 | ); | ||
| 58 | |||
| 59 | // Get the critical bit. | ||
| 60 | 143 | char const theByte = Om_Tree_Branch_GetByteArray(theBranch)[ | |
| 61 | theNewBranchByteCount | ||
| 62 | ]; | ||
| 63 | 143 | bool const theBit = Om_Bit_Get(theByte, theNewBranchBitCount); | |
| 64 | |||
| 65 | // Split the branch. | ||
| 66 | 143 | Om_Tree_Branch * theChildBranch = NULL; | |
| 67 | 143 | uint_fast8_t theChildBranchBitCount = 0U; | |
| 68 | 143 | theBranch = Om_Tree_Branch_Split( | |
| 69 | theBranch, theBranchBitCount, | ||
| 70 | theNewBranchByteCount, theNewBranchBitCount, | ||
| 71 | &theChildBranch, &theChildBranchBitCount | ||
| 72 | ); | ||
| 73 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 140 times.
|
143 | if(!theBranch) { |
| 74 | 3 | return NULL; | |
| 75 | } | ||
| 76 | |||
| 77 | // Set the children. | ||
| 78 | 140 | Om_Tree_Node * const theChildArray = Om_Tree_Branch_GetChildArray(theBranch); | |
| 79 | 140 | theChildArray[theBit] = Om_Tree_BranchNode_Create( | |
| 80 | theChildBranch, theChildBranchBitCount | ||
| 81 | ); | ||
| 82 |
2/2✓ Branch 0 taken 75 times.
✓ Branch 1 taken 65 times.
|
140 | theChildArray[!theBit] = theOtherChild; |
| 83 | |||
| 84 | 140 | return theBranch; | |
| 85 | } | ||
| 86 | |||
| 87 | 119 | static Om_Tree_Branch * Om_Tree_BranchNode_Merge( | |
| 88 | Om_Tree_Branch * theBranch, | ||
| 89 | uint_fast8_t * const theBranchBitCount, | ||
| 90 | bool const theChildOffset | ||
| 91 | ) { | ||
| 92 | − | assert(theBranch); | |
| 93 | − | assert(theBranchBitCount && *theBranchBitCount < CHAR_BIT); | |
| 94 | // Assert that the child is a branch. | ||
| 95 | − | assert( | |
| 96 | !Om_Tree_Branch_HasLeafChild(theBranch, *theBranchBitCount) || | ||
| 97 | theChildOffset | ||
| 98 | ); | ||
| 99 | |||
| 100 | // Get the child. | ||
| 101 | // Assert that the other child is either a leaf or a null branch. | ||
| 102 | // The other child is not a branch when there is a leaf child, and the child | ||
| 103 | // offset is true. | ||
| 104 | 119 | Om_Tree_Node * const theChildArray = Om_Tree_Branch_GetChildArray(theBranch); | |
| 105 | − | assert( | |
| 106 | ( | ||
| 107 | Om_Tree_Branch_HasLeafChild(theBranch, *theBranchBitCount) && | ||
| 108 | theChildOffset | ||
| 109 | ) || (theChildArray[!theChildOffset] == (Om_Tree_BranchNode)NULL) | ||
| 110 | ); | ||
| 111 | 119 | Om_Tree_Node const theChild = theChildArray[theChildOffset]; | |
| 112 | 119 | Om_Tree_Branch * const theChildBranch = Om_Tree_BranchNode_GetBranch( | |
| 113 | theChild | ||
| 114 | ); | ||
| 115 | − | assert(theChildBranch); | |
| 116 | uint_fast8_t const theChildBranchBitCount = ( | ||
| 117 | 119 | Om_Tree_BranchNode_GetBranchBitCount(theChild) | |
| 118 | ); | ||
| 119 | |||
| 120 | 119 | return Om_Tree_Branch_Merge( | |
| 121 | theBranch, theBranchBitCount, | ||
| 122 | theChildOffset, theChildBranch, theChildBranchBitCount | ||
| 123 | ); | ||
| 124 | } | ||
| 125 | |||
| 126 | /*! | ||
| 127 | @brief Finds the first mismatch, if any, between the byte array and the string. | ||
| 128 | @param theByteCount | ||
| 129 | The byte count. | ||
| 130 | @param theByteArray | ||
| 131 | The byte array. | ||
| 132 | @param theBitCount | ||
| 133 | The bit count in the last byte of the byte array; if non-zero, the remaining | ||
| 134 | bits are assumed to be 1. | ||
| 135 | @param theString | ||
| 136 | The string. | ||
| 137 | @param theBitIndex | ||
| 138 | A non-null pointer to a variable to store the mismatched bit index, if any. | ||
| 139 | Gives the bit index to start from if the mismatch is in the first byte. | ||
| 140 | @returns The byte index of the first mismatch, or the maximum value if none. | ||
| 141 | */ | ||
| 142 | 661 | static size_t Om_Tree_BranchNode_FindMismatch( | |
| 143 | size_t const theByteCount, | ||
| 144 | char const * const theByteArray, | ||
| 145 | uint_fast8_t const theBitCount, | ||
| 146 | char const * Om_Restrict const theString, | ||
| 147 | uint_fast8_t * theBitIndex | ||
| 148 | ) { | ||
| 149 | − | assert(theByteArray); | |
| 150 | − | assert(theBitCount < CHAR_BIT); | |
| 151 | − | assert(theString); | |
| 152 | − | assert(theBitIndex); | |
| 153 | |||
| 154 | 661 | size_t theByteIndex = 0U; | |
| 155 | // NOLINTBEGIN(cppcoreguidelines-init-variables) | ||
| 156 | char theByte; | ||
| 157 | char theCodeUnit; | ||
| 158 | // NOLINTEND(cppcoreguidelines-init-variables) | ||
| 159 | |||
| 160 | // Check each byte. | ||
| 161 |
2/2✓ Branch 0 taken 170 times.
✓ Branch 1 taken 558 times.
|
728 | for(; theByteIndex < theByteCount; ++theByteIndex) { |
| 162 | 170 | theByte = theByteArray[theByteIndex]; | |
| 163 | 170 | theCodeUnit = theString[theByteIndex]; | |
| 164 |
2/2✓ Branch 0 taken 103 times.
✓ Branch 1 taken 67 times.
|
170 | if(theByte != theCodeUnit) { |
| 165 | 103 | goto Mismatch; | |
| 166 | } | ||
| 167 | − | assert(theCodeUnit); | |
| 168 | } | ||
| 169 | |||
| 170 | // Check each bit. | ||
| 171 |
2/2✓ Branch 0 taken 439 times.
✓ Branch 1 taken 119 times.
|
558 | if(theBitCount) { |
| 172 | 439 | theByte = theByteArray[theByteIndex]; | |
| 173 | − | assert((uint_fast8_t)theByte & Om_Bit_MaskRemainder(theBitCount)); | |
| 174 | 439 | theCodeUnit = (char)( | |
| 175 | 439 | (uint_fast8_t)theString[theByteIndex] | Om_Bit_MaskRemainder(theBitCount) | |
| 176 | ); | ||
| 177 |
2/2✓ Branch 0 taken 43 times.
✓ Branch 1 taken 396 times.
|
439 | if(theByte != theCodeUnit) { |
| 178 | 43 | goto Mismatch; | |
| 179 | } | ||
| 180 | − | assert(theByte); | |
| 181 | } | ||
| 182 | |||
| 183 | 515 | return SIZE_MAX; | |
| 184 | |||
| 185 | 146 | Mismatch: | |
| 186 | |||
| 187 | 292 | *theBitIndex = Om_Bit_FindMismatch( | |
| 188 | 146 | (uint_fast8_t)(*theBitIndex * !theByteIndex), theByte, theCodeUnit | |
| 189 | ); | ||
| 190 | − | assert(*theBitIndex < CHAR_BIT); | |
| 191 | 146 | return theByteIndex; | |
| 192 | } | ||
| 193 | |||
| 194 | 6639 | Om_Tree_Branch * Om_Tree_BranchNode_GetBranch( | |
| 195 | Om_Tree_BranchNode const theBranchNode | ||
| 196 | ) { | ||
| 197 | static_assert(Om_Alignment > 0U, "The alignment must be positive."); | ||
| 198 | static_assert(!((uint_fast8_t)Om_Alignment & (Om_Alignment - 1U)), | ||
| 199 | "The alignment must be a power of 2." | ||
| 200 | ); | ||
| 201 | |||
| 202 | // NOLINTNEXTLINE(performance-no-int-to-ptr) | ||
| 203 | 6639 | return (Om_Tree_Branch *)(theBranchNode & ~(uintptr_t)(Om_Alignment - 1U)); | |
| 204 | } | ||
| 205 | |||
| 206 | 6181 | uint_fast8_t Om_Tree_BranchNode_GetBranchBitCount( | |
| 207 | Om_Tree_BranchNode const theBranchNode | ||
| 208 | ) { | ||
| 209 | static_assert(CHAR_BIT > 0U, "The byte size must be positive."); | ||
| 210 | static_assert(Om_Alignment >= CHAR_BIT, | ||
| 211 | "The alignment must be greater than or equal to the byte size." | ||
| 212 | ); | ||
| 213 | static_assert(!(CHAR_BIT & (CHAR_BIT - 1U)), | ||
| 214 | "The byte size must be a power of 2." | ||
| 215 | ); | ||
| 216 | |||
| 217 | 6181 | return (uint_fast8_t)(theBranchNode & (CHAR_BIT - 1U)); | |
| 218 | } | ||
| 219 | |||
| 220 | // NOLINTNEXTLINE(readability-function-cognitive-complexity) | ||
| 221 | 49 | Om_Tree_BranchNode Om_Tree_BranchNode_CreateCopy( | |
| 222 | Om_Tree_BranchNode theBranchNode, | ||
| 223 | Om_Tree_LeafNode_Interface const * const theLeafNodeInterface, | ||
| 224 | Om_Tree_NodeStack * const theStack, | ||
| 225 | Om_Tree_NodePointerStack * const theCopyStack | ||
| 226 | ) { | ||
| 227 | − | assert(theBranchNode != (Om_Tree_BranchNode)NULL); | |
| 228 | − | assert(theStack); | |
| 229 | − | assert(Om_Tree_NodeStack_IsEmpty(theStack)); | |
| 230 | − | assert(theCopyStack); | |
| 231 | − | assert(Om_Tree_NodePointerStack_IsEmpty(theCopyStack)); | |
| 232 | |||
| 233 | 49 | Om_Tree_BranchNode theCopy = (Om_Tree_BranchNode)NULL; | |
| 234 | 276 | for(Om_Tree_BranchNode * theBranchNodeCopy = &theCopy;; ) { | |
| 235 | 247 | for(;; ) { | |
| 236 | 523 | Om_Tree_Branch * const theBranch = Om_Tree_BranchNode_GetBranch( | |
| 237 | theBranchNode | ||
| 238 | ); | ||
| 239 | − | assert(theBranch); | |
| 240 | uint_fast8_t const theBranchBitCount = ( | ||
| 241 | 523 | Om_Tree_BranchNode_GetBranchBitCount(theBranchNode) | |
| 242 | ); | ||
| 243 | |||
| 244 | 523 | Om_Tree_Branch * const theBranchCopy = Om_Tree_Branch_CreateCopy( | |
| 245 | theBranch | ||
| 246 | ); | ||
| 247 |
2/2✓ Branch 0 taken 7 times.
✓ Branch 1 taken 516 times.
|
523 | if(!theBranchCopy) { |
| 248 |
2/2✓ Branch 0 taken 5 times.
✓ Branch 1 taken 2 times.
|
7 | if(theCopy != (Om_Tree_BranchNode)NULL) { |
| 249 | 5 | Om_Tree_NodeStack_Clear(theStack); | |
| 250 | 5 | Om_Tree_BranchNode_Destroy(theCopy, theLeafNodeInterface, theStack); | |
| 251 | } | ||
| 252 | 7 | return (Om_Tree_BranchNode)NULL; | |
| 253 | } | ||
| 254 | 516 | *theBranchNodeCopy = Om_Tree_BranchNode_Create( | |
| 255 | theBranchCopy, theBranchBitCount | ||
| 256 | ); | ||
| 257 | |||
| 258 | 516 | Om_Tree_Node const theChild0 = Om_Tree_Branch_GetChildArray(theBranch)[0]; | |
| 259 | 516 | Om_Tree_Node const theChild1 = Om_Tree_Branch_GetChildArray(theBranch)[1]; | |
| 260 | |||
| 261 | 516 | Om_Tree_Node * const theChildCopy0 = Om_Tree_Branch_GetChildArray( | |
| 262 | theBranchCopy | ||
| 263 | ); | ||
| 264 | 516 | Om_Tree_Node * const theChildCopy1 = theChildCopy0 + 1; | |
| 265 | |||
| 266 | 516 | *theChildCopy1 = (Om_Tree_BranchNode)NULL; | |
| 267 |
2/2✓ Branch 1 taken 285 times.
✓ Branch 2 taken 231 times.
|
516 | if(Om_Tree_Branch_HasLeafChild(theBranch, theBranchBitCount)) { |
| 268 |
2/2✓ Branch 0 taken 6 times.
✓ Branch 1 taken 279 times.
|
285 | if(theLeafNodeInterface) { |
| 269 | − | assert(theLeafNodeInterface->InitializeCopy); | |
| 270 | // The function is guaranteed to set the copy to a value that can be | ||
| 271 | // destroyed safely, even if it fails. | ||
| 272 |
2/2✓ Branch 1 taken 2 times.
✓ Branch 2 taken 4 times.
|
6 | if(!theLeafNodeInterface->InitializeCopy(theChildCopy0, theChild0)) { |
| 273 | 2 | Om_Tree_NodeStack_Clear(theStack); | |
| 274 | 2 | Om_Tree_BranchNode_Destroy(theCopy, theLeafNodeInterface, theStack); | |
| 275 | 2 | return (Om_Tree_BranchNode)NULL; | |
| 276 | } | ||
| 277 | } else { | ||
| 278 | 279 | *theChildCopy0 = theChild0; | |
| 279 | } | ||
| 280 | |||
| 281 |
2/2✓ Branch 0 taken 267 times.
✓ Branch 1 taken 16 times.
|
283 | if(theChild1 == (Om_Tree_BranchNode)NULL) { |
| 282 | 267 | break; | |
| 283 | } | ||
| 284 | } else { | ||
| 285 | − | assert(theChild0 != (Om_Tree_BranchNode)NULL); | |
| 286 | − | assert(theChild1 != (Om_Tree_BranchNode)NULL); | |
| 287 | 231 | *theChildCopy0 = (Om_Tree_BranchNode)NULL; | |
| 288 | 231 | Om_Tree_NodeStack_Push(theStack, theChild0); | |
| 289 | 231 | Om_Tree_NodePointerStack_Push(theCopyStack, theChildCopy0); | |
| 290 | } | ||
| 291 | 247 | theBranchNode = theChild1; | |
| 292 | 247 | theBranchNodeCopy = theChildCopy1; | |
| 293 | } | ||
| 294 | |||
| 295 |
2/2✓ Branch 1 taken 40 times.
✓ Branch 2 taken 227 times.
|
267 | if(Om_Tree_NodeStack_IsEmpty(theStack)) { |
| 296 | − | assert(Om_Tree_NodePointerStack_IsEmpty(theCopyStack)); | |
| 297 | 40 | return theCopy; | |
| 298 | } | ||
| 299 | 227 | theBranchNode = Om_Tree_NodeStack_Pop(theStack); | |
| 300 | − | assert(theBranchNode != (Om_Tree_BranchNode)NULL); | |
| 301 | 227 | theBranchNodeCopy = Om_Tree_NodePointerStack_Pop(theCopyStack); | |
| 302 | − | assert(theBranchNodeCopy); | |
| 303 | − | assert(*theBranchNodeCopy == (Om_Tree_BranchNode)NULL); | |
| 304 | } | ||
| 305 | } | ||
| 306 | |||
| 307 | // NOLINTNEXTLINE(readability-function-cognitive-complexity) | ||
| 308 | 212 | int Om_Tree_BranchNode_Insert( | |
| 309 | Om_Tree_BranchNode * theBranchNode, | ||
| 310 | size_t const theStringLength, | ||
| 311 | char const * const theString, | ||
| 312 | Om_Tree_LeafNode * * const theLeafNode | ||
| 313 | ) { | ||
| 314 | − | assert(theBranchNode); | |
| 315 | − | assert(theString); | |
| 316 | − | assert(theStringLength == strlen(theString)); | |
| 317 | − | assert(theLeafNode); | |
| 318 | |||
| 319 | 212 | size_t theStringIndex = 0U; | |
| 320 | |||
| 321 | // Iterate down through trees until the branch node pointer points to empty. | ||
| 322 | 212 | for( | |
| 323 | 212 | uint_fast8_t theBitOffset = 0U; | |
| 324 |
2/2✓ Branch 0 taken 661 times.
✓ Branch 1 taken 52 times.
|
713 | *theBranchNode != (Om_Tree_BranchNode)NULL; |
| 325 | ) { | ||
| 326 | 661 | Om_Tree_Branch * theBranch = Om_Tree_BranchNode_GetBranch(*theBranchNode); | |
| 327 | − | assert(theBranch); | |
| 328 | 661 | uint_fast8_t theBranchBitCount = Om_Tree_BranchNode_GetBranchBitCount( | |
| 329 | *theBranchNode | ||
| 330 | ); | ||
| 331 | |||
| 332 | // Advance past the branch byte array, or split and return if there is a | ||
| 333 | // mismatch. | ||
| 334 | { | ||
| 335 | 661 | size_t const theBranchByteCount = Om_Tree_Branch_GetByteCount( | |
| 336 | theBranch, theBranchBitCount | ||
| 337 | ); | ||
| 338 | |||
| 339 | 661 | char const * const theBranchByteArray = Om_Tree_Branch_GetByteArray( | |
| 340 | theBranch | ||
| 341 | ); | ||
| 342 | − | assert(theBranchByteArray); | |
| 343 | |||
| 344 | // If there is a byte array mismatch, split the branch. | ||
| 345 | 661 | uint_fast8_t theBitIndex = theBitOffset; | |
| 346 | 661 | size_t const theByteIndex = Om_Tree_BranchNode_FindMismatch( | |
| 347 | theBranchByteCount, theBranchByteArray, theBranchBitCount, | ||
| 348 | theString + theStringIndex, &theBitIndex | ||
| 349 | ); | ||
| 350 |
2/2✓ Branch 0 taken 146 times.
✓ Branch 1 taken 515 times.
|
661 | if(theByteIndex != SIZE_MAX) { |
| 351 | 146 | theStringIndex += theByteIndex; | |
| 352 | |||
| 353 | // If the mismatch is the last bit of the null terminator, split the | ||
| 354 | // branch and make the "other" child the leaf. | ||
| 355 | − | assert(theBitIndex < CHAR_BIT); | |
| 356 |
4/4✓ Branch 0 taken 11 times.
✓ Branch 1 taken 135 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 7 times.
|
146 | if(!theString[theStringIndex] && (theBitIndex == (CHAR_BIT - 1U))) { |
| 357 | 4 | theBranch = Om_Tree_BranchNode_Split( | |
| 358 | theBranch, &theBranchBitCount, theByteIndex, theBitIndex, 0U | ||
| 359 | ); | ||
| 360 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3 times.
|
4 | if(!theBranch) { |
| 361 | 1 | return 0; | |
| 362 | } | ||
| 363 | 3 | *theBranchNode = Om_Tree_BranchNode_Create( | |
| 364 | theBranch, theBranchBitCount | ||
| 365 | ); | ||
| 366 | 3 | *theLeafNode = Om_Tree_Branch_GetChildArray(theBranch); | |
| 367 | 3 | return 1; | |
| 368 | } | ||
| 369 | |||
| 370 | // Advance the string if the byte won't be repeated in the child. | ||
| 371 | 142 | theStringIndex += (theBitIndex == (CHAR_BIT - 1U)); | |
| 372 | |||
| 373 | // Create a child branch to hold the string remainder. | ||
| 374 | − | assert(theStringIndex <= theStringLength); | |
| 375 | 142 | uint_fast8_t theChildBranchBitCount = 0U; | |
| 376 | 142 | Om_Tree_Branch * const theChildBranch = Om_Tree_Branch_Create( | |
| 377 | &theChildBranchBitCount, | ||
| 378 | theStringLength - theStringIndex, | ||
| 379 | theString + theStringIndex | ||
| 380 | ); | ||
| 381 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 139 times.
|
142 | if(!theChildBranch) { |
| 382 | 3 | return 0; | |
| 383 | } | ||
| 384 | 139 | Om_Tree_Node * const theGrandchildArray = Om_Tree_Branch_GetChildArray( | |
| 385 | theChildBranch | ||
| 386 | ); | ||
| 387 | 139 | theGrandchildArray[1] = (Om_Tree_BranchNode)NULL; | |
| 388 | 139 | *theLeafNode = theGrandchildArray; | |
| 389 | |||
| 390 | // Split the branch and set the "other" child to the new child branch. | ||
| 391 | 139 | theBranch = Om_Tree_BranchNode_Split( | |
| 392 | theBranch, &theBranchBitCount, theByteIndex, theBitIndex, | ||
| 393 | Om_Tree_BranchNode_Create(theChildBranch, theChildBranchBitCount) | ||
| 394 | ); | ||
| 395 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 137 times.
|
139 | if(!theBranch) { |
| 396 | 2 | Om_Tree_Branch_Destroy(theChildBranch); | |
| 397 | 2 | return 0; | |
| 398 | } | ||
| 399 | 137 | *theBranchNode = Om_Tree_BranchNode_Create( | |
| 400 | theBranch, theBranchBitCount | ||
| 401 | ); | ||
| 402 | 137 | return 1; | |
| 403 | } | ||
| 404 | |||
| 405 | 515 | theStringIndex += theBranchByteCount; | |
| 406 | } | ||
| 407 | |||
| 408 | 515 | bool const theChildOffset = Om_Bit_Get( | |
| 409 | theString[theStringIndex], theBranchBitCount | ||
| 410 | ); | ||
| 411 | 515 | Om_Tree_Node * const theChild = ( | |
| 412 | 515 | Om_Tree_Branch_GetChildArray(theBranch) + theChildOffset | |
| 413 | ); | ||
| 414 | |||
| 415 | // Compute the new bit offset by advancing past the critical bit, modulo | ||
| 416 | // `CHAR_BIT`. | ||
| 417 | 515 | theBitOffset = (theBranchBitCount + 1U) % CHAR_BIT; | |
| 418 |
2/2✓ Branch 0 taken 37 times.
✓ Branch 1 taken 478 times.
|
515 | if(!theBitOffset) { |
| 419 |
2/2✓ Branch 0 taken 14 times.
✓ Branch 1 taken 23 times.
|
37 | if(!theString[theStringIndex]) { |
| 420 | // Since the whole branch byte array was matched, the null terminator | ||
| 421 | // here means that there is a leaf child; return it. | ||
| 422 | − | assert(Om_Tree_Branch_HasLeafChild(theBranch, theBranchBitCount)); | |
| 423 | − | assert(!theChildOffset); | |
| 424 | 14 | *theLeafNode = theChild; | |
| 425 | 14 | return -1; | |
| 426 | } | ||
| 427 | |||
| 428 | // The byte is not repeated in the child. | ||
| 429 | 23 | ++theStringIndex; | |
| 430 | } | ||
| 431 | |||
| 432 | 501 | theBranchNode = theChild; | |
| 433 | } | ||
| 434 | − | assert(*theBranchNode == (Om_Tree_BranchNode)NULL); | |
| 435 | |||
| 436 | // The branch is null. Set it to a new branch containing the remainder of the | ||
| 437 | // string, if any, and whose 0 child is the leaf to return. | ||
| 438 | − | assert(theStringIndex <= theStringLength); | |
| 439 | 52 | uint_fast8_t theBranchBitCount = 0U; | |
| 440 | 52 | Om_Tree_Branch * const theBranch = Om_Tree_Branch_Create( | |
| 441 | &theBranchBitCount, | ||
| 442 | theStringLength - theStringIndex, | ||
| 443 | theString + theStringIndex | ||
| 444 | ); | ||
| 445 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 50 times.
|
52 | if(!theBranch) { |
| 446 | 2 | return 0; | |
| 447 | } | ||
| 448 | 50 | Om_Tree_Node * const theChildArray = Om_Tree_Branch_GetChildArray(theBranch); | |
| 449 | 50 | theChildArray[1] = (Om_Tree_BranchNode)NULL; | |
| 450 | 50 | *theLeafNode = theChildArray; | |
| 451 | |||
| 452 | 50 | *theBranchNode = Om_Tree_BranchNode_Create(theBranch, theBranchBitCount); | |
| 453 | 50 | return 1; | |
| 454 | } | ||
| 455 | |||
| 456 | // NOLINTNEXTLINE(readability-function-cognitive-complexity) | ||
| 457 | 138 | int Om_Tree_BranchNode_Remove( | |
| 458 | Om_Tree_BranchNode * theBranchNode, | ||
| 459 | size_t const theStringLength, | ||
| 460 | char const * const theString, | ||
| 461 | Om_Tree_LeafNode * const theLeafNode | ||
| 462 | ) { | ||
| 463 | − | assert(theBranchNode); | |
| 464 | − | assert(theString); | |
| 465 | − | assert(theStringLength == strlen(theString)); | |
| 466 | − | assert(theLeafNode); | |
| 467 | |||
| 468 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 137 times.
|
138 | if(*theBranchNode == (Om_Tree_BranchNode)NULL) { |
| 469 | 1 | return -1; | |
| 470 | } | ||
| 471 | |||
| 472 | 137 | Om_Tree_BranchNode * theParentBranchNode = NULL; | |
| 473 | 137 | Om_Tree_Branch * theParentBranch = NULL; | |
| 474 | 137 | uint_fast8_t theParentBranchBitCount = 0U; | |
| 475 | 137 | bool theParentHasLeafChild = false; | |
| 476 | 137 | bool theBranchOffset = false; | |
| 477 | |||
| 478 | 137 | for(size_t theStringIndex = 0U;; ) { | |
| 479 | 570 | Om_Tree_Branch * theBranch = Om_Tree_BranchNode_GetBranch(*theBranchNode); | |
| 480 | − | assert(theBranch); | |
| 481 | 570 | uint_fast8_t theBranchBitCount = Om_Tree_BranchNode_GetBranchBitCount( | |
| 482 | *theBranchNode | ||
| 483 | ); | ||
| 484 | |||
| 485 | // Advance past the branch byte array, or return -1 if there is a mismatch. | ||
| 486 | { | ||
| 487 | 570 | size_t const theBranchByteCount = Om_Tree_Branch_GetByteCount( | |
| 488 | theBranch, theBranchBitCount | ||
| 489 | ); | ||
| 490 | |||
| 491 | 570 | char const * const theBranchByteArray = Om_Tree_Branch_GetByteArray( | |
| 492 | theBranch | ||
| 493 | ); | ||
| 494 | − | assert(theBranchByteArray); | |
| 495 | |||
| 496 | − | assert(theStringIndex <= theStringLength); | |
| 497 | 570 | if( | |
| 498 |
2/2✓ Branch 0 taken 568 times.
✓ Branch 1 taken 2 times.
|
570 | ((theStringLength - theStringIndex) < theBranchByteCount) || ( |
| 499 |
2/2✓ Branch 0 taken 484 times.
✓ Branch 1 taken 84 times.
|
568 | theBranchBitCount && ( |
| 500 | 484 | theBranchByteArray[theBranchByteCount] != (char)( | |
| 501 | 484 | (uint_fast8_t)(theString + theStringIndex)[theBranchByteCount] | | |
| 502 |
2/2✓ Branch 0 taken 479 times.
✓ Branch 1 taken 5 times.
|
484 | Om_Bit_MaskRemainder(theBranchBitCount) |
| 503 | ) | ||
| 504 | ) | ||
| 505 | 563 | ) || ( | |
| 506 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 559 times.
|
563 | 0 != strncmp( |
| 507 | theBranchByteArray, theString + theStringIndex, theBranchByteCount | ||
| 508 | ) | ||
| 509 | ) | ||
| 510 | ) { | ||
| 511 | 137 | return -1; | |
| 512 | } | ||
| 513 | |||
| 514 | 559 | theStringIndex += theBranchByteCount; | |
| 515 | } | ||
| 516 | |||
| 517 | 559 | bool const theChildOffset = Om_Bit_Get( | |
| 518 | theString[theStringIndex], theBranchBitCount | ||
| 519 | ); | ||
| 520 | 559 | Om_Tree_Node * const theChild = ( | |
| 521 | 559 | Om_Tree_Branch_GetChildArray(theBranch) + theChildOffset | |
| 522 | ); | ||
| 523 | |||
| 524 | 559 | bool const hasLeafChild = Om_Tree_Branch_HasLeafChild( | |
| 525 | theBranch, theBranchBitCount | ||
| 526 | ); | ||
| 527 |
2/2✓ Branch 0 taken 128 times.
✓ Branch 1 taken 431 times.
|
559 | if(hasLeafChild) { |
| 528 | // If the child is a leaf, remove it and return. | ||
| 529 |
2/2✓ Branch 0 taken 125 times.
✓ Branch 1 taken 3 times.
|
128 | if(!theChildOffset) { |
| 530 | − | assert(!theString[theStringIndex]); | |
| 531 | 125 | *theLeafNode = *theChild; | |
| 532 | |||
| 533 | // If the leaf sibling is null, destroy this branch. | ||
| 534 | − | assert(!theChildOffset); | |
| 535 | 125 | if( | |
| 536 |
2/2✓ Branch 1 taken 119 times.
✓ Branch 2 taken 6 times.
|
125 | Om_Tree_Branch_GetChildArray(theBranch)[1U] == |
| 537 | (Om_Tree_BranchNode)NULL | ||
| 538 | ) { | ||
| 539 | // Destroy the branch node, but cache the old value in case a | ||
| 540 | // roll-back is needed due to error. | ||
| 541 | 119 | Om_Tree_BranchNode const theOldBranchNode = *theBranchNode; | |
| 542 | 119 | *theBranchNode = (Om_Tree_BranchNode)NULL; | |
| 543 | |||
| 544 | // If there is a parent and the branch sibling is a branch, merge it. | ||
| 545 | // It is necessarily non-null: if both children are branches, they | ||
| 546 | // must both be non-null. | ||
| 547 |
6/6✓ Branch 0 taken 115 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 109 times.
✓ Branch 4 taken 4 times.
✓ Branch 5 taken 2 times.
|
119 | if(theParentBranch && (!theBranchOffset || !theParentHasLeafChild)) { |
| 548 | − | assert( | |
| 549 | Om_Tree_Branch_GetChildArray(theParentBranch)[!theBranchOffset] != | ||
| 550 | (Om_Tree_BranchNode)NULL | ||
| 551 | ); | ||
| 552 | |||
| 553 | 113 | theParentBranch = Om_Tree_BranchNode_Merge( | |
| 554 | 113 | theParentBranch, &theParentBranchBitCount, !theBranchOffset | |
| 555 | 113 | ); | |
| 556 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 111 times.
|
113 | if(!theParentBranch) { |
| 557 | 2 | *theBranchNode = theOldBranchNode; | |
| 558 | 2 | return 0; | |
| 559 | } | ||
| 560 | 111 | *theParentBranchNode = Om_Tree_BranchNode_Create( | |
| 561 | theParentBranch, theParentBranchBitCount | ||
| 562 | ); | ||
| 563 | } | ||
| 564 | |||
| 565 | // Destroy the branch and return. | ||
| 566 | 117 | Om_Tree_Branch_Destroy(theBranch); | |
| 567 | 117 | return 1; | |
| 568 | } | ||
| 569 | |||
| 570 | // The other child isn't null. Merge it with the branch. | ||
| 571 | 6 | theBranch = Om_Tree_BranchNode_Merge( | |
| 572 | 6 | theBranch, &theBranchBitCount, !theChildOffset | |
| 573 | 6 | ); | |
| 574 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 5 times.
|
6 | if(!theBranch) { |
| 575 | 1 | return 0; | |
| 576 | } | ||
| 577 | 5 | *theBranchNode = Om_Tree_BranchNode_Create( | |
| 578 | theBranch, theBranchBitCount | ||
| 579 | ); | ||
| 580 | 5 | return 1; | |
| 581 | } | ||
| 582 | |||
| 583 | // The child is a branch. If it's empty, we're done. | ||
| 584 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2 times.
|
3 | if(*theChild == (Om_Tree_BranchNode)NULL) { |
| 585 | 1 | return -1; | |
| 586 | } | ||
| 587 | } | ||
| 588 | − | assert(*theChild != (Om_Tree_BranchNode)NULL); | |
| 589 | |||
| 590 | // If the critical bit is rightmost, the byte is not repeated in the child. | ||
| 591 | − | assert((theBranchBitCount != (CHAR_BIT - 1U)) || theString[theStringIndex]); | |
| 592 | 433 | theStringIndex += (theBranchBitCount == (CHAR_BIT - 1U)); | |
| 593 | |||
| 594 | 433 | theParentBranchNode = theBranchNode; | |
| 595 | 433 | theParentBranch = theBranch; | |
| 596 | 433 | theParentBranchBitCount = theBranchBitCount; | |
| 597 | 433 | theParentHasLeafChild = hasLeafChild; | |
| 598 | 433 | theBranchOffset = theChildOffset; | |
| 599 | 433 | theBranchNode = theChild; | |
| 600 | } | ||
| 601 | } | ||
| 602 | |||
| 603 | // NOLINTNEXTLINE(misc-no-recursion, readability-function-cognitive-complexity) | ||
| 604 | 60 | bool Om_Tree_BranchNode_Match( | |
| 605 | Om_Tree_BranchNode theBranchNode, | ||
| 606 | Om_Tree_BranchNode theOtherBranchNode, | ||
| 607 | Om_Tree_LeafNode_Interface const * const theLeafNodeInterface, | ||
| 608 | Om_Tree_NodeStack * const theStack, | ||
| 609 | Om_Tree_NodeStack * const theOtherStack | ||
| 610 | ) { | ||
| 611 | − | assert(theBranchNode != (Om_Tree_BranchNode)NULL); | |
| 612 | − | assert(theOtherBranchNode != (Om_Tree_BranchNode)NULL); | |
| 613 | − | assert(theBranchNode != theOtherBranchNode); | |
| 614 | − | assert(!theStack || Om_Tree_NodeStack_IsEmpty(theStack)); | |
| 615 | − | assert(!theOtherStack || Om_Tree_NodeStack_IsEmpty(theOtherStack)); | |
| 616 | |||
| 617 | 224 | for(;; ) { | |
| 618 | 240 | for(;; ) { | |
| 619 | 524 | Om_Tree_Branch * const theBranch = Om_Tree_BranchNode_GetBranch( | |
| 620 | theBranchNode | ||
| 621 | ); | ||
| 622 | − | assert(theBranch); | |
| 623 | uint_fast8_t const theBranchBitCount = ( | ||
| 624 | 524 | Om_Tree_BranchNode_GetBranchBitCount(theBranchNode) | |
| 625 | ); | ||
| 626 | |||
| 627 | Om_Tree_Branch * const theOtherBranch = ( | ||
| 628 | 524 | Om_Tree_BranchNode_GetBranch(theOtherBranchNode) | |
| 629 | ); | ||
| 630 | − | assert(theOtherBranch); | |
| 631 | uint_fast8_t const theOtherBranchBitCount = ( | ||
| 632 | 524 | Om_Tree_BranchNode_GetBranchBitCount(theOtherBranchNode) | |
| 633 | ); | ||
| 634 | |||
| 635 | 524 | if( | |
| 636 |
2/2✓ Branch 1 taken 10 times.
✓ Branch 2 taken 514 times.
|
524 | !Om_Tree_Branch_Match( |
| 637 | theBranch, theBranchBitCount, theOtherBranch, theOtherBranchBitCount | ||
| 638 | ) | ||
| 639 | ) { | ||
| 640 | 10 | return false; | |
| 641 | } | ||
| 642 | |||
| 643 | 514 | Om_Tree_Node const theChild0 = Om_Tree_Branch_GetChildArray(theBranch)[0]; | |
| 644 | 514 | Om_Tree_Node const theChild1 = Om_Tree_Branch_GetChildArray(theBranch)[1]; | |
| 645 | |||
| 646 | 514 | Om_Tree_Node const theOtherChild0 = Om_Tree_Branch_GetChildArray( | |
| 647 | theOtherBranch | ||
| 648 | 514 | )[0]; | |
| 649 | 514 | Om_Tree_Node const theOtherChild1 = Om_Tree_Branch_GetChildArray( | |
| 650 | theOtherBranch | ||
| 651 | )[1]; | ||
| 652 | |||
| 653 |
2/2✓ Branch 1 taken 283 times.
✓ Branch 2 taken 231 times.
|
514 | if(Om_Tree_Branch_HasLeafChild(theBranch, theBranchBitCount)) { |
| 654 | − | assert(Om_Tree_Branch_HasLeafChild(theOtherBranch, theBranchBitCount)); | |
| 655 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 279 times.
|
283 | if(theLeafNodeInterface) { |
| 656 | − | assert(theLeafNodeInterface->Match); | |
| 657 |
2/2✓ Branch 1 taken 2 times.
✓ Branch 2 taken 2 times.
|
4 | if(!theLeafNodeInterface->Match(theChild0, theOtherChild0)) { |
| 658 | 2 | return false; | |
| 659 | } | ||
| 660 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 277 times.
|
279 | } else if(theChild0 != theOtherChild0) { |
| 661 | 2 | return false; | |
| 662 | } | ||
| 663 | |||
| 664 |
2/2✓ Branch 0 taken 14 times.
✓ Branch 1 taken 265 times.
|
279 | if( |
| 665 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 13 times.
|
14 | (theChild1 == (Om_Tree_BranchNode)NULL) || |
| 666 | (theOtherChild1 == (Om_Tree_BranchNode)NULL) | ||
| 667 | ) { | ||
| 668 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 264 times.
|
266 | if(theChild1 != theOtherChild1) { |
| 669 | 2 | return false; | |
| 670 | } | ||
| 671 | 264 | break; | |
| 672 | } | ||
| 673 | } else { | ||
| 674 | − | assert(theChild0 != (Om_Tree_BranchNode)NULL); | |
| 675 | − | assert(theChild1 != (Om_Tree_BranchNode)NULL); | |
| 676 | − | assert(theOtherChild0 != (Om_Tree_BranchNode)NULL); | |
| 677 | − | assert(theOtherChild1 != (Om_Tree_BranchNode)NULL); | |
| 678 |
4/4✓ Branch 0 taken 227 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 226 times.
|
231 | if(!theStack || !theOtherStack) { |
| 679 | 5 | if( | |
| 680 |
2/2✓ Branch 1 taken 4 times.
✓ Branch 2 taken 1 times.
|
5 | !Om_Tree_BranchNode_Match( |
| 681 | theChild0, theOtherChild0, theLeafNodeInterface, NULL, NULL | ||
| 682 | ) | ||
| 683 | ) { | ||
| 684 | 4 | return false; | |
| 685 | } | ||
| 686 | } else { | ||
| 687 | 226 | Om_Tree_NodeStack_Push(theStack, theChild0); | |
| 688 | 226 | Om_Tree_NodeStack_Push(theOtherStack, theOtherChild0); | |
| 689 | } | ||
| 690 | } | ||
| 691 | 240 | theBranchNode = theChild1; | |
| 692 | 240 | theOtherBranchNode = theOtherChild1; | |
| 693 | } | ||
| 694 | |||
| 695 |
4/4✓ Branch 0 taken 262 times.
✓ Branch 1 taken 2 times.
✓ Branch 3 taken 38 times.
✓ Branch 4 taken 224 times.
|
264 | if(!theStack || Om_Tree_NodeStack_IsEmpty(theStack)) { |
| 696 | − | assert(!theOtherStack || Om_Tree_NodeStack_IsEmpty(theOtherStack)); | |
| 697 | 40 | return true; | |
| 698 | } | ||
| 699 | 224 | theBranchNode = Om_Tree_NodeStack_Pop(theStack); | |
| 700 | − | assert(theBranchNode != (Om_Tree_BranchNode)NULL); | |
| 701 | 224 | theOtherBranchNode = Om_Tree_NodeStack_Pop(theOtherStack); | |
| 702 | − | assert(theOtherBranchNode != (Om_Tree_BranchNode)NULL); | |
| 703 | } | ||
| 704 | } | ||
| 705 | |||
| 706 | #if Om_Tree_IsPrintEnabled | ||
| 707 | // NOLINTNEXTLINE(misc-no-recursion, readability-function-cognitive-complexity) | ||
| 708 | 1302 | bool Om_Tree_BranchNode_Print( | |
| 709 | Om_Tree_BranchNode const theBranchNode, | ||
| 710 | FILE * const theStream, | ||
| 711 | uintmax_t const theIndent, | ||
| 712 | Om_Tree_LeafNode_Interface const * const theLeafNodeInterface | ||
| 713 | ) { | ||
| 714 | − | assert(!theLeafNodeInterface || theLeafNodeInterface->Print); | |
| 715 | − | assert(theStream); | |
| 716 | |||
| 717 | 1302 | Om_Tree_Branch * const theBranch = Om_Tree_BranchNode_GetBranch( | |
| 718 | theBranchNode | ||
| 719 | ); | ||
| 720 |
2/2✓ Branch 0 taken 458 times.
✓ Branch 1 taken 844 times.
|
1302 | if(!theBranch) { |
| 721 | 458 | return (fputs("-\n", theStream) != EOF); | |
| 722 | } | ||
| 723 | uint_fast8_t const theBranchBitCount = ( | ||
| 724 | 844 | Om_Tree_BranchNode_GetBranchBitCount(theBranchNode) | |
| 725 | ); | ||
| 726 | |||
| 727 | // Print an opening quote for the branch bytes. | ||
| 728 | // LCOV_EXCL_START | ||
| 729 | − | if(fputc('\"', theStream) == EOF) { | |
| 730 | − | return false; | |
| 731 | } | ||
| 732 | // LCOV_EXCL_STOP | ||
| 733 | |||
| 734 | // Print the branch byte array. | ||
| 735 | 844 | char const * const theBranchByteArray = Om_Tree_Branch_GetByteArray( | |
| 736 | theBranch | ||
| 737 | ); | ||
| 738 | 844 | size_t const theBranchByteCount = Om_Tree_Branch_GetByteCount( | |
| 739 | theBranch, theBranchBitCount | ||
| 740 | ); | ||
| 741 | // LCOV_EXCL_START | ||
| 742 | − | if( | |
| 743 | − | !Om_Print_BinaryByteArray(theBranchByteCount, theBranchByteArray, theStream) | |
| 744 | ) { | ||
| 745 | − | return false; | |
| 746 | } | ||
| 747 | // LCOV_EXCL_STOP | ||
| 748 | |||
| 749 | // Print the bits of the partial branch byte, if any. | ||
| 750 |
2/2✓ Branch 0 taken 780 times.
✓ Branch 1 taken 64 times.
|
844 | if(theBranchBitCount) { |
| 751 | // LCOV_EXCL_START | ||
| 752 | − | if( | |
| 753 | − | (theBranchByteCount && (fputc(' ', theStream) == EOF)) || | |
| 754 | − | !Om_Print_BinaryByte(theBranchByteArray[theBranchByteCount], theStream) || | |
| 755 | − | (fprintf(theStream, ":%i", theBranchBitCount) < 0) | |
| 756 | ) { | ||
| 757 | − | return false; | |
| 758 | } | ||
| 759 | // LCOV_EXCL_STOP | ||
| 760 | } | ||
| 761 | |||
| 762 | // Print a closing quote and newline. | ||
| 763 | // LCOV_EXCL_START | ||
| 764 | − | if(fputs("\"\n", theStream) == EOF) { | |
| 765 | − | return false; | |
| 766 | } | ||
| 767 | // LCOV_EXCL_STOP | ||
| 768 | |||
| 769 | // Deal with an indentation overflow. | ||
| 770 | // LCOV_EXCL_START | ||
| 771 | − | if(theIndent == UINTMAX_MAX) { | |
| 772 | − | errno = ERANGE; | |
| 773 | − | if(Om_Print_Bytes('\t', theIndent, theStream)) { | |
| 774 | − | (void)fputs("...\n", theStream); | |
| 775 | } | ||
| 776 | − | return false; | |
| 777 | } | ||
| 778 | // LCOV_EXCL_STOP | ||
| 779 | |||
| 780 | // Print children. | ||
| 781 | 844 | bool theResult = true; | |
| 782 | 844 | Om_Tree_Node const theChild0 = Om_Tree_Branch_GetChildArray(theBranch)[0]; | |
| 783 | 844 | Om_Tree_Node const theChild1 = Om_Tree_Branch_GetChildArray(theBranch)[1]; | |
| 784 | // LCOV_EXCL_START | ||
| 785 | − | if( | |
| 786 | − | !Om_Print_Bytes('\t', theIndent, theStream) || | |
| 787 | − | (fputs("0 ", theStream) == EOF) | |
| 788 | ) { | ||
| 789 | − | return false; | |
| 790 | } | ||
| 791 | // LCOV_EXCL_STOP | ||
| 792 |
2/2✓ Branch 1 taken 490 times.
✓ Branch 2 taken 354 times.
|
844 | if(Om_Tree_Branch_HasLeafChild(theBranch, theBranchBitCount)) { |
| 793 | // LCOV_EXCL_START | ||
| 794 | − | if( | |
| 795 | − | (fputs(". ", theStream) == EOF) || | |
| 796 | ( | ||
| 797 | theLeafNodeInterface ? | ||
| 798 | − | !theLeafNodeInterface->Print(theChild0, theStream) : | |
| 799 | − | (fprintf(theStream, "%" PRIdPTR, theChild0) < 0) | |
| 800 | − | ) || | |
| 801 | − | (fputc('\n', theStream) == EOF) | |
| 802 | ) { | ||
| 803 | − | theResult = false; | |
| 804 | } | ||
| 805 | // LCOV_EXCL_STOP | ||
| 806 | } else { | ||
| 807 | // LCOV_EXCL_START | ||
| 808 | − | if( | |
| 809 | − | (fputs(": ", theStream) == EOF) || | |
| 810 | − | !Om_Tree_BranchNode_Print( | |
| 811 | theChild0, theStream, theIndent + 1U, theLeafNodeInterface | ||
| 812 | ) | ||
| 813 | ) { | ||
| 814 | − | theResult = false; | |
| 815 | } | ||
| 816 | // LCOV_EXCL_STOP | ||
| 817 | } | ||
| 818 | // LCOV_EXCL_START | ||
| 819 | − | if( | |
| 820 | − | !Om_Print_Bytes('\t', theIndent, theStream) || | |
| 821 | − | (fputs("1 : ", theStream) == EOF) | |
| 822 | ) { | ||
| 823 | − | return false; | |
| 824 | } | ||
| 825 | − | if( | |
| 826 | − | !Om_Tree_BranchNode_Print( | |
| 827 | theChild1, theStream, theIndent + 1U, theLeafNodeInterface | ||
| 828 | ) | ||
| 829 | ) { | ||
| 830 | − | theResult = false; | |
| 831 | } | ||
| 832 | // LCOV_EXCL_STOP | ||
| 833 | 844 | return theResult; | |
| 834 | } | ||
| 835 | #endif | ||
| 836 | |||
| 837 | // NOLINTNEXTLINE(misc-no-recursion, readability-function-cognitive-complexity) | ||
| 838 | 95 | void Om_Tree_BranchNode_Destroy( | |
| 839 | Om_Tree_BranchNode theBranchNode, | ||
| 840 | Om_Tree_LeafNode_Interface const * const theLeafNodeInterface, | ||
| 841 | Om_Tree_NodeStack * const theStack | ||
| 842 | ) { | ||
| 843 | − | assert(theBranchNode != (Om_Tree_BranchNode)NULL); | |
| 844 | − | assert(!theStack || Om_Tree_NodeStack_IsEmpty(theStack)); | |
| 845 | |||
| 846 | 515 | for(;; ) { | |
| 847 | 610 | Om_Tree_Branch * const theBranch = Om_Tree_BranchNode_GetBranch( | |
| 848 | theBranchNode | ||
| 849 | ); | ||
| 850 | − | assert(theBranch); | |
| 851 | 610 | uint_fast8_t const theBranchBitCount = Om_Tree_BranchNode_GetBranchBitCount( | |
| 852 | theBranchNode | ||
| 853 | ); | ||
| 854 | |||
| 855 | // Cache these before destroying the branch. | ||
| 856 | 610 | bool const hasLeafChild = Om_Tree_Branch_HasLeafChild( | |
| 857 | theBranch, theBranchBitCount | ||
| 858 | ); | ||
| 859 | 610 | Om_Tree_Node const theChild0 = Om_Tree_Branch_GetChildArray(theBranch)[0]; | |
| 860 | 610 | Om_Tree_Node const theChild1 = Om_Tree_Branch_GetChildArray(theBranch)[1]; | |
| 861 | |||
| 862 | 610 | Om_Tree_Branch_Destroy(theBranch); | |
| 863 | |||
| 864 | // Note that child branches can be null where it would not normally be | ||
| 865 | // permitted if this is called mid-copy due to an allocation error. | ||
| 866 |
2/2✓ Branch 0 taken 353 times.
✓ Branch 1 taken 257 times.
|
610 | if(hasLeafChild) { |
| 867 |
2/2✓ Branch 0 taken 12 times.
✓ Branch 1 taken 341 times.
|
353 | if(theLeafNodeInterface) { |
| 868 | − | assert(theLeafNodeInterface->Deinitialize); | |
| 869 | 12 | theLeafNodeInterface->Deinitialize(theChild0); | |
| 870 | } | ||
| 871 |
2/2✓ Branch 0 taken 251 times.
✓ Branch 1 taken 6 times.
|
257 | } else if(theChild0 != (Om_Tree_BranchNode)NULL) { |
| 872 |
2/2✓ Branch 0 taken 239 times.
✓ Branch 1 taken 12 times.
|
251 | if(theStack) { |
| 873 | 239 | Om_Tree_NodeStack_Push(theStack, theChild0); | |
| 874 | } else { | ||
| 875 | 12 | Om_Tree_BranchNode_Destroy(theChild0, theLeafNodeInterface, NULL); | |
| 876 | } | ||
| 877 | } | ||
| 878 | 610 | theBranchNode = theChild1; | |
| 879 |
2/2✓ Branch 0 taken 334 times.
✓ Branch 1 taken 276 times.
|
610 | if(theBranchNode == (Om_Tree_BranchNode)NULL) { |
| 880 |
4/4✓ Branch 0 taken 309 times.
✓ Branch 1 taken 25 times.
✓ Branch 3 taken 239 times.
✓ Branch 4 taken 70 times.
|
334 | if(!theStack || Om_Tree_NodeStack_IsEmpty(theStack)) { |
| 881 | break; | ||
| 882 | } | ||
| 883 | 239 | theBranchNode = Om_Tree_NodeStack_Pop(theStack); | |
| 884 | } | ||
| 885 | − | assert(theBranchNode != (Om_Tree_BranchNode)NULL); | |
| 886 | } | ||
| 887 | 95 | } | |
| 888 |