| 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 | // TBD: It would probably be faster for the caller if the JudyL version took |
| 19 | // PIndex as an interleaved array of indexes and values rather than just |
| 20 | // indexes with a separate values array (PValue), especially considering |
| 21 | // indexes and values are copied here with for-loops anyway and not the |
| 22 | // equivalent of memcpy(). All code could be revised to simply count by two |
| 23 | // words for JudyL? Supports "streaming" the data to/from disk better later? |
| 24 | // In which case get rid of JU_ERRNO_NULLPVALUE, no longer needed, and simplify |
| 25 | // the API to this code. |
| 26 | // _________________ |
| 27 | |
| 28 | // @(#) $Revision: 4.21 $ $Source: /judy/src/JudyCommon/JudyInsArray.c $ |
| 29 | // |
| 30 | // Judy1SetArray() and JudyLInsArray() functions for Judy1 and JudyL. |
| 31 | // Compile with one of -DJUDY1 or -DJUDYL. |
| 32 | |
| 33 | #if (! (defined(JUDY1) || defined(JUDYL))) |
| 34 | #error: One of -DJUDY1 or -DJUDYL must be specified. |
| 35 | #endif |
| 36 | |
| 37 | #ifdef JUDY1 |
| 38 | #include "Judy1.h" |
| 39 | #else |
| 40 | #include "JudyL.h" |
| 41 | #endif |
| 42 | |
| 43 | #include "JudyPrivate1L.h" |
| 44 | |
| 45 | DBGCODE(extern void JudyCheckPop(Pvoid_t PArray);) |
| 46 | |
| 47 | |
| 48 | // IMMED AND LEAF SIZE AND BRANCH TYPE ARRAYS: |
| 49 | // |
| 50 | // These support fast and easy lookup by level. |
| 51 | |
| 52 | static uint8_t immed_maxpop1[] = { |
| 53 | 0, |
| 54 | cJU_IMMED1_MAXPOP1, |
| 55 | cJU_IMMED2_MAXPOP1, |
| 56 | cJU_IMMED3_MAXPOP1, |
| 57 | #ifdef JU_64BIT |
| 58 | cJU_IMMED4_MAXPOP1, |
| 59 | cJU_IMMED5_MAXPOP1, |
| 60 | cJU_IMMED6_MAXPOP1, |
| 61 | cJU_IMMED7_MAXPOP1, |
| 62 | #endif |
| 63 | // note: There are no IMMEDs for whole words. |
| 64 | }; |
| 65 | |
| 66 | static uint8_t leaf_maxpop1[] = { |
| 67 | 0, |
| 68 | #if (defined(JUDYL) || (! defined(JU_64BIT))) |
| 69 | cJU_LEAF1_MAXPOP1, |
| 70 | #else |
| 71 | 0, // 64-bit Judy1 has no Leaf1. |
| 72 | #endif |
| 73 | cJU_LEAF2_MAXPOP1, |
| 74 | cJU_LEAF3_MAXPOP1, |
| 75 | #ifdef JU_64BIT |
| 76 | cJU_LEAF4_MAXPOP1, |
| 77 | cJU_LEAF5_MAXPOP1, |
| 78 | cJU_LEAF6_MAXPOP1, |
| 79 | cJU_LEAF7_MAXPOP1, |
| 80 | #endif |
| 81 | // note: Root-level leaves are handled differently. |
| 82 | }; |
| 83 | |
| 84 | static uint8_t branchL_JPtype[] = { |
| 85 | 0, |
| 86 | 0, |
| 87 | cJU_JPBRANCH_L2, |
| 88 | cJU_JPBRANCH_L3, |
| 89 | #ifdef JU_64BIT |
| 90 | cJU_JPBRANCH_L4, |
| 91 | cJU_JPBRANCH_L5, |
| 92 | cJU_JPBRANCH_L6, |
| 93 | cJU_JPBRANCH_L7, |
| 94 | #endif |
| 95 | cJU_JPBRANCH_L, |
| 96 | }; |
| 97 | |
| 98 | static uint8_t branchB_JPtype[] = { |
| 99 | 0, |
| 100 | 0, |
| 101 | cJU_JPBRANCH_B2, |
| 102 | cJU_JPBRANCH_B3, |
| 103 | #ifdef JU_64BIT |
| 104 | cJU_JPBRANCH_B4, |
| 105 | cJU_JPBRANCH_B5, |
| 106 | cJU_JPBRANCH_B6, |
| 107 | cJU_JPBRANCH_B7, |
| 108 | #endif |
| 109 | cJU_JPBRANCH_B, |
| 110 | }; |
| 111 | |
| 112 | static uint8_t branchU_JPtype[] = { |
| 113 | 0, |
| 114 | 0, |
| 115 | cJU_JPBRANCH_U2, |
| 116 | cJU_JPBRANCH_U3, |
| 117 | #ifdef JU_64BIT |
| 118 | cJU_JPBRANCH_U4, |
| 119 | cJU_JPBRANCH_U5, |
| 120 | cJU_JPBRANCH_U6, |
| 121 | cJU_JPBRANCH_U7, |
| 122 | #endif |
| 123 | cJU_JPBRANCH_U, |
| 124 | }; |
| 125 | |
| 126 | // Subexpanse masks are similer to JU_DCDMASK() but without the need to clear |
| 127 | // the first digits bits. Avoid doing variable shifts by precomputing a |
| 128 | // lookup array. |
| 129 | |
| 130 | static Word_t subexp_mask[] = { |
| 131 | 0, |
| 132 | ~cJU_POP0MASK(1), |
| 133 | ~cJU_POP0MASK(2), |
| 134 | ~cJU_POP0MASK(3), |
| 135 | #ifdef JU_64BIT |
| 136 | ~cJU_POP0MASK(4), |
| 137 | ~cJU_POP0MASK(5), |
| 138 | ~cJU_POP0MASK(6), |
| 139 | ~cJU_POP0MASK(7), |
| 140 | #endif |
| 141 | }; |
| 142 | |
| 143 | |
| 144 | // FUNCTION PROTOTYPES: |
| 145 | |
| 146 | static bool_t j__udyInsArray(Pjp_t PjpParent, int Level, PWord_t PPop1, |
| 147 | PWord_t PIndex, |
| 148 | #ifdef JUDYL |
| 149 | Pjv_t PValue, |
| 150 | #endif |
| 151 | Pjpm_t Pjpm); |
| 152 | |
| 153 | |
| 154 | // **************************************************************************** |
| 155 | // J U D Y 1 S E T A R R A Y |
| 156 | // J U D Y L I N S A R R A Y |
| 157 | // |
| 158 | // Main entry point. See the manual entry for external overview. |
| 159 | // |
| 160 | // TBD: Until thats written, note that the function returns 1 for success or |
| 161 | // JERRI for serious error, including insufficient memory to build whole array; |
| 162 | // use Judy*Count() to see how many were stored, the first N of the total |
| 163 | // Count. Also, since it takes Count == Pop1, it cannot handle a full array. |
| 164 | // Also, "sorted" means ascending without duplicates, otherwise you get the |
| 165 | // "unsorted" error. |
| 166 | // |
| 167 | // The purpose of these functions is to allow rapid construction of a large |
| 168 | // Judy array given a sorted list of indexes (and for JudyL, corresponding |
| 169 | // values). At least one customer saw this as useful, and probably it would |
| 170 | // also be useful as a sufficient workaround for fast(er) unload/reload to/from |
| 171 | // disk. |
| 172 | // |
| 173 | // This code is written recursively for simplicity, until/unless someone |
| 174 | // decides to make it faster and more complex. Hopefully recursion is fast |
| 175 | // enough simply because the function is so much faster than a series of |
| 176 | // Set/Ins calls. |
| 177 | |
| 178 | #ifdef JUDY1 |
| 179 | FUNCTION int Judy1SetArray |
| 180 | #else |
| 181 | FUNCTION int JudyLInsArray |
| 182 | #endif |
| 183 | ( |
| 184 | PPvoid_t PPArray, // in which to insert, initially empty. |
| 185 | Word_t Count, // number of indexes (and values) to insert. |
| 186 | const Word_t * const PIndex, // list of indexes to insert. |
| 187 | #ifdef JUDYL |
| 188 | const Word_t * const PValue, // list of corresponding values. |
| 189 | #endif |
| 190 | PJError_t PJError // optional, for returning error info. |
| 191 | ) |
| 192 | { |
| 193 | Pjlw_t Pjlw; // new root-level leaf. |
| 194 | Pjlw_t Pjlwindex; // first index in root-level leaf. |
| 195 | int offset; // in PIndex. |
| 196 | |
| 197 | |
| 198 | // CHECK FOR NULL OR NON-NULL POINTER (error by caller): |
| 199 | |
| 200 | if (PPArray == (PPvoid_t) NULL) |
| 201 | { JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY); return(JERRI); } |
| 202 | |
| 203 | if (*PPArray != (Pvoid_t) NULL) |
| 204 | { JU_SET_ERRNO(PJError, JU_ERRNO_NONNULLPARRAY); return(JERRI); } |
| 205 | |
| 206 | if (PIndex == (PWord_t) NULL) |
| 207 | { JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX); return(JERRI); } |
| 208 | |
| 209 | #ifdef JUDYL |
| 210 | if (PValue == (PWord_t) NULL) |
| 211 | { JU_SET_ERRNO(PJError, JU_ERRNO_NULLPVALUE); return(JERRI); } |
| 212 | #endif |
| 213 | |
| 214 | |
| 215 | // HANDLE LARGE COUNT (= POP1) (typical case): |
| 216 | // |
| 217 | // Allocate and initialize a JPM, set the root pointer to point to it, and then |
| 218 | // build the tree underneath it. |
| 219 | |
| 220 | // Common code for unusual error handling when no JPM available: |
| 221 | |
| 222 | if (Count > cJU_LEAFW_MAXPOP1) // too big for root-level leaf. |
| 223 | { |
| 224 | Pjpm_t Pjpm; // new, to allocate. |
| 225 | |
| 226 | // Allocate JPM: |
| 227 | |
| 228 | Pjpm = j__udyAllocJPM(); |
| 229 | JU_CHECKALLOC(Pjpm_t, Pjpm, JERRI); |
| 230 | *PPArray = (Pvoid_t) Pjpm; |
| 231 | |
| 232 | // Set some JPM fields: |
| 233 | |
| 234 | (Pjpm->jpm_Pop0) = Count - 1; |
| 235 | // note: (Pjpm->jpm_TotalMemWords) is now initialized. |
| 236 | |
| 237 | // Build Judy tree: |
| 238 | // |
| 239 | // In case of error save the final Count, possibly modified, unless modified to |
| 240 | // 0, in which case free the JPM itself: |
| 241 | |
| 242 | if (! j__udyInsArray(&(Pjpm->jpm_JP), cJU_ROOTSTATE, &Count, |
| 243 | (PWord_t) PIndex, |
| 244 | #ifdef JUDYL |
| 245 | (Pjv_t) PValue, |
| 246 | #endif |
| 247 | Pjpm)) |
| 248 | { |
| 249 | JU_COPY_ERRNO(PJError, Pjpm); |
| 250 | |
| 251 | if (Count) // partial success, adjust pop0: |
| 252 | { |
| 253 | (Pjpm->jpm_Pop0) = Count - 1; |
| 254 | } |
| 255 | else // total failure, free JPM: |
| 256 | { |
| 257 | j__udyFreeJPM(Pjpm, (Pjpm_t) NULL); |
| 258 | *PPArray = (Pvoid_t) NULL; |
| 259 | } |
| 260 | |
| 261 | DBGCODE(JudyCheckPop(*PPArray);) |
| 262 | return(JERRI); |
| 263 | } |
| 264 | |
| 265 | DBGCODE(JudyCheckPop(*PPArray);) |
| 266 | return(1); |
| 267 | |
| 268 | } // large count |
| 269 | |
| 270 | |
| 271 | // HANDLE SMALL COUNT (= POP1): |
| 272 | // |
| 273 | // First ensure indexes are in sorted order: |
| 274 | |
| 275 | for (offset = 1; offset < Count; ++offset) |
| 276 | { |
| 277 | if (PIndex[offset - 1] >= PIndex[offset]) |
| 278 | { JU_SET_ERRNO(PJError, JU_ERRNO_UNSORTED); return(JERRI); } |
| 279 | } |
| 280 | |
| 281 | if (Count == 0) return(1); // *PPArray remains null. |
| 282 | |
| 283 | { |
| 284 | Pjlw = j__udyAllocJLW(Count + 1); |
| 285 | JU_CHECKALLOC(Pjlw_t, Pjlw, JERRI); |
| 286 | *PPArray = (Pvoid_t) Pjlw; |
| 287 | Pjlw[0] = Count - 1; // set pop0. |
| 288 | Pjlwindex = Pjlw + 1; |
| 289 | } |
| 290 | |
| 291 | // Copy whole-word indexes (and values) to the root-level leaf: |
| 292 | |
| 293 | JU_COPYMEM(Pjlwindex, PIndex, Count); |
| 294 | JUDYLCODE(JU_COPYMEM(JL_LEAFWVALUEAREA(Pjlw, Count), PValue, Count)); |
| 295 | |
| 296 | DBGCODE(JudyCheckPop(*PPArray);) |
| 297 | return(1); |
| 298 | |
| 299 | } // Judy1SetArray() / JudyLInsArray() |
| 300 | |
| 301 | |
| 302 | // **************************************************************************** |
| 303 | // __ J U D Y I N S A R R A Y |
| 304 | // |
| 305 | // Given: |
| 306 | // |
| 307 | // - a pointer to a JP |
| 308 | // |
| 309 | // - the JPs level in the tree, that is, the number of digits left to decode |
| 310 | // in the indexes under the JP (one less than the level of the JPM or branch |
| 311 | // in which the JP resides); cJU_ROOTSTATE on first entry (when JP is the one |
| 312 | // in the JPM), down to 1 for a Leaf1, LeafB1, or FullPop |
| 313 | // |
| 314 | // - a pointer to the number of indexes (and corresponding values) to store in |
| 315 | // this subtree, to modify in case of partial success |
| 316 | // |
| 317 | // - a list of indexes (and for JudyL, corresponding values) to store in this |
| 318 | // subtree |
| 319 | // |
| 320 | // - a JPM for tracking memory usage and returning errors |
| 321 | // |
| 322 | // Recursively build a subtree (immediate indexes, leaf, or branch with |
| 323 | // subtrees) and modify the JP accordingly. On the way down, build a BranchU |
| 324 | // (only) for any expanse with *PPop1 too high for a leaf; on the way out, |
| 325 | // convert the BranchU to a BranchL or BranchB if appropriate. Keep memory |
| 326 | // statistics in the JPM. |
| 327 | // |
| 328 | // Return TRUE for success, or FALSE with error information set in the JPM in |
| 329 | // case of error, in which case leave a partially constructed but healthy tree, |
| 330 | // and modify parent population counts on the way out. |
| 331 | // |
| 332 | // Note: Each call of this function makes all modifications to the PjpParent |
| 333 | // it receives; neither the parent nor child calls do this. |
| 334 | |
| 335 | FUNCTION static bool_t j__udyInsArray( |
| 336 | Pjp_t PjpParent, // parent JP in/under which to store. |
| 337 | int Level, // initial digits remaining to decode. |
| 338 | PWord_t PPop1, // number of indexes to store. |
| 339 | PWord_t PIndex, // list of indexes to store. |
| 340 | #ifdef JUDYL |
| 341 | Pjv_t PValue, // list of corresponding values. |
| 342 | #endif |
| 343 | Pjpm_t Pjpm) // for memory and errors. |
| 344 | { |
| 345 | Pjp_t Pjp; // lower-level JP. |
| 346 | Word_t Pjbany; // any type of branch. |
| 347 | int levelsub; // actual, of Pjps node, <= Level. |
| 348 | Word_t pop1 = *PPop1; // fast local value. |
| 349 | Word_t pop1sub; // population of one subexpanse. |
| 350 | uint8_t JPtype; // current JP type. |
| 351 | uint8_t JPtype_null; // precomputed value for new branch. |
| 352 | jp_t JPnull; // precomputed for speed. |
| 353 | Pjbu_t PjbuRaw; // constructed BranchU. |
| 354 | Pjbu_t Pjbu; |
| 355 | int digit; // in BranchU. |
| 356 | Word_t digitmask; // for a digit in a BranchU. |
| 357 | Word_t digitshifted; // shifted to correct offset. |
| 358 | Word_t digitshincr; // increment for digitshifted. |
| 359 | int offset; // in PIndex, or a bitmap subexpanse. |
| 360 | int numJPs; // number non-null in a BranchU. |
| 361 | bool_t retval; // to return from this func. |
| 362 | JUDYLCODE(Pjv_t PjvRaw); // destination value area. |
| 363 | JUDYLCODE(Pjv_t Pjv); |
| 364 | |
| 365 | |
| 366 | // MACROS FOR COMMON CODE: |
| 367 | // |
| 368 | // Note: These use function and local parameters from the context. |
| 369 | // Note: Assume newly allocated memory is zeroed. |
| 370 | |
| 371 | // Indicate whether a sorted list of indexes in PIndex, based on the first and |
| 372 | // last indexes in the list using pop1, are in the same subexpanse between |
| 373 | // Level and L_evel: |
| 374 | // |
| 375 | // This can be confusing! Note that SAMESUBEXP(L) == TRUE means the indexes |
| 376 | // are the same through level L + 1, and it says nothing about level L and |
| 377 | // lower; they might be the same or they might differ. |
| 378 | // |
| 379 | // Note: In principle SAMESUBEXP needs a mask for the digits from Level, |
| 380 | // inclusive, to L_evel, exclusive. But in practice, since the indexes are all |
| 381 | // known to be identical above Level, it just uses a mask for the digits |
| 382 | // through L_evel + 1; see subexp_mask[]. |
| 383 | |
| 384 | #define SAMESUBEXP(L_evel) \ |
| 385 | (! ((PIndex[0] ^ PIndex[pop1 - 1]) & subexp_mask[L_evel])) |
| 386 | |
| 387 | // Set PjpParent to a null JP appropriate for the level of the node to which it |
| 388 | // points, which is 1 less than the level of the node in which the JP resides, |
| 389 | // which is by definition Level: |
| 390 | // |
| 391 | // Note: This can set the JPMs JP to an invalid jp_Type, but it doesnt |
| 392 | // matter because the JPM is deleted by the caller. |
| 393 | |
| 394 | #define SETJPNULL_PARENT \ |
| 395 | JU_JPSETADT(PjpParent, 0, 0, cJU_JPNULL1 + Level - 1); |
| 396 | |
| 397 | // Variation to set a specified JP (in a branch being built) to a precomputed |
| 398 | // null JP: |
| 399 | |
| 400 | #define SETJPNULL(Pjp) *(Pjp) = JPnull |
| 401 | |
| 402 | // Handle complete (as opposed to partial) memory allocation failure: Set the |
| 403 | // parent JP to an appropriate null type (to leave a consistent tree), zero the |
| 404 | // callers population count, and return FALSE: |
| 405 | // |
| 406 | // Note: At Level == cJU_ROOTSTATE this sets the JPMs JPs jp_Type to a bogus |
| 407 | // value, but it doesnt matter because the JPM should be deleted by the |
| 408 | // caller. |
| 409 | |
| 410 | #define NOMEM { SETJPNULL_PARENT; *PPop1 = 0; return(FALSE); } |
| 411 | |
| 412 | // Allocate a Leaf1-N and save the address in Pjll; in case of failure, NOMEM: |
| 413 | |
| 414 | #define ALLOCLEAF(AllocLeaf) \ |
| 415 | if ((PjllRaw = AllocLeaf(pop1, Pjpm)) == (Pjll_t) NULL) NOMEM; \ |
| 416 | Pjll = P_JLL(PjllRaw); |
| 417 | |
| 418 | // Copy indexes smaller than words (and values which are whole words) from |
| 419 | // given arrays to immediate indexes or a leaf: |
| 420 | // |
| 421 | // TBD: These macros overlap with some of the code in JudyCascade.c; do some |
| 422 | // merging? That file has functions while these are macros. |
| 423 | |
| 424 | #define COPYTOLEAF_EVEN_SUB(Pjll,LeafType) \ |
| 425 | { \ |
| 426 | LeafType * P_leaf = (LeafType *) (Pjll); \ |
| 427 | Word_t p_op1 = pop1; \ |
| 428 | PWord_t P_Index = PIndex; \ |
| 429 | \ |
| 430 | assert(pop1 > 0); \ |
| 431 | \ |
| 432 | do { *P_leaf++ = *P_Index++; /* truncates */\ |
| 433 | } while (--(p_op1)); \ |
| 434 | } |
| 435 | |
| 436 | #define COPYTOLEAF_ODD_SUB(cLevel,Pjll,Copy) \ |
| 437 | { \ |
| 438 | uint8_t * P_leaf = (uint8_t *) (Pjll); \ |
| 439 | Word_t p_op1 = pop1; \ |
| 440 | PWord_t P_Index = PIndex; \ |
| 441 | \ |
| 442 | assert(pop1 > 0); \ |
| 443 | \ |
| 444 | do { \ |
| 445 | Copy(P_leaf, *P_Index); \ |
| 446 | P_leaf += (cLevel); ++P_Index; \ |
| 447 | } while (--(p_op1)); \ |
| 448 | } |
| 449 | |
| 450 | #ifdef JUDY1 |
| 451 | |
| 452 | #define COPYTOLEAF_EVEN(Pjll,LeafType) COPYTOLEAF_EVEN_SUB(Pjll,LeafType) |
| 453 | #define COPYTOLEAF_ODD(cLevel,Pjll,Copy) COPYTOLEAF_ODD_SUB(cLevel,Pjll,Copy) |
| 454 | |
| 455 | #else // JUDYL adds copying of values: |
| 456 | |
| 457 | #define COPYTOLEAF_EVEN(Pjll,LeafType) \ |
| 458 | { \ |
| 459 | COPYTOLEAF_EVEN_SUB(Pjll,LeafType) \ |
| 460 | JU_COPYMEM(Pjv, PValue, pop1); \ |
| 461 | } |
| 462 | |
| 463 | #define COPYTOLEAF_ODD(cLevel,Pjll,Copy) \ |
| 464 | { \ |
| 465 | COPYTOLEAF_ODD_SUB( cLevel,Pjll,Copy) \ |
| 466 | JU_COPYMEM(Pjv, PValue, pop1); \ |
| 467 | } |
| 468 | |
| 469 | #endif |
| 470 | |
| 471 | // Set the JP type for an immediate index, where BaseJPType is JPIMMED_*_02: |
| 472 | |
| 473 | #define SETIMMTYPE(BaseJPType) (PjpParent->jp_Type) = (BaseJPType) + pop1 - 2 |
| 474 | |
| 475 | // Allocate and populate a Leaf1-N: |
| 476 | // |
| 477 | // Build MAKELEAF_EVEN() and MAKELEAF_ODD() using macros for common code. |
| 478 | |
| 479 | #define MAKELEAF_SUB1(AllocLeaf,ValueArea,LeafType) \ |
| 480 | ALLOCLEAF(AllocLeaf); \ |
| 481 | JUDYLCODE(Pjv = ValueArea(Pjll, pop1)) |
| 482 | |
| 483 | |
| 484 | #define MAKELEAF_SUB2(cLevel,JPType) \ |
| 485 | { \ |
| 486 | Word_t D_cdP0; \ |
| 487 | assert(pop1 - 1 <= cJU_POP0MASK(cLevel)); \ |
| 488 | D_cdP0 = (*PIndex & cJU_DCDMASK(cLevel)) | (pop1 - 1); \ |
| 489 | JU_JPSETADT(PjpParent, (Word_t)PjllRaw, D_cdP0, JPType); \ |
| 490 | } |
| 491 | |
| 492 | |
| 493 | #define MAKELEAF_EVEN(cLevel,JPType,AllocLeaf,ValueArea,LeafType) \ |
| 494 | MAKELEAF_SUB1(AllocLeaf,ValueArea,LeafType); \ |
| 495 | COPYTOLEAF_EVEN(Pjll, LeafType); \ |
| 496 | MAKELEAF_SUB2(cLevel, JPType) |
| 497 | |
| 498 | #define MAKELEAF_ODD(cLevel,JPType,AllocLeaf,ValueArea,Copy) \ |
| 499 | MAKELEAF_SUB1(AllocLeaf,ValueArea,LeafType); \ |
| 500 | COPYTOLEAF_ODD(cLevel, Pjll, Copy); \ |
| 501 | MAKELEAF_SUB2(cLevel, JPType) |
| 502 | |
| 503 | // Ensure that the indexes to be stored in immediate indexes or a leaf are |
| 504 | // sorted: |
| 505 | // |
| 506 | // This check is pure overhead, but required in order to protect the Judy array |
| 507 | // against caller error, to avoid a later corruption or core dump from a |
| 508 | // seemingly valid Judy array. Do this check piecemeal at the leaf level while |
| 509 | // the indexes are already in the cache. Higher-level order-checking occurs |
| 510 | // while building branches. |
| 511 | // |
| 512 | // Note: Any sorting error in the expanse of a single immediate indexes JP or |
| 513 | // a leaf => save no indexes in that expanse. |
| 514 | |
| 515 | #define CHECKLEAFORDER \ |
| 516 | { \ |
| 517 | for (offset = 1; offset < pop1; ++offset) \ |
| 518 | { \ |
| 519 | if (PIndex[offset - 1] >= PIndex[offset]) \ |
| 520 | { \ |
| 521 | SETJPNULL_PARENT; \ |
| 522 | *PPop1 = 0; \ |
| 523 | JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_UNSORTED); \ |
| 524 | return(FALSE); \ |
| 525 | } \ |
| 526 | } \ |
| 527 | } |
| 528 | |
| 529 | |
| 530 | // ------ START OF CODE ------ |
| 531 | |
| 532 | assert( Level >= 1); |
| 533 | assert( Level <= cJU_ROOTSTATE); |
| 534 | assert((Level < cJU_ROOTSTATE) || (pop1 > cJU_LEAFW_MAXPOP1)); |
| 535 | |
| 536 | |
| 537 | // CHECK FOR TOP LEVEL: |
| 538 | // |
| 539 | // Special case: If at the top level (PjpParent is in the JPM), a top-level |
| 540 | // branch must be created, even if its a BranchL with just one JP. (The JPM |
| 541 | // cannot point to a leaf because the leaf would have to be a lower-level, |
| 542 | // higher-capacity leaf under a narrow pointer (otherwise a root-level leaf |
| 543 | // would suffice), and the JPMs JP cant handle a narrow pointer because the |
| 544 | // jp_DcdPopO field isnt big enough.) Otherwise continue to check for a pop1 |
| 545 | // small enough to support immediate indexes or a leaf before giving up and |
| 546 | // making a lower-level branch. |
| 547 | |
| 548 | if (Level == cJU_ROOTSTATE) |
| 549 | { |
| 550 | levelsub = cJU_ROOTSTATE; |
| 551 | goto BuildBranch2; |
| 552 | } |
| 553 | assert(Level < cJU_ROOTSTATE); |
| 554 | |
| 555 | |
| 556 | // SKIP JPIMMED_*_01: |
| 557 | // |
| 558 | // Immeds with pop1 == 1 should be handled in-line during branch construction. |
| 559 | |
| 560 | assert(pop1 > 1); |
| 561 | |
| 562 | |
| 563 | // BUILD JPIMMED_*_02+: |
| 564 | // |
| 565 | // The starting address of the indexes depends on Judy1 or JudyL; also, JudyL |
| 566 | // includes a pointer to a values-only leaf. |
| 567 | |
| 568 | if (pop1 <= immed_maxpop1[Level]) // note: always < root level. |
| 569 | { |
| 570 | JUDY1CODE(uint8_t * Pjll = (uint8_t *) (PjpParent->jp_1Index);) |
| 571 | JUDYLCODE(uint8_t * Pjll = (uint8_t *) (PjpParent->jp_LIndex);) |
| 572 | |
| 573 | CHECKLEAFORDER; // indexes to be stored are sorted. |
| 574 | |
| 575 | #ifdef JUDYL |
| 576 | if ((PjvRaw = j__udyLAllocJV(pop1, Pjpm)) == (Pjv_t) NULL) |
| 577 | NOMEM; |
| 578 | (PjpParent->jp_Addr) = (Word_t) PjvRaw; |
| 579 | Pjv = P_JV(PjvRaw); |
| 580 | #endif |
| 581 | |
| 582 | switch (Level) |
| 583 | { |
| 584 | case 1: COPYTOLEAF_EVEN(Pjll, uint8_t); |
| 585 | SETIMMTYPE(cJU_JPIMMED_1_02); |
| 586 | break; |
| 587 | #if (defined(JUDY1) || defined(JU_64BIT)) |
| 588 | case 2: COPYTOLEAF_EVEN(Pjll, uint16_t); |
| 589 | SETIMMTYPE(cJU_JPIMMED_2_02); |
| 590 | break; |
| 591 | case 3: COPYTOLEAF_ODD(3, Pjll, JU_COPY3_LONG_TO_PINDEX); |
| 592 | SETIMMTYPE(cJU_JPIMMED_3_02); |
| 593 | break; |
| 594 | #endif |
| 595 | #if (defined(JUDY1) && defined(JU_64BIT)) |
| 596 | case 4: COPYTOLEAF_EVEN(Pjll, uint32_t); |
| 597 | SETIMMTYPE(cJ1_JPIMMED_4_02); |
| 598 | break; |
| 599 | case 5: COPYTOLEAF_ODD(5, Pjll, JU_COPY5_LONG_TO_PINDEX); |
| 600 | SETIMMTYPE(cJ1_JPIMMED_5_02); |
| 601 | break; |
| 602 | case 6: COPYTOLEAF_ODD(6, Pjll, JU_COPY6_LONG_TO_PINDEX); |
| 603 | SETIMMTYPE(cJ1_JPIMMED_6_02); |
| 604 | break; |
| 605 | case 7: COPYTOLEAF_ODD(7, Pjll, JU_COPY7_LONG_TO_PINDEX); |
| 606 | SETIMMTYPE(cJ1_JPIMMED_7_02); |
| 607 | break; |
| 608 | #endif |
| 609 | default: assert(FALSE); // should be impossible. |
| 610 | } |
| 611 | |
| 612 | return(TRUE); // note: no children => no *PPop1 mods. |
| 613 | |
| 614 | } // JPIMMED_*_02+ |
| 615 | |
| 616 | |
| 617 | // BUILD JPLEAF*: |
| 618 | // |
| 619 | // This code is a little tricky. The method is: For each level starting at |
| 620 | // the present Level down through levelsub = 1, and then as a special case for |
| 621 | // LeafB1 and FullPop (which are also at levelsub = 1 but have different |
| 622 | // capacity, see later), check if pop1 fits in a leaf (using leaf_maxpop1[]) |
| 623 | // at that level. If so, except for Level == levelsub, check if all of the |
| 624 | // current indexes to be stored are in the same (narrow) subexpanse, that is, |
| 625 | // the digits from Level to levelsub + 1, inclusive, are identical between the |
| 626 | // first and last index in the (sorted) list (in PIndex). If this condition is |
| 627 | // satisfied at any level, build a leaf at that level (under a narrow pointer |
| 628 | // if Level > levelsub). |
| 629 | // |
| 630 | // Note: Doing the search in this order results in storing the indexes in |
| 631 | // "least compressed form." |
| 632 | |
| 633 | for (levelsub = Level; levelsub >= 1; --levelsub) |
| 634 | { |
| 635 | Pjll_t PjllRaw; |
| 636 | Pjll_t Pjll; |
| 637 | |
| 638 | // Check if pop1 is too large to fit in a leaf at levelsub; if so, try the next |
| 639 | // lower level: |
| 640 | |
| 641 | if (pop1 > leaf_maxpop1[levelsub]) continue; |
| 642 | |
| 643 | // If pop1 fits in a leaf at levelsub, but levelsub is lower than Level, must |
| 644 | // also check whether all the indexes in the expanse to store can in fact be |
| 645 | // placed under a narrow pointer; if not, a leaf cannot be used, at this or any |
| 646 | // lower level (levelsub): |
| 647 | |
| 648 | if ((levelsub < Level) && (! SAMESUBEXP(levelsub))) |
| 649 | goto BuildBranch; // cant use a narrow, need a branch. |
| 650 | |
| 651 | // Ensure valid pop1 and all indexes are in fact common through Level: |
| 652 | |
| 653 | assert(pop1 <= cJU_POP0MASK(Level) + 1); |
| 654 | assert(! ((PIndex[0] ^ PIndex[pop1 - 1]) & cJU_DCDMASK(Level))); |
| 655 | |
| 656 | CHECKLEAFORDER; // indexes to be stored are sorted. |
| 657 | |
| 658 | // Build correct type of leaf: |
| 659 | // |
| 660 | // Note: The jp_DcdPopO and jp_Type assignments in MAKELEAF_* happen correctly |
| 661 | // for the levelsub (not Level) of the new leaf, even if its under a narrow |
| 662 | // pointer. |
| 663 | |
| 664 | switch (levelsub) |
| 665 | { |
| 666 | #if (defined(JUDYL) || (! defined(JU_64BIT))) |
| 667 | case 1: MAKELEAF_EVEN(1, cJU_JPLEAF1, j__udyAllocJLL1, |
| 668 | JL_LEAF1VALUEAREA, uint8_t); |
| 669 | break; |
| 670 | #endif |
| 671 | case 2: MAKELEAF_EVEN(2, cJU_JPLEAF2, j__udyAllocJLL2, |
| 672 | JL_LEAF2VALUEAREA, uint16_t); |
| 673 | break; |
| 674 | case 3: MAKELEAF_ODD( 3, cJU_JPLEAF3, j__udyAllocJLL3, |
| 675 | JL_LEAF3VALUEAREA, JU_COPY3_LONG_TO_PINDEX); |
| 676 | break; |
| 677 | #ifdef JU_64BIT |
| 678 | case 4: MAKELEAF_EVEN(4, cJU_JPLEAF4, j__udyAllocJLL4, |
| 679 | JL_LEAF4VALUEAREA, uint32_t); |
| 680 | break; |
| 681 | case 5: MAKELEAF_ODD( 5, cJU_JPLEAF5, j__udyAllocJLL5, |
| 682 | JL_LEAF5VALUEAREA, JU_COPY5_LONG_TO_PINDEX); |
| 683 | break; |
| 684 | case 6: MAKELEAF_ODD( 6, cJU_JPLEAF6, j__udyAllocJLL6, |
| 685 | JL_LEAF6VALUEAREA, JU_COPY6_LONG_TO_PINDEX); |
| 686 | break; |
| 687 | case 7: MAKELEAF_ODD( 7, cJU_JPLEAF7, j__udyAllocJLL7, |
| 688 | JL_LEAF7VALUEAREA, JU_COPY7_LONG_TO_PINDEX); |
| 689 | break; |
| 690 | #endif |
| 691 | default: assert(FALSE); // should be impossible. |
| 692 | } |
| 693 | |
| 694 | return(TRUE); // note: no children => no *PPop1 mods. |
| 695 | |
| 696 | } // JPLEAF* |
| 697 | |
| 698 | |
| 699 | // BUILD JPLEAF_B1 OR JPFULLPOPU1: |
| 700 | // |
| 701 | // See above about JPLEAF*. If pop1 doesnt fit in any level of linear leaf, |
| 702 | // it might still fit in a LeafB1 or FullPop, perhaps under a narrow pointer. |
| 703 | |
| 704 | if ((Level == 1) || SAMESUBEXP(1)) // same until last digit. |
| 705 | { |
| 706 | Pjlb_t PjlbRaw; // for bitmap leaf. |
| 707 | Pjlb_t Pjlb; |
| 708 | |
| 709 | assert(pop1 <= cJU_JPFULLPOPU1_POP0 + 1); |
| 710 | CHECKLEAFORDER; // indexes to be stored are sorted. |
| 711 | |
| 712 | #ifdef JUDY1 |
| 713 | |
| 714 | // JPFULLPOPU1: |
| 715 | |
| 716 | if (pop1 == cJU_JPFULLPOPU1_POP0 + 1) |
| 717 | { |
| 718 | Word_t Addr = PjpParent->jp_Addr; |
| 719 | Word_t DcdP0 = (*PIndex & cJU_DCDMASK(1)) |
| 720 | | cJU_JPFULLPOPU1_POP0; |
| 721 | JU_JPSETADT(PjpParent, Addr, DcdP0, cJ1_JPFULLPOPU1); |
| 722 | |
| 723 | return(TRUE); |
| 724 | } |
| 725 | #endif |
| 726 | |
| 727 | // JPLEAF_B1: |
| 728 | |
| 729 | if ((PjlbRaw = j__udyAllocJLB1(Pjpm)) == (Pjlb_t) NULL) |
| 730 | NOMEM; |
| 731 | Pjlb = P_JLB(PjlbRaw); |
| 732 | |
| 733 | for (offset = 0; offset < pop1; ++offset) |
| 734 | JU_BITMAPSETL(Pjlb, PIndex[offset]); |
| 735 | |
| 736 | retval = TRUE; // default. |
| 737 | |
| 738 | #ifdef JUDYL |
| 739 | |
| 740 | // Build subexpanse values-only leaves (LeafVs) under LeafB1: |
| 741 | |
| 742 | for (offset = 0; offset < cJU_NUMSUBEXPL; ++offset) |
| 743 | { |
| 744 | if (! (pop1sub = j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, offset)))) |
| 745 | continue; // skip empty subexpanse. |
| 746 | |
| 747 | // Allocate one LeafV = JP subarray; if out of memory, clear bitmaps for higher |
| 748 | // subexpanses and adjust *PPop1: |
| 749 | |
| 750 | if ((PjvRaw = j__udyLAllocJV(pop1sub, Pjpm)) |
| 751 | == (Pjv_t) NULL) |
| 752 | { |
| 753 | for (/* null */; offset < cJU_NUMSUBEXPL; ++offset) |
| 754 | { |
| 755 | *PPop1 -= j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, offset)); |
| 756 | JU_JLB_BITMAP(Pjlb, offset) = 0; |
| 757 | } |
| 758 | |
| 759 | retval = FALSE; |
| 760 | break; |
| 761 | } |
| 762 | |
| 763 | // Populate values-only leaf and save the pointer to it: |
| 764 | |
| 765 | Pjv = P_JV(PjvRaw); |
| 766 | JU_COPYMEM(Pjv, PValue, pop1sub); |
| 767 | JL_JLB_PVALUE(Pjlb, offset) = PjvRaw; // first-tier pointer. |
| 768 | PValue += pop1sub; |
| 769 | |
| 770 | } // for each subexpanse |
| 771 | |
| 772 | #endif // JUDYL |
| 773 | |
| 774 | // Attach new LeafB1 to parent JP; note use of *PPop1 possibly < pop1: |
| 775 | |
| 776 | JU_JPSETADT(PjpParent, (Word_t) PjlbRaw, |
| 777 | (*PIndex & cJU_DCDMASK(1)) | (*PPop1 - 1), cJU_JPLEAF_B1); |
| 778 | |
| 779 | return(retval); |
| 780 | |
| 781 | } // JPLEAF_B1 or JPFULLPOPU1 |
| 782 | |
| 783 | |
| 784 | // BUILD JPBRANCH_U*: |
| 785 | // |
| 786 | // Arriving at BuildBranch means Level < top level but the pop1 is too large |
| 787 | // for immediate indexes or a leaf, even under a narrow pointer, including a |
| 788 | // LeafB1 or FullPop at level 1. This implies SAMESUBEXP(1) == FALSE, that is, |
| 789 | // the indexes to be stored "branch" at level 2 or higher. |
| 790 | |
| 791 | BuildBranch: // come here directly if a leaf wont work. |
| 792 | |
| 793 | assert(Level >= 2); |
| 794 | assert(Level < cJU_ROOTSTATE); |
| 795 | assert(! SAMESUBEXP(1)); // sanity check, see above. |
| 796 | |
| 797 | // Determine the appropriate level for a new branch node; see if a narrow |
| 798 | // pointer can be used: |
| 799 | // |
| 800 | // This can be confusing. The branch is required at the lowest level L where |
| 801 | // the indexes to store are not in the same subexpanse at level L-1. Work down |
| 802 | // from Level to tree level 3, which is 1 above the lowest tree level = 2 at |
| 803 | // which a branch can be used. Theres no need to check SAMESUBEXP at level 2 |
| 804 | // because its known to be false at level 2-1 = 1. |
| 805 | // |
| 806 | // Note: Unlike for a leaf node, a narrow pointer is always used for a branch |
| 807 | // if possible, that is, maximum compression is always used, except at the top |
| 808 | // level of the tree, where a JPM cannot support a narrow pointer, meaning a |
| 809 | // top BranchL can have a single JP (fanout = 1); but that case jumps directly |
| 810 | // to BuildBranch2. |
| 811 | // |
| 812 | // Note: For 32-bit systems the only usable values for a narrow pointer are |
| 813 | // Level = 3 and levelsub = 2; 64-bit systems have many more choices; but |
| 814 | // hopefully this for-loop is fast enough even on a 32-bit system. |
| 815 | // |
| 816 | // TBD: If not fast enough, #ifdef JU_64BIT and handle the 32-bit case faster. |
| 817 | |
| 818 | for (levelsub = Level; levelsub >= 3; --levelsub) // see above. |
| 819 | if (! SAMESUBEXP(levelsub - 1)) // at limit of narrow pointer. |
| 820 | break; // put branch at levelsub. |
| 821 | |
| 822 | BuildBranch2: // come here directly for Level = levelsub = cJU_ROOTSTATE. |
| 823 | |
| 824 | assert(levelsub >= 2); |
| 825 | assert(levelsub <= Level); |
| 826 | |
| 827 | // Initially build a BranchU: |
| 828 | // |
| 829 | // Always start with a BranchU because the number of populated subexpanses is |
| 830 | // not yet known. Use digitmask, digitshifted, and digitshincr to avoid |
| 831 | // expensive variable shifts within JU_DIGITATSTATE within the loop. |
| 832 | // |
| 833 | // TBD: The use of digitmask, etc. results in more increment operations per |
| 834 | // loop, is there an even faster way? |
| 835 | // |
| 836 | // TBD: Would it pay to pre-count the populated JPs (subexpanses) and |
| 837 | // pre-compress the branch, that is, build a BranchL or BranchB immediately, |
| 838 | // also taking account of opportunistic uncompression rules? Probably not |
| 839 | // because at high levels of the tree there might be huge numbers of indexes |
| 840 | // (hence cache lines) to scan in the PIndex array to determine the fanout |
| 841 | // (number of JPs) needed. |
| 842 | |
| 843 | if ((PjbuRaw = j__udyAllocJBU(Pjpm)) == (Pjbu_t) NULL) NOMEM; |
| 844 | Pjbu = P_JBU(PjbuRaw); |
| 845 | |
| 846 | JPtype_null = cJU_JPNULL1 + levelsub - 2; // in new BranchU. |
| 847 | JU_JPSETADT(&JPnull, 0, 0, JPtype_null); |
| 848 | |
| 849 | Pjp = Pjbu->jbu_jp; // for convenience in loop. |
| 850 | numJPs = 0; // non-null in the BranchU. |
| 851 | digitmask = cJU_MASKATSTATE(levelsub); // see above. |
| 852 | digitshincr = 1UL << (cJU_BITSPERBYTE * (levelsub - 1)); |
| 853 | retval = TRUE; |
| 854 | |
| 855 | // Scan and populate JPs (subexpanses): |
| 856 | // |
| 857 | // Look for all indexes matching each digit in the BranchU (at the correct |
| 858 | // levelsub), and meanwhile notice any sorting error. Increment PIndex (and |
| 859 | // PValue) and reduce pop1 for each subexpanse handled successfully. |
| 860 | |
| 861 | for (digit = digitshifted = 0; |
| 862 | digit < cJU_BRANCHUNUMJPS; |
| 863 | ++digit, digitshifted += digitshincr, ++Pjp) |
| 864 | { |
| 865 | DBGCODE(Word_t pop1subprev;) |
| 866 | assert(pop1 != 0); // end of indexes is handled elsewhere. |
| 867 | |
| 868 | // Count indexes in digits subexpanse: |
| 869 | |
| 870 | for (pop1sub = 0; pop1sub < pop1; ++pop1sub) |
| 871 | if (digitshifted != (PIndex[pop1sub] & digitmask)) break; |
| 872 | |
| 873 | // Empty subexpanse (typical, performance path) or sorting error (rare): |
| 874 | |
| 875 | if (pop1sub == 0) |
| 876 | { |
| 877 | if (digitshifted < (PIndex[0] & digitmask)) |
| 878 | { SETJPNULL(Pjp); continue; } // empty subexpanse. |
| 879 | |
| 880 | assert(pop1 < *PPop1); // did save >= 1 index and decr pop1. |
| 881 | JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_UNSORTED); |
| 882 | goto AbandonBranch; |
| 883 | } |
| 884 | |
| 885 | // Non-empty subexpanse: |
| 886 | // |
| 887 | // First shortcut by handling pop1sub == 1 (JPIMMED_*_01) inline locally. |
| 888 | |
| 889 | if (pop1sub == 1) // note: can be at root level. |
| 890 | { |
| 891 | Word_t Addr = 0; |
| 892 | JUDYLCODE(Addr = (Word_t) (*PValue++);) |
| 893 | JU_JPSETADT(Pjp, Addr, *PIndex, cJU_JPIMMED_1_01 + levelsub -2); |
| 894 | |
| 895 | ++numJPs; |
| 896 | |
| 897 | if (--pop1) { ++PIndex; continue; } // more indexes to store. |
| 898 | |
| 899 | ++digit; ++Pjp; // skip JP just saved. |
| 900 | goto ClearBranch; // save time. |
| 901 | } |
| 902 | |
| 903 | // Recurse to populate one digits (subexpanses) JP; if successful, skip |
| 904 | // indexes (and values) just stored (performance path), except when expanse is |
| 905 | // completely stored: |
| 906 | |
| 907 | DBGCODE(pop1subprev = pop1sub;) |
| 908 | |
| 909 | if (j__udyInsArray(Pjp, levelsub - 1, &pop1sub, (PWord_t) PIndex, |
| 910 | #ifdef JUDYL |
| 911 | (Pjv_t) PValue, |
| 912 | #endif |
| 913 | Pjpm)) |
| 914 | { // complete success. |
| 915 | ++numJPs; |
| 916 | assert(pop1subprev == pop1sub); |
| 917 | assert(pop1 >= pop1sub); |
| 918 | |
| 919 | if ((pop1 -= pop1sub) != 0) // more indexes to store: |
| 920 | { |
| 921 | PIndex += pop1sub; // skip indexes just stored. |
| 922 | JUDYLCODE(PValue += pop1sub;) |
| 923 | continue; |
| 924 | } |
| 925 | // else leave PIndex in BranchUs expanse. |
| 926 | |
| 927 | // No more indexes to store in BranchUs expanse: |
| 928 | |
| 929 | ++digit; ++Pjp; // skip JP just saved. |
| 930 | goto ClearBranch; // save time. |
| 931 | } |
| 932 | |
| 933 | // Handle any error at a lower level of recursion: |
| 934 | // |
| 935 | // In case of partial success, pop1sub != 0, but it was reduced from the value |
| 936 | // passed to j__udyInsArray(); skip this JP later during ClearBranch. |
| 937 | |
| 938 | assert(pop1subprev > pop1sub); // check j__udyInsArray(). |
| 939 | assert(pop1 > pop1sub); // check j__udyInsArray(). |
| 940 | |
| 941 | if (pop1sub) // partial success. |
| 942 | { ++digit; ++Pjp; ++numJPs; } // skip JP just saved. |
| 943 | |
| 944 | pop1 -= pop1sub; // deduct saved indexes if any. |
| 945 | |
| 946 | // Same-level sorting error, or any lower-level error; abandon the rest of the |
| 947 | // branch: |
| 948 | // |
| 949 | // Arrive here with pop1 = remaining unsaved indexes (always non-zero). Adjust |
| 950 | // the *PPop1 value to record and return, modify retval, and use ClearBranch to |
| 951 | // finish up. |
| 952 | |
| 953 | AbandonBranch: |
| 954 | assert(pop1 != 0); // more to store, see above. |
| 955 | assert(pop1 <= *PPop1); // sanity check. |
| 956 | |
| 957 | *PPop1 -= pop1; // deduct unsaved indexes. |
| 958 | pop1 = 0; // to avoid error later. |
| 959 | retval = FALSE; |
| 960 | |
| 961 | // Error (rare), or end of indexes while traversing new BranchU (performance |
| 962 | // path); either way, mark the remaining JPs, if any, in the BranchU as nulls |
| 963 | // and exit the loop: |
| 964 | // |
| 965 | // Arrive here with digit and Pjp set to the first JP to set to null. |
| 966 | |
| 967 | ClearBranch: |
| 968 | for (/* null */; digit < cJU_BRANCHUNUMJPS; ++digit, ++Pjp) |
| 969 | SETJPNULL(Pjp); |
| 970 | break; // saves one more compare. |
| 971 | |
| 972 | } // for each digit |
| 973 | |
| 974 | |
| 975 | // FINISH JPBRANCH_U*: |
| 976 | // |
| 977 | // Arrive here with a BranchU built under Pjbu, numJPs set, and either: retval |
| 978 | // == TRUE and *PPop1 unmodified, or else retval == FALSE, *PPop1 set to the |
| 979 | // actual number of indexes saved (possibly 0 for complete failure at a lower |
| 980 | // level upon the first call of j__udyInsArray()), and the Judy error set in |
| 981 | // Pjpm. Either way, PIndex points to an index within the expanse just |
| 982 | // handled. |
| 983 | |
| 984 | Pjbany = (Word_t) PjbuRaw; // default = use this BranchU. |
| 985 | JPtype = branchU_JPtype[levelsub]; |
| 986 | |
| 987 | // Check for complete failure above: |
| 988 | |
| 989 | assert((! retval) || *PPop1); // sanity check. |
| 990 | |
| 991 | if ((! retval) && (*PPop1 == 0)) // nothing stored, full failure. |
| 992 | { |
| 993 | j__udyFreeJBU(PjbuRaw, Pjpm); |
| 994 | SETJPNULL_PARENT; |
| 995 | return(FALSE); |
| 996 | } |
| 997 | |
| 998 | // Complete or partial success so far; watch for sorting error after the |
| 999 | // maximum digit (255) in the BranchU, which is indicated by having more |
| 1000 | // indexes to store in the BranchUs expanse: |
| 1001 | // |
| 1002 | // For example, if an index to store has a digit of 255 at levelsub, followed |
| 1003 | // by an index with a digit of 254, the for-loop above runs out of digits |
| 1004 | // without reducing pop1 to 0. |
| 1005 | |
| 1006 | if (pop1 != 0) |
| 1007 | { |
| 1008 | JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_UNSORTED); |
| 1009 | *PPop1 -= pop1; // deduct unsaved indexes. |
| 1010 | retval = FALSE; |
| 1011 | } |
| 1012 | assert(*PPop1 != 0); // branch (still) cannot be empty. |
| 1013 | |
| 1014 | |
| 1015 | // OPTIONALLY COMPRESS JPBRANCH_U*: |
| 1016 | // |
| 1017 | // See if the BranchU should be compressed to a BranchL or BranchB; if so, do |
| 1018 | // that and free the BranchU; otherwise just use the existing BranchU. Follow |
| 1019 | // the same rules as in JudyIns.c (version 4.95): Only check local population |
| 1020 | // (cJU_OPP_UNCOMP_POP0) for BranchL, and only check global memory efficiency |
| 1021 | // (JU_OPP_UNCOMPRESS) for BranchB. TBD: Have the rules changed? |
| 1022 | // |
| 1023 | // Note: Because of differing order of operations, the latter compression |
| 1024 | // might not result in the same set of branch nodes as a series of sequential |
| 1025 | // insertions. |
| 1026 | // |
| 1027 | // Note: Allocating a BranchU only to sometimes convert it to a BranchL or |
| 1028 | // BranchB is unfortunate, but attempting to work with a temporary BranchU on |
| 1029 | // the stack and then allocate and keep it as a BranchU in many cases is worse |
| 1030 | // in terms of error handling. |
| 1031 | |
| 1032 | |
| 1033 | // COMPRESS JPBRANCH_U* TO JPBRANCH_L*: |
| 1034 | |
| 1035 | if (numJPs <= cJU_BRANCHLMAXJPS) // JPs fit in a BranchL. |
| 1036 | { |
| 1037 | Pjbl_t PjblRaw = (Pjbl_t) NULL; // new BranchL; init for cc. |
| 1038 | Pjbl_t Pjbl; |
| 1039 | |
| 1040 | if ((*PPop1 > JU_BRANCHL_MAX_POP) // pop too high. |
| 1041 | || ((PjblRaw = j__udyAllocJBL(Pjpm)) == (Pjbl_t) NULL)) |
| 1042 | { // cant alloc BranchL. |
| 1043 | goto SetParent; // just keep BranchU. |
| 1044 | } |
| 1045 | |
| 1046 | Pjbl = P_JBL(PjblRaw); |
| 1047 | |
| 1048 | // Copy BranchU JPs to BranchL: |
| 1049 | |
| 1050 | (Pjbl->jbl_NumJPs) = numJPs; |
| 1051 | offset = 0; |
| 1052 | |
| 1053 | for (digit = 0; digit < cJU_BRANCHUNUMJPS; ++digit) |
| 1054 | { |
| 1055 | if ((((Pjbu->jbu_jp) + digit)->jp_Type) == JPtype_null) |
| 1056 | continue; |
| 1057 | |
| 1058 | (Pjbl->jbl_Expanse[offset ]) = digit; |
| 1059 | (Pjbl->jbl_jp [offset++]) = Pjbu->jbu_jp[digit]; |
| 1060 | } |
| 1061 | assert(offset == numJPs); // found same number. |
| 1062 | |
| 1063 | // Free the BranchU and prepare to use the new BranchL instead: |
| 1064 | |
| 1065 | j__udyFreeJBU(PjbuRaw, Pjpm); |
| 1066 | |
| 1067 | Pjbany = (Word_t) PjblRaw; |
| 1068 | JPtype = branchL_JPtype[levelsub]; |
| 1069 | |
| 1070 | } // compress to BranchL |
| 1071 | |
| 1072 | |
| 1073 | // COMPRESS JPBRANCH_U* TO JPBRANCH_B*: |
| 1074 | // |
| 1075 | // If unable to allocate the BranchB or any JP subarray, free all related |
| 1076 | // memory and just keep the BranchU. |
| 1077 | // |
| 1078 | // Note: This use of JU_OPP_UNCOMPRESS is a bit conservative because the |
| 1079 | // BranchU is already allocated while the (presumably smaller) BranchB is not, |
| 1080 | // the opposite of how its used in single-insert code. |
| 1081 | |
| 1082 | else |
| 1083 | { |
| 1084 | Pjbb_t PjbbRaw = (Pjbb_t) NULL; // new BranchB; init for cc. |
| 1085 | Pjbb_t Pjbb; |
| 1086 | Pjp_t Pjp2; // in BranchU. |
| 1087 | |
| 1088 | if ((*PPop1 > JU_BRANCHB_MAX_POP) // pop too high. |
| 1089 | || ((PjbbRaw = j__udyAllocJBB(Pjpm)) == (Pjbb_t) NULL)) |
| 1090 | { // cant alloc BranchB. |
| 1091 | goto SetParent; // just keep BranchU. |
| 1092 | } |
| 1093 | |
| 1094 | Pjbb = P_JBB(PjbbRaw); |
| 1095 | |
| 1096 | // Set bits in bitmap for populated subexpanses: |
| 1097 | |
| 1098 | Pjp2 = Pjbu->jbu_jp; |
| 1099 | |
| 1100 | for (digit = 0; digit < cJU_BRANCHUNUMJPS; ++digit) |
| 1101 | if ((((Pjbu->jbu_jp) + digit)->jp_Type) != JPtype_null) |
| 1102 | JU_BITMAPSETB(Pjbb, digit); |
| 1103 | |
| 1104 | // Copy non-null JPs to BranchB JP subarrays: |
| 1105 | |
| 1106 | for (offset = 0; offset < cJU_NUMSUBEXPB; ++offset) |
| 1107 | { |
| 1108 | Pjp_t PjparrayRaw; |
| 1109 | Pjp_t Pjparray; |
| 1110 | |
| 1111 | if (! (numJPs = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, offset)))) |
| 1112 | continue; // skip empty subexpanse. |
| 1113 | |
| 1114 | // If unable to allocate a JP subarray, free all BranchB memory so far and |
| 1115 | // continue to use the BranchU: |
| 1116 | |
| 1117 | if ((PjparrayRaw = j__udyAllocJBBJP(numJPs, Pjpm)) |
| 1118 | == (Pjp_t) NULL) |
| 1119 | { |
| 1120 | while (offset-- > 0) |
| 1121 | { |
| 1122 | if (JU_JBB_PJP(Pjbb, offset) == (Pjp_t) NULL) continue; |
| 1123 | |
| 1124 | j__udyFreeJBBJP(JU_JBB_PJP(Pjbb, offset), |
| 1125 | j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, offset)), |
| 1126 | Pjpm); |
| 1127 | } |
| 1128 | j__udyFreeJBB(PjbbRaw, Pjpm); |
| 1129 | goto SetParent; // keep BranchU. |
| 1130 | } |
| 1131 | |
| 1132 | // Set one JP subarray pointer and copy the subexpanses JPs to the subarray: |
| 1133 | // |
| 1134 | // Scan the BranchU for non-null JPs until numJPs JPs are copied. |
| 1135 | |
| 1136 | JU_JBB_PJP(Pjbb, offset) = PjparrayRaw; |
| 1137 | Pjparray = P_JP(PjparrayRaw); |
| 1138 | |
| 1139 | while (numJPs-- > 0) |
| 1140 | { |
| 1141 | while ((Pjp2->jp_Type) == JPtype_null) |
| 1142 | { |
| 1143 | ++Pjp2; |
| 1144 | assert(Pjp2 < (Pjbu->jbu_jp) + cJU_BRANCHUNUMJPS); |
| 1145 | } |
| 1146 | *Pjparray++ = *Pjp2++; |
| 1147 | } |
| 1148 | } // for each subexpanse |
| 1149 | |
| 1150 | // Free the BranchU and prepare to use the new BranchB instead: |
| 1151 | |
| 1152 | j__udyFreeJBU(PjbuRaw, Pjpm); |
| 1153 | |
| 1154 | Pjbany = (Word_t) PjbbRaw; |
| 1155 | JPtype = branchB_JPtype[levelsub]; |
| 1156 | |
| 1157 | } // compress to BranchB |
| 1158 | |
| 1159 | |
| 1160 | // COMPLETE OR PARTIAL SUCCESS: |
| 1161 | // |
| 1162 | // Attach new branch (under Pjp, with JPtype) to parent JP; note use of *PPop1, |
| 1163 | // possibly reduced due to partial failure. |
| 1164 | |
| 1165 | SetParent: |
| 1166 | (PjpParent->jp_Addr) = Pjbany; |
| 1167 | (PjpParent->jp_Type) = JPtype; |
| 1168 | |
| 1169 | if (Level < cJU_ROOTSTATE) // PjpParent not in JPM: |
| 1170 | { |
| 1171 | Word_t DcdP0 = (*PIndex & cJU_DCDMASK(levelsub)) | (*PPop1 - 1); |
| 1172 | |
| 1173 | JU_JPSETADT(PjpParent ,Pjbany, DcdP0, JPtype); |
| 1174 | } |
| 1175 | |
| 1176 | return(retval); |
| 1177 | |
| 1178 | } // j__udyInsArray() |