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 #ifdef JUDY1
19 #include "Judy1.h"
20 #else
21 #include "JudyL.h"
22 #endif
23
24 #include "JudyPrivate1L.h"
25
26 extern int j__udyCreateBranchL(Pjp_t, Pjp_t, uint8_t *, Word_t, Pvoid_t);
27 extern int j__udyCreateBranchB(Pjp_t, Pjp_t, uint8_t *, Word_t, Pvoid_t);
28
29 DBGCODE(extern void JudyCheckSorted(Pjll_t Pjll, Word_t Pop1, long IndexSize);)
30
31 static const jbb_t StageJBBZero; // zeroed versions of namesake struct.
32
33 // TBD: There are multiple copies of (some of) these CopyWto3, Copy3toW,
34 // CopyWto7 and Copy7toW functions in Judy1Cascade.c, JudyLCascade.c, and
35 // JudyDecascade.c. These static functions should probably be moved to a
36 // common place, made macros, or something to avoid having four copies.
37
38
39 // ****************************************************************************
40 // __ J U D Y C O P Y X T O W
41
42
j__udyCopy3toW(PWord_t PDest,uint8_t * PSrc,Word_t LeafIndexes)43 FUNCTION static void j__udyCopy3toW(
44 PWord_t PDest,
45 uint8_t * PSrc,
46 Word_t LeafIndexes)
47 {
48 do
49 {
50 JU_COPY3_PINDEX_TO_LONG(*PDest, PSrc);
51 PSrc += 3;
52 PDest += 1;
53
54 } while(--LeafIndexes);
55
56 } //j__udyCopy3toW()
57
58
59 #ifdef JU_64BIT
60
j__udyCopy4toW(PWord_t PDest,uint32_t * PSrc,Word_t LeafIndexes)61 FUNCTION static void j__udyCopy4toW(
62 PWord_t PDest,
63 uint32_t * PSrc,
64 Word_t LeafIndexes)
65 {
66 do { *PDest++ = *PSrc++;
67 } while(--LeafIndexes);
68
69 } // j__udyCopy4toW()
70
71
j__udyCopy5toW(PWord_t PDest,uint8_t * PSrc,Word_t LeafIndexes)72 FUNCTION static void j__udyCopy5toW(
73 PWord_t PDest,
74 uint8_t * PSrc,
75 Word_t LeafIndexes)
76 {
77 do
78 {
79 JU_COPY5_PINDEX_TO_LONG(*PDest, PSrc);
80 PSrc += 5;
81 PDest += 1;
82
83 } while(--LeafIndexes);
84
85 } // j__udyCopy5toW()
86
87
j__udyCopy6toW(PWord_t PDest,uint8_t * PSrc,Word_t LeafIndexes)88 FUNCTION static void j__udyCopy6toW(
89 PWord_t PDest,
90 uint8_t * PSrc,
91 Word_t LeafIndexes)
92 {
93 do
94 {
95 JU_COPY6_PINDEX_TO_LONG(*PDest, PSrc);
96 PSrc += 6;
97 PDest += 1;
98
99 } while(--LeafIndexes);
100
101 } // j__udyCopy6toW()
102
103
j__udyCopy7toW(PWord_t PDest,uint8_t * PSrc,Word_t LeafIndexes)104 FUNCTION static void j__udyCopy7toW(
105 PWord_t PDest,
106 uint8_t * PSrc,
107 Word_t LeafIndexes)
108 {
109 do
110 {
111 JU_COPY7_PINDEX_TO_LONG(*PDest, PSrc);
112 PSrc += 7;
113 PDest += 1;
114
115 } while(--LeafIndexes);
116
117 } // j__udyCopy7toW()
118
119 #endif // JU_64BIT
120
121
122 // ****************************************************************************
123 // __ J U D Y C O P Y W T O X
124
125
j__udyCopyWto3(uint8_t * PDest,PWord_t PSrc,Word_t LeafIndexes)126 FUNCTION static void j__udyCopyWto3(
127 uint8_t * PDest,
128 PWord_t PSrc,
129 Word_t LeafIndexes)
130 {
131 do
132 {
133 JU_COPY3_LONG_TO_PINDEX(PDest, *PSrc);
134 PSrc += 1;
135 PDest += 3;
136
137 } while(--LeafIndexes);
138
139 } // j__udyCopyWto3()
140
141
142 #ifdef JU_64BIT
143
j__udyCopyWto4(uint8_t * PDest,PWord_t PSrc,Word_t LeafIndexes)144 FUNCTION static void j__udyCopyWto4(
145 uint8_t * PDest,
146 PWord_t PSrc,
147 Word_t LeafIndexes)
148 {
149 uint32_t *PDest32 = (uint32_t *)PDest;
150
151 do
152 {
153 *PDest32 = *PSrc;
154 PSrc += 1;
155 PDest32 += 1;
156 } while(--LeafIndexes);
157
158 } // j__udyCopyWto4()
159
160
j__udyCopyWto5(uint8_t * PDest,PWord_t PSrc,Word_t LeafIndexes)161 FUNCTION static void j__udyCopyWto5(
162 uint8_t * PDest,
163 PWord_t PSrc,
164 Word_t LeafIndexes)
165 {
166 do
167 {
168 JU_COPY5_LONG_TO_PINDEX(PDest, *PSrc);
169 PSrc += 1;
170 PDest += 5;
171
172 } while(--LeafIndexes);
173
174 } // j__udyCopyWto5()
175
176
j__udyCopyWto6(uint8_t * PDest,PWord_t PSrc,Word_t LeafIndexes)177 FUNCTION static void j__udyCopyWto6(
178 uint8_t * PDest,
179 PWord_t PSrc,
180 Word_t LeafIndexes)
181 {
182 do
183 {
184 JU_COPY6_LONG_TO_PINDEX(PDest, *PSrc);
185 PSrc += 1;
186 PDest += 6;
187
188 } while(--LeafIndexes);
189
190 } // j__udyCopyWto6()
191
192
j__udyCopyWto7(uint8_t * PDest,PWord_t PSrc,Word_t LeafIndexes)193 FUNCTION static void j__udyCopyWto7(
194 uint8_t * PDest,
195 PWord_t PSrc,
196 Word_t LeafIndexes)
197 {
198 do
199 {
200 JU_COPY7_LONG_TO_PINDEX(PDest, *PSrc);
201 PSrc += 1;
202 PDest += 7;
203
204 } while(--LeafIndexes);
205
206 } // j__udyCopyWto7()
207
208 #endif // JU_64BIT
209
210
211 // ****************************************************************************
212 // COMMON CODE (MACROS):
213 //
214 // Free objects in an array of valid JPs, StageJP[ExpCnt] == last one may
215 // include Immeds, which are ignored.
216
217 #define FREEALLEXIT(ExpCnt,StageJP,Pjpm) \
218 { \
219 Word_t _expct = (ExpCnt); \
220 while (_expct--) j__udyFreeSM(&((StageJP)[_expct]), Pjpm); \
221 return(-1); \
222 }
223
224 // Clear the array that keeps track of the number of JPs in a subexpanse:
225
226 #define ZEROJP(SubJPCount) \
227 { \
228 int ii; \
229 for (ii = 0; ii < cJU_NUMSUBEXPB; ii++) (SubJPCount[ii]) = 0; \
230 }
231
232 // ****************************************************************************
233 // __ J U D Y S T A G E J B B T O J B B
234 //
235 // Create a mallocd BranchB (jbb_t) from a staged BranchB while "splaying" a
236 // single old leaf. Return -1 if out of memory, otherwise 1.
237
j__udyStageJBBtoJBB(Pjp_t PjpLeaf,Pjbb_t PStageJBB,Pjp_t PjpArray,uint8_t * PSubCount,Pjpm_t Pjpm)238 static int j__udyStageJBBtoJBB(
239 Pjp_t PjpLeaf, // JP of leaf being splayed.
240 Pjbb_t PStageJBB, // temp jbb_t on stack.
241 Pjp_t PjpArray, // array of JPs to splayed new leaves.
242 uint8_t * PSubCount, // count of JPs for each subexpanse.
243 Pjpm_t Pjpm) // the jpm_t for JudyAlloc*().
244 {
245 Pjbb_t PjbbRaw; // pointer to new bitmap branch.
246 Pjbb_t Pjbb;
247 Word_t subexp;
248
249 // Get memory for new BranchB:
250
251 if ((PjbbRaw = j__udyAllocJBB(Pjpm)) == (Pjbb_t) NULL) return(-1);
252 Pjbb = P_JBB(PjbbRaw);
253
254 // Copy staged BranchB into just-allocated BranchB:
255
256 *Pjbb = *PStageJBB;
257
258 // Allocate the JP subarrays (BJP) for the new BranchB:
259
260 for (subexp = 0; subexp < cJU_NUMSUBEXPB; subexp++)
261 {
262 Pjp_t PjpRaw;
263 Pjp_t Pjp;
264 Word_t NumJP; // number of JPs in each subexpanse.
265
266 if ((NumJP = PSubCount[subexp]) == 0) continue; // empty.
267
268 // Out of memory, back out previous allocations:
269
270 if ((PjpRaw = j__udyAllocJBBJP(NumJP, Pjpm)) == (Pjp_t) NULL)
271 {
272 while(subexp--)
273 {
274 if ((NumJP = PSubCount[subexp]) == 0) continue;
275
276 PjpRaw = JU_JBB_PJP(Pjbb, subexp);
277 j__udyFreeJBBJP(PjpRaw, NumJP, Pjpm);
278 }
279 j__udyFreeJBB(PjbbRaw, Pjpm);
280 return(-1); // out of memory.
281 }
282 Pjp = P_JP(PjpRaw);
283
284 // Place the JP subarray pointer in the new BranchB, copy subarray JPs, and
285 // advance to the next subexpanse:
286
287 JU_JBB_PJP(Pjbb, subexp) = PjpRaw;
288 JU_COPYMEM(Pjp, PjpArray, NumJP);
289 PjpArray += NumJP;
290
291 } // for each subexpanse.
292
293 // Change the PjpLeaf from Leaf to BranchB:
294
295 PjpLeaf->jp_Addr = (Word_t) PjbbRaw;
296 PjpLeaf->jp_Type += cJU_JPBRANCH_B2 - cJU_JPLEAF2; // Leaf to BranchB.
297
298 return(1);
299
300 } // j__udyStageJBBtoJBB()
301
302
303 // ****************************************************************************
304 // __ J U D Y J L L 2 T O J L B 1
305 //
306 // Create a LeafB1 (jlb_t = JLB1) from a Leaf2 (2-byte Indexes and for JudyL,
307 // Word_t Values). Return NULL if out of memory, else a pointer to the new
308 // LeafB1.
309 //
310 // NOTE: Caller must release the Leaf2 that was passed in.
311
j__udyJLL2toJLB1(uint16_t * Pjll,Pjv_t Pjv,Word_t LeafPop1,Pvoid_t Pjpm)312 FUNCTION static Pjlb_t j__udyJLL2toJLB1(
313 uint16_t * Pjll, // array of 16-bit indexes.
314 #ifdef JUDYL
315 Pjv_t Pjv, // array of associated values.
316 #endif
317 Word_t LeafPop1, // number of indexes/values.
318 Pvoid_t Pjpm) // jpm_t for JudyAlloc*()/JudyFree*().
319 {
320 Pjlb_t PjlbRaw;
321 Pjlb_t Pjlb;
322 int offset;
323 JUDYLCODE(int subexp;)
324
325 // Allocate the LeafB1:
326
327 if ((PjlbRaw = j__udyAllocJLB1(Pjpm)) == (Pjlb_t) NULL)
328 return((Pjlb_t) NULL);
329 Pjlb = P_JLB(PjlbRaw);
330
331 // Copy Leaf2 indexes to LeafB1:
332
333 for (offset = 0; offset < LeafPop1; ++offset)
334 JU_BITMAPSETL(Pjlb, Pjll[offset]);
335
336 #ifdef JUDYL
337
338 // Build LeafVs from bitmap:
339
340 for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp)
341 {
342 struct _POINTER_VALUES
343 {
344 Word_t pv_Pop1; // size of value area.
345 Pjv_t pv_Pjv; // raw pointer to value area.
346 } pv[cJU_NUMSUBEXPL];
347
348 // Get the population of the subexpanse, and if any, allocate a LeafV:
349
350 pv[subexp].pv_Pop1 = j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp));
351
352 if (pv[subexp].pv_Pop1)
353 {
354 Pjv_t Pjvnew;
355
356 // TBD: There is an opportunity to put pop == 1 value in pointer:
357
358 pv[subexp].pv_Pjv = j__udyLAllocJV(pv[subexp].pv_Pop1, Pjpm);
359
360 // Upon out of memory, free all previously allocated:
361
362 if (pv[subexp].pv_Pjv == (Pjv_t) NULL)
363 {
364 while(subexp--)
365 {
366 if (pv[subexp].pv_Pop1)
367 {
368 j__udyLFreeJV(pv[subexp].pv_Pjv, pv[subexp].pv_Pop1,
369 Pjpm);
370 }
371 }
372 j__udyFreeJLB1(PjlbRaw, Pjpm);
373 return((Pjlb_t) NULL);
374 }
375
376 Pjvnew = P_JV(pv[subexp].pv_Pjv);
377 JU_COPYMEM(Pjvnew, Pjv, pv[subexp].pv_Pop1);
378 Pjv += pv[subexp].pv_Pop1; // advance value pointer.
379
380 // Place raw pointer to value array in bitmap subexpanse:
381
382 JL_JLB_PVALUE(Pjlb, subexp) = pv[subexp].pv_Pjv;
383
384 } // populated subexpanse.
385 } // each subexpanse.
386
387 #endif // JUDYL
388
389 return(PjlbRaw); // pointer to LeafB1.
390
391 } // j__udyJLL2toJLB1()
392
393
394 // ****************************************************************************
395 // __ J U D Y C A S C A D E 1
396 //
397 // Create bitmap leaf from 1-byte Indexes and Word_t Values.
398 //
399 // TBD: There must be a better way.
400 //
401 // Only for JudyL 32 bit: (note, unifdef disallows comment on next line)
402
403 #if (defined(JUDYL) || (! defined(JU_64BIT)))
404
j__udyCascade1(Pjp_t Pjp,Pvoid_t Pjpm)405 FUNCTION int j__udyCascade1(
406 Pjp_t Pjp,
407 Pvoid_t Pjpm)
408 {
409 Word_t DcdP0;
410 uint8_t * PLeaf;
411 Pjlb_t PjlbRaw;
412 Pjlb_t Pjlb;
413 Word_t Pop1;
414 Word_t ii; // temp for loop counter
415 JUDYLCODE(Pjv_t Pjv;)
416
417 assert(JU_JPTYPE(Pjp) == cJU_JPLEAF1);
418 assert((JU_JPDCDPOP0(Pjp) & 0xFF) == (cJU_LEAF1_MAXPOP1-1));
419
420 PjlbRaw = j__udyAllocJLB1(Pjpm);
421 if (PjlbRaw == (Pjlb_t) NULL) return(-1);
422
423 Pjlb = P_JLB(PjlbRaw);
424 PLeaf = (uint8_t *) P_JLL(Pjp->jp_Addr);
425 Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
426
427 JUDYLCODE(Pjv = JL_LEAF1VALUEAREA(PLeaf, Pop1);)
428
429 // Copy 1 byte index Leaf to bitmap Leaf
430 for (ii = 0; ii < Pop1; ii++) JU_BITMAPSETL(Pjlb, PLeaf[ii]);
431
432 #ifdef JUDYL
433 // Build 8 subexpanse Value leaves from bitmap
434 for (ii = 0; ii < cJU_NUMSUBEXPL; ii++)
435 {
436 // Get number of Indexes in subexpanse
437 if ((Pop1 = j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, ii))))
438 {
439 Pjv_t PjvnewRaw; // value area of new leaf.
440 Pjv_t Pjvnew;
441
442 PjvnewRaw = j__udyLAllocJV(Pop1, Pjpm);
443 if (PjvnewRaw == (Pjv_t) NULL) // out of memory.
444 {
445 // Free prevously allocated LeafVs:
446 while(ii--)
447 {
448 if ((Pop1 = j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, ii))))
449 {
450 PjvnewRaw = JL_JLB_PVALUE(Pjlb, ii);
451 j__udyLFreeJV(PjvnewRaw, Pop1, Pjpm);
452 }
453 }
454 // Free the bitmap leaf
455 j__udyLFreeJLB1(PjlbRaw,Pjpm);
456 return(-1);
457 }
458 Pjvnew = P_JV(PjvnewRaw);
459 JU_COPYMEM(Pjvnew, Pjv, Pop1);
460
461 Pjv += Pop1;
462 JL_JLB_PVALUE(Pjlb, ii) = PjvnewRaw;
463 }
464 }
465 #endif // JUDYL
466
467 DcdP0 = JU_JPDCDPOP0(Pjp) | (PLeaf[0] & cJU_DCDMASK(1));
468 JU_JPSETADT(Pjp, (Word_t)PjlbRaw, DcdP0, cJU_JPLEAF_B1);
469
470 return(1); // return success
471
472 } // j__udyCascade1()
473
474 #endif // (!(JUDY1 && JU_64BIT))
475
476
477 // ****************************************************************************
478 // __ J U D Y C A S C A D E 2
479 //
480 // Entry PLeaf of size LeafPop1 is either compressed or splayed with pointer
481 // returned in Pjp. Entry Levels sizeof(Word_t) down to level 2.
482 //
483 // Splay or compress the 2-byte Index Leaf that Pjp point to. Return *Pjp as a
484 // (compressed) cJU_LEAFB1 or a cJU_BRANCH_*2
485
j__udyCascade2(Pjp_t Pjp,Pvoid_t Pjpm)486 FUNCTION int j__udyCascade2(
487 Pjp_t Pjp,
488 Pvoid_t Pjpm)
489 {
490 uint16_t * PLeaf; // pointer to leaf, explicit type.
491 Word_t End, Start; // temporaries.
492 Word_t ExpCnt; // count of expanses of splay.
493 Word_t CIndex; // current Index word.
494 JUDYLCODE(Pjv_t Pjv;) // value area of leaf.
495
496 // Temp staging for parts(Leaves) of newly splayed leaf
497 jp_t StageJP [cJU_LEAF2_MAXPOP1]; // JPs of new leaves
498 uint8_t StageExp [cJU_LEAF2_MAXPOP1]; // Expanses of new leaves
499 uint8_t SubJPCount[cJU_NUMSUBEXPB]; // JPs in each subexpanse
500 jbb_t StageJBB; // staged bitmap branch
501
502 assert(JU_JPTYPE(Pjp) == cJU_JPLEAF2);
503 assert((JU_JPDCDPOP0(Pjp) & 0xFFFF) == (cJU_LEAF2_MAXPOP1-1));
504
505 // Get the address of the Leaf
506 PLeaf = (uint16_t *) P_JLL(Pjp->jp_Addr);
507
508 // And its Value area
509 JUDYLCODE(Pjv = JL_LEAF2VALUEAREA(PLeaf, cJU_LEAF2_MAXPOP1);)
510
511 // If Leaf is in 1 expanse -- just compress it to a Bitmap Leaf
512
513 CIndex = PLeaf[0];
514 if (!JU_DIGITATSTATE(CIndex ^ PLeaf[cJU_LEAF2_MAXPOP1-1], 2))
515 {
516 // cJU_JPLEAF_B1
517 Word_t DcdP0;
518 Pjlb_t PjlbRaw;
519 PjlbRaw = j__udyJLL2toJLB1(PLeaf,
520 #ifdef JUDYL
521 Pjv,
522 #endif
523 cJU_LEAF2_MAXPOP1, Pjpm);
524 if (PjlbRaw == (Pjlb_t)NULL) return(-1); // out of memory
525
526 // Merge in another Dcd byte because compressing
527 DcdP0 = (CIndex & cJU_DCDMASK(1)) | JU_JPDCDPOP0(Pjp);
528 JU_JPSETADT(Pjp, (Word_t)PjlbRaw, DcdP0, cJU_JPLEAF_B1);
529
530 return(1);
531 }
532
533 // Else in 2+ expanses, splay Leaf into smaller leaves at higher compression
534
535 StageJBB = StageJBBZero; // zero staged bitmap branch
536 ZEROJP(SubJPCount);
537
538 // Splay the 2 byte index Leaf to 1 byte Index Leaves
539 for (ExpCnt = Start = 0, End = 1; ; End++)
540 {
541 // Check if new expanse or last one
542 if ( (End == cJU_LEAF2_MAXPOP1)
543 ||
544 (JU_DIGITATSTATE(CIndex ^ PLeaf[End], 2))
545 )
546 {
547 // Build a leaf below the previous expanse
548 //
549 Pjp_t PjpJP = StageJP + ExpCnt;
550 Word_t Pop1 = End - Start;
551 Word_t expanse = JU_DIGITATSTATE(CIndex, 2);
552 Word_t subexp = expanse / cJU_BITSPERSUBEXPB;
553 //
554 // set the bit that is the current expanse
555 JU_JBB_BITMAP(&StageJBB, subexp) |= JU_BITPOSMASKB(expanse);
556 #ifdef SUBEXPCOUNTS
557 StageJBB.jbb_subPop1[subexp] += Pop1; // pop of subexpanse
558 #endif
559 // count number of expanses in each subexpanse
560 SubJPCount[subexp]++;
561
562 // Save byte expanse of leaf
563 StageExp[ExpCnt] = JU_DIGITATSTATE(CIndex, 2);
564
565 if (Pop1 == 1) // cJU_JPIMMED_1_01
566 {
567 Word_t DcdP0;
568 DcdP0 = (JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(1)) |
569 CIndex;
570 #ifdef JUDY1
571 JU_JPSETADT(PjpJP, 0, DcdP0, cJ1_JPIMMED_1_01);
572 #else // JUDYL
573 JU_JPSETADT(PjpJP, Pjv[Start], DcdP0,
574 cJL_JPIMMED_1_01);
575 #endif // JUDYL
576 }
577 else if (Pop1 <= cJU_IMMED1_MAXPOP1) // bigger
578 {
579 // cJL_JPIMMED_1_02..3: JudyL 32
580 // cJ1_JPIMMED_1_02..7: Judy1 32
581 // cJL_JPIMMED_1_02..7: JudyL 64
582 // cJ1_JPIMMED_1_02..15: Judy1 64
583 #ifdef JUDYL
584 Pjv_t PjvnewRaw; // value area of leaf.
585 Pjv_t Pjvnew;
586
587 // Allocate Value area for Immediate Leaf
588 PjvnewRaw = j__udyLAllocJV(Pop1, Pjpm);
589 if (PjvnewRaw == (Pjv_t) NULL)
590 FREEALLEXIT(ExpCnt, StageJP, Pjpm);
591
592 Pjvnew = P_JV(PjvnewRaw);
593
594 // Copy to Values to Value Leaf
595 JU_COPYMEM(Pjvnew, Pjv + Start, Pop1);
596 PjpJP->jp_Addr = (Word_t) PjvnewRaw;
597
598 // Copy to JP as an immediate Leaf
599 JU_COPYMEM(PjpJP->jp_LIndex, PLeaf + Start,
600 Pop1);
601 #else
602 JU_COPYMEM(PjpJP->jp_1Index, PLeaf + Start,
603 Pop1);
604 #endif
605 // Set Type, Population and Index size
606 PjpJP->jp_Type = cJU_JPIMMED_1_02 + Pop1 - 2;
607 }
608
609 // 64Bit Judy1 does not have Leaf1: (note, unifdef disallows comment on next
610 // line)
611
612 #if (! (defined(JUDY1) && defined(JU_64BIT)))
613 else if (Pop1 <= cJU_LEAF1_MAXPOP1) // still bigger
614 {
615 // cJU_JPLEAF1
616 Word_t DcdP0;
617 Pjll_t PjllRaw; // pointer to new leaf.
618 Pjll_t Pjll;
619 JUDYLCODE(Pjv_t Pjvnew;) // value area of new leaf.
620
621 // Get a new Leaf
622 PjllRaw = j__udyAllocJLL1(Pop1, Pjpm);
623 if (PjllRaw == (Pjll_t)NULL)
624 FREEALLEXIT(ExpCnt, StageJP, Pjpm);
625
626 Pjll = P_JLL(PjllRaw);
627 #ifdef JUDYL
628 // Copy to Values to new Leaf
629 Pjvnew = JL_LEAF1VALUEAREA(Pjll, Pop1);
630 JU_COPYMEM(Pjvnew, Pjv + Start, Pop1);
631 #endif
632 // Copy Indexes to new Leaf
633 JU_COPYMEM((uint8_t *)Pjll, PLeaf+Start, Pop1);
634
635 DBGCODE(JudyCheckSorted(Pjll, Pop1, 1);)
636
637 DcdP0 = (JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(2))
638 |
639 (CIndex & cJU_DCDMASK(2-1))
640 |
641 (Pop1 - 1);
642
643 JU_JPSETADT(PjpJP, (Word_t)PjllRaw, DcdP0,
644 cJU_JPLEAF1);
645 }
646 #endif // (!(JUDY1 && JU_64BIT)) // Not 64Bit Judy1
647
648 else // biggest
649 {
650 // cJU_JPLEAF_B1
651 Word_t DcdP0;
652 Pjlb_t PjlbRaw;
653 PjlbRaw = j__udyJLL2toJLB1(
654 PLeaf + Start,
655 #ifdef JUDYL
656 Pjv + Start,
657 #endif
658 Pop1, Pjpm);
659 if (PjlbRaw == (Pjlb_t)NULL)
660 FREEALLEXIT(ExpCnt, StageJP, Pjpm);
661
662 DcdP0 = (JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(2))
663 |
664 (CIndex & cJU_DCDMASK(2-1))
665 |
666 (Pop1 - 1);
667
668 JU_JPSETADT(PjpJP, (Word_t)PjlbRaw, DcdP0,
669 cJU_JPLEAF_B1);
670 }
671 ExpCnt++;
672 // Done?
673 if (End == cJU_LEAF2_MAXPOP1) break;
674
675 // New Expanse, Start and Count
676 CIndex = PLeaf[End];
677 Start = End;
678 }
679 }
680
681 // Now put all the Leaves below a BranchL or BranchB:
682 if (ExpCnt <= cJU_BRANCHLMAXJPS) // put the Leaves below a BranchL
683 {
684 if (j__udyCreateBranchL(Pjp, StageJP, StageExp, ExpCnt,
685 Pjpm) == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
686
687 Pjp->jp_Type = cJU_JPBRANCH_L2;
688 }
689 else
690 {
691 if (j__udyStageJBBtoJBB(Pjp, &StageJBB, StageJP, SubJPCount, Pjpm)
692 == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
693 }
694 return(1);
695
696 } // j__udyCascade2()
697
698
699 // ****************************************************************************
700 // __ J U D Y C A S C A D E 3
701 //
702 // Return *Pjp as a (compressed) cJU_LEAF2, cJU_BRANCH_L3, cJU_BRANCH_B3.
703
j__udyCascade3(Pjp_t Pjp,Pvoid_t Pjpm)704 FUNCTION int j__udyCascade3(
705 Pjp_t Pjp,
706 Pvoid_t Pjpm)
707 {
708 uint8_t * PLeaf; // pointer to leaf, explicit type.
709 Word_t End, Start; // temporaries.
710 Word_t ExpCnt; // count of expanses of splay.
711 Word_t CIndex; // current Index word.
712 JUDYLCODE(Pjv_t Pjv;) // value area of leaf.
713
714 // Temp staging for parts(Leaves) of newly splayed leaf
715 jp_t StageJP [cJU_LEAF3_MAXPOP1]; // JPs of new leaves
716 Word_t StageA [cJU_LEAF3_MAXPOP1];
717 uint8_t StageExp [cJU_LEAF3_MAXPOP1]; // Expanses of new leaves
718 uint8_t SubJPCount[cJU_NUMSUBEXPB]; // JPs in each subexpanse
719 jbb_t StageJBB; // staged bitmap branch
720
721 assert(JU_JPTYPE(Pjp) == cJU_JPLEAF3);
722 assert((JU_JPDCDPOP0(Pjp) & 0xFFFFFF) == (cJU_LEAF3_MAXPOP1-1));
723
724 // Get the address of the Leaf
725 PLeaf = (uint8_t *) P_JLL(Pjp->jp_Addr);
726
727 // Extract leaf to Word_t and insert-sort Index into it
728 j__udyCopy3toW(StageA, PLeaf, cJU_LEAF3_MAXPOP1);
729
730 // Get the address of the Leaf and Value area
731 JUDYLCODE(Pjv = JL_LEAF3VALUEAREA(PLeaf, cJU_LEAF3_MAXPOP1);)
732
733 // If Leaf is in 1 expanse -- just compress it (compare 1st, last & Index)
734
735 CIndex = StageA[0];
736 if (!JU_DIGITATSTATE(CIndex ^ StageA[cJU_LEAF3_MAXPOP1-1], 3))
737 {
738 Word_t DcdP0;
739 Pjll_t PjllRaw; // pointer to new leaf.
740 Pjll_t Pjll;
741 JUDYLCODE(Pjv_t Pjvnew;) // value area of new leaf.
742
743 // Alloc a 2 byte Index Leaf
744 PjllRaw = j__udyAllocJLL2(cJU_LEAF3_MAXPOP1, Pjpm);
745 if (PjllRaw == (Pjlb_t)NULL) return(-1); // out of memory
746
747 Pjll = P_JLL(PjllRaw);
748
749 // Copy just 2 bytes Indexes to new Leaf
750 // j__udyCopyWto2((uint16_t *) Pjll, StageA, cJU_LEAF3_MAXPOP1);
751 JU_COPYMEM ((uint16_t *) Pjll, StageA, cJU_LEAF3_MAXPOP1);
752 #ifdef JUDYL
753 // Copy Value area into new Leaf
754 Pjvnew = JL_LEAF2VALUEAREA(Pjll, cJU_LEAF3_MAXPOP1);
755 JU_COPYMEM(Pjvnew, Pjv, cJU_LEAF3_MAXPOP1);
756 #endif
757 DBGCODE(JudyCheckSorted(Pjll, cJU_LEAF3_MAXPOP1, 2);)
758
759 // Form new JP, Pop0 field is unchanged
760 // Add in another Dcd byte because compressing
761 DcdP0 = (CIndex & cJU_DCDMASK(2)) | JU_JPDCDPOP0(Pjp);
762
763 JU_JPSETADT(Pjp, (Word_t) PjllRaw, DcdP0, cJU_JPLEAF2);
764
765 return(1); // Success
766 }
767
768 // Else in 2+ expanses, splay Leaf into smaller leaves at higher compression
769
770 StageJBB = StageJBBZero; // zero staged bitmap branch
771 ZEROJP(SubJPCount);
772
773 // Splay the 3 byte index Leaf to 2 byte Index Leaves
774 for (ExpCnt = Start = 0, End = 1; ; End++)
775 {
776 // Check if new expanse or last one
777 if ( (End == cJU_LEAF3_MAXPOP1)
778 ||
779 (JU_DIGITATSTATE(CIndex ^ StageA[End], 3))
780 )
781 {
782 // Build a leaf below the previous expanse
783
784 Pjp_t PjpJP = StageJP + ExpCnt;
785 Word_t Pop1 = End - Start;
786 Word_t expanse = JU_DIGITATSTATE(CIndex, 3);
787 Word_t subexp = expanse / cJU_BITSPERSUBEXPB;
788 //
789 // set the bit that is the current expanse
790 JU_JBB_BITMAP(&StageJBB, subexp) |= JU_BITPOSMASKB(expanse);
791 #ifdef SUBEXPCOUNTS
792 StageJBB.jbb_subPop1[subexp] += Pop1; // pop of subexpanse
793 #endif
794 // count number of expanses in each subexpanse
795 SubJPCount[subexp]++;
796
797 // Save byte expanse of leaf
798 StageExp[ExpCnt] = JU_DIGITATSTATE(CIndex, 3);
799
800 if (Pop1 == 1) // cJU_JPIMMED_2_01
801 {
802 Word_t DcdP0;
803 DcdP0 = (JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(2)) |
804 CIndex;
805 #ifdef JUDY1
806 JU_JPSETADT(PjpJP, 0, DcdP0, cJ1_JPIMMED_2_01);
807 #else // JUDYL
808 JU_JPSETADT(PjpJP, Pjv[Start], DcdP0,
809 cJL_JPIMMED_2_01);
810 #endif // JUDYL
811 }
812 #if (defined(JUDY1) || defined(JU_64BIT))
813 else if (Pop1 <= cJU_IMMED2_MAXPOP1)
814 {
815 // cJ1_JPIMMED_2_02..3: Judy1 32
816 // cJL_JPIMMED_2_02..3: JudyL 64
817 // cJ1_JPIMMED_2_02..7: Judy1 64
818 #ifdef JUDYL
819 // Alloc is 1st in case of malloc fail
820 Pjv_t PjvnewRaw; // value area of new leaf.
821 Pjv_t Pjvnew;
822
823 // Allocate Value area for Immediate Leaf
824 PjvnewRaw = j__udyLAllocJV(Pop1, Pjpm);
825 if (PjvnewRaw == (Pjv_t) NULL)
826 FREEALLEXIT(ExpCnt, StageJP, Pjpm);
827
828 Pjvnew = P_JV(PjvnewRaw);
829
830 // Copy to Values to Value Leaf
831 JU_COPYMEM(Pjvnew, Pjv + Start, Pop1);
832
833 PjpJP->jp_Addr = (Word_t) PjvnewRaw;
834
835 // Copy to Index to JP as an immediate Leaf
836 JU_COPYMEM((uint16_t *) (PjpJP->jp_LIndex),
837 StageA + Start, Pop1);
838 #else // JUDY1
839 JU_COPYMEM((uint16_t *) (PjpJP->jp_1Index),
840 StageA + Start, Pop1);
841 #endif // JUDY1
842 // Set Type, Population and Index size
843 PjpJP->jp_Type = cJU_JPIMMED_2_02 + Pop1 - 2;
844 }
845 #endif // (JUDY1 || JU_64BIT)
846
847 else // Make a linear leaf2
848 {
849 // cJU_JPLEAF2
850 Word_t DcdP0;
851 Pjll_t PjllRaw; // pointer to new leaf.
852 Pjll_t Pjll;
853 JUDYLCODE(Pjv_t Pjvnew;) // value area of new leaf.
854
855 PjllRaw = j__udyAllocJLL2(Pop1, Pjpm);
856 if (PjllRaw == (Pjll_t) NULL)
857 FREEALLEXIT(ExpCnt, StageJP, Pjpm);
858
859 Pjll = P_JLL(PjllRaw);
860 #ifdef JUDYL
861 // Copy to Values to new Leaf
862 Pjvnew = JL_LEAF2VALUEAREA(Pjll, Pop1);
863 JU_COPYMEM(Pjvnew, Pjv + Start, Pop1);
864 #endif
865 // Copy least 2 bytes per Index of Leaf to new Leaf
866 JU_COPYMEM((uint16_t *) Pjll, StageA+Start,
867 Pop1);
868
869 DBGCODE(JudyCheckSorted(Pjll, Pop1, 2);)
870
871 DcdP0 = (JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(3))
872 |
873 (CIndex & cJU_DCDMASK(3-1))
874 |
875 (Pop1 - 1);
876
877 JU_JPSETADT(PjpJP, (Word_t)PjllRaw, DcdP0,
878 cJU_JPLEAF2);
879 }
880 ExpCnt++;
881 // Done?
882 if (End == cJU_LEAF3_MAXPOP1) break;
883
884 // New Expanse, Start and Count
885 CIndex = StageA[End];
886 Start = End;
887 }
888 }
889
890 // Now put all the Leaves below a BranchL or BranchB:
891 if (ExpCnt <= cJU_BRANCHLMAXJPS) // put the Leaves below a BranchL
892 {
893 if (j__udyCreateBranchL(Pjp, StageJP, StageExp, ExpCnt,
894 Pjpm) == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
895
896 Pjp->jp_Type = cJU_JPBRANCH_L3;
897 }
898 else
899 {
900 if (j__udyStageJBBtoJBB(Pjp, &StageJBB, StageJP, SubJPCount, Pjpm)
901 == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
902 }
903 return(1);
904
905 } // j__udyCascade3()
906
907
908 #ifdef JU_64BIT // JudyCascade[4567]
909
910 // ****************************************************************************
911 // __ J U D Y C A S C A D E 4
912 //
913 // Cascade from a cJU_JPLEAF4 to one of the following:
914 // 1. if leaf is in 1 expanse:
915 // compress it into a JPLEAF3
916 // 2. if leaf contains multiple expanses:
917 // create linear or bitmap branch containing
918 // each new expanse is either a:
919 // JPIMMED_3_01 branch
920 // JPIMMED_3_02 branch
921 // JPLEAF3
922
j__udyCascade4(Pjp_t Pjp,Pvoid_t Pjpm)923 FUNCTION int j__udyCascade4(
924 Pjp_t Pjp,
925 Pvoid_t Pjpm)
926 {
927 uint32_t * PLeaf; // pointer to leaf, explicit type.
928 Word_t End, Start; // temporaries.
929 Word_t ExpCnt; // count of expanses of splay.
930 Word_t CIndex; // current Index word.
931 JUDYLCODE(Pjv_t Pjv;) // value area of leaf.
932
933 // Temp staging for parts(Leaves) of newly splayed leaf
934 jp_t StageJP [cJU_LEAF4_MAXPOP1]; // JPs of new leaves
935 Word_t StageA [cJU_LEAF4_MAXPOP1];
936 uint8_t StageExp [cJU_LEAF4_MAXPOP1]; // Expanses of new leaves
937 uint8_t SubJPCount[cJU_NUMSUBEXPB]; // JPs in each subexpanse
938 jbb_t StageJBB; // staged bitmap branch
939
940 assert(JU_JPTYPE(Pjp) == cJU_JPLEAF4);
941 assert((JU_JPDCDPOP0(Pjp) & 0xFFFFFFFF) == (cJU_LEAF4_MAXPOP1-1));
942
943 // Get the address of the Leaf
944 PLeaf = (uint32_t *) P_JLL(Pjp->jp_Addr);
945
946 // Extract 4 byte index Leaf to Word_t
947 j__udyCopy4toW(StageA, PLeaf, cJU_LEAF4_MAXPOP1);
948
949 // Get the address of the Leaf and Value area
950 JUDYLCODE(Pjv = JL_LEAF4VALUEAREA(PLeaf, cJU_LEAF4_MAXPOP1);)
951
952 // If Leaf is in 1 expanse -- just compress it (compare 1st, last & Index)
953
954 CIndex = StageA[0];
955 if (!JU_DIGITATSTATE(CIndex ^ StageA[cJU_LEAF4_MAXPOP1-1], 4))
956 {
957 Word_t DcdP0;
958 Pjll_t PjllRaw; // pointer to new leaf.
959 Pjll_t Pjll;
960 JUDYLCODE(Pjv_t Pjvnew;) // value area of new Leaf.
961
962 // Alloc a 3 byte Index Leaf
963 PjllRaw = j__udyAllocJLL3(cJU_LEAF4_MAXPOP1, Pjpm);
964 if (PjllRaw == (Pjlb_t)NULL) return(-1); // out of memory
965
966 Pjll = P_JLL(PjllRaw);
967
968 // Copy Index area into new Leaf
969 j__udyCopyWto3((uint8_t *) Pjll, StageA, cJU_LEAF4_MAXPOP1);
970 #ifdef JUDYL
971 // Copy Value area into new Leaf
972 Pjvnew = JL_LEAF3VALUEAREA(Pjll, cJU_LEAF4_MAXPOP1);
973 JU_COPYMEM(Pjvnew, Pjv, cJU_LEAF4_MAXPOP1);
974 #endif
975 DBGCODE(JudyCheckSorted(Pjll, cJU_LEAF4_MAXPOP1, 3);)
976
977 DcdP0 = JU_JPDCDPOP0(Pjp) | (CIndex & cJU_DCDMASK(3));
978 JU_JPSETADT(Pjp, (Word_t)PjllRaw, DcdP0, cJU_JPLEAF3);
979
980 return(1);
981 }
982
983 // Else in 2+ expanses, splay Leaf into smaller leaves at higher compression
984
985 StageJBB = StageJBBZero; // zero staged bitmap branch
986 ZEROJP(SubJPCount);
987
988 // Splay the 4 byte index Leaf to 3 byte Index Leaves
989 for (ExpCnt = Start = 0, End = 1; ; End++)
990 {
991 // Check if new expanse or last one
992 if ( (End == cJU_LEAF4_MAXPOP1)
993 ||
994 (JU_DIGITATSTATE(CIndex ^ StageA[End], 4))
995 )
996 {
997 // Build a leaf below the previous expanse
998
999 Pjp_t PjpJP = StageJP + ExpCnt;
1000 Word_t Pop1 = End - Start;
1001 Word_t expanse = JU_DIGITATSTATE(CIndex, 4);
1002 Word_t subexp = expanse / cJU_BITSPERSUBEXPB;
1003 //
1004 // set the bit that is the current expanse
1005 JU_JBB_BITMAP(&StageJBB, subexp) |= JU_BITPOSMASKB(expanse);
1006 #ifdef SUBEXPCOUNTS
1007 StageJBB.jbb_subPop1[subexp] += Pop1; // pop of subexpanse
1008 #endif
1009 // count number of expanses in each subexpanse
1010 SubJPCount[subexp]++;
1011
1012 // Save byte expanse of leaf
1013 StageExp[ExpCnt] = JU_DIGITATSTATE(CIndex, 4);
1014
1015 if (Pop1 == 1) // cJU_JPIMMED_3_01
1016 {
1017 Word_t DcdP0;
1018 DcdP0 = (JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(3)) |
1019 CIndex;
1020 #ifdef JUDY1
1021 JU_JPSETADT(PjpJP, 0, DcdP0, cJ1_JPIMMED_3_01);
1022 #else // JUDYL
1023 JU_JPSETADT(PjpJP, Pjv[Start], DcdP0,
1024 cJL_JPIMMED_3_01);
1025 #endif // JUDYL
1026 }
1027 else if (Pop1 <= cJU_IMMED3_MAXPOP1)
1028 {
1029 // cJ1_JPIMMED_3_02 : Judy1 32
1030 // cJL_JPIMMED_3_02 : JudyL 64
1031 // cJ1_JPIMMED_3_02..5: Judy1 64
1032
1033 #ifdef JUDYL
1034 // Alloc is 1st in case of malloc fail
1035 Pjv_t PjvnewRaw; // value area of new leaf.
1036 Pjv_t Pjvnew;
1037
1038 // Allocate Value area for Immediate Leaf
1039 PjvnewRaw = j__udyLAllocJV(Pop1, Pjpm);
1040 if (PjvnewRaw == (Pjv_t) NULL)
1041 FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1042
1043 Pjvnew = P_JV(PjvnewRaw);
1044
1045 // Copy to Values to Value Leaf
1046 JU_COPYMEM(Pjvnew, Pjv + Start, Pop1);
1047 PjpJP->jp_Addr = (Word_t) PjvnewRaw;
1048
1049 // Copy to Index to JP as an immediate Leaf
1050 j__udyCopyWto3(PjpJP->jp_LIndex,
1051 StageA + Start, Pop1);
1052 #else
1053 j__udyCopyWto3(PjpJP->jp_1Index,
1054 StageA + Start, Pop1);
1055 #endif
1056 // Set type, population and Index size
1057 PjpJP->jp_Type = cJU_JPIMMED_3_02 + Pop1 - 2;
1058 }
1059 else
1060 {
1061 // cJU_JPLEAF3
1062 Word_t DcdP0;
1063 Pjll_t PjllRaw; // pointer to new leaf.
1064 Pjll_t Pjll;
1065 JUDYLCODE(Pjv_t Pjvnew;) // value area of new leaf.
1066
1067 PjllRaw = j__udyAllocJLL3(Pop1, Pjpm);
1068 if (PjllRaw == (Pjll_t)NULL)
1069 FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1070
1071 Pjll = P_JLL(PjllRaw);
1072
1073 // Copy Indexes to new Leaf
1074 j__udyCopyWto3((uint8_t *) Pjll, StageA + Start,
1075 Pop1);
1076 #ifdef JUDYL
1077 // Copy to Values to new Leaf
1078 Pjvnew = JL_LEAF3VALUEAREA(Pjll, Pop1);
1079 JU_COPYMEM(Pjvnew, Pjv + Start, Pop1);
1080 #endif
1081 DBGCODE(JudyCheckSorted(Pjll, Pop1, 3);)
1082
1083 DcdP0 = (JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(4))
1084 |
1085 (CIndex & cJU_DCDMASK(4-1))
1086 |
1087 (Pop1 - 1);
1088
1089 JU_JPSETADT(PjpJP, (Word_t)PjllRaw, DcdP0,
1090 cJU_JPLEAF3);
1091 }
1092 ExpCnt++;
1093 // Done?
1094 if (End == cJU_LEAF4_MAXPOP1) break;
1095
1096 // New Expanse, Start and Count
1097 CIndex = StageA[End];
1098 Start = End;
1099 }
1100 }
1101
1102 // Now put all the Leaves below a BranchL or BranchB:
1103 if (ExpCnt <= cJU_BRANCHLMAXJPS) // put the Leaves below a BranchL
1104 {
1105 if (j__udyCreateBranchL(Pjp, StageJP, StageExp, ExpCnt,
1106 Pjpm) == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1107
1108 Pjp->jp_Type = cJU_JPBRANCH_L4;
1109 }
1110 else
1111 {
1112 if (j__udyStageJBBtoJBB(Pjp, &StageJBB, StageJP, SubJPCount, Pjpm)
1113 == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1114 }
1115 return(1);
1116
1117 } // j__udyCascade4()
1118
1119
1120 // ****************************************************************************
1121 // __ J U D Y C A S C A D E 5
1122 //
1123 // Cascade from a cJU_JPLEAF5 to one of the following:
1124 // 1. if leaf is in 1 expanse:
1125 // compress it into a JPLEAF4
1126 // 2. if leaf contains multiple expanses:
1127 // create linear or bitmap branch containing
1128 // each new expanse is either a:
1129 // JPIMMED_4_01 branch
1130 // JPLEAF4
1131
j__udyCascade5(Pjp_t Pjp,Pvoid_t Pjpm)1132 FUNCTION int j__udyCascade5(
1133 Pjp_t Pjp,
1134 Pvoid_t Pjpm)
1135 {
1136 uint8_t * PLeaf; // pointer to leaf, explicit type.
1137 Word_t End, Start; // temporaries.
1138 Word_t ExpCnt; // count of expanses of splay.
1139 Word_t CIndex; // current Index word.
1140 JUDYLCODE(Pjv_t Pjv;) // value area of leaf.
1141
1142 // Temp staging for parts(Leaves) of newly splayed leaf
1143 jp_t StageJP [cJU_LEAF5_MAXPOP1]; // JPs of new leaves
1144 Word_t StageA [cJU_LEAF5_MAXPOP1];
1145 uint8_t StageExp [cJU_LEAF5_MAXPOP1]; // Expanses of new leaves
1146 uint8_t SubJPCount[cJU_NUMSUBEXPB]; // JPs in each subexpanse
1147 jbb_t StageJBB; // staged bitmap branch
1148
1149 assert(JU_JPTYPE(Pjp) == cJU_JPLEAF5);
1150 assert((JU_JPDCDPOP0(Pjp) & 0xFFFFFFFFFF) == (cJU_LEAF5_MAXPOP1-1));
1151
1152 // Get the address of the Leaf
1153 PLeaf = (uint8_t *) P_JLL(Pjp->jp_Addr);
1154
1155 // Extract 5 byte index Leaf to Word_t
1156 j__udyCopy5toW(StageA, PLeaf, cJU_LEAF5_MAXPOP1);
1157
1158 // Get the address of the Leaf and Value area
1159 JUDYLCODE(Pjv = JL_LEAF5VALUEAREA(PLeaf, cJU_LEAF5_MAXPOP1);)
1160
1161 // If Leaf is in 1 expanse -- just compress it (compare 1st, last & Index)
1162
1163 CIndex = StageA[0];
1164 if (!JU_DIGITATSTATE(CIndex ^ StageA[cJU_LEAF5_MAXPOP1-1], 5))
1165 {
1166 Word_t DcdP0;
1167 Pjll_t PjllRaw; // pointer to new leaf.
1168 Pjll_t Pjll;
1169 JUDYLCODE(Pjv_t Pjvnew;) // value area of new leaf.
1170
1171 // Alloc a 4 byte Index Leaf
1172 PjllRaw = j__udyAllocJLL4(cJU_LEAF5_MAXPOP1, Pjpm);
1173 if (PjllRaw == (Pjlb_t)NULL) return(-1); // out of memory
1174
1175 Pjll = P_JLL(PjllRaw);
1176
1177 // Copy Index area into new Leaf
1178 j__udyCopyWto4((uint8_t *) Pjll, StageA, cJU_LEAF5_MAXPOP1);
1179 #ifdef JUDYL
1180 // Copy Value area into new Leaf
1181 Pjvnew = JL_LEAF4VALUEAREA(Pjll, cJU_LEAF5_MAXPOP1);
1182 JU_COPYMEM(Pjvnew, Pjv, cJU_LEAF5_MAXPOP1);
1183 #endif
1184 DBGCODE(JudyCheckSorted(Pjll, cJU_LEAF5_MAXPOP1, 4);)
1185
1186 DcdP0 = JU_JPDCDPOP0(Pjp) | (CIndex & cJU_DCDMASK(4));
1187 JU_JPSETADT(Pjp, (Word_t)PjllRaw, DcdP0, cJU_JPLEAF4);
1188
1189 return(1);
1190 }
1191
1192 // Else in 2+ expanses, splay Leaf into smaller leaves at higher compression
1193
1194 StageJBB = StageJBBZero; // zero staged bitmap branch
1195 ZEROJP(SubJPCount);
1196
1197 // Splay the 5 byte index Leaf to 4 byte Index Leaves
1198 for (ExpCnt = Start = 0, End = 1; ; End++)
1199 {
1200 // Check if new expanse or last one
1201 if ( (End == cJU_LEAF5_MAXPOP1)
1202 ||
1203 (JU_DIGITATSTATE(CIndex ^ StageA[End], 5))
1204 )
1205 {
1206 // Build a leaf below the previous expanse
1207
1208 Pjp_t PjpJP = StageJP + ExpCnt;
1209 Word_t Pop1 = End - Start;
1210 Word_t expanse = JU_DIGITATSTATE(CIndex, 5);
1211 Word_t subexp = expanse / cJU_BITSPERSUBEXPB;
1212 //
1213 // set the bit that is the current expanse
1214 JU_JBB_BITMAP(&StageJBB, subexp) |= JU_BITPOSMASKB(expanse);
1215 #ifdef SUBEXPCOUNTS
1216 StageJBB.jbb_subPop1[subexp] += Pop1; // pop of subexpanse
1217 #endif
1218 // count number of expanses in each subexpanse
1219 SubJPCount[subexp]++;
1220
1221 // Save byte expanse of leaf
1222 StageExp[ExpCnt] = JU_DIGITATSTATE(CIndex, 5);
1223
1224 if (Pop1 == 1) // cJU_JPIMMED_4_01
1225 {
1226 Word_t DcdP0;
1227 DcdP0 = (JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(4)) |
1228 CIndex;
1229 #ifdef JUDY1
1230 JU_JPSETADT(PjpJP, 0, DcdP0, cJ1_JPIMMED_4_01);
1231 #else // JUDYL
1232 JU_JPSETADT(PjpJP, Pjv[Start], DcdP0,
1233 cJL_JPIMMED_4_01);
1234 #endif // JUDYL
1235 }
1236 #ifdef JUDY1
1237 else if (Pop1 <= cJ1_IMMED4_MAXPOP1)
1238 {
1239 // cJ1_JPIMMED_4_02..3: Judy1 64
1240
1241 // Copy to Index to JP as an immediate Leaf
1242 j__udyCopyWto4(PjpJP->jp_1Index,
1243 StageA + Start, Pop1);
1244
1245 // Set pointer, type, population and Index size
1246 PjpJP->jp_Type = cJ1_JPIMMED_4_02 + Pop1 - 2;
1247 }
1248 #endif
1249 else
1250 {
1251 // cJU_JPLEAF4
1252 Word_t DcdP0;
1253 Pjll_t PjllRaw; // pointer to new leaf.
1254 Pjll_t Pjll;
1255 JUDYLCODE(Pjv_t Pjvnew;) // value area of new leaf.
1256
1257 // Get a new Leaf
1258 PjllRaw = j__udyAllocJLL4(Pop1, Pjpm);
1259 if (PjllRaw == (Pjll_t)NULL)
1260 FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1261
1262 Pjll = P_JLL(PjllRaw);
1263
1264 // Copy Indexes to new Leaf
1265 j__udyCopyWto4((uint8_t *) Pjll, StageA + Start,
1266 Pop1);
1267 #ifdef JUDYL
1268 // Copy to Values to new Leaf
1269 Pjvnew = JL_LEAF4VALUEAREA(Pjll, Pop1);
1270 JU_COPYMEM(Pjvnew, Pjv + Start, Pop1);
1271 #endif
1272 DBGCODE(JudyCheckSorted(Pjll, Pop1, 4);)
1273
1274 DcdP0 = (JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(5))
1275 |
1276 (CIndex & cJU_DCDMASK(5-1))
1277 |
1278 (Pop1 - 1);
1279
1280 JU_JPSETADT(PjpJP, (Word_t)PjllRaw, DcdP0,
1281 cJU_JPLEAF4);
1282 }
1283 ExpCnt++;
1284 // Done?
1285 if (End == cJU_LEAF5_MAXPOP1) break;
1286
1287 // New Expanse, Start and Count
1288 CIndex = StageA[End];
1289 Start = End;
1290 }
1291 }
1292
1293 // Now put all the Leaves below a BranchL or BranchB:
1294 if (ExpCnt <= cJU_BRANCHLMAXJPS) // put the Leaves below a BranchL
1295 {
1296 if (j__udyCreateBranchL(Pjp, StageJP, StageExp, ExpCnt,
1297 Pjpm) == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1298
1299 Pjp->jp_Type = cJU_JPBRANCH_L5;
1300 }
1301 else
1302 {
1303 if (j__udyStageJBBtoJBB(Pjp, &StageJBB, StageJP, SubJPCount, Pjpm)
1304 == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1305 }
1306 return(1);
1307
1308 } // j__udyCascade5()
1309
1310
1311 // ****************************************************************************
1312 // __ J U D Y C A S C A D E 6
1313 //
1314 // Cascade from a cJU_JPLEAF6 to one of the following:
1315 // 1. if leaf is in 1 expanse:
1316 // compress it into a JPLEAF5
1317 // 2. if leaf contains multiple expanses:
1318 // create linear or bitmap branch containing
1319 // each new expanse is either a:
1320 // JPIMMED_5_01 ... JPIMMED_5_03 branch
1321 // JPIMMED_5_01 branch
1322 // JPLEAF5
1323
j__udyCascade6(Pjp_t Pjp,Pvoid_t Pjpm)1324 FUNCTION int j__udyCascade6(
1325 Pjp_t Pjp,
1326 Pvoid_t Pjpm)
1327 {
1328 uint8_t * PLeaf; // pointer to leaf, explicit type.
1329 Word_t End, Start; // temporaries.
1330 Word_t ExpCnt; // count of expanses of splay.
1331 Word_t CIndex; // current Index word.
1332 JUDYLCODE(Pjv_t Pjv;) // value area of leaf.
1333
1334 // Temp staging for parts(Leaves) of newly splayed leaf
1335 jp_t StageJP [cJU_LEAF6_MAXPOP1]; // JPs of new leaves
1336 Word_t StageA [cJU_LEAF6_MAXPOP1];
1337 uint8_t StageExp [cJU_LEAF6_MAXPOP1]; // Expanses of new leaves
1338 uint8_t SubJPCount[cJU_NUMSUBEXPB]; // JPs in each subexpanse
1339 jbb_t StageJBB; // staged bitmap branch
1340
1341 assert(JU_JPTYPE(Pjp) == cJU_JPLEAF6);
1342 assert((JU_JPDCDPOP0(Pjp) & 0xFFFFFFFFFFFF) == (cJU_LEAF6_MAXPOP1-1));
1343
1344 // Get the address of the Leaf
1345 PLeaf = (uint8_t *) P_JLL(Pjp->jp_Addr);
1346
1347 // Extract 6 byte index Leaf to Word_t
1348 j__udyCopy6toW(StageA, PLeaf, cJU_LEAF6_MAXPOP1);
1349
1350 // Get the address of the Leaf and Value area
1351 JUDYLCODE(Pjv = JL_LEAF6VALUEAREA(PLeaf, cJU_LEAF6_MAXPOP1);)
1352
1353 // If Leaf is in 1 expanse -- just compress it (compare 1st, last & Index)
1354
1355 CIndex = StageA[0];
1356 if (!JU_DIGITATSTATE(CIndex ^ StageA[cJU_LEAF6_MAXPOP1-1], 6))
1357 {
1358 Word_t DcdP0;
1359 Pjll_t PjllRaw; // pointer to new leaf.
1360 Pjll_t Pjll;
1361 JUDYLCODE(Pjv_t Pjvnew;) // value area of new leaf.
1362
1363 // Alloc a 5 byte Index Leaf
1364 PjllRaw = j__udyAllocJLL5(cJU_LEAF6_MAXPOP1, Pjpm);
1365 if (PjllRaw == (Pjlb_t)NULL) return(-1); // out of memory
1366
1367 Pjll = P_JLL(PjllRaw);
1368
1369 // Copy Index area into new Leaf
1370 j__udyCopyWto5((uint8_t *) Pjll, StageA, cJU_LEAF6_MAXPOP1);
1371 #ifdef JUDYL
1372 // Copy Value area into new Leaf
1373 Pjvnew = JL_LEAF5VALUEAREA(Pjll, cJU_LEAF6_MAXPOP1);
1374 JU_COPYMEM(Pjvnew, Pjv, cJU_LEAF6_MAXPOP1);
1375 #endif
1376 DBGCODE(JudyCheckSorted(Pjll, cJU_LEAF6_MAXPOP1, 5);)
1377
1378 DcdP0 = JU_JPDCDPOP0(Pjp) | (CIndex & cJU_DCDMASK(5));
1379 JU_JPSETADT(Pjp, (Word_t)PjllRaw, DcdP0, cJU_JPLEAF5);
1380
1381 return(1);
1382 }
1383
1384 // Else in 2+ expanses, splay Leaf into smaller leaves at higher compression
1385
1386 StageJBB = StageJBBZero; // zero staged bitmap branch
1387 ZEROJP(SubJPCount);
1388
1389 // Splay the 6 byte index Leaf to 5 byte Index Leaves
1390 for (ExpCnt = Start = 0, End = 1; ; End++)
1391 {
1392 // Check if new expanse or last one
1393 if ( (End == cJU_LEAF6_MAXPOP1)
1394 ||
1395 (JU_DIGITATSTATE(CIndex ^ StageA[End], 6))
1396 )
1397 {
1398 // Build a leaf below the previous expanse
1399
1400 Pjp_t PjpJP = StageJP + ExpCnt;
1401 Word_t Pop1 = End - Start;
1402 Word_t expanse = JU_DIGITATSTATE(CIndex, 6);
1403 Word_t subexp = expanse / cJU_BITSPERSUBEXPB;
1404 //
1405 // set the bit that is the current expanse
1406 JU_JBB_BITMAP(&StageJBB, subexp) |= JU_BITPOSMASKB(expanse);
1407 #ifdef SUBEXPCOUNTS
1408 StageJBB.jbb_subPop1[subexp] += Pop1; // pop of subexpanse
1409 #endif
1410 // count number of expanses in each subexpanse
1411 SubJPCount[subexp]++;
1412
1413 // Save byte expanse of leaf
1414 StageExp[ExpCnt] = JU_DIGITATSTATE(CIndex, 6);
1415
1416 if (Pop1 == 1) // cJU_JPIMMED_5_01
1417 {
1418 Word_t DcdP0;
1419 DcdP0 = (JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(5)) |
1420 CIndex;
1421 #ifdef JUDY1
1422 JU_JPSETADT(PjpJP, 0, DcdP0, cJ1_JPIMMED_5_01);
1423 #else // JUDYL
1424 JU_JPSETADT(PjpJP, Pjv[Start], DcdP0,
1425 cJL_JPIMMED_5_01);
1426 #endif // JUDYL
1427 }
1428 #ifdef JUDY1
1429 else if (Pop1 <= cJ1_IMMED5_MAXPOP1)
1430 {
1431 // cJ1_JPIMMED_5_02..3: Judy1 64
1432
1433 // Copy to Index to JP as an immediate Leaf
1434 j__udyCopyWto5(PjpJP->jp_1Index,
1435 StageA + Start, Pop1);
1436
1437 // Set pointer, type, population and Index size
1438 PjpJP->jp_Type = cJ1_JPIMMED_5_02 + Pop1 - 2;
1439 }
1440 #endif
1441 else
1442 {
1443 // cJU_JPLEAF5
1444 Word_t DcdP0;
1445 Pjll_t PjllRaw; // pointer to new leaf.
1446 Pjll_t Pjll;
1447 JUDYLCODE(Pjv_t Pjvnew;) // value area of new leaf.
1448
1449 // Get a new Leaf
1450 PjllRaw = j__udyAllocJLL5(Pop1, Pjpm);
1451 if (PjllRaw == (Pjll_t)NULL)
1452 FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1453
1454 Pjll = P_JLL(PjllRaw);
1455
1456 // Copy Indexes to new Leaf
1457 j__udyCopyWto5((uint8_t *) Pjll, StageA + Start,
1458 Pop1);
1459
1460 // Copy to Values to new Leaf
1461 #ifdef JUDYL
1462 Pjvnew = JL_LEAF5VALUEAREA(Pjll, Pop1);
1463 JU_COPYMEM(Pjvnew, Pjv + Start, Pop1);
1464 #endif
1465 DBGCODE(JudyCheckSorted(Pjll, Pop1, 5);)
1466
1467 DcdP0 = (JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(6))
1468 |
1469 (CIndex & cJU_DCDMASK(6-1))
1470 |
1471 (Pop1 - 1);
1472
1473 JU_JPSETADT(PjpJP, (Word_t)PjllRaw, DcdP0,
1474 cJU_JPLEAF5);
1475 }
1476 ExpCnt++;
1477 // Done?
1478 if (End == cJU_LEAF6_MAXPOP1) break;
1479
1480 // New Expanse, Start and Count
1481 CIndex = StageA[End];
1482 Start = End;
1483 }
1484 }
1485
1486 // Now put all the Leaves below a BranchL or BranchB:
1487 if (ExpCnt <= cJU_BRANCHLMAXJPS) // put the Leaves below a BranchL
1488 {
1489 if (j__udyCreateBranchL(Pjp, StageJP, StageExp, ExpCnt,
1490 Pjpm) == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1491
1492 Pjp->jp_Type = cJU_JPBRANCH_L6;
1493 }
1494 else
1495 {
1496 if (j__udyStageJBBtoJBB(Pjp, &StageJBB, StageJP, SubJPCount, Pjpm)
1497 == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1498 }
1499 return(1);
1500
1501 } // j__udyCascade6()
1502
1503
1504 // ****************************************************************************
1505 // __ J U D Y C A S C A D E 7
1506 //
1507 // Cascade from a cJU_JPLEAF7 to one of the following:
1508 // 1. if leaf is in 1 expanse:
1509 // compress it into a JPLEAF6
1510 // 2. if leaf contains multiple expanses:
1511 // create linear or bitmap branch containing
1512 // each new expanse is either a:
1513 // JPIMMED_6_01 ... JPIMMED_6_02 branch
1514 // JPIMMED_6_01 branch
1515 // JPLEAF6
1516
j__udyCascade7(Pjp_t Pjp,Pvoid_t Pjpm)1517 FUNCTION int j__udyCascade7(
1518 Pjp_t Pjp,
1519 Pvoid_t Pjpm)
1520 {
1521 uint8_t * PLeaf; // pointer to leaf, explicit type.
1522 Word_t End, Start; // temporaries.
1523 Word_t ExpCnt; // count of expanses of splay.
1524 Word_t CIndex; // current Index word.
1525 JUDYLCODE(Pjv_t Pjv;) // value area of leaf.
1526
1527 // Temp staging for parts(Leaves) of newly splayed leaf
1528 jp_t StageJP [cJU_LEAF7_MAXPOP1]; // JPs of new leaves
1529 Word_t StageA [cJU_LEAF7_MAXPOP1];
1530 uint8_t StageExp [cJU_LEAF7_MAXPOP1]; // Expanses of new leaves
1531 uint8_t SubJPCount[cJU_NUMSUBEXPB]; // JPs in each subexpanse
1532 jbb_t StageJBB; // staged bitmap branch
1533
1534 assert(JU_JPTYPE(Pjp) == cJU_JPLEAF7);
1535 assert(JU_JPDCDPOP0(Pjp) == (cJU_LEAF7_MAXPOP1-1));
1536
1537 // Get the address of the Leaf
1538 PLeaf = (uint8_t *) P_JLL(Pjp->jp_Addr);
1539
1540 // Extract 7 byte index Leaf to Word_t
1541 j__udyCopy7toW(StageA, PLeaf, cJU_LEAF7_MAXPOP1);
1542
1543 // Get the address of the Leaf and Value area
1544 JUDYLCODE(Pjv = JL_LEAF7VALUEAREA(PLeaf, cJU_LEAF7_MAXPOP1);)
1545
1546 // If Leaf is in 1 expanse -- just compress it (compare 1st, last & Index)
1547
1548 CIndex = StageA[0];
1549 if (!JU_DIGITATSTATE(CIndex ^ StageA[cJU_LEAF7_MAXPOP1-1], 7))
1550 {
1551 Word_t DcdP0;
1552 Pjll_t PjllRaw; // pointer to new leaf.
1553 Pjll_t Pjll;
1554 JUDYLCODE(Pjv_t Pjvnew;) // value area of new leaf.
1555
1556 // Alloc a 6 byte Index Leaf
1557 PjllRaw = j__udyAllocJLL6(cJU_LEAF7_MAXPOP1, Pjpm);
1558 if (PjllRaw == (Pjlb_t)NULL) return(-1); // out of memory
1559
1560 Pjll = P_JLL(PjllRaw);
1561
1562 // Copy Index area into new Leaf
1563 j__udyCopyWto6((uint8_t *) Pjll, StageA, cJU_LEAF7_MAXPOP1);
1564 #ifdef JUDYL
1565 // Copy Value area into new Leaf
1566 Pjvnew = JL_LEAF6VALUEAREA(Pjll, cJU_LEAF7_MAXPOP1);
1567 JU_COPYMEM(Pjvnew, Pjv, cJU_LEAF7_MAXPOP1);
1568 #endif
1569 DBGCODE(JudyCheckSorted(Pjll, cJU_LEAF7_MAXPOP1, 6);)
1570
1571 DcdP0 = JU_JPDCDPOP0(Pjp) | (CIndex & cJU_DCDMASK(6));
1572 JU_JPSETADT(Pjp, (Word_t)PjllRaw, DcdP0, cJU_JPLEAF6);
1573
1574 return(1);
1575 }
1576
1577 // Else in 2+ expanses, splay Leaf into smaller leaves at higher compression
1578
1579 StageJBB = StageJBBZero; // zero staged bitmap branch
1580 ZEROJP(SubJPCount);
1581
1582 // Splay the 7 byte index Leaf to 6 byte Index Leaves
1583 for (ExpCnt = Start = 0, End = 1; ; End++)
1584 {
1585 // Check if new expanse or last one
1586 if ( (End == cJU_LEAF7_MAXPOP1)
1587 ||
1588 (JU_DIGITATSTATE(CIndex ^ StageA[End], 7))
1589 )
1590 {
1591 // Build a leaf below the previous expanse
1592
1593 Pjp_t PjpJP = StageJP + ExpCnt;
1594 Word_t Pop1 = End - Start;
1595 Word_t expanse = JU_DIGITATSTATE(CIndex, 7);
1596 Word_t subexp = expanse / cJU_BITSPERSUBEXPB;
1597 //
1598 // set the bit that is the current expanse
1599 JU_JBB_BITMAP(&StageJBB, subexp) |= JU_BITPOSMASKB(expanse);
1600 #ifdef SUBEXPCOUNTS
1601 StageJBB.jbb_subPop1[subexp] += Pop1; // pop of subexpanse
1602 #endif
1603 // count number of expanses in each subexpanse
1604 SubJPCount[subexp]++;
1605
1606 // Save byte expanse of leaf
1607 StageExp[ExpCnt] = JU_DIGITATSTATE(CIndex, 7);
1608
1609 if (Pop1 == 1) // cJU_JPIMMED_6_01
1610 {
1611 Word_t DcdP0;
1612 DcdP0 = (JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(6)) |
1613 CIndex;
1614 #ifdef JUDY1
1615 JU_JPSETADT(PjpJP, 0, DcdP0, cJ1_JPIMMED_6_01);
1616 #else // JUDYL
1617 JU_JPSETADT(PjpJP, Pjv[Start], DcdP0,
1618 cJL_JPIMMED_6_01);
1619 #endif // JUDYL
1620 }
1621 #ifdef JUDY1
1622 else if (Pop1 == cJ1_IMMED6_MAXPOP1)
1623 {
1624 // cJ1_JPIMMED_6_02: Judy1 64
1625
1626 // Copy to Index to JP as an immediate Leaf
1627 j__udyCopyWto6(PjpJP->jp_1Index,
1628 StageA + Start, 2);
1629
1630 // Set pointer, type, population and Index size
1631 PjpJP->jp_Type = cJ1_JPIMMED_6_02;
1632 }
1633 #endif
1634 else
1635 {
1636 // cJU_JPLEAF6
1637 Word_t DcdP0;
1638 Pjll_t PjllRaw; // pointer to new leaf.
1639 Pjll_t Pjll;
1640 JUDYLCODE(Pjv_t Pjvnew;) // value area of new leaf.
1641
1642 // Get a new Leaf
1643 PjllRaw = j__udyAllocJLL6(Pop1, Pjpm);
1644 if (PjllRaw == (Pjll_t)NULL)
1645 FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1646 Pjll = P_JLL(PjllRaw);
1647
1648 // Copy Indexes to new Leaf
1649 j__udyCopyWto6((uint8_t *) Pjll, StageA + Start,
1650 Pop1);
1651 #ifdef JUDYL
1652 // Copy to Values to new Leaf
1653 Pjvnew = JL_LEAF6VALUEAREA(Pjll, Pop1);
1654 JU_COPYMEM(Pjvnew, Pjv + Start, Pop1);
1655 #endif
1656 DBGCODE(JudyCheckSorted(Pjll, Pop1, 6);)
1657
1658 DcdP0 = (JU_JPDCDPOP0(Pjp) & cJU_DCDMASK(7))
1659 |
1660 (CIndex & cJU_DCDMASK(7-1))
1661 |
1662 (Pop1 - 1);
1663
1664 JU_JPSETADT(PjpJP, (Word_t)PjllRaw, DcdP0,
1665 cJU_JPLEAF6);
1666 }
1667 ExpCnt++;
1668 // Done?
1669 if (End == cJU_LEAF7_MAXPOP1) break;
1670
1671 // New Expanse, Start and Count
1672 CIndex = StageA[End];
1673 Start = End;
1674 }
1675 }
1676
1677 // Now put all the Leaves below a BranchL or BranchB:
1678 if (ExpCnt <= cJU_BRANCHLMAXJPS) // put the Leaves below a BranchL
1679 {
1680 if (j__udyCreateBranchL(Pjp, StageJP, StageExp, ExpCnt,
1681 Pjpm) == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1682
1683 Pjp->jp_Type = cJU_JPBRANCH_L7;
1684 }
1685 else
1686 {
1687 if (j__udyStageJBBtoJBB(Pjp, &StageJBB, StageJP, SubJPCount, Pjpm)
1688 == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1689 }
1690 return(1);
1691
1692 } // j__udyCascade7()
1693
1694 #endif // JU_64BIT
1695
1696
1697 // ****************************************************************************
1698 // __ J U D Y C A S C A D E L
1699 //
1700 // (Compressed) cJU_LEAF3[7], cJ1_JPBRANCH_L.
1701 //
1702 // Cascade from a LEAFW (under Pjp) to one of the following:
1703 // 1. if LEAFW is in 1 expanse:
1704 // create linear branch with a JPLEAF3[7] under it
1705 // 2. LEAFW contains multiple expanses:
1706 // create linear or bitmap branch containing new expanses
1707 // each new expanse is either a: 32 64
1708 // JPIMMED_3_01 branch Y N
1709 // JPIMMED_7_01 branch N Y
1710 // JPLEAF3 Y N
1711 // JPLEAF7 N Y
1712
j__udyCascadeL(Pjp_t Pjp,Pvoid_t Pjpm)1713 FUNCTION int j__udyCascadeL(
1714 Pjp_t Pjp,
1715 Pvoid_t Pjpm)
1716 {
1717 Pjlw_t Pjlw; // leaf to work on.
1718 Word_t End, Start; // temporaries.
1719 Word_t ExpCnt; // count of expanses of splay.
1720 Word_t CIndex; // current Index word.
1721 JUDYLCODE(Pjv_t Pjv;) // value area of leaf.
1722
1723 // Temp staging for parts(Leaves) of newly splayed leaf
1724 jp_t StageJP [cJU_LEAFW_MAXPOP1];
1725 uint8_t StageExp[cJU_LEAFW_MAXPOP1];
1726 uint8_t SubJPCount[cJU_NUMSUBEXPB]; // JPs in each subexpanse
1727 jbb_t StageJBB; // staged bitmap branch
1728
1729 // Get the address of the Leaf
1730 Pjlw = P_JLW(Pjp->jp_Addr);
1731
1732 assert(Pjlw[0] == (cJU_LEAFW_MAXPOP1 - 1));
1733
1734 // Get pointer to Value area of old Leaf
1735 JUDYLCODE(Pjv = JL_LEAFWVALUEAREA(Pjlw, cJU_LEAFW_MAXPOP1);)
1736
1737 Pjlw++; // Now point to Index area
1738
1739 // If Leaf is in 1 expanse -- first compress it (compare 1st, last & Index):
1740
1741 CIndex = Pjlw[0]; // also used far below
1742 if (!JU_DIGITATSTATE(CIndex ^ Pjlw[cJU_LEAFW_MAXPOP1 - 1],
1743 cJU_ROOTSTATE))
1744 {
1745 Pjll_t PjllRaw; // pointer to new leaf.
1746 Pjll_t Pjll;
1747 JUDYLCODE(Pjv_t Pjvnew;) // value area of new leaf.
1748
1749 // Get the common expanse to all elements in Leaf
1750 StageExp[0] = JU_DIGITATSTATE(CIndex, cJU_ROOTSTATE);
1751
1752 // Alloc a 3[7] byte Index Leaf
1753 #ifdef JU_64BIT
1754 PjllRaw = j__udyAllocJLL7(cJU_LEAFW_MAXPOP1, Pjpm);
1755 if (PjllRaw == (Pjlb_t)NULL) return(-1); // out of memory
1756
1757 Pjll = P_JLL(PjllRaw);
1758
1759 // Copy LEAFW to a cJU_JPLEAF7
1760 j__udyCopyWto7((uint8_t *) Pjll, Pjlw, cJU_LEAFW_MAXPOP1);
1761 #ifdef JUDYL
1762 // Get the Value area of new Leaf
1763 Pjvnew = JL_LEAF7VALUEAREA(Pjll, cJU_LEAFW_MAXPOP1);
1764 JU_COPYMEM(Pjvnew, Pjv, cJU_LEAFW_MAXPOP1);
1765 #endif
1766 DBGCODE(JudyCheckSorted(Pjll, cJU_LEAFW_MAXPOP1, 7);)
1767 #else // 32 Bit
1768 PjllRaw = j__udyAllocJLL3(cJU_LEAFW_MAXPOP1, Pjpm);
1769 if (PjllRaw == (Pjll_t) NULL) return(-1);
1770
1771 Pjll = P_JLL(PjllRaw);
1772
1773 // Copy LEAFW to a cJU_JPLEAF3
1774 j__udyCopyWto3((uint8_t *) Pjll, Pjlw, cJU_LEAFW_MAXPOP1);
1775 #ifdef JUDYL
1776 // Get the Value area of new Leaf
1777 Pjvnew = JL_LEAF3VALUEAREA(Pjll, cJU_LEAFW_MAXPOP1);
1778 JU_COPYMEM(Pjvnew, Pjv, cJU_LEAFW_MAXPOP1);
1779 #endif
1780 DBGCODE(JudyCheckSorted(Pjll, cJU_LEAFW_MAXPOP1, 3);)
1781 #endif // 32 Bit
1782
1783 // Following not needed because cJU_DCDMASK(3[7]) is == 0
1784 ////// StageJP[0].jp_DcdPopO |= (CIndex & cJU_DCDMASK(3[7]));
1785 #ifdef JU_64BIT
1786 JU_JPSETADT(&(StageJP[0]), (Word_t)PjllRaw, cJU_LEAFW_MAXPOP1-1,
1787 cJU_JPLEAF7);
1788 #else // 32BIT
1789 JU_JPSETADT(&(StageJP[0]), (Word_t)PjllRaw, cJU_LEAFW_MAXPOP1-1,
1790 cJU_JPLEAF3);
1791 #endif // 32BIT
1792 // Create a 1 element Linear branch
1793 if (j__udyCreateBranchL(Pjp, StageJP, StageExp, 1, Pjpm) == -1)
1794 return(-1);
1795
1796 // Change the type of callers JP
1797 Pjp->jp_Type = cJU_JPBRANCH_L;
1798
1799 return(1);
1800 }
1801
1802 // Else in 2+ expanses, splay Leaf into smaller leaves at higher compression
1803
1804 StageJBB = StageJBBZero; // zero staged bitmap branch
1805 ZEROJP(SubJPCount);
1806
1807 // Splay the 4[8] byte Index Leaf to 3[7] byte Index Leaves
1808 for (ExpCnt = Start = 0, End = 1; ; End++)
1809 {
1810 // Check if new expanse or last one
1811 if ( (End == cJU_LEAFW_MAXPOP1)
1812 ||
1813 (JU_DIGITATSTATE(CIndex ^ Pjlw[End], cJU_ROOTSTATE))
1814 )
1815 {
1816 // Build a leaf below the previous expanse
1817
1818 Pjp_t PjpJP = StageJP + ExpCnt;
1819 Word_t Pop1 = End - Start;
1820 Word_t expanse = JU_DIGITATSTATE(CIndex, cJU_ROOTSTATE);
1821 Word_t subexp = expanse / cJU_BITSPERSUBEXPB;
1822 //
1823 // set the bit that is the current expanse
1824 JU_JBB_BITMAP(&StageJBB, subexp) |= JU_BITPOSMASKB(expanse);
1825 #ifdef SUBEXPCOUNTS
1826 StageJBB.jbb_subPop1[subexp] += Pop1; // pop of subexpanse
1827 #endif
1828 // count number of expanses in each subexpanse
1829 SubJPCount[subexp]++;
1830
1831 // Save byte expanse of leaf
1832 StageExp[ExpCnt] = JU_DIGITATSTATE(CIndex,
1833 cJU_ROOTSTATE);
1834
1835 if (Pop1 == 1) // cJU_JPIMMED_3[7]_01
1836 {
1837 #ifdef JU_64BIT
1838 #ifdef JUDY1
1839 JU_JPSETADT(PjpJP, 0, CIndex, cJ1_JPIMMED_7_01);
1840 #else // JUDYL
1841 JU_JPSETADT(PjpJP, Pjv[Start], CIndex,
1842 cJL_JPIMMED_7_01);
1843 #endif // JUDYL
1844
1845 #else // JU_32BIT
1846 #ifdef JUDY1
1847 JU_JPSETADT(PjpJP, 0, CIndex, cJ1_JPIMMED_3_01);
1848 #else // JUDYL
1849 JU_JPSETADT(PjpJP, Pjv[Start], CIndex,
1850 cJL_JPIMMED_3_01);
1851 #endif // JUDYL
1852 #endif // JU_32BIT
1853 }
1854 #ifdef JUDY1
1855 #ifdef JU_64BIT
1856 else if (Pop1 <= cJ1_IMMED7_MAXPOP1)
1857 #else
1858 else if (Pop1 <= cJ1_IMMED3_MAXPOP1)
1859 #endif
1860 {
1861 // cJ1_JPIMMED_3_02 : Judy1 32
1862 // cJ1_JPIMMED_7_02 : Judy1 64
1863 // Copy to JP as an immediate Leaf
1864 #ifdef JU_64BIT
1865 j__udyCopyWto7(PjpJP->jp_1Index, Pjlw+Start, 2);
1866 PjpJP->jp_Type = cJ1_JPIMMED_7_02;
1867 #else
1868 j__udyCopyWto3(PjpJP->jp_1Index, Pjlw+Start, 2);
1869 PjpJP->jp_Type = cJ1_JPIMMED_3_02;
1870 #endif // 32 Bit
1871 }
1872 #endif // JUDY1
1873 else // Linear Leaf JPLEAF3[7]
1874 {
1875 // cJU_JPLEAF3[7]
1876 Pjll_t PjllRaw; // pointer to new leaf.
1877 Pjll_t Pjll;
1878 JUDYLCODE(Pjv_t Pjvnew;) // value area of new leaf.
1879 #ifdef JU_64BIT
1880 PjllRaw = j__udyAllocJLL7(Pop1, Pjpm);
1881 if (PjllRaw == (Pjll_t) NULL) return(-1);
1882 Pjll = P_JLL(PjllRaw);
1883
1884 j__udyCopyWto7((uint8_t *) Pjll, Pjlw + Start,
1885 Pop1);
1886 #ifdef JUDYL
1887 Pjvnew = JL_LEAF7VALUEAREA(Pjll, Pop1);
1888 JU_COPYMEM(Pjvnew, Pjv + Start, Pop1);
1889 #endif // JUDYL
1890 DBGCODE(JudyCheckSorted(Pjll, Pop1, 7);)
1891 #else // JU_64BIT - 32 Bit
1892 PjllRaw = j__udyAllocJLL3(Pop1, Pjpm);
1893 if (PjllRaw == (Pjll_t) NULL) return(-1);
1894 Pjll = P_JLL(PjllRaw);
1895
1896 j__udyCopyWto3((uint8_t *) Pjll, Pjlw + Start,
1897 Pop1);
1898 #ifdef JUDYL
1899 Pjvnew = JL_LEAF3VALUEAREA(Pjll, Pop1);
1900 JU_COPYMEM(Pjvnew, Pjv + Start, Pop1);
1901 #endif // JUDYL
1902 DBGCODE(JudyCheckSorted(Pjll, Pop1, 3);)
1903 #endif // 32 Bit
1904
1905 #ifdef JU_64BIT
1906 JU_JPSETADT(PjpJP, (Word_t)PjllRaw, Pop1 - 1,
1907 cJU_JPLEAF7);
1908 #else // JU_64BIT - 32 Bit
1909 JU_JPSETADT(PjpJP, (Word_t)PjllRaw, Pop1 - 1,
1910 cJU_JPLEAF3);
1911 #endif // 32 Bit
1912 }
1913 ExpCnt++;
1914 // Done?
1915 if (End == cJU_LEAFW_MAXPOP1) break;
1916
1917 // New Expanse, Start and Count
1918 CIndex = Pjlw[End];
1919 Start = End;
1920 }
1921 }
1922
1923 // Now put all the Leaves below a BranchL or BranchB:
1924 if (ExpCnt <= cJU_BRANCHLMAXJPS) // put the Leaves below a BranchL
1925 {
1926 if (j__udyCreateBranchL(Pjp, StageJP, StageExp, ExpCnt,
1927 Pjpm) == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1928
1929 Pjp->jp_Type = cJU_JPBRANCH_L;
1930 }
1931 else
1932 {
1933 if (j__udyStageJBBtoJBB(Pjp, &StageJBB, StageJP, SubJPCount, Pjpm)
1934 == -1) FREEALLEXIT(ExpCnt, StageJP, Pjpm);
1935
1936 Pjp->jp_Type = cJU_JPBRANCH_B; // cJU_LEAFW is out of sequence
1937 }
1938 return(1);
1939
1940 } // j__udyCascadeL()
1941