| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /*! | ||
| 2 | @file | ||
| 3 | @brief The @ref Om_Tree_Branch type and function definitions. | ||
| 4 | */ | ||
| 5 | |||
| 6 | #include <om/tree/branch.h> | ||
| 7 | |||
| 8 | #include <om/bit.h> | ||
| 9 | #include <om/memory.h> | ||
| 10 | |||
| 11 | #include <assert.h> | ||
| 12 | #include <limits.h> | ||
| 13 | #include <string.h> | ||
| 14 | |||
| 15 | /*! | ||
| 16 | @brief A tree branch. | ||
| 17 | */ | ||
| 18 | struct Om_Tree_Branch { | ||
| 19 | |||
| 20 | /*! | ||
| 21 | @brief An array of children. | ||
| 22 | @details The functions in this file treat the child nodes as opaque values; it | ||
| 23 | is up to the caller to manage the children as necessary. | ||
| 24 | */ | ||
| 25 | Om_Tree_Node thisChildArray[2U]; | ||
| 26 | |||
| 27 | /*! | ||
| 28 | @brief The size of the byte array. | ||
| 29 | */ | ||
| 30 | size_t thisByteArraySize; | ||
| 31 | |||
| 32 | /*! | ||
| 33 | @brief A byte array containing the bytes and bits that prefix each child. | ||
| 34 | @details If the bit count is non-zero, the last byte is a bit array with the | ||
| 35 | specified bit count, and all extra insignificant bits are set to 1. | ||
| 36 | */ | ||
| 37 | char thisByteArray[]; | ||
| 38 | |||
| 39 | }; | ||
| 40 | |||
| 41 | /*! | ||
| 42 | @brief Allocates memory for the branch and sets the byte array size. | ||
| 43 | @param theByteArray | ||
| 44 | The byte array to copy into the branch. | ||
| 45 | @param theByteArraySize | ||
| 46 | The size of the byte array to copy into the branch. | ||
| 47 | @returns The resulting branch, or null on failure. | ||
| 48 | */ | ||
| 49 | 860 | static Om_Tree_Branch * Om_Tree_Branch_Allocate( | |
| 50 | char const * Om_Restrict const theByteArray, | ||
| 51 | size_t const theByteArraySize | ||
| 52 | ) { | ||
| 53 | − | assert(theByteArray); | |
| 54 | |||
| 55 | 860 | Om_Tree_Branch * Om_Restrict const theBranch = Om_Memory_Allocate( | |
| 56 | sizeof(*theBranch) + theByteArraySize | ||
| 57 | ); | ||
| 58 |
2/2✓ Branch 0 taken 15 times.
✓ Branch 1 taken 845 times.
|
860 | if(!theBranch) { |
| 59 | 15 | return NULL; | |
| 60 | } | ||
| 61 | 845 | theBranch->thisByteArraySize = theByteArraySize; | |
| 62 | // NOLINTNEXTLINE(clang-analyzer-security.insecureAPI.DeprecatedOrUnsafeBufferHandling) | ||
| 63 | 845 | memcpy(theBranch->thisByteArray, theByteArray, theByteArraySize); | |
| 64 | 845 | return theBranch; | |
| 65 | } | ||
| 66 | |||
| 67 | /*! | ||
| 68 | @brief Shrinks the branch byte array and updates the byte array size. | ||
| 69 | @param theBranch | ||
| 70 | The branch. | ||
| 71 | @param theByteArraySize | ||
| 72 | The size to shrink the byte array to. | ||
| 73 | @returns The resulting branch; never null. | ||
| 74 | */ | ||
| 75 | 56 | static Om_Tree_Branch * Om_Tree_Branch_Shrink( | |
| 76 | Om_Tree_Branch * theBranch, | ||
| 77 | size_t const theByteArraySize | ||
| 78 | ) { | ||
| 79 | − | assert(theBranch); | |
| 80 | − | assert(theByteArraySize <= theBranch->thisByteArraySize); | |
| 81 | |||
| 82 | { | ||
| 83 | 56 | void * const theReallocation = Om_Memory_Reallocate( | |
| 84 | theBranch, sizeof(*theBranch) + theByteArraySize | ||
| 85 | ); | ||
| 86 |
2/2✓ Branch 0 taken 54 times.
✓ Branch 1 taken 2 times.
|
56 | if(theReallocation) { |
| 87 | 54 | theBranch = theReallocation; | |
| 88 | } | ||
| 89 | } | ||
| 90 | 56 | theBranch->thisByteArraySize = theByteArraySize; | |
| 91 | // cppcheck-suppress deallocret | ||
| 92 | 56 | return theBranch; | |
| 93 | } | ||
| 94 | |||
| 95 | /*! | ||
| 96 | @brief Grows the branch byte array and updates the byte array size. | ||
| 97 | @param theBranch | ||
| 98 | The branch. | ||
| 99 | @param theByteArraySize | ||
| 100 | The size to expand the byte array to. | ||
| 101 | @returns The resulting branch; null if allocation failed. | ||
| 102 | */ | ||
| 103 | 43 | static Om_Tree_Branch * Om_Tree_Branch_Grow( | |
| 104 | Om_Tree_Branch * theBranch, | ||
| 105 | size_t const theByteArraySize | ||
| 106 | ) { | ||
| 107 | − | assert(theBranch); | |
| 108 | − | assert(theByteArraySize >= theBranch->thisByteArraySize); | |
| 109 | |||
| 110 | 43 | theBranch = Om_Memory_Reallocate( | |
| 111 | theBranch, sizeof(*theBranch) + theByteArraySize | ||
| 112 | ); | ||
| 113 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 40 times.
|
43 | if(!theBranch) { |
| 114 | 3 | return NULL; | |
| 115 | } | ||
| 116 | 40 | theBranch->thisByteArraySize = theByteArraySize; | |
| 117 | 40 | return theBranch; | |
| 118 | } | ||
| 119 | |||
| 120 | 194 | Om_Tree_Branch * Om_Tree_Branch_Create( | |
| 121 | uint_fast8_t * Om_Restrict const theBranchBitCount, | ||
| 122 | size_t const theStringLength, | ||
| 123 | char const * Om_Restrict const theString | ||
| 124 | ) { | ||
| 125 | − | assert(theBranchBitCount); | |
| 126 | − | assert(theString); | |
| 127 | − | assert(theStringLength == strlen(theString)); | |
| 128 | |||
| 129 | // Include the null terminator as a proper byte, but with the last bit masked | ||
| 130 | // to account for the child index. | ||
| 131 | 194 | Om_Tree_Branch * Om_Restrict const theBranch = Om_Tree_Branch_Allocate( | |
| 132 | theString, theStringLength + 1U | ||
| 133 | ); | ||
| 134 |
2/2✓ Branch 0 taken 5 times.
✓ Branch 1 taken 189 times.
|
194 | if(!theBranch) { |
| 135 | 5 | return NULL; | |
| 136 | } | ||
| 137 | 189 | theBranch->thisByteArray[theStringLength] = '\1'; | |
| 138 | 189 | *theBranchBitCount = (CHAR_BIT - 1U); | |
| 139 | 189 | return theBranch; | |
| 140 | } | ||
| 141 | |||
| 142 | 523 | Om_Tree_Branch * Om_Tree_Branch_CreateCopy( | |
| 143 | Om_Tree_Branch const * Om_Restrict const theBranch | ||
| 144 | ) { | ||
| 145 | − | assert(theBranch); | |
| 146 | |||
| 147 | 523 | Om_Tree_Branch * const theCopy = Om_Tree_Branch_Allocate( | |
| 148 | 523 | theBranch->thisByteArray, theBranch->thisByteArraySize | |
| 149 | ); | ||
| 150 |
2/2✓ Branch 0 taken 7 times.
✓ Branch 1 taken 516 times.
|
523 | if(!theCopy) { |
| 151 | 7 | return NULL; | |
| 152 | } | ||
| 153 | // NOLINTNEXTLINE(clang-analyzer-security.insecureAPI.DeprecatedOrUnsafeBufferHandling) | ||
| 154 | 516 | memcpy( | |
| 155 | 516 | theCopy->thisChildArray, theBranch->thisChildArray, | |
| 156 | sizeof(theBranch->thisChildArray) | ||
| 157 | ); | ||
| 158 | 516 | return theCopy; | |
| 159 | } | ||
| 160 | |||
| 161 | 143 | Om_Tree_Branch * Om_Tree_Branch_Split( | |
| 162 | Om_Tree_Branch * theBranch, | ||
| 163 | uint_fast8_t * const theBranchBitCount, | ||
| 164 | size_t const theNewBranchByteCount, | ||
| 165 | uint_fast8_t const theNewBranchBitCount, | ||
| 166 | Om_Tree_Branch * * const theChildBranch, | ||
| 167 | uint_fast8_t * const theChildBranchBitCount | ||
| 168 | ) { | ||
| 169 | − | assert(theBranch); | |
| 170 | − | assert(theBranchBitCount && (*theBranchBitCount < CHAR_BIT)); | |
| 171 | − | assert( | |
| 172 | theNewBranchByteCount <= | ||
| 173 | Om_Tree_Branch_GetByteCount(theBranch, *theBranchBitCount) | ||
| 174 | ); | ||
| 175 | − | assert(theNewBranchBitCount < CHAR_BIT); | |
| 176 | // Assert that if the new byte count is the same, that the new bit count is | ||
| 177 | // less than the old one. | ||
| 178 | − | assert( | |
| 179 | ( | ||
| 180 | Om_Tree_Branch_GetByteCount(theBranch, *theBranchBitCount) > | ||
| 181 | theNewBranchByteCount | ||
| 182 | ) || !*theBranchBitCount || (theNewBranchBitCount < *theBranchBitCount) | ||
| 183 | ); | ||
| 184 | − | assert(theChildBranch); | |
| 185 | − | assert(theChildBranchBitCount); | |
| 186 | |||
| 187 | // Determine the new byte array size for the branch. If the critical bit is | ||
| 188 | // leftmost, do not duplicate the child branch byte in the branch. | ||
| 189 | 143 | size_t const theNewBranchByteArraySize = ( | |
| 190 | 143 | theNewBranchByteCount + !!theNewBranchBitCount | |
| 191 | ); | ||
| 192 | |||
| 193 | // Split the remainder off to a new child. | ||
| 194 |
4/4✓ Branch 0 taken 122 times.
✓ Branch 1 taken 21 times.
✓ Branch 2 taken 85 times.
✓ Branch 3 taken 37 times.
|
143 | if(!theNewBranchByteCount && (theNewBranchBitCount < (CHAR_BIT - 1U))) { |
| 195 | // Optimization for byte index 0 and critical bit not rightmost (i.e. the | ||
| 196 | // byte is also in the child): the branch becomes the child. | ||
| 197 | 85 | *theChildBranch = theBranch; | |
| 198 | 85 | *theChildBranchBitCount = *theBranchBitCount; | |
| 199 | 85 | theBranch = Om_Tree_Branch_Allocate( | |
| 200 | 85 | theBranch->thisByteArray, theNewBranchByteArraySize | |
| 201 | ); | ||
| 202 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 84 times.
|
85 | if(!theBranch) { |
| 203 | 1 | return NULL; | |
| 204 | } | ||
| 205 | } else { | ||
| 206 | // Determine the remainder to copy to the new child. If the critical bit is | ||
| 207 | // rightmost, do not duplicate the branch byte in the child branch. | ||
| 208 | 58 | char const * const theByteArrayRemainder = theBranch->thisByteArray + ( | |
| 209 | 58 | theNewBranchByteCount + (theNewBranchBitCount == (CHAR_BIT - 1U)) | |
| 210 | ); | ||
| 211 | 58 | size_t const theByteArrayRemainderSize = theBranch->thisByteArraySize - ( | |
| 212 | 58 | (size_t)(theByteArrayRemainder - theBranch->thisByteArray) | |
| 213 | ); | ||
| 214 | |||
| 215 | 58 | *theChildBranch = Om_Tree_Branch_Allocate( | |
| 216 | theByteArrayRemainder, theByteArrayRemainderSize | ||
| 217 | ); | ||
| 218 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 56 times.
|
58 | if(!*theChildBranch) { |
| 219 | 2 | return NULL; | |
| 220 | } | ||
| 221 | // NOLINTNEXTLINE(clang-analyzer-security.insecureAPI.DeprecatedOrUnsafeBufferHandling) | ||
| 222 | 56 | memcpy( | |
| 223 | 56 | (*theChildBranch)->thisChildArray, theBranch->thisChildArray, | |
| 224 | sizeof(theBranch->thisChildArray) | ||
| 225 | ); | ||
| 226 | |||
| 227 | // If the child branch is empty, then either the bit count count is 0, or | ||
| 228 | // the critical byte was skipped. | ||
| 229 | − | assert( | |
| 230 | theByteArrayRemainderSize || | ||
| 231 | !*theBranchBitCount || | ||
| 232 | (theNewBranchBitCount == (CHAR_BIT - 1U)) | ||
| 233 | ); | ||
| 234 | 56 | *theChildBranchBitCount = (uint_fast8_t)( | |
| 235 | 56 | !!theByteArrayRemainderSize * *theBranchBitCount | |
| 236 | ); | ||
| 237 | |||
| 238 | 56 | theBranch = Om_Tree_Branch_Shrink(theBranch, theNewBranchByteArraySize); | |
| 239 | − | assert(theBranch); | |
| 240 | } | ||
| 241 | |||
| 242 | // Mask the new partial byte. | ||
| 243 |
2/2✓ Branch 0 taken 131 times.
✓ Branch 1 taken 9 times.
|
140 | if(theNewBranchBitCount) { |
| 244 | − | assert(theNewBranchByteCount < theBranch->thisByteArraySize); | |
| 245 | 131 | theBranch->thisByteArray[theNewBranchByteCount] = (char)( | |
| 246 | 131 | (uint_fast8_t)theBranch->thisByteArray[theNewBranchByteCount] | | |
| 247 | 131 | Om_Bit_MaskRemainder(theNewBranchBitCount) | |
| 248 | ); | ||
| 249 | } | ||
| 250 | |||
| 251 | // Update the branch bit count and return the new branch. | ||
| 252 | 140 | *theBranchBitCount = theNewBranchBitCount; | |
| 253 | 140 | return theBranch; | |
| 254 | } | ||
| 255 | |||
| 256 | 119 | Om_Tree_Branch * Om_Tree_Branch_Merge( | |
| 257 | Om_Tree_Branch * theBranch, | ||
| 258 | uint_fast8_t * const theBranchBitCount, | ||
| 259 | uint_fast8_t const theChildOffset, | ||
| 260 | Om_Tree_Branch * const theChildBranch, | ||
| 261 | uint_fast8_t const theChildBranchBitCount | ||
| 262 | ) { | ||
| 263 | − | assert(theBranch); | |
| 264 | − | assert(theBranchBitCount && *theBranchBitCount < CHAR_BIT); | |
| 265 | − | assert(theChildBranch); | |
| 266 | − | assert(theChildBranchBitCount < CHAR_BIT); | |
| 267 | |||
| 268 | // Determine the branch byte array size that the child byte array size will be | ||
| 269 | // added to, excluding the critical byte if it is in both; this is the case if | ||
| 270 | // the bit count is not zero and is less than the maximum. | ||
| 271 | 238 | size_t const theBranchByteArraySize = theBranch->thisByteArraySize - ( | |
| 272 |
4/4✓ Branch 0 taken 111 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 85 times.
✓ Branch 3 taken 26 times.
|
119 | *theBranchBitCount && (*theBranchBitCount < (CHAR_BIT - 1U)) |
| 273 | ); | ||
| 274 | |||
| 275 | // Merge the child into the branch. | ||
| 276 |
2/2✓ Branch 0 taken 76 times.
✓ Branch 1 taken 43 times.
|
119 | if(!theBranchByteArraySize) { |
| 277 | // Optimization for empty branch: the branch can be replaced with the child. | ||
| 278 | 76 | Om_Tree_Branch_Destroy(theBranch); | |
| 279 | 76 | theBranch = theChildBranch; | |
| 280 | } else { | ||
| 281 | // Expand the branch. | ||
| 282 | 43 | size_t const theChildBranchByteArraySize = ( | |
| 283 | theChildBranch->thisByteArraySize | ||
| 284 | ); | ||
| 285 | 43 | theBranch = Om_Tree_Branch_Grow( | |
| 286 | theBranch, theBranchByteArraySize + theChildBranchByteArraySize | ||
| 287 | ); | ||
| 288 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 40 times.
|
43 | if(!theBranch) { |
| 289 | 3 | return NULL; | |
| 290 | } | ||
| 291 | |||
| 292 | // If the bit count is the maximum, the critical byte only exists in the | ||
| 293 | // parent, but with the rightmost bit masked; unmask it. Because the bit is | ||
| 294 | // 1 due to masking. it only needs to be changed if the child index is 0. | ||
| 295 |
2/2✓ Branch 0 taken 24 times.
✓ Branch 1 taken 16 times.
|
40 | if(*theBranchBitCount == (CHAR_BIT - 1U)) { |
| 296 | − | assert(theBranchByteArraySize); | |
| 297 | // The extra variables are to avoid "helpful" compile warnings. | ||
| 298 | 24 | char * const theByte = theBranch->thisByteArray + ( | |
| 299 | theBranchByteArraySize - 1U | ||
| 300 | ); | ||
| 301 | − | assert((uint_fast8_t)*theByte & 1U); | |
| 302 | 24 | char unsigned const theOtherChildOffset = !theChildOffset; | |
| 303 | 24 | *theByte = (char)( | |
| 304 | 24 | (uint_fast8_t)*theByte & (uint_fast8_t)(~theOtherChildOffset) | |
| 305 | ); | ||
| 306 | } | ||
| 307 | |||
| 308 | // Copy the child bytes and grandchildren, then destroy the child. | ||
| 309 | // NOLINTNEXTLINE(clang-analyzer-security.insecureAPI.DeprecatedOrUnsafeBufferHandling) | ||
| 310 | 40 | memcpy( | |
| 311 | 40 | theBranch->thisByteArray + theBranchByteArraySize, | |
| 312 | 40 | theChildBranch->thisByteArray, | |
| 313 | theChildBranchByteArraySize | ||
| 314 | ); | ||
| 315 | // NOLINTNEXTLINE(clang-analyzer-security.insecureAPI.DeprecatedOrUnsafeBufferHandling) | ||
| 316 | 40 | memcpy( | |
| 317 | 40 | theBranch->thisChildArray, theChildBranch->thisChildArray, | |
| 318 | sizeof(theChildBranch->thisChildArray) | ||
| 319 | ); | ||
| 320 | 40 | Om_Tree_Branch_Destroy(theChildBranch); | |
| 321 | } | ||
| 322 | |||
| 323 | // Update the branch bit count and return the new branch. | ||
| 324 | 116 | *theBranchBitCount = theChildBranchBitCount; | |
| 325 | 116 | return theBranch; | |
| 326 | } | ||
| 327 | |||
| 328 | 3900 | bool Om_Tree_Branch_HasLeafChild( | |
| 329 | Om_Tree_Branch const * Om_Restrict const theBranch, | ||
| 330 | uint_fast8_t const theBranchBitCount | ||
| 331 | ) { | ||
| 332 | − | assert(theBranch); | |
| 333 | − | assert(theBranchBitCount < CHAR_BIT); | |
| 334 | − | assert(!theBranchBitCount || theBranch->thisByteArraySize); | |
| 335 | |||
| 336 | return ( | ||
| 337 |
2/2✓ Branch 0 taken 2346 times.
✓ Branch 1 taken 1554 times.
|
6246 | (theBranchBitCount == (CHAR_BIT - 1U)) && |
| 338 |
2/2✓ Branch 0 taken 2068 times.
✓ Branch 1 taken 278 times.
|
2346 | (theBranch->thisByteArray[theBranch->thisByteArraySize - 1U] == '\1') |
| 339 | ); | ||
| 340 | } | ||
| 341 | |||
| 342 | 10292 | Om_Tree_Node * Om_Tree_Branch_GetChildArray( | |
| 343 | Om_Tree_Branch * Om_Restrict const theBranch | ||
| 344 | ) { | ||
| 345 | − | assert(theBranch); | |
| 346 | |||
| 347 | 10292 | return theBranch->thisChildArray; | |
| 348 | } | ||
| 349 | |||
| 350 | 3707 | char const * Om_Tree_Branch_GetByteArray( | |
| 351 | Om_Tree_Branch const * Om_Restrict const theBranch | ||
| 352 | ) { | ||
| 353 | − | assert(theBranch); | |
| 354 | |||
| 355 | 3707 | return theBranch->thisByteArray; | |
| 356 | } | ||
| 357 | |||
| 358 | 4343 | size_t Om_Tree_Branch_GetByteCount( | |
| 359 | Om_Tree_Branch const * Om_Restrict const theBranch, | ||
| 360 | uint_fast8_t const theBranchBitCount | ||
| 361 | ) { | ||
| 362 | − | assert(theBranch); | |
| 363 | − | assert(theBranchBitCount < CHAR_BIT); | |
| 364 | − | assert(!theBranchBitCount || theBranch->thisByteArraySize); | |
| 365 | |||
| 366 | 4343 | return (theBranch->thisByteArraySize - !!theBranchBitCount); | |
| 367 | } | ||
| 368 | |||
| 369 | 524 | bool Om_Tree_Branch_Match( | |
| 370 | Om_Tree_Branch const * Om_Restrict const theBranch, | ||
| 371 | uint_fast8_t const theBranchBitCount, | ||
| 372 | Om_Tree_Branch const * Om_Restrict const theOtherBranch, | ||
| 373 | uint_fast8_t const theOtherBranchBitCount | ||
| 374 | ) { | ||
| 375 | return ( | ||
| 376 | 522 | (theBranchBitCount == theOtherBranchBitCount) && | |
| 377 |
4/4✓ Branch 0 taken 522 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 516 times.
✓ Branch 3 taken 6 times.
|
1040 | (theBranch->thisByteArraySize == theOtherBranch->thisByteArraySize) && |
| 378 | ( | ||
| 379 | 516 | 0 == strncmp( | |
| 380 | 516 | theBranch->thisByteArray, theOtherBranch->thisByteArray, | |
| 381 |
2/2✓ Branch 0 taken 514 times.
✓ Branch 1 taken 2 times.
|
516 | theBranch->thisByteArraySize |
| 382 | ) | ||
| 383 | ) | ||
| 384 | ); | ||
| 385 | } | ||
| 386 | |||
| 387 | 845 | void Om_Tree_Branch_Destroy( | |
| 388 | Om_Tree_Branch * Om_Restrict const theBranch | ||
| 389 | ) { | ||
| 390 | 845 | Om_Memory_Deallocate(theBranch); | |
| 391 | 845 | } | |
| 392 |