Code Coverage Report

Directory: targets/
File: om-tree-library/source/om/tree/lookup.c
Date: 2024-10-29 22:25:26
Exec Total Coverage
Lines: 52 52 100.0%
Functions: 4 4 100.0%
Branches: 24 24 100.0%
Line Branch Exec Source
1 /*!
2 @file
3 @brief The Om_Tree_Lookup function definitions.
4 */
5
6 #include <om/tree/lookup.h>
7
8 #include <om/bit.h>
9 #include <om/tree/branch_node.h>
10
11 #include <assert.h>
12 #include <limits.h>
13 #include <string.h>
14
15 241 void Om_Tree_Lookup_Initialize(
16 Om_Tree_Lookup * const theLookup,
17 Om_Tree const * const theTree
18 ) {
19 − assert(theLookup);
20 − assert(theTree);
21
22 241 theLookup->thisLeafNode = NULL;
23 241 theLookup->thisBranchNode = theTree->thisRootNode;
24 241 theLookup->thisBranchByteIndex = 0U;
25 241 }
26
27 489 bool Om_Tree_Lookup_CanAdvance(
28 Om_Tree_Lookup const * const theLookup
29 ) {
30 − assert(theLookup);
31
32 return (
33
2/2
✓ Branch 0 taken 488 times.
✓ Branch 1 taken 1 times.
 977 (theLookup->thisBranchNode != (Om_Tree_BranchNode)NULL) &&
34
2/2
✓ Branch 0 taken 487 times.
✓ Branch 1 taken 1 times.
 488 (theLookup->thisLeafNode == NULL)
35 );
36 }
37
38 // NOLINTNEXTLINE(readability-function-cognitive-complexity)
39 245 int Om_Tree_Lookup_Advance(
40 Om_Tree_Lookup * Om_Restrict const theLookup,
41 size_t const theByteCount,
42 char const * Om_Restrict const theByteArray
43 ) {
44 − assert(theLookup);
45 − assert(Om_Tree_Lookup_CanAdvance(theLookup));
46 − assert(theByteArray);
47 − assert(theByteCount);
48
49 1277 for(size_t theByteIndex = 0U;; ) {
50 − assert(theByteIndex < theByteCount);
51
52 1277 Om_Tree_Branch * const theBranch = Om_Tree_BranchNode_GetBranch(
53 theLookup->thisBranchNode
54 );
55 − assert(theBranch);
56 1277 uint_fast8_t const theBranchBitCount = Om_Tree_BranchNode_GetBranchBitCount(
57 theLookup->thisBranchNode
58 );
59
60 // Match branch bytes against the byte array and advance the indices.
61 // Afterward, the byte index will refer to the critical byte and the lookup
62 // index will be the branch length.
63 {
64 1277 char const * const theBranchByteArray = Om_Tree_Branch_GetByteArray(
65 theBranch
66 );
67 − assert(theBranchByteArray);
68
69 1277 size_t const theBranchByteCount = Om_Tree_Branch_GetByteCount(
70 theBranch, theBranchBitCount
71 );
72 − assert(theBranchByteCount >= theLookup->thisBranchByteIndex);
73
74 1277 size_t theRemainingByteCount = theByteCount - theByteIndex;
75 {
76 1277 size_t const theRemainingBranchByteCount = (
77 1277 theBranchByteCount - theLookup->thisBranchByteIndex
78 );
79
2/2
✓ Branch 0 taken 1244 times.
✓ Branch 1 taken 33 times.
 1277 if(theRemainingByteCount > theRemainingBranchByteCount) {
80 1244 theRemainingByteCount = theRemainingBranchByteCount;
81 }
82 }
83
84 1277 if(
85 1277 0 != strncmp(
86
2/2
✓ Branch 0 taken 65 times.
✓ Branch 1 taken 1212 times.
 1277 theBranchByteArray + theLookup->thisBranchByteIndex,
87 theByteArray + theByteIndex,
88 theRemainingByteCount
89 )
90 ) {
91 65 break;
92 }
93
94 // Advance the indexes past the bytes checked and return if done.
95 1212 theLookup->thisBranchByteIndex += theRemainingByteCount;
96 1212 theByteIndex += theRemainingByteCount;
97 − assert(theByteIndex <= theByteCount);
98
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1210 times.
 1212 if(theByteIndex == theByteCount) {
99 2 return 1;
100 }
101
102 // Compare the partial byte. Don't advance the byte index since the
103 // remaining bits still need to be dealt with.
104
2/2
✓ Branch 0 taken 983 times.
✓ Branch 1 taken 227 times.
 1210 if(theBranchBitCount) {
105 − assert(theLookup->thisBranchByteIndex == theBranchByteCount);
106 983 if(
107 983 theBranchByteArray[theLookup->thisBranchByteIndex] != (char)(
108 983 (uint_fast8_t)theByteArray[theByteIndex] |
109
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 947 times.
 983 Om_Bit_MaskRemainder(theBranchBitCount)
110 )
111 ) {
112 36 break;
113 }
114 // Advance the lookup byte index past the byte checked.
115 947 ++theLookup->thisBranchByteIndex;
116 }
117 }
118
119 // Advance to the child.
120 {
121 1174 char const theByte = theByteArray[theByteIndex];
122
123 // If the critical bit is rightmost, either it is a leaf, or the critical
124 // branch byte is not repeated in the child branch byte array.
125
2/2
✓ Branch 0 taken 168 times.
✓ Branch 1 taken 1006 times.
 1174 if(theBranchBitCount == (CHAR_BIT - 1U)) {
126
2/2
✓ Branch 0 taken 140 times.
✓ Branch 1 taken 28 times.
 168 if(!theByte) {
127 // It's a leaf.
128 140 theLookup->thisLeafNode = Om_Tree_Branch_GetChildArray(theBranch);
129 140 return -1;
130 }
131 // The byte is not repeated in the child; advance to the next byte.
132 28 ++theByteIndex;
133 }
134
135 // Advance to the child.
136 2068 theLookup->thisBranchNode = Om_Tree_Branch_GetChildArray(theBranch)[
137
2/2
✓ Branch 0 taken 505 times.
✓ Branch 1 taken 529 times.
 1034 Om_Bit_Get(theByte, theBranchBitCount)
138 ];
139 1034 theLookup->thisBranchByteIndex = 0U;
140
141 // If the child is null, return 0.
142
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1033 times.
 1034 if(theLookup->thisBranchNode == (Om_Tree_BranchNode)NULL) {
143 1 return 0;
144 }
145 }
146
147 // If the byte array is done, return success.
148 − assert(theByteIndex <= theByteCount);
149
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1032 times.
 1033 if(theByteIndex == theByteCount) {
150 1 return 1;
151 }
152 }
153
154 − assert(!theLookup->thisLeafNode);
155 101 theLookup->thisBranchNode = (Om_Tree_BranchNode)NULL;
156 101 theLookup->thisBranchByteIndex = 0U;
157 101 return 0;
158 }
159
160 239 Om_Tree_LeafNode * Om_Tree_Lookup_GetLeafNode(
161 Om_Tree_Lookup const * const theLookup
162 ) {
163 − assert(theLookup);
164
165 239 return theLookup->thisLeafNode;
166 }
167