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