| 1 | // Copyright (C) 2000 - 2002 Hewlett-Packard Company |
| 2 | // |
| 3 | // This program is free software; you can redistribute it and/or modify it |
| 4 | // under the term of the GNU Lesser General Public License as published by the |
| 5 | // Free Software Foundation; either version 2 of the License, or (at your |
| 6 | // option) any later version. |
| 7 | // |
| 8 | // This program is distributed in the hope that it will be useful, but WITHOUT |
| 9 | // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 10 | // FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License |
| 11 | // for more details. |
| 12 | // |
| 13 | // You should have received a copy of the GNU Lesser General Public License |
| 14 | // along with this program; if not, write to the Free Software Foundation, |
| 15 | // Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| 16 | // _________________ |
| 17 | |
| 18 | // @(#) $Revision: 4.78 $ $Source: /judy/src/JudyCommon/JudyCount.c $ |
| 19 | // |
| 20 | // Judy*Count() function for Judy1 and JudyL. |
| 21 | // Compile with one of -DJUDY1 or -DJUDYL. |
| 22 | // |
| 23 | // Compile with -DNOSMARTJBB, -DNOSMARTJBU, and/or -DNOSMARTJLB to build a |
| 24 | // version with cache line optimizations deleted, for testing. |
| 25 | // |
| 26 | // Compile with -DSMARTMETRICS to obtain global variables containing smart |
| 27 | // cache line metrics. Note: Dont turn this on simultaneously for this file |
| 28 | // and JudyByCount.c because they export the same globals. |
| 29 | // |
| 30 | // Judy*Count() returns the "count of Indexes" (inclusive) between the two |
| 31 | // specified limits (Indexes). This code is remarkably fast. It traverses the |
| 32 | // "Judy array" data structure. |
| 33 | // |
| 34 | // This count code is the GENERIC untuned version (minimum code size). It |
| 35 | // might be possible to tuned to a specific architecture to be faster. |
| 36 | // However, in real applications, with a modern machine, it is expected that |
| 37 | // the instruction times will be swamped by cache line fills. |
| 38 | // **************************************************************************** |
| 39 | |
| 40 | #if (! (defined(JUDY1) || defined(JUDYL))) |
| 41 | #error: One of -DJUDY1 or -DJUDYL must be specified. |
| 42 | #endif |
| 43 | |
| 44 | #ifdef JUDY1 |
| 45 | #include "Judy1.h" |
| 46 | #else |
| 47 | #include "JudyL.h" |
| 48 | #endif |
| 49 | |
| 50 | #include "JudyPrivate1L.h" |
| 51 | |
| 52 | |
| 53 | // define a phoney that is for sure |
| 54 | |
| 55 | #define cJU_LEAFW cJU_JPIMMED_CAP |
| 56 | |
| 57 | // Avoid duplicate symbols since this file is multi-compiled: |
| 58 | |
| 59 | #ifdef SMARTMETRICS |
| 60 | #ifdef JUDY1 |
| 61 | Word_t jbb_upward = 0; // counts of directions taken: |
| 62 | Word_t jbb_downward = 0; |
| 63 | Word_t jbu_upward = 0; |
| 64 | Word_t jbu_downward = 0; |
| 65 | Word_t jlb_upward = 0; |
| 66 | Word_t jlb_downward = 0; |
| 67 | #else |
| 68 | extern Word_t jbb_upward; |
| 69 | extern Word_t jbb_downward; |
| 70 | extern Word_t jbu_upward; |
| 71 | extern Word_t jbu_downward; |
| 72 | extern Word_t jlb_upward; |
| 73 | extern Word_t jlb_downward; |
| 74 | #endif |
| 75 | #endif |
| 76 | |
| 77 | |
| 78 | // FORWARD DECLARATIONS (prototypes): |
| 79 | |
| 80 | static Word_t j__udy1LCountSM(const Pjp_t Pjp, const Word_t Index, |
| 81 | const Pjpm_t Pjpm); |
| 82 | |
| 83 | // Each of Judy1 and JudyL get their own private (static) version of this |
| 84 | // function: |
| 85 | |
| 86 | static int j__udyCountLeafB1(const Pjll_t Pjll, const Word_t Pop1, |
| 87 | const Word_t Index); |
| 88 | |
| 89 | // These functions are not static because they are exported to Judy*ByCount(): |
| 90 | // |
| 91 | // TBD: Should be made static for performance reasons? And thus duplicated? |
| 92 | // |
| 93 | // Note: There really are two different functions, but for convenience they |
| 94 | // are referred to here with a generic name. |
| 95 | |
| 96 | #ifdef JUDY1 |
| 97 | #define j__udyJPPop1 j__udy1JPPop1 |
| 98 | #else |
| 99 | #define j__udyJPPop1 j__udyLJPPop1 |
| 100 | #endif |
| 101 | |
| 102 | Word_t j__udyJPPop1(const Pjp_t Pjp); |
| 103 | |
| 104 | |
| 105 | // LOCAL ERROR HANDLING: |
| 106 | // |
| 107 | // The Judy*Count() functions are unusual because they return 0 instead of JERR |
| 108 | // for an error. In this source file, define C_JERR for clarity. |
| 109 | |
| 110 | #define C_JERR 0 |
| 111 | |
| 112 | |
| 113 | // **************************************************************************** |
| 114 | // J U D Y 1 C O U N T |
| 115 | // J U D Y L C O U N T |
| 116 | // |
| 117 | // See the manual entry for details. |
| 118 | // |
| 119 | // This code is written recursively, at least at first, because thats much |
| 120 | // simpler; hope its fast enough. |
| 121 | |
| 122 | #ifdef JUDY1 |
| 123 | FUNCTION Word_t Judy1Count |
| 124 | #else |
| 125 | FUNCTION Word_t JudyLCount |
| 126 | #endif |
| 127 | ( |
| 128 | Pcvoid_t PArray, // JRP to first branch/leaf in SM. |
| 129 | Word_t Index1, // starting Index. |
| 130 | Word_t Index2, // ending Index. |
| 131 | PJError_t PJError // optional, for returning error info. |
| 132 | ) |
| 133 | { |
| 134 | jpm_t fakejpm; // local temporary for small arrays. |
| 135 | Pjpm_t Pjpm; // top JPM or local temporary for error info. |
| 136 | jp_t fakejp; // constructed for calling j__udy1LCountSM(). |
| 137 | Pjp_t Pjp; // JP to pass to j__udy1LCountSM(). |
| 138 | Word_t pop1; // total for the array. |
| 139 | Word_t pop1above1; // indexes at or above Index1, inclusive. |
| 140 | Word_t pop1above2; // indexes at or above Index2, exclusive. |
| 141 | int retcode; // from Judy*First() calls. |
| 142 | JUDYLCODE(PPvoid_t PPvalue); // from JudyLFirst() calls. |
| 143 | |
| 144 | |
| 145 | // CHECK FOR SHORTCUTS: |
| 146 | // |
| 147 | // As documented, return C_JERR if the Judy array is empty or Index1 > Index2. |
| 148 | |
| 149 | if ((PArray == (Pvoid_t) NULL) || (Index1 > Index2)) |
| 150 | { |
| 151 | JU_SET_ERRNO(PJError, JU_ERRNO_NONE); |
| 152 | return(C_JERR); |
| 153 | } |
| 154 | |
| 155 | // If Index1 == Index2, simply check if the specified Index is set; pass |
| 156 | // through the return value from Judy1Test() or JudyLGet() with appropriate |
| 157 | // translations. |
| 158 | |
| 159 | if (Index1 == Index2) |
| 160 | { |
| 161 | #ifdef JUDY1 |
| 162 | retcode = Judy1Test(PArray, Index1, PJError); |
| 163 | |
| 164 | if (retcode == JERRI) return(C_JERR); // pass through error. |
| 165 | |
| 166 | if (retcode == 0) |
| 167 | { |
| 168 | JU_SET_ERRNO(PJError, JU_ERRNO_NONE); |
| 169 | return(C_JERR); |
| 170 | } |
| 171 | #else |
| 172 | PPvalue = JudyLGet(PArray, Index1, PJError); |
| 173 | |
| 174 | if (PPvalue == PPJERR) return(C_JERR); // pass through error. |
| 175 | |
| 176 | if (PPvalue == (PPvoid_t) NULL) // Index is not set. |
| 177 | { |
| 178 | JU_SET_ERRNO(PJError, JU_ERRNO_NONE); |
| 179 | return(C_JERR); |
| 180 | } |
| 181 | #endif |
| 182 | return(1); // single index is set. |
| 183 | } |
| 184 | |
| 185 | |
| 186 | // CHECK JRP TYPE: |
| 187 | // |
| 188 | // Use an if/then for speed rather than a switch, and put the most common cases |
| 189 | // first. |
| 190 | // |
| 191 | // Note: Since even cJU_LEAFW types require counting between two Indexes, |
| 192 | // prepare them here for common code below that calls j__udy1LCountSM(), rather |
| 193 | // than handling them even more specially here. |
| 194 | |
| 195 | if (JU_LEAFW_POP0(PArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW |
| 196 | { |
| 197 | Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf. |
| 198 | Pjpm = & fakejpm; |
| 199 | Pjp = & fakejp; |
| 200 | Pjp->jp_Addr = (Word_t) Pjlw; |
| 201 | Pjp->jp_Type = cJU_LEAFW; |
| 202 | Pjpm->jpm_Pop0 = Pjlw[0]; // from first word of leaf. |
| 203 | pop1 = Pjpm->jpm_Pop0 + 1; |
| 204 | } |
| 205 | else |
| 206 | { |
| 207 | Pjpm = P_JPM(PArray); |
| 208 | Pjp = &(Pjpm->jpm_JP); |
| 209 | pop1 = (Pjpm->jpm_Pop0) + 1; // note: can roll over to 0. |
| 210 | |
| 211 | #if (defined(JUDY1) && (! defined(JU_64BIT))) |
| 212 | if (pop1 == 0) // rare special case of full array: |
| 213 | { |
| 214 | Word_t count = Index2 - Index1 + 1; // can roll over again. |
| 215 | |
| 216 | if (count == 0) |
| 217 | { |
| 218 | JU_SET_ERRNO(PJError, JU_ERRNO_FULL); |
| 219 | return(C_JERR); |
| 220 | } |
| 221 | return(count); |
| 222 | } |
| 223 | #else |
| 224 | assert(pop1); // JudyL or 64-bit cannot create a full array! |
| 225 | #endif |
| 226 | } |
| 227 | |
| 228 | |
| 229 | // COUNT POP1 ABOVE INDEX1, INCLUSIVE: |
| 230 | |
| 231 | assert(pop1); // just to be safe. |
| 232 | |
| 233 | if (Index1 == 0) // shortcut, pop1above1 is entire population: |
| 234 | { |
| 235 | pop1above1 = pop1; |
| 236 | } |
| 237 | else // find first valid Index above Index1, if any: |
| 238 | { |
| 239 | #ifdef JUDY1 |
| 240 | if ((retcode = Judy1First(PArray, & Index1, PJError)) == JERRI) |
| 241 | return(C_JERR); // pass through error. |
| 242 | #else |
| 243 | if ((PPvalue = JudyLFirst(PArray, & Index1, PJError)) == PPJERR) |
| 244 | return(C_JERR); // pass through error. |
| 245 | |
| 246 | retcode = (PPvalue != (PPvoid_t) NULL); // found a next Index. |
| 247 | #endif |
| 248 | |
| 249 | // If theres no Index at or above Index1, just return C_JERR (early exit): |
| 250 | |
| 251 | if (retcode == 0) |
| 252 | { |
| 253 | JU_SET_ERRNO(PJError, JU_ERRNO_NONE); |
| 254 | return(C_JERR); |
| 255 | } |
| 256 | |
| 257 | // If a first/next Index was found, call the counting motor starting with that |
| 258 | // known valid Index, meaning the return should be positive, not C_JERR except |
| 259 | // in case of a real error: |
| 260 | |
| 261 | if ((pop1above1 = j__udy1LCountSM(Pjp, Index1, Pjpm)) == C_JERR) |
| 262 | { |
| 263 | JU_COPY_ERRNO(PJError, Pjpm); // pass through error. |
| 264 | return(C_JERR); |
| 265 | } |
| 266 | } |
| 267 | |
| 268 | |
| 269 | // COUNT POP1 ABOVE INDEX2, EXCLUSIVE, AND RETURN THE DIFFERENCE: |
| 270 | // |
| 271 | // In principle, calculate the ordinal of each Index and take the difference, |
| 272 | // with caution about off-by-one errors due to the specified Indexes being set |
| 273 | // or unset. In practice: |
| 274 | // |
| 275 | // - The ordinals computed here are inverse ordinals, that is, the populations |
| 276 | // ABOVE the specified Indexes (Index1 inclusive, Index2 exclusive), so |
| 277 | // subtract pop1above2 from pop1above1, rather than vice-versa. |
| 278 | // |
| 279 | // - Index1s result already includes a count for Index1 and/or Index2 if |
| 280 | // either is set, so calculate pop1above2 exclusive of Index2. |
| 281 | // |
| 282 | // TBD: If Index1 and Index2 fall in the same expanse in the top-state |
| 283 | // branch(es), would it be faster to walk the SM only once, to their divergence |
| 284 | // point, before calling j__udy1LCountSM() or equivalent? Possibly a non-issue |
| 285 | // if a top-state pop1 becomes stored with each Judy1 array. Also, consider |
| 286 | // whether the first call of j__udy1LCountSM() fills the cache, for common tree |
| 287 | // branches, for the second call. |
| 288 | // |
| 289 | // As for pop1above1, look for shortcuts for special cases when pop1above2 is |
| 290 | // zero. Otherwise call the counting "motor". |
| 291 | |
| 292 | assert(pop1above1); // just to be safe. |
| 293 | |
| 294 | if (Index2++ == cJU_ALLONES) return(pop1above1); // Index2 at limit. |
| 295 | |
| 296 | #ifdef JUDY1 |
| 297 | if ((retcode = Judy1First(PArray, & Index2, PJError)) == JERRI) |
| 298 | return(C_JERR); |
| 299 | #else |
| 300 | if ((PPvalue = JudyLFirst(PArray, & Index2, PJError)) == PPJERR) |
| 301 | return(C_JERR); |
| 302 | |
| 303 | retcode = (PPvalue != (PPvoid_t) NULL); // found a next Index. |
| 304 | #endif |
| 305 | if (retcode == 0) return(pop1above1); // no Index above Index2. |
| 306 | |
| 307 | // Just as for Index1, j__udy1LCountSM() cannot return 0 (locally == C_JERR) |
| 308 | // except in case of a real error: |
| 309 | |
| 310 | if ((pop1above2 = j__udy1LCountSM(Pjp, Index2, Pjpm)) == C_JERR) |
| 311 | { |
| 312 | JU_COPY_ERRNO(PJError, Pjpm); // pass through error. |
| 313 | return(C_JERR); |
| 314 | } |
| 315 | |
| 316 | if (pop1above1 == pop1above2) |
| 317 | { |
| 318 | JU_SET_ERRNO(PJError, JU_ERRNO_NONE); |
| 319 | return(C_JERR); |
| 320 | } |
| 321 | |
| 322 | return(pop1above1 - pop1above2); |
| 323 | |
| 324 | } // Judy1Count() / JudyLCount() |
| 325 | |
| 326 | |
| 327 | // **************************************************************************** |
| 328 | // __ J U D Y 1 L C O U N T S M |
| 329 | // |
| 330 | // Given a pointer to a JP (with invalid jp_DcdPopO at cJU_ROOTSTATE), a known |
| 331 | // valid Index, and a Pjpm for returning error info, recursively visit a Judy |
| 332 | // array state machine (SM) and return the count of Indexes, including Index, |
| 333 | // through the end of the Judy array at this state or below. In case of error |
| 334 | // or a count of 0 (should never happen), return C_JERR with appropriate |
| 335 | // JU_ERRNO in the Pjpm. |
| 336 | // |
| 337 | // Note: This function is not told the current state because its encoded in |
| 338 | // the JP Type. |
| 339 | // |
| 340 | // Method: To minimize cache line fills, while studying each branch, if Index |
| 341 | // resides above the midpoint of the branch (which often consists of multiple |
| 342 | // cache lines), ADD the populations at or above Index; otherwise, SUBTRACT |
| 343 | // from the population of the WHOLE branch (available from the JP) the |
| 344 | // populations at or above Index. This is especially tricky for bitmap |
| 345 | // branches. |
| 346 | // |
| 347 | // Note: Unlike, say, the Ins and Del walk routines, this function returns the |
| 348 | // same type of returns as Judy*Count(), so it can use *_SET_ERRNO*() macros |
| 349 | // the same way. |
| 350 | |
| 351 | FUNCTION static Word_t j__udy1LCountSM( |
| 352 | const Pjp_t Pjp, // top of Judy (sub)SM. |
| 353 | const Word_t Index, // count at or above this Index. |
| 354 | const Pjpm_t Pjpm) // for returning error info. |
| 355 | { |
| 356 | Pjbl_t Pjbl; // Pjp->jp_Addr masked and cast to types: |
| 357 | Pjbb_t Pjbb; |
| 358 | Pjbu_t Pjbu; |
| 359 | Pjll_t Pjll; // a Judy lower-level linear leaf. |
| 360 | |
| 361 | Word_t digit; // next digit to decode from Index. |
| 362 | long jpnum; // JP number in a branch (base 0). |
| 363 | int offset; // index ordinal within a leaf, base 0. |
| 364 | Word_t pop1; // total population of an expanse. |
| 365 | Word_t pop1above; // to return. |
| 366 | |
| 367 | // Common code to check Decode bits in a JP against the equivalent portion of |
| 368 | // Index; XOR together, then mask bits of interest; must be all 0: |
| 369 | // |
| 370 | // Note: Why does this code only assert() compliance rather than actively |
| 371 | // checking for outliers? Its because Index is supposed to be valid, hence |
| 372 | // always match any Dcd bits traversed. |
| 373 | // |
| 374 | // Note: This assertion turns out to be always true for cState = 3 on 32-bit |
| 375 | // and 7 on 64-bit, but its harmless, probably removed by the compiler. |
| 376 | |
| 377 | #define CHECKDCD(Pjp,cState) \ |
| 378 | assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, cState)) |
| 379 | |
| 380 | // Common code to prepare to handle a root-level or lower-level branch: |
| 381 | // Extract a state-dependent digit from Index in a "constant" way, obtain the |
| 382 | // total population for the branch in a state-dependent way, and then branch to |
| 383 | // common code for multiple cases: |
| 384 | // |
| 385 | // For root-level branches, the state is always cJU_ROOTSTATE, and the |
| 386 | // population is received in Pjpm->jpm_Pop0. |
| 387 | // |
| 388 | // Note: The total population is only needed in cases where the common code |
| 389 | // "counts up" instead of down to minimize cache line fills. However, its |
| 390 | // available cheaply, and its better to do it with a constant shift (constant |
| 391 | // state value) instead of a variable shift later "when needed". |
| 392 | |
| 393 | #define PREPB_ROOT(Pjp,Next) \ |
| 394 | digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE); \ |
| 395 | pop1 = (Pjpm->jpm_Pop0) + 1; \ |
| 396 | goto Next |
| 397 | |
| 398 | #define PREPB(Pjp,cState,Next) \ |
| 399 | digit = JU_DIGITATSTATE(Index, cState); \ |
| 400 | pop1 = JU_JPBRANCH_POP0(Pjp, (cState)) + 1; \ |
| 401 | goto Next |
| 402 | |
| 403 | |
| 404 | // SWITCH ON JP TYPE: |
| 405 | // |
| 406 | // WARNING: For run-time efficiency the following cases replicate code with |
| 407 | // varying constants, rather than using common code with variable values! |
| 408 | |
| 409 | switch (JU_JPTYPE(Pjp)) |
| 410 | { |
| 411 | |
| 412 | |
| 413 | // ---------------------------------------------------------------------------- |
| 414 | // ROOT-STATE LEAF that starts with a Pop0 word; just count within the leaf: |
| 415 | |
| 416 | case cJU_LEAFW: |
| 417 | { |
| 418 | Pjlw_t Pjlw = P_JLW(Pjp->jp_Addr); // first word of leaf. |
| 419 | |
| 420 | assert((Pjpm->jpm_Pop0) + 1 == Pjlw[0] + 1); // sent correctly. |
| 421 | offset = j__udySearchLeafW(Pjlw + 1, Pjpm->jpm_Pop0 + 1, Index); |
| 422 | assert(offset >= 0); // Index must exist. |
| 423 | assert(offset < (Pjpm->jpm_Pop0) + 1); // Index be in range. |
| 424 | return((Pjpm->jpm_Pop0) + 1 - offset); // INCLUSIVE of Index. |
| 425 | } |
| 426 | |
| 427 | // ---------------------------------------------------------------------------- |
| 428 | // LINEAR BRANCH; count populations in JPs in the JBL ABOVE the next digit in |
| 429 | // Index, and recurse for the next digit in Index: |
| 430 | // |
| 431 | // Note: There are no null JPs in a JBL; watch out for pop1 == 0. |
| 432 | // |
| 433 | // Note: A JBL should always fit in one cache line => no need to count up |
| 434 | // versus down to save cache line fills. (PREPB() sets pop1 for no reason.) |
| 435 | |
| 436 | case cJU_JPBRANCH_L2: CHECKDCD(Pjp, 2); PREPB(Pjp, 2, BranchL); |
| 437 | case cJU_JPBRANCH_L3: CHECKDCD(Pjp, 3); PREPB(Pjp, 3, BranchL); |
| 438 | |
| 439 | #ifdef JU_64BIT |
| 440 | case cJU_JPBRANCH_L4: CHECKDCD(Pjp, 4); PREPB(Pjp, 4, BranchL); |
| 441 | case cJU_JPBRANCH_L5: CHECKDCD(Pjp, 5); PREPB(Pjp, 5, BranchL); |
| 442 | case cJU_JPBRANCH_L6: CHECKDCD(Pjp, 6); PREPB(Pjp, 6, BranchL); |
| 443 | case cJU_JPBRANCH_L7: CHECKDCD(Pjp, 7); PREPB(Pjp, 7, BranchL); |
| 444 | #endif |
| 445 | case cJU_JPBRANCH_L: PREPB_ROOT(Pjp, BranchL); |
| 446 | |
| 447 | // Common code (state-independent) for all cases of linear branches: |
| 448 | |
| 449 | BranchL: |
| 450 | |
| 451 | Pjbl = P_JBL(Pjp->jp_Addr); |
| 452 | jpnum = Pjbl->jbl_NumJPs; // above last JP. |
| 453 | pop1above = 0; |
| 454 | |
| 455 | while (digit < (Pjbl->jbl_Expanse[--jpnum])) // still ABOVE digit. |
| 456 | { |
| 457 | if ((pop1 = j__udyJPPop1((Pjbl->jbl_jp) + jpnum)) == cJU_ALLONES) |
| 458 | { |
| 459 | JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); |
| 460 | return(C_JERR); |
| 461 | } |
| 462 | |
| 463 | pop1above += pop1; |
| 464 | assert(jpnum > 0); // should find digit. |
| 465 | } |
| 466 | |
| 467 | assert(digit == (Pjbl->jbl_Expanse[jpnum])); // should find digit. |
| 468 | |
| 469 | pop1 = j__udy1LCountSM((Pjbl->jbl_jp) + jpnum, Index, Pjpm); |
| 470 | if (pop1 == C_JERR) return(C_JERR); // pass error up. |
| 471 | |
| 472 | assert(pop1above + pop1); |
| 473 | return(pop1above + pop1); |
| 474 | |
| 475 | |
| 476 | // ---------------------------------------------------------------------------- |
| 477 | // BITMAP BRANCH; count populations in JPs in the JBB ABOVE the next digit in |
| 478 | // Index, and recurse for the next digit in Index: |
| 479 | // |
| 480 | // Note: There are no null JPs in a JBB; watch out for pop1 == 0. |
| 481 | |
| 482 | case cJU_JPBRANCH_B2: CHECKDCD(Pjp, 2); PREPB(Pjp, 2, BranchB); |
| 483 | case cJU_JPBRANCH_B3: CHECKDCD(Pjp, 3); PREPB(Pjp, 3, BranchB); |
| 484 | #ifdef JU_64BIT |
| 485 | case cJU_JPBRANCH_B4: CHECKDCD(Pjp, 4); PREPB(Pjp, 4, BranchB); |
| 486 | case cJU_JPBRANCH_B5: CHECKDCD(Pjp, 5); PREPB(Pjp, 5, BranchB); |
| 487 | case cJU_JPBRANCH_B6: CHECKDCD(Pjp, 6); PREPB(Pjp, 6, BranchB); |
| 488 | case cJU_JPBRANCH_B7: CHECKDCD(Pjp, 7); PREPB(Pjp, 7, BranchB); |
| 489 | #endif |
| 490 | case cJU_JPBRANCH_B: PREPB_ROOT(Pjp, BranchB); |
| 491 | |
| 492 | // Common code (state-independent) for all cases of bitmap branches: |
| 493 | |
| 494 | BranchB: |
| 495 | { |
| 496 | long subexp; // for stepping through layer 1 (subexpanses). |
| 497 | long findsub; // subexpanse containing Index (digit). |
| 498 | Word_t findbit; // bit representing Index (digit). |
| 499 | Word_t lowermask; // bits for indexes at or below Index. |
| 500 | Word_t jpcount; // JPs in a subexpanse. |
| 501 | Word_t clbelow; // cache lines below digits cache line. |
| 502 | Word_t clabove; // cache lines above digits cache line. |
| 503 | |
| 504 | Pjbb = P_JBB(Pjp->jp_Addr); |
| 505 | findsub = digit / cJU_BITSPERSUBEXPB; |
| 506 | findbit = digit % cJU_BITSPERSUBEXPB; |
| 507 | lowermask = JU_MASKLOWERINC(JU_BITPOSMASKB(findbit)); |
| 508 | clbelow = clabove = 0; // initial/default => always downward. |
| 509 | |
| 510 | assert(JU_BITMAPTESTB(Pjbb, digit)); // digit must have a JP. |
| 511 | assert(findsub < cJU_NUMSUBEXPB); // falls in expected range. |
| 512 | |
| 513 | // Shorthand for one subexpanse in a bitmap and for one JP in a bitmap branch: |
| 514 | // |
| 515 | // Note: BMPJP0 exists separately to support assertions. |
| 516 | |
| 517 | #define BMPJP0(Subexp) (P_JP(JU_JBB_PJP(Pjbb, Subexp))) |
| 518 | #define BMPJP(Subexp,JPnum) (BMPJP0(Subexp) + (JPnum)) |
| 519 | |
| 520 | #ifndef NOSMARTJBB // enable to turn off smart code for comparison purposes. |
| 521 | |
| 522 | // FIGURE OUT WHICH DIRECTION CAUSES FEWER CACHE LINE FILLS; adding the pop1s |
| 523 | // in JPs above Indexs JP, or subtracting the pop1s in JPs below Indexs JP. |
| 524 | // |
| 525 | // This is tricky because, while each set bit in the bitmap represents a JP, |
| 526 | // the JPs are scattered over cJU_NUMSUBEXPB subexpanses, each of which can |
| 527 | // contain JPs packed into multiple cache lines, and this code must visit every |
| 528 | // JP either BELOW or ABOVE the JP for Index. |
| 529 | // |
| 530 | // Number of cache lines required to hold a linear list of the given number of |
| 531 | // JPs, assuming the first JP is at the start of a cache line or the JPs in |
| 532 | // jpcount fit wholly within a single cache line, which is ensured by |
| 533 | // JudyMalloc(): |
| 534 | |
| 535 | #define CLPERJPS(jpcount) \ |
| 536 | ((((jpcount) * cJU_WORDSPERJP) + cJU_WORDSPERCL - 1) / cJU_WORDSPERCL) |
| 537 | |
| 538 | // Count cache lines below/above for each subexpanse: |
| 539 | |
| 540 | for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp) |
| 541 | { |
| 542 | jpcount = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp)); |
| 543 | |
| 544 | // When at the subexpanse containing Index (digit), add cache lines |
| 545 | // below/above appropriately, excluding the cache line containing the JP for |
| 546 | // Index itself: |
| 547 | |
| 548 | if (subexp < findsub) clbelow += CLPERJPS(jpcount); |
| 549 | else if (subexp > findsub) clabove += CLPERJPS(jpcount); |
| 550 | else // (subexp == findsub) |
| 551 | { |
| 552 | Word_t clfind; // cache line containing Index (digit). |
| 553 | |
| 554 | clfind = CLPERJPS(j__udyCountBitsB( |
| 555 | JU_JBB_BITMAP(Pjbb, subexp) & lowermask)); |
| 556 | |
| 557 | assert(clfind > 0); // digit itself should have 1 CL. |
| 558 | clbelow += clfind - 1; |
| 559 | clabove += CLPERJPS(jpcount) - clfind; |
| 560 | } |
| 561 | } |
| 562 | #endif // ! NOSMARTJBB |
| 563 | |
| 564 | // Note: Its impossible to get through the following "if" without setting |
| 565 | // jpnum -- see some of the assertions below -- but gcc -Wall doesnt know |
| 566 | // this, so preset jpnum to make it happy: |
| 567 | |
| 568 | jpnum = 0; |
| 569 | |
| 570 | |
| 571 | // COUNT POPULATION FOR A BITMAP BRANCH, in whichever direction should result |
| 572 | // in fewer cache line fills: |
| 573 | // |
| 574 | // Note: If the remainder of Index is zero, pop1above is the pop1 of the |
| 575 | // entire expanse and theres no point in recursing to lower levels; but this |
| 576 | // should be so rare that its not worth checking for; |
| 577 | // Judy1Count()/JudyLCount() never even calls the motor for Index == 0 (all |
| 578 | // bytes). |
| 579 | |
| 580 | |
| 581 | // COUNT UPWARD, subtracting each "below or at" JPs pop1 from the whole |
| 582 | // expanses pop1: |
| 583 | // |
| 584 | // Note: If this causes clbelow + 1 cache line fills including JPs cache |
| 585 | // line, thats OK; at worst this is the same as clabove. |
| 586 | |
| 587 | if (clbelow < clabove) |
| 588 | { |
| 589 | #ifdef SMARTMETRICS |
| 590 | ++jbb_upward; |
| 591 | #endif |
| 592 | pop1above = pop1; // subtract JPs at/below Index. |
| 593 | |
| 594 | // Count JPs for which to accrue pop1s in this subexpanse: |
| 595 | // |
| 596 | // TBD: If JU_JBB_BITMAP is cJU_FULLBITMAPB, dont bother counting. |
| 597 | |
| 598 | for (subexp = 0; subexp <= findsub; ++subexp) |
| 599 | { |
| 600 | jpcount = j__udyCountBitsB((subexp < findsub) ? |
| 601 | JU_JBB_BITMAP(Pjbb, subexp) : |
| 602 | JU_JBB_BITMAP(Pjbb, subexp) & lowermask); |
| 603 | |
| 604 | // should always find findbit: |
| 605 | assert((subexp < findsub) || jpcount); |
| 606 | |
| 607 | // Subtract pop1s from JPs BELOW OR AT Index (digit): |
| 608 | // |
| 609 | // Note: The pop1 for Indexs JP itself is partially added back later at a |
| 610 | // lower state. |
| 611 | // |
| 612 | // Note: An empty subexpanse (jpcount == 0) is handled "for free". |
| 613 | // |
| 614 | // Note: Must be null JP subexp pointer in empty subexpanse and non-empty in |
| 615 | // non-empty subexpanse: |
| 616 | |
| 617 | assert( jpcount || (BMPJP0(subexp) == (Pjp_t) NULL)); |
| 618 | assert((! jpcount) || (BMPJP0(subexp) != (Pjp_t) NULL)); |
| 619 | |
| 620 | for (jpnum = 0; jpnum < jpcount; ++jpnum) |
| 621 | { |
| 622 | if ((pop1 = j__udyJPPop1(BMPJP(subexp, jpnum))) |
| 623 | == cJU_ALLONES) |
| 624 | { |
| 625 | JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); |
| 626 | return(C_JERR); |
| 627 | } |
| 628 | |
| 629 | pop1above -= pop1; |
| 630 | } |
| 631 | |
| 632 | jpnum = jpcount - 1; // make correct for digit. |
| 633 | } |
| 634 | } |
| 635 | |
| 636 | // COUNT DOWNWARD, adding each "above" JPs pop1: |
| 637 | |
| 638 | else |
| 639 | { |
| 640 | long jpcountbf; // below findbit, inclusive. |
| 641 | #ifdef SMARTMETRICS |
| 642 | ++jbb_downward; |
| 643 | #endif |
| 644 | pop1above = 0; // add JPs above Index. |
| 645 | jpcountbf = 0; // until subexp == findsub. |
| 646 | |
| 647 | // Count JPs for which to accrue pop1s in this subexpanse: |
| 648 | // |
| 649 | // This is more complicated than counting upward because the scan of digits |
| 650 | // subexpanse must count ALL JPs, to know where to START counting down, and |
| 651 | // ALSO note the offset of digits JP to know where to STOP counting down. |
| 652 | |
| 653 | for (subexp = cJU_NUMSUBEXPB - 1; subexp >= findsub; --subexp) |
| 654 | { |
| 655 | jpcount = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp)); |
| 656 | |
| 657 | // should always find findbit: |
| 658 | assert((subexp > findsub) || jpcount); |
| 659 | |
| 660 | if (! jpcount) continue; // empty subexpanse, save time. |
| 661 | |
| 662 | // Count JPs below digit, inclusive: |
| 663 | |
| 664 | if (subexp == findsub) |
| 665 | { |
| 666 | jpcountbf = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp) |
| 667 | & lowermask); |
| 668 | } |
| 669 | |
| 670 | // should always find findbit: |
| 671 | assert((subexp > findsub) || jpcountbf); |
| 672 | assert(jpcount >= jpcountbf); // proper relationship. |
| 673 | |
| 674 | // Add pop1s from JPs ABOVE Index (digit): |
| 675 | |
| 676 | // no null JP subexp pointers: |
| 677 | assert(BMPJP0(subexp) != (Pjp_t) NULL); |
| 678 | |
| 679 | for (jpnum = jpcount - 1; jpnum >= jpcountbf; --jpnum) |
| 680 | { |
| 681 | if ((pop1 = j__udyJPPop1(BMPJP(subexp, jpnum))) |
| 682 | == cJU_ALLONES) |
| 683 | { |
| 684 | JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); |
| 685 | return(C_JERR); |
| 686 | } |
| 687 | |
| 688 | pop1above += pop1; |
| 689 | } |
| 690 | // jpnum is now correct for digit. |
| 691 | } |
| 692 | } // else. |
| 693 | |
| 694 | // Return the net population ABOVE the digits JP at this state (in this JBB) |
| 695 | // plus the population AT OR ABOVE Index in the SM under the digits JP: |
| 696 | |
| 697 | pop1 = j__udy1LCountSM(BMPJP(findsub, jpnum), Index, Pjpm); |
| 698 | if (pop1 == C_JERR) return(C_JERR); // pass error up. |
| 699 | |
| 700 | assert(pop1above + pop1); |
| 701 | return(pop1above + pop1); |
| 702 | |
| 703 | } // case. |
| 704 | |
| 705 | |
| 706 | // ---------------------------------------------------------------------------- |
| 707 | // UNCOMPRESSED BRANCH; count populations in JPs in the JBU ABOVE the next |
| 708 | // digit in Index, and recurse for the next digit in Index: |
| 709 | // |
| 710 | // Note: If the remainder of Index is zero, pop1above is the pop1 of the |
| 711 | // entire expanse and theres no point in recursing to lower levels; but this |
| 712 | // should be so rare that its not worth checking for; |
| 713 | // Judy1Count()/JudyLCount() never even calls the motor for Index == 0 (all |
| 714 | // bytes). |
| 715 | |
| 716 | case cJU_JPBRANCH_U2: CHECKDCD(Pjp, 2); PREPB(Pjp, 2, BranchU); |
| 717 | case cJU_JPBRANCH_U3: CHECKDCD(Pjp, 3); PREPB(Pjp, 3, BranchU); |
| 718 | #ifdef JU_64BIT |
| 719 | case cJU_JPBRANCH_U4: CHECKDCD(Pjp, 4); PREPB(Pjp, 4, BranchU); |
| 720 | case cJU_JPBRANCH_U5: CHECKDCD(Pjp, 5); PREPB(Pjp, 5, BranchU); |
| 721 | case cJU_JPBRANCH_U6: CHECKDCD(Pjp, 6); PREPB(Pjp, 6, BranchU); |
| 722 | case cJU_JPBRANCH_U7: CHECKDCD(Pjp, 7); PREPB(Pjp, 7, BranchU); |
| 723 | #endif |
| 724 | case cJU_JPBRANCH_U: PREPB_ROOT(Pjp, BranchU); |
| 725 | |
| 726 | // Common code (state-independent) for all cases of uncompressed branches: |
| 727 | |
| 728 | BranchU: |
| 729 | Pjbu = P_JBU(Pjp->jp_Addr); |
| 730 | |
| 731 | #ifndef NOSMARTJBU // enable to turn off smart code for comparison purposes. |
| 732 | |
| 733 | // FIGURE OUT WHICH WAY CAUSES FEWER CACHE LINE FILLS; adding the JPs above |
| 734 | // Indexs JP, or subtracting the JPs below Indexs JP. |
| 735 | // |
| 736 | // COUNT UPWARD, subtracting the pop1 of each JP BELOW OR AT Index, from the |
| 737 | // whole expanses pop1: |
| 738 | |
| 739 | if (digit < (cJU_BRANCHUNUMJPS / 2)) |
| 740 | { |
| 741 | pop1above = pop1; // subtract JPs below Index. |
| 742 | #ifdef SMARTMETRICS |
| 743 | ++jbu_upward; |
| 744 | #endif |
| 745 | for (jpnum = 0; jpnum <= digit; ++jpnum) |
| 746 | { |
| 747 | if ((Pjbu->jbu_jp[jpnum].jp_Type) <= cJU_JPNULLMAX) |
| 748 | continue; // shortcut, save a function call. |
| 749 | |
| 750 | if ((pop1 = j__udyJPPop1(Pjbu->jbu_jp + jpnum)) |
| 751 | == cJU_ALLONES) |
| 752 | { |
| 753 | JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); |
| 754 | return(C_JERR); |
| 755 | } |
| 756 | |
| 757 | pop1above -= pop1; |
| 758 | } |
| 759 | } |
| 760 | |
| 761 | // COUNT DOWNWARD, simply adding the pop1 of each JP ABOVE Index: |
| 762 | |
| 763 | else |
| 764 | #endif // NOSMARTJBU |
| 765 | { |
| 766 | assert(digit < cJU_BRANCHUNUMJPS); |
| 767 | #ifdef SMARTMETRICS |
| 768 | ++jbu_downward; |
| 769 | #endif |
| 770 | pop1above = 0; // add JPs above Index. |
| 771 | |
| 772 | for (jpnum = cJU_BRANCHUNUMJPS - 1; jpnum > digit; --jpnum) |
| 773 | { |
| 774 | if ((Pjbu->jbu_jp[jpnum].jp_Type) <= cJU_JPNULLMAX) |
| 775 | continue; // shortcut, save a function call. |
| 776 | |
| 777 | if ((pop1 = j__udyJPPop1(Pjbu->jbu_jp + jpnum)) |
| 778 | == cJU_ALLONES) |
| 779 | { |
| 780 | JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); |
| 781 | return(C_JERR); |
| 782 | } |
| 783 | |
| 784 | pop1above += pop1; |
| 785 | } |
| 786 | } |
| 787 | |
| 788 | if ((pop1 = j__udy1LCountSM(Pjbu->jbu_jp + digit, Index, Pjpm)) |
| 789 | == C_JERR) return(C_JERR); // pass error up. |
| 790 | |
| 791 | assert(pop1above + pop1); |
| 792 | return(pop1above + pop1); |
| 793 | |
| 794 | |
| 795 | // ---------------------------------------------------------------------------- |
| 796 | // LEAF COUNT MACROS: |
| 797 | // |
| 798 | // LEAF*ABOVE() are common code for different JP types (linear leaves, bitmap |
| 799 | // leaves, and immediates) and different leaf Index Sizes, which result in |
| 800 | // calling different leaf search functions. Linear leaves get the leaf address |
| 801 | // from jp_Addr and the Population from jp_DcdPopO, while immediates use Pjp |
| 802 | // itself as the leaf address and get Population from jp_Type. |
| 803 | |
| 804 | #define LEAFLABOVE(Func) \ |
| 805 | Pjll = P_JLL(Pjp->jp_Addr); \ |
| 806 | pop1 = JU_JPLEAF_POP0(Pjp) + 1; \ |
| 807 | LEAFABOVE(Func, Pjll, pop1) |
| 808 | |
| 809 | #define LEAFB1ABOVE(Func) LEAFLABOVE(Func) // different Func, otherwise same. |
| 810 | |
| 811 | #ifdef JUDY1 |
| 812 | #define IMMABOVE(Func,Pop1) \ |
| 813 | Pjll = (Pjll_t) Pjp; \ |
| 814 | LEAFABOVE(Func, Pjll, Pop1) |
| 815 | #else |
| 816 | // Note: For JudyL immediates with >= 2 Indexes, the index bytes are in a |
| 817 | // different place than for Judy1: |
| 818 | |
| 819 | #define IMMABOVE(Func,Pop1) \ |
| 820 | LEAFABOVE(Func, (Pjll_t) (Pjp->jp_LIndex), Pop1) |
| 821 | #endif |
| 822 | |
| 823 | // For all leaf types, the population AT OR ABOVE is the total pop1 less the |
| 824 | // offset of Index; and Index should always be found: |
| 825 | |
| 826 | #define LEAFABOVE(Func,Pjll,Pop1) \ |
| 827 | offset = Func(Pjll, Pop1, Index); \ |
| 828 | assert(offset >= 0); \ |
| 829 | assert(offset < (Pop1)); \ |
| 830 | return((Pop1) - offset) |
| 831 | |
| 832 | // IMMABOVE_01 handles the special case of an immediate JP with 1 index, which |
| 833 | // the search functions arent used for anyway: |
| 834 | // |
| 835 | // The target Index should be the one in this Immediate, in which case the |
| 836 | // count above (inclusive) is always 1. |
| 837 | |
| 838 | #define IMMABOVE_01 \ |
| 839 | assert((JU_JPDCDPOP0(Pjp)) == JU_TRIMTODCDSIZE(Index)); \ |
| 840 | return(1) |
| 841 | |
| 842 | |
| 843 | // ---------------------------------------------------------------------------- |
| 844 | // LINEAR LEAF; search the leaf for Index; size is computed from jp_Type: |
| 845 | |
| 846 | #if (defined(JUDYL) || (! defined(JU_64BIT))) |
| 847 | case cJU_JPLEAF1: LEAFLABOVE(j__udySearchLeaf1); |
| 848 | #endif |
| 849 | case cJU_JPLEAF2: LEAFLABOVE(j__udySearchLeaf2); |
| 850 | case cJU_JPLEAF3: LEAFLABOVE(j__udySearchLeaf3); |
| 851 | |
| 852 | #ifdef JU_64BIT |
| 853 | case cJU_JPLEAF4: LEAFLABOVE(j__udySearchLeaf4); |
| 854 | case cJU_JPLEAF5: LEAFLABOVE(j__udySearchLeaf5); |
| 855 | case cJU_JPLEAF6: LEAFLABOVE(j__udySearchLeaf6); |
| 856 | case cJU_JPLEAF7: LEAFLABOVE(j__udySearchLeaf7); |
| 857 | #endif |
| 858 | |
| 859 | |
| 860 | // ---------------------------------------------------------------------------- |
| 861 | // BITMAP LEAF; search the leaf for Index: |
| 862 | // |
| 863 | // Since the bitmap describes Indexes digitally rather than linearly, this is |
| 864 | // not really a search, but just a count. |
| 865 | |
| 866 | case cJU_JPLEAF_B1: LEAFB1ABOVE(j__udyCountLeafB1); |
| 867 | |
| 868 | |
| 869 | #ifdef JUDY1 |
| 870 | // ---------------------------------------------------------------------------- |
| 871 | // FULL POPULATION: |
| 872 | // |
| 873 | // Return the count of Indexes AT OR ABOVE Index, which is the total population |
| 874 | // of the expanse (a constant) less the value of the undecoded digit remaining |
| 875 | // in Index (its base-0 offset in the expanse), which yields an inclusive count |
| 876 | // above. |
| 877 | // |
| 878 | // TBD: This only supports a 1-byte full expanse. Should this extract a |
| 879 | // stored value for pop0 and possibly more LSBs of Index, to handle larger full |
| 880 | // expanses? |
| 881 | |
| 882 | case cJ1_JPFULLPOPU1: |
| 883 | return(cJU_JPFULLPOPU1_POP0 + 1 - JU_DIGITATSTATE(Index, 1)); |
| 884 | #endif |
| 885 | |
| 886 | |
| 887 | // ---------------------------------------------------------------------------- |
| 888 | // IMMEDIATE: |
| 889 | |
| 890 | case cJU_JPIMMED_1_01: IMMABOVE_01; |
| 891 | case cJU_JPIMMED_2_01: IMMABOVE_01; |
| 892 | case cJU_JPIMMED_3_01: IMMABOVE_01; |
| 893 | #ifdef JU_64BIT |
| 894 | case cJU_JPIMMED_4_01: IMMABOVE_01; |
| 895 | case cJU_JPIMMED_5_01: IMMABOVE_01; |
| 896 | case cJU_JPIMMED_6_01: IMMABOVE_01; |
| 897 | case cJU_JPIMMED_7_01: IMMABOVE_01; |
| 898 | #endif |
| 899 | |
| 900 | case cJU_JPIMMED_1_02: IMMABOVE(j__udySearchLeaf1, 2); |
| 901 | case cJU_JPIMMED_1_03: IMMABOVE(j__udySearchLeaf1, 3); |
| 902 | #if (defined(JUDY1) || defined(JU_64BIT)) |
| 903 | case cJU_JPIMMED_1_04: IMMABOVE(j__udySearchLeaf1, 4); |
| 904 | case cJU_JPIMMED_1_05: IMMABOVE(j__udySearchLeaf1, 5); |
| 905 | case cJU_JPIMMED_1_06: IMMABOVE(j__udySearchLeaf1, 6); |
| 906 | case cJU_JPIMMED_1_07: IMMABOVE(j__udySearchLeaf1, 7); |
| 907 | #endif |
| 908 | #if (defined(JUDY1) && defined(JU_64BIT)) |
| 909 | case cJ1_JPIMMED_1_08: IMMABOVE(j__udySearchLeaf1, 8); |
| 910 | case cJ1_JPIMMED_1_09: IMMABOVE(j__udySearchLeaf1, 9); |
| 911 | case cJ1_JPIMMED_1_10: IMMABOVE(j__udySearchLeaf1, 10); |
| 912 | case cJ1_JPIMMED_1_11: IMMABOVE(j__udySearchLeaf1, 11); |
| 913 | case cJ1_JPIMMED_1_12: IMMABOVE(j__udySearchLeaf1, 12); |
| 914 | case cJ1_JPIMMED_1_13: IMMABOVE(j__udySearchLeaf1, 13); |
| 915 | case cJ1_JPIMMED_1_14: IMMABOVE(j__udySearchLeaf1, 14); |
| 916 | case cJ1_JPIMMED_1_15: IMMABOVE(j__udySearchLeaf1, 15); |
| 917 | #endif |
| 918 | |
| 919 | #if (defined(JUDY1) || defined(JU_64BIT)) |
| 920 | case cJU_JPIMMED_2_02: IMMABOVE(j__udySearchLeaf2, 2); |
| 921 | case cJU_JPIMMED_2_03: IMMABOVE(j__udySearchLeaf2, 3); |
| 922 | #endif |
| 923 | #if (defined(JUDY1) && defined(JU_64BIT)) |
| 924 | case cJ1_JPIMMED_2_04: IMMABOVE(j__udySearchLeaf2, 4); |
| 925 | case cJ1_JPIMMED_2_05: IMMABOVE(j__udySearchLeaf2, 5); |
| 926 | case cJ1_JPIMMED_2_06: IMMABOVE(j__udySearchLeaf2, 6); |
| 927 | case cJ1_JPIMMED_2_07: IMMABOVE(j__udySearchLeaf2, 7); |
| 928 | #endif |
| 929 | |
| 930 | #if (defined(JUDY1) || defined(JU_64BIT)) |
| 931 | case cJU_JPIMMED_3_02: IMMABOVE(j__udySearchLeaf3, 2); |
| 932 | #endif |
| 933 | #if (defined(JUDY1) && defined(JU_64BIT)) |
| 934 | case cJ1_JPIMMED_3_03: IMMABOVE(j__udySearchLeaf3, 3); |
| 935 | case cJ1_JPIMMED_3_04: IMMABOVE(j__udySearchLeaf3, 4); |
| 936 | case cJ1_JPIMMED_3_05: IMMABOVE(j__udySearchLeaf3, 5); |
| 937 | |
| 938 | case cJ1_JPIMMED_4_02: IMMABOVE(j__udySearchLeaf4, 2); |
| 939 | case cJ1_JPIMMED_4_03: IMMABOVE(j__udySearchLeaf4, 3); |
| 940 | |
| 941 | case cJ1_JPIMMED_5_02: IMMABOVE(j__udySearchLeaf5, 2); |
| 942 | case cJ1_JPIMMED_5_03: IMMABOVE(j__udySearchLeaf5, 3); |
| 943 | |
| 944 | case cJ1_JPIMMED_6_02: IMMABOVE(j__udySearchLeaf6, 2); |
| 945 | |
| 946 | case cJ1_JPIMMED_7_02: IMMABOVE(j__udySearchLeaf7, 2); |
| 947 | #endif |
| 948 | |
| 949 | |
| 950 | // ---------------------------------------------------------------------------- |
| 951 | // OTHER CASES: |
| 952 | |
| 953 | default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); return(C_JERR); |
| 954 | |
| 955 | } // switch on JP type |
| 956 | |
| 957 | /*NOTREACHED*/ |
| 958 | |
| 959 | } // j__udy1LCountSM() |
| 960 | |
| 961 | |
| 962 | // **************************************************************************** |
| 963 | // J U D Y C O U N T L E A F B 1 |
| 964 | // |
| 965 | // This is a private analog of the j__udySearchLeaf*() functions for counting |
| 966 | // in bitmap 1-byte leaves. Since a bitmap leaf describes Indexes digitally |
| 967 | // rather than linearly, this is not really a search, but just a count of the |
| 968 | // valid Indexes == set bits below or including Index, which should be valid. |
| 969 | // Return the "offset" (really the ordinal), 0 .. Pop1 - 1, of Index in Pjll; |
| 970 | // if Indexs bit is not set (which should never happen, so this is DEBUG-mode |
| 971 | // only), return the 1s-complement equivalent (== negative offset minus 1). |
| 972 | // |
| 973 | // Note: The source code for this function looks identical for both Judy1 and |
| 974 | // JudyL, but the JU_JLB_BITMAP macro varies. |
| 975 | // |
| 976 | // Note: For simpler calling, the first arg is of type Pjll_t but then cast to |
| 977 | // Pjlb_t. |
| 978 | |
| 979 | FUNCTION static int j__udyCountLeafB1( |
| 980 | const Pjll_t Pjll, // bitmap leaf, as Pjll_t for consistency. |
| 981 | const Word_t Pop1, // Population of whole leaf. |
| 982 | const Word_t Index) // to which to count. |
| 983 | { |
| 984 | Pjlb_t Pjlb = (Pjlb_t) Pjll; // to proper type. |
| 985 | Word_t digit = Index & cJU_MASKATSTATE(1); |
| 986 | Word_t findsub = digit / cJU_BITSPERSUBEXPL; |
| 987 | Word_t findbit = digit % cJU_BITSPERSUBEXPL; |
| 988 | int count; // in leaf through Index. |
| 989 | long subexp; // for stepping through subexpanses. |
| 990 | |
| 991 | |
| 992 | // COUNT UPWARD: |
| 993 | // |
| 994 | // The entire bitmap should fit in one cache line, but still try to save some |
| 995 | // CPU time by counting the fewest possible number of subexpanses from the |
| 996 | // bitmap. |
| 997 | |
| 998 | #ifndef NOSMARTJLB // enable to turn off smart code for comparison purposes. |
| 999 | |
| 1000 | if (findsub < (cJU_NUMSUBEXPL / 2)) |
| 1001 | { |
| 1002 | #ifdef SMARTMETRICS |
| 1003 | ++jlb_upward; |
| 1004 | #endif |
| 1005 | count = 0; |
| 1006 | |
| 1007 | for (subexp = 0; subexp < findsub; ++subexp) |
| 1008 | { |
| 1009 | count += ((JU_JLB_BITMAP(Pjlb, subexp) == cJU_FULLBITMAPL) ? |
| 1010 | cJU_BITSPERSUBEXPL : |
| 1011 | j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp))); |
| 1012 | } |
| 1013 | |
| 1014 | // This count includes findbit, which should be set, resulting in a base-1 |
| 1015 | // offset: |
| 1016 | |
| 1017 | count += j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, findsub) |
| 1018 | & JU_MASKLOWERINC(JU_BITPOSMASKL(findbit))); |
| 1019 | |
| 1020 | DBGCODE(if (! JU_BITMAPTESTL(Pjlb, digit)) return(~count);) |
| 1021 | assert(count >= 1); |
| 1022 | return(count - 1); // convert to base-0 offset. |
| 1023 | } |
| 1024 | #endif // NOSMARTJLB |
| 1025 | |
| 1026 | |
| 1027 | // COUNT DOWNWARD: |
| 1028 | // |
| 1029 | // Count the valid Indexes above or at Index, and subtract from Pop1. |
| 1030 | |
| 1031 | #ifdef SMARTMETRICS |
| 1032 | ++jlb_downward; |
| 1033 | #endif |
| 1034 | count = Pop1; // base-1 for now. |
| 1035 | |
| 1036 | for (subexp = cJU_NUMSUBEXPL - 1; subexp > findsub; --subexp) |
| 1037 | { |
| 1038 | count -= ((JU_JLB_BITMAP(Pjlb, subexp) == cJU_FULLBITMAPL) ? |
| 1039 | cJU_BITSPERSUBEXPL : |
| 1040 | j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp))); |
| 1041 | } |
| 1042 | |
| 1043 | // This count includes findbit, which should be set, resulting in a base-0 |
| 1044 | // offset: |
| 1045 | |
| 1046 | count -= j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, findsub) |
| 1047 | & JU_MASKHIGHERINC(JU_BITPOSMASKL(findbit))); |
| 1048 | |
| 1049 | DBGCODE(if (! JU_BITMAPTESTL(Pjlb, digit)) return(~count);) |
| 1050 | assert(count >= 0); // should find Index itself. |
| 1051 | return(count); // is already a base-0 offset. |
| 1052 | |
| 1053 | } // j__udyCountLeafB1() |
| 1054 | |
| 1055 | |
| 1056 | // **************************************************************************** |
| 1057 | // J U D Y J P P O P 1 |
| 1058 | // |
| 1059 | // This function takes any type of JP other than a root-level JP (cJU_LEAFW* or |
| 1060 | // cJU_JPBRANCH* with no number suffix) and extracts the Pop1 from it. In some |
| 1061 | // sense this is a wrapper around the JU_JP*_POP0 macros. Why write it as a |
| 1062 | // function instead of a complex macro containing a trinary? (See version |
| 1063 | // Judy1.h version 4.17.) We think its cheaper to call a function containing |
| 1064 | // a switch statement with "constant" cases than to do the variable |
| 1065 | // calculations in a trinary. |
| 1066 | // |
| 1067 | // For invalid JP Types return cJU_ALLONES. Note that this is an impossibly |
| 1068 | // high Pop1 for any JP below a top level branch. |
| 1069 | |
| 1070 | FUNCTION Word_t j__udyJPPop1( |
| 1071 | const Pjp_t Pjp) // JP to count. |
| 1072 | { |
| 1073 | switch (JU_JPTYPE(Pjp)) |
| 1074 | { |
| 1075 | #ifdef notdef // caller should shortcut and not even call with these: |
| 1076 | |
| 1077 | case cJU_JPNULL1: |
| 1078 | case cJU_JPNULL2: |
| 1079 | case cJU_JPNULL3: return(0); |
| 1080 | #ifdef JU_64BIT |
| 1081 | case cJU_JPNULL4: |
| 1082 | case cJU_JPNULL5: |
| 1083 | case cJU_JPNULL6: |
| 1084 | case cJU_JPNULL7: return(0); |
| 1085 | #endif |
| 1086 | #endif // notdef |
| 1087 | |
| 1088 | case cJU_JPBRANCH_L2: |
| 1089 | case cJU_JPBRANCH_B2: |
| 1090 | case cJU_JPBRANCH_U2: return(JU_JPBRANCH_POP0(Pjp,2) + 1); |
| 1091 | |
| 1092 | case cJU_JPBRANCH_L3: |
| 1093 | case cJU_JPBRANCH_B3: |
| 1094 | case cJU_JPBRANCH_U3: return(JU_JPBRANCH_POP0(Pjp,3) + 1); |
| 1095 | |
| 1096 | #ifdef JU_64BIT |
| 1097 | case cJU_JPBRANCH_L4: |
| 1098 | case cJU_JPBRANCH_B4: |
| 1099 | case cJU_JPBRANCH_U4: return(JU_JPBRANCH_POP0(Pjp,4) + 1); |
| 1100 | |
| 1101 | case cJU_JPBRANCH_L5: |
| 1102 | case cJU_JPBRANCH_B5: |
| 1103 | case cJU_JPBRANCH_U5: return(JU_JPBRANCH_POP0(Pjp,5) + 1); |
| 1104 | |
| 1105 | case cJU_JPBRANCH_L6: |
| 1106 | case cJU_JPBRANCH_B6: |
| 1107 | case cJU_JPBRANCH_U6: return(JU_JPBRANCH_POP0(Pjp,6) + 1); |
| 1108 | |
| 1109 | case cJU_JPBRANCH_L7: |
| 1110 | case cJU_JPBRANCH_B7: |
| 1111 | case cJU_JPBRANCH_U7: return(JU_JPBRANCH_POP0(Pjp,7) + 1); |
| 1112 | #endif |
| 1113 | |
| 1114 | #if (defined(JUDYL) || (! defined(JU_64BIT))) |
| 1115 | case cJU_JPLEAF1: |
| 1116 | #endif |
| 1117 | case cJU_JPLEAF2: |
| 1118 | case cJU_JPLEAF3: |
| 1119 | #ifdef JU_64BIT |
| 1120 | case cJU_JPLEAF4: |
| 1121 | case cJU_JPLEAF5: |
| 1122 | case cJU_JPLEAF6: |
| 1123 | case cJU_JPLEAF7: |
| 1124 | #endif |
| 1125 | case cJU_JPLEAF_B1: return(JU_JPLEAF_POP0(Pjp) + 1); |
| 1126 | |
| 1127 | #ifdef JUDY1 |
| 1128 | case cJ1_JPFULLPOPU1: return(cJU_JPFULLPOPU1_POP0 + 1); |
| 1129 | #endif |
| 1130 | |
| 1131 | case cJU_JPIMMED_1_01: |
| 1132 | case cJU_JPIMMED_2_01: |
| 1133 | case cJU_JPIMMED_3_01: return(1); |
| 1134 | #ifdef JU_64BIT |
| 1135 | case cJU_JPIMMED_4_01: |
| 1136 | case cJU_JPIMMED_5_01: |
| 1137 | case cJU_JPIMMED_6_01: |
| 1138 | case cJU_JPIMMED_7_01: return(1); |
| 1139 | #endif |
| 1140 | |
| 1141 | case cJU_JPIMMED_1_02: return(2); |
| 1142 | case cJU_JPIMMED_1_03: return(3); |
| 1143 | #if (defined(JUDY1) || defined(JU_64BIT)) |
| 1144 | case cJU_JPIMMED_1_04: return(4); |
| 1145 | case cJU_JPIMMED_1_05: return(5); |
| 1146 | case cJU_JPIMMED_1_06: return(6); |
| 1147 | case cJU_JPIMMED_1_07: return(7); |
| 1148 | #endif |
| 1149 | #if (defined(JUDY1) && defined(JU_64BIT)) |
| 1150 | case cJ1_JPIMMED_1_08: return(8); |
| 1151 | case cJ1_JPIMMED_1_09: return(9); |
| 1152 | case cJ1_JPIMMED_1_10: return(10); |
| 1153 | case cJ1_JPIMMED_1_11: return(11); |
| 1154 | case cJ1_JPIMMED_1_12: return(12); |
| 1155 | case cJ1_JPIMMED_1_13: return(13); |
| 1156 | case cJ1_JPIMMED_1_14: return(14); |
| 1157 | case cJ1_JPIMMED_1_15: return(15); |
| 1158 | #endif |
| 1159 | |
| 1160 | #if (defined(JUDY1) || defined(JU_64BIT)) |
| 1161 | case cJU_JPIMMED_2_02: return(2); |
| 1162 | case cJU_JPIMMED_2_03: return(3); |
| 1163 | #endif |
| 1164 | #if (defined(JUDY1) && defined(JU_64BIT)) |
| 1165 | case cJ1_JPIMMED_2_04: return(4); |
| 1166 | case cJ1_JPIMMED_2_05: return(5); |
| 1167 | case cJ1_JPIMMED_2_06: return(6); |
| 1168 | case cJ1_JPIMMED_2_07: return(7); |
| 1169 | #endif |
| 1170 | |
| 1171 | #if (defined(JUDY1) || defined(JU_64BIT)) |
| 1172 | case cJU_JPIMMED_3_02: return(2); |
| 1173 | #endif |
| 1174 | #if (defined(JUDY1) && defined(JU_64BIT)) |
| 1175 | case cJ1_JPIMMED_3_03: return(3); |
| 1176 | case cJ1_JPIMMED_3_04: return(4); |
| 1177 | case cJ1_JPIMMED_3_05: return(5); |
| 1178 | |
| 1179 | case cJ1_JPIMMED_4_02: return(2); |
| 1180 | case cJ1_JPIMMED_4_03: return(3); |
| 1181 | |
| 1182 | case cJ1_JPIMMED_5_02: return(2); |
| 1183 | case cJ1_JPIMMED_5_03: return(3); |
| 1184 | |
| 1185 | case cJ1_JPIMMED_6_02: return(2); |
| 1186 | |
| 1187 | case cJ1_JPIMMED_7_02: return(2); |
| 1188 | #endif |
| 1189 | |
| 1190 | default: return(cJU_ALLONES); |
| 1191 | } |
| 1192 | |
| 1193 | /*NOTREACHED*/ |
| 1194 | |
| 1195 | } // j__udyJPPop1() |