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 // Judy1Set() and JudyLIns() functions for Judy1 and JudyL.
19 // Compile with one of -DJUDY1 or -DJUDYL.
20 //
21 // TBD: Should some of the assertions here be converted to product code that
22 // returns JU_ERRNO_CORRUPT?
23
24 #if (! (defined(JUDY1) || defined(JUDYL)))
25 #error: One of -DJUDY1 or -DJUDYL must be specified.
26 #endif
27
28 #ifdef JUDY1
29 #include "Judy1.h"
30 #else
31 #include "JudyL.h"
32 #endif
33
34 #include "JudyPrivate1L.h"
35
36 // Note: Call JudyCheckPop() even before "already inserted" returns, to catch
37 // population errors; see fix in 4.84:
38
39 DBGCODE(extern void JudyCheckPop(Pvoid_t PArray);)
40 DBGCODE(extern void JudyCheckSorted(Pjll_t Pjll, Word_t Pop1, long IndexSize);)
41
42 #ifdef TRACEJP
43 #include "JudyPrintJP.c"
44 #endif
45
46
47 // These are defined to generic values in JudyCommon/JudyPrivateTypes.h:
48 //
49 // TBD: These should be exported from a header file, but perhaps not, as they
50 // are only used here, and exported from Judy*Decascade, which is a separate
51 // file for profiling reasons (to prevent inlining), but which potentially
52 // could be merged with this file, either in SoftCM or at compile-time.
53
54 #ifdef JUDY1
55 extern int j__udy1CreateBranchB(Pjp_t, Pjp_t, uint8_t *, Word_t, Pvoid_t);
56 extern int j__udy1CreateBranchU(Pjp_t, Pvoid_t);
57
58 #ifndef JU_64BIT
59 extern int j__udy1Cascade1(Pjp_t, Pvoid_t);
60 #endif
61 extern int j__udy1Cascade2(Pjp_t, Pvoid_t);
62 extern int j__udy1Cascade3(Pjp_t, Pvoid_t);
63 #ifdef JU_64BIT
64 extern int j__udy1Cascade4(Pjp_t, Pvoid_t);
65 extern int j__udy1Cascade5(Pjp_t, Pvoid_t);
66 extern int j__udy1Cascade6(Pjp_t, Pvoid_t);
67 extern int j__udy1Cascade7(Pjp_t, Pvoid_t);
68 #endif
69 extern int j__udy1CascadeL(Pjp_t, Pvoid_t);
70
71 extern int j__udy1InsertBranch(Pjp_t Pjp, Word_t Index, Word_t Btype, Pjpm_t);
72
73 #else // JUDYL
74
75 extern int j__udyLCreateBranchB(Pjp_t, Pjp_t, uint8_t *, Word_t, Pvoid_t);
76 extern int j__udyLCreateBranchU(Pjp_t, Pvoid_t);
77
78 extern int j__udyLCascade1(Pjp_t, Pvoid_t);
79 extern int j__udyLCascade2(Pjp_t, Pvoid_t);
80 extern int j__udyLCascade3(Pjp_t, Pvoid_t);
81 #ifdef JU_64BIT
82 extern int j__udyLCascade4(Pjp_t, Pvoid_t);
83 extern int j__udyLCascade5(Pjp_t, Pvoid_t);
84 extern int j__udyLCascade6(Pjp_t, Pvoid_t);
85 extern int j__udyLCascade7(Pjp_t, Pvoid_t);
86 #endif
87 extern int j__udyLCascadeL(Pjp_t, Pvoid_t);
88
89 extern int j__udyLInsertBranch(Pjp_t Pjp, Word_t Index, Word_t Btype, Pjpm_t);
90 #endif
91
92
93 // ****************************************************************************
94 // MACROS FOR COMMON CODE:
95 //
96 // Check if Index is an outlier to (that is, not a member of) this expanse:
97 //
98 // An outlier is an Index in-the-expanse of the slot containing the pointer,
99 // but not-in-the-expanse of the "narrow" pointer in that slot. (This means
100 // the Dcd part of the Index differs from the equivalent part of jp_DcdPopO.)
101 // Therefore, the remedy is to put a cJU_JPBRANCH_L* between the narrow pointer
102 // and the object to which it points, and add the outlier Index as an Immediate
103 // in the cJU_JPBRANCH_L*. The "trick" is placing the cJU_JPBRANCH_L* at a
104 // Level that is as low as possible. This is determined by counting the digits
105 // in the existing narrow pointer that are the same as the digits in the new
106 // Index (see j__udyInsertBranch()).
107 //
108 // Note: At some high Levels, cJU_DCDMASK() is all zeros => dead code; assume
109 // the compiler optimizes this out.
110
111 #define JU_CHECK_IF_OUTLIER(Pjp, Index, cLevel, Pjpm) \
112 if (JU_DCDNOTMATCHINDEX(Index, Pjp, cLevel)) \
113 return(j__udyInsertBranch(Pjp, Index, cLevel, Pjpm))
114
115 // Check if an Index is already in a leaf or immediate, after calling
116 // j__udySearchLeaf*() to set Offset:
117 //
118 // A non-negative Offset means the Index already exists, so return 0; otherwise
119 // complement Offset to proceed.
120
121 #ifdef JUDY1
122 #define Pjv ignore // placeholder.
123 #define JU_CHECK_IF_EXISTS(Offset,ignore,Pjpm) \
124 { \
125 if ((Offset) >= 0) return(0); \
126 (Offset) = ~(Offset); \
127 }
128 #else
129 // For JudyL, also set the value area pointer in the Pjpm:
130
131 #define JU_CHECK_IF_EXISTS(Offset,Pjv,Pjpm) \
132 { \
133 if ((Offset) >= 0) \
134 { \
135 (Pjpm)->jpm_PValue = (Pjv) + (Offset); \
136 return(0); \
137 } \
138 (Offset) = ~(Offset); \
139 }
140 #endif
141
142
143 // ****************************************************************************
144 // __ J U D Y I N S W A L K
145 //
146 // Walk the Judy tree to do a set/insert. This is only called internally, and
147 // recursively. Unlike Judy1Test() and JudyLGet(), the extra time required for
148 // recursion should be negligible compared with the total.
149 //
150 // Return -1 for error (details in JPM), 0 for Index already inserted, 1 for
151 // new Index inserted.
152
j__udyInsWalk(Pjp_t Pjp,Word_t Index,Pjpm_t Pjpm)153 FUNCTION static int j__udyInsWalk(
154 Pjp_t Pjp, // current JP to descend.
155 Word_t Index, // to insert.
156 Pjpm_t Pjpm) // for returning info to top Level.
157 {
158 uint8_t digit; // from Index, current offset into a branch.
159 jp_t newJP; // for creating a new Immed JP.
160 Word_t exppop1; // expanse (leaf) population.
161 int retcode; // return codes: -1, 0, 1.
162
163 #ifdef SUBEXPCOUNTS
164 // Pointer to BranchB/U subexpanse counter:
165 //
166 // Note: Very important for performance reasons (avoids cache fills).
167
168 PWord_t PSubExp = (PWord_t) NULL;
169 #endif
170
171 ContinueInsWalk: // for modifying state without recursing.
172
173 #ifdef TRACEJP
174 JudyPrintJP(Pjp, "i", __LINE__);
175 #endif
176
177 switch (JU_JPTYPE(Pjp)) // entry: Pjp, Index.
178 {
179
180
181 // ****************************************************************************
182 // JPNULL*:
183 //
184 // Convert JP in place from current null type to cJU_JPIMMED_*_01 by
185 // calculating new JP type.
186
187 case cJU_JPNULL1:
188 case cJU_JPNULL2:
189 case cJU_JPNULL3:
190 #ifdef JU_64BIT
191 case cJU_JPNULL4:
192 case cJU_JPNULL5:
193 case cJU_JPNULL6:
194 case cJU_JPNULL7:
195 #endif
196 assert((Pjp->jp_Addr) == 0);
197 JU_JPSETADT(Pjp, 0, Index, JU_JPTYPE(Pjp) + cJU_JPIMMED_1_01 - cJU_JPNULL1);
198 #ifdef JUDYL
199 // value area is first word of new Immed_01 JP:
200 Pjpm->jpm_PValue = (Pjv_t) (&(Pjp->jp_Addr));
201 #endif
202 return(1);
203
204
205 // ****************************************************************************
206 // JPBRANCH_L*:
207 //
208 // If the new Index is not an outlier to the branchs expanse, and the branch
209 // should not be converted to uncompressed, extract the digit and record the
210 // Immediate type to create for a new Immed JP, before going to common code.
211 //
212 // Note: JU_CHECK_IF_OUTLIER() is a no-op for BranchB3[7] on 32[64]-bit.
213
214 #define JU_BRANCH_OUTLIER(DIGIT,POP1,cLEVEL,PJP,INDEX,PJPM) \
215 JU_CHECK_IF_OUTLIER(PJP, INDEX, cLEVEL, PJPM); \
216 (DIGIT) = JU_DIGITATSTATE(INDEX, cLEVEL); \
217 (POP1) = JU_JPBRANCH_POP0(PJP, cLEVEL)
218
219 case cJU_JPBRANCH_L2:
220 JU_BRANCH_OUTLIER(digit, exppop1, 2, Pjp, Index, Pjpm);
221 goto JudyBranchL;
222
223 case cJU_JPBRANCH_L3:
224 JU_BRANCH_OUTLIER(digit, exppop1, 3, Pjp, Index, Pjpm);
225 goto JudyBranchL;
226
227 #ifdef JU_64BIT
228 case cJU_JPBRANCH_L4:
229 JU_BRANCH_OUTLIER(digit, exppop1, 4, Pjp, Index, Pjpm);
230 goto JudyBranchL;
231
232 case cJU_JPBRANCH_L5:
233 JU_BRANCH_OUTLIER(digit, exppop1, 5, Pjp, Index, Pjpm);
234 goto JudyBranchL;
235
236 case cJU_JPBRANCH_L6:
237 JU_BRANCH_OUTLIER(digit, exppop1, 6, Pjp, Index, Pjpm);
238 goto JudyBranchL;
239
240 case cJU_JPBRANCH_L7:
241 JU_BRANCH_OUTLIER(digit, exppop1, 7, Pjp, Index, Pjpm);
242 goto JudyBranchL;
243 #endif
244
245 // Similar to common code above, but no outlier check is needed, and the Immed
246 // type depends on the word size:
247
248 case cJU_JPBRANCH_L:
249 {
250 Pjbl_t PjblRaw; // pointer to old linear branch.
251 Pjbl_t Pjbl;
252 Pjbu_t PjbuRaw; // pointer to new uncompressed branch.
253 Pjbu_t Pjbu;
254 Word_t numJPs; // number of JPs = populated expanses.
255 int offset; // in branch.
256
257 digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
258 exppop1 = Pjpm->jpm_Pop0;
259
260 // fall through:
261
262 // COMMON CODE FOR LINEAR BRANCHES:
263 //
264 // Come here with digit and exppop1 already set.
265
266 JudyBranchL:
267 PjblRaw = (Pjbl_t) (Pjp->jp_Addr);
268 Pjbl = P_JBL(PjblRaw);
269
270 // If population under this branch greater than:
271
272 if (exppop1 > JU_BRANCHL_MAX_POP)
273 goto ConvertBranchLtoU;
274
275 numJPs = Pjbl->jbl_NumJPs;
276
277 if ((numJPs == 0) || (numJPs > cJU_BRANCHLMAXJPS))
278 {
279 JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
280 return(-1);
281 }
282
283 // Search for a match to the digit:
284
285 offset = j__udySearchLeaf1((Pjll_t) (Pjbl->jbl_Expanse), numJPs,
286 digit);
287
288 // If Index is found, offset is into an array of 1..cJU_BRANCHLMAXJPS JPs:
289
290 if (offset >= 0)
291 {
292 Pjp = (Pjbl->jbl_jp) + offset; // address of next JP.
293 break; // continue walk.
294 }
295
296 // Expanse is missing (not populated) for the passed Index, so insert an Immed
297 // -- if theres room:
298
299 if (numJPs < cJU_BRANCHLMAXJPS)
300 {
301 offset = ~offset; // insertion offset.
302
303 JU_JPSETADT(&newJP, 0, Index,
304 JU_JPTYPE(Pjp) + cJU_JPIMMED_1_01-cJU_JPBRANCH_L2);
305
306 JU_INSERTINPLACE(Pjbl->jbl_Expanse, numJPs, offset, digit);
307 JU_INSERTINPLACE(Pjbl->jbl_jp, numJPs, offset, newJP);
308
309 DBGCODE(JudyCheckSorted((Pjll_t) (Pjbl->jbl_Expanse),
310 numJPs + 1, /* IndexSize = */ 1);)
311 ++(Pjbl->jbl_NumJPs);
312 #ifdef JUDYL
313 // value area is first word of new Immed 01 JP:
314 Pjpm->jpm_PValue = (Pjv_t) ((Pjbl->jbl_jp) + offset);
315 #endif
316 return(1);
317 }
318
319
320 // MAXED OUT LINEAR BRANCH, CONVERT TO A BITMAP BRANCH, THEN INSERT:
321 //
322 // Copy the linear branch to a bitmap branch.
323 //
324 // TBD: Consider renaming j__udyCreateBranchB() to j__udyConvertBranchLtoB().
325
326 assert((numJPs) <= cJU_BRANCHLMAXJPS);
327
328 if (j__udyCreateBranchB(Pjp, Pjbl->jbl_jp, Pjbl->jbl_Expanse,
329 numJPs, Pjpm) == -1)
330 {
331 return(-1);
332 }
333
334 // Convert jp_Type from linear branch to equivalent bitmap branch:
335
336 Pjp->jp_Type += cJU_JPBRANCH_B - cJU_JPBRANCH_L;
337
338 j__udyFreeJBL(PjblRaw, Pjpm); // free old BranchL.
339
340 // Having changed branch types, now do the insert in the new branch type:
341
342 goto ContinueInsWalk;
343
344
345 // OPPORTUNISTICALLY CONVERT FROM BRANCHL TO BRANCHU:
346 //
347 // Memory efficiency is no object because the branchs pop1 is large enough, so
348 // speed up array access. Come here with PjblRaw set. Note: This is goto
349 // code because the previous block used to fall through into it as well, but no
350 // longer.
351
352 ConvertBranchLtoU:
353
354 // Allocate memory for an uncompressed branch:
355
356 if ((PjbuRaw = j__udyAllocJBU(Pjpm)) == (Pjbu_t) NULL)
357 return(-1);
358 Pjbu = P_JBU(PjbuRaw);
359
360 // Set the proper NULL type for most of the uncompressed branchs JPs:
361
362 JU_JPSETADT(&newJP, 0, 0,
363 JU_JPTYPE(Pjp) - cJU_JPBRANCH_L2 + cJU_JPNULL1);
364
365 // Initialize: Pre-set uncompressed branch to mostly JPNULL*s:
366
367 for (numJPs = 0; numJPs < cJU_BRANCHUNUMJPS; ++numJPs)
368 Pjbu->jbu_jp[numJPs] = newJP;
369
370 // Copy JPs from linear branch to uncompressed branch:
371
372 {
373 #ifdef SUBEXPCOUNTS
374 Word_t popmask = cJU_POP0MASK(JU_JPTYPE(Pjp))
375 - cJU_JPBRANCH_L2 - 2;
376
377 for (numJPs = 0; numJPs < cJU_NUMSUBEXPU; ++numJPs)
378 Pjbu->jbu_subPop1[numJPs] = 0;
379 #endif
380 for (numJPs = 0; numJPs < Pjbl->jbl_NumJPs; ++numJPs)
381 {
382 Pjp_t Pjp1 = &(Pjbl->jbl_jp[numJPs]);
383 offset = Pjbl->jbl_Expanse[numJPs];
384 Pjbu->jbu_jp[offset] = *Pjp1;
385 #ifdef SUBEXPCOUNTS
386 Pjbu->jbu_subPop1[offset/cJU_NUMSUBEXPU] +=
387 JU_JPDCDPOP0(Pjp1) & popmask + 1;
388 #endif
389 }
390 }
391 j__udyFreeJBL(PjblRaw, Pjpm); // free old BranchL.
392
393 // Plug new values into parent JP:
394
395 Pjp->jp_Addr = (Word_t) PjbuRaw;
396 Pjp->jp_Type += cJU_JPBRANCH_U - cJU_JPBRANCH_L; // to BranchU.
397
398 // Save global population of last BranchU conversion:
399
400 Pjpm->jpm_LastUPop0 = Pjpm->jpm_Pop0;
401 goto ContinueInsWalk;
402
403 } // case cJU_JPBRANCH_L.
404
405
406 // ****************************************************************************
407 // JPBRANCH_B*:
408 //
409 // If the new Index is not an outlier to the branchs expanse, extract the
410 // digit and record the Immediate type to create for a new Immed JP, before
411 // going to common code.
412 //
413 // Note: JU_CHECK_IF_OUTLIER() is a no-op for BranchB3[7] on 32[64]-bit.
414
415 case cJU_JPBRANCH_B2:
416 JU_BRANCH_OUTLIER(digit, exppop1, 2, Pjp, Index, Pjpm);
417 goto JudyBranchB;
418
419 case cJU_JPBRANCH_B3:
420 JU_BRANCH_OUTLIER(digit, exppop1, 3, Pjp, Index, Pjpm);
421 goto JudyBranchB;
422
423 #ifdef JU_64BIT
424 case cJU_JPBRANCH_B4:
425 JU_BRANCH_OUTLIER(digit, exppop1, 4, Pjp, Index, Pjpm);
426 goto JudyBranchB;
427
428 case cJU_JPBRANCH_B5:
429 JU_BRANCH_OUTLIER(digit, exppop1, 5, Pjp, Index, Pjpm);
430 goto JudyBranchB;
431
432 case cJU_JPBRANCH_B6:
433 JU_BRANCH_OUTLIER(digit, exppop1, 6, Pjp, Index, Pjpm);
434 goto JudyBranchB;
435
436 case cJU_JPBRANCH_B7:
437 JU_BRANCH_OUTLIER(digit, exppop1, 7, Pjp, Index, Pjpm);
438 goto JudyBranchB;
439 #endif
440
441 case cJU_JPBRANCH_B:
442 {
443 Pjbb_t Pjbb; // pointer to bitmap branch.
444 Pjbb_t PjbbRaw; // pointer to bitmap branch.
445 Pjp_t Pjp2Raw; // 1 of N arrays of JPs.
446 Pjp_t Pjp2; // 1 of N arrays of JPs.
447 Word_t subexp; // 1 of N subexpanses in bitmap.
448 BITMAPB_t bitmap; // for one subexpanse.
449 BITMAPB_t bitmask; // bit set for Indexs digit.
450 Word_t numJPs; // number of JPs = populated expanses.
451 int offset; // in bitmap branch.
452
453 // Similar to common code above, but no outlier check is needed, and the Immed
454 // type depends on the word size:
455
456 digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
457 exppop1 = Pjpm->jpm_Pop0;
458
459 // fall through:
460
461
462 // COMMON CODE FOR BITMAP BRANCHES:
463 //
464 // Come here with digit and exppop1 already set.
465
466 JudyBranchB:
467
468 // If population increment is greater than.. (300):
469
470 if ((Pjpm->jpm_Pop0 - Pjpm->jpm_LastUPop0) > JU_BTOU_POP_INCREMENT)
471 {
472
473 // If total population of array is greater than.. (750):
474
475 if (Pjpm->jpm_Pop0 > JU_BRANCHB_MAX_POP)
476 {
477
478 // If population under the branch is greater than.. (135):
479
480 if (exppop1 > JU_BRANCHB_MIN_POP)
481 {
482 if (j__udyCreateBranchU(Pjp, Pjpm) == -1) return(-1);
483
484 // Save global population of last BranchU conversion:
485
486 Pjpm->jpm_LastUPop0 = Pjpm->jpm_Pop0;
487
488 goto ContinueInsWalk;
489 }
490 }
491 }
492
493 // CONTINUE TO USE BRANCHB:
494 //
495 // Get pointer to bitmap branch (JBB):
496
497 PjbbRaw = (Pjbb_t) (Pjp->jp_Addr);
498 Pjbb = P_JBB(PjbbRaw);
499
500 // Form the Int32 offset, and Bit offset values:
501 //
502 // 8 bit Decode | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
503 // |SubExpanse | Bit offset |
504 //
505 // Get the 1 of 8 expanses from digit, Bits 5..7 = 1 of 8, and get the 32-bit
506 // word that may have a bit set:
507
508 subexp = digit / cJU_BITSPERSUBEXPB;
509 bitmap = JU_JBB_BITMAP(Pjbb, subexp);
510
511 Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);
512 Pjp2 = P_JP(Pjp2Raw);
513
514 // Get the bit position that represents the desired expanse, and get the offset
515 // into the array of JPs for the JP that matches the bit.
516
517 bitmask = JU_BITPOSMASKB(digit);
518 offset = j__udyCountBitsB(bitmap & (bitmask - 1));
519
520 // If JP is already in this expanse, get Pjp and continue the walk:
521
522 if (bitmap & bitmask)
523 {
524 #ifdef SUBEXPCOUNTS
525 PSubExp = &(Pjbb->jbb_Counts[subexp]); // ptr to subexp counts.
526 #endif
527 Pjp = Pjp2 + offset;
528 break; // continue walk.
529 }
530
531
532 // ADD NEW EXPANSE FOR NEW INDEX:
533 //
534 // The new expanse always an cJU_JPIMMED_*_01 containing just the new Index, so
535 // finish setting up an Immed JP.
536
537 JU_JPSETADT(&newJP, 0, Index,
538 JU_JPTYPE(Pjp) + cJU_JPIMMED_1_01-cJU_JPBRANCH_B2);
539
540 // Get 1 of the 8 JP arrays and calculate number of JPs in subexpanse array:
541
542 Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);
543 Pjp2 = P_JP(Pjp2Raw);
544 numJPs = j__udyCountBitsB(bitmap);
545
546 // Expand branch JP subarray in-place:
547
548 if (JU_BRANCHBJPGROWINPLACE(numJPs))
549 {
550 assert(numJPs > 0);
551 JU_INSERTINPLACE(Pjp2, numJPs, offset, newJP);
552 #ifdef JUDYL
553 // value area is first word of new Immed 01 JP:
554 Pjpm->jpm_PValue = (Pjv_t) (Pjp2 + offset);
555 #endif
556 }
557
558 // No room, allocate a bigger bitmap branch JP subarray:
559
560 else
561 {
562 Pjp_t PjpnewRaw;
563 Pjp_t Pjpnew;
564
565 if ((PjpnewRaw = j__udyAllocJBBJP(numJPs + 1, Pjpm)) == 0)
566 return(-1);
567 Pjpnew = P_JP(PjpnewRaw);
568
569 // If there was an old JP array, then copy it, insert the new Immed JP, and
570 // free the old array:
571
572 if (numJPs)
573 {
574 JU_INSERTCOPY(Pjpnew, Pjp2, numJPs, offset, newJP);
575 j__udyFreeJBBJP(Pjp2Raw, numJPs, Pjpm);
576 #ifdef JUDYL
577 // value area is first word of new Immed 01 JP:
578 Pjpm->jpm_PValue = (Pjv_t) (Pjpnew + offset);
579 #endif
580 }
581
582 // New JP subarray; point to cJU_JPIMMED_*_01 and place it:
583
584 else
585 {
586 assert(JU_JBB_PJP(Pjbb, subexp) == (Pjp_t) NULL);
587 Pjp = Pjpnew;
588 *Pjp = newJP; // copy to new memory.
589 #ifdef JUDYL
590 // value area is first word of new Immed 01 JP:
591 Pjpm->jpm_PValue = (Pjv_t) (&(Pjp->jp_Addr));
592 #endif
593 }
594
595 // Place new JP subarray in BranchB:
596
597 JU_JBB_PJP(Pjbb, subexp) = PjpnewRaw;
598
599 } // else
600
601 // Set the new Indexs bit:
602
603 JU_JBB_BITMAP(Pjbb, subexp) |= bitmask;
604
605 return(1);
606
607 } // case
608
609
610 // ****************************************************************************
611 // JPBRANCH_U*:
612 //
613 // Just drop through the JP for the correct digit. If the JP turns out to be a
614 // JPNULL*, thats OK, the memory is already allocated, and the next walk
615 // simply places an Immed in it.
616 //
617 #ifdef SUBEXPCOUNTS
618 #define JU_GETSUBEXP(PSubExp,Pjbu,Digit) \
619 (PSubExp) = &((Pjbu)->jbu_subPop1[(Digit) / cJU_NUMSUBEXPU])
620 #else
621 #define JU_GETSUBEXP(PSubExp,Pjbu,Digit) // null.
622 #endif
623
624 #define JU_JBU_PJP_SUBEXP(Pjp,PSubExp,Index,Level) \
625 { \
626 uint8_t digit = JU_DIGITATSTATE(Index, Level); \
627 Pjbu_t P_jbu = P_JBU((Pjp)->jp_Addr); \
628 (Pjp) = &(P_jbu->jbu_jp[digit]); \
629 JU_GETSUBEXP(PSubExp, P_jbu, digit); \
630 }
631
632 case cJU_JPBRANCH_U2:
633 JU_CHECK_IF_OUTLIER(Pjp, Index, 2, Pjpm);
634 JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 2);
635 break;
636
637 #ifdef JU_64BIT
638 case cJU_JPBRANCH_U3:
639 JU_CHECK_IF_OUTLIER(Pjp, Index, 3, Pjpm);
640 JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 3);
641 break;
642
643 case cJU_JPBRANCH_U4:
644 JU_CHECK_IF_OUTLIER(Pjp, Index, 4, Pjpm);
645 JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 4);
646 break;
647
648 case cJU_JPBRANCH_U5:
649 JU_CHECK_IF_OUTLIER(Pjp, Index, 5, Pjpm);
650 JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 5);
651 break;
652
653 case cJU_JPBRANCH_U6:
654 JU_CHECK_IF_OUTLIER(Pjp, Index, 6, Pjpm);
655 JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 6);
656 break;
657
658 case cJU_JPBRANCH_U7:
659 JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 7);
660 #else
661 case cJU_JPBRANCH_U3:
662 JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 3);
663 #endif
664 break;
665
666 case cJU_JPBRANCH_U:
667 JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, cJU_ROOTSTATE);
668 break;
669
670
671 // ****************************************************************************
672 // JPLEAF*:
673 //
674 // COMMON CODE FRAGMENTS TO MINIMIZE REDUNDANCY BELOW:
675 //
676 // These are necessary to support performance by function and loop unrolling
677 // while avoiding huge amounts of nearly identical code.
678 //
679 // Prepare to handle a linear leaf: Check for an outlier; set pop1 and pointer
680 // to leaf:
681
682 #ifdef JUDY1
683 #define JU_LEAFVALUE(Pjv) // null.
684 #define JU_LEAFPREPVALUE(Pjv, ValueArea) // null.
685 #else
686 #define JU_LEAFVALUE(Pjv) Pjv_t Pjv
687 #define JU_LEAFPREPVALUE(Pjv, ValueArea) (Pjv) = ValueArea(Pleaf, exppop1)
688 #endif
689
690 #define JU_LEAFPREP(cIS,Type,MaxPop1,ValueArea) \
691 Pjll_t PjllRaw; \
692 Type Pleaf; /* specific type */ \
693 int offset; \
694 JU_LEAFVALUE(Pjv); \
695 \
696 JU_CHECK_IF_OUTLIER(Pjp, Index, cIS, Pjpm); \
697 \
698 exppop1 = JU_JPLEAF_POP0(Pjp) + 1; \
699 assert(exppop1 <= (MaxPop1)); \
700 PjllRaw = (Pjll_t) (Pjp->jp_Addr); \
701 Pleaf = (Type) P_JLL(PjllRaw); \
702 JU_LEAFPREPVALUE(Pjv, ValueArea)
703
704 // Add to, or grow, a linear leaf: Find Index position; if the Index is
705 // absent, if theres room in the leaf, insert the Index [and value of 0] in
706 // place, otherwise grow the leaf:
707 //
708 // Note: These insertions always take place with whole words, using
709 // JU_INSERTINPLACE() or JU_INSERTCOPY().
710
711 #ifdef JUDY1
712 #define JU_LEAFGROWVALUEADD(Pjv,ExpPop1,Offset) // null.
713 #else
714 #define JU_LEAFGROWVALUEADD(Pjv,ExpPop1,Offset) \
715 JU_INSERTINPLACE(Pjv, ExpPop1, Offset, 0); \
716 Pjpm->jpm_PValue = (Pjv) + (Offset)
717 #endif
718
719 #ifdef JUDY1
720 #define JU_LEAFGROWVALUENEW(ValueArea,Pjv,ExpPop1,Offset) // null.
721 #else
722 #define JU_LEAFGROWVALUENEW(ValueArea,Pjv,ExpPop1,Offset) \
723 { \
724 Pjv_t Pjvnew = ValueArea(Pleafnew, (ExpPop1) + 1); \
725 JU_INSERTCOPY(Pjvnew, Pjv, ExpPop1, Offset, 0); \
726 Pjpm->jpm_PValue = (Pjvnew) + (Offset); \
727 }
728 #endif
729
730 #define JU_LEAFGROW(cIS,Type,MaxPop1,Search,ValueArea,GrowInPlace, \
731 InsertInPlace,InsertCopy,Alloc,Free) \
732 \
733 offset = Search(Pleaf, exppop1, Index); \
734 JU_CHECK_IF_EXISTS(offset, Pjv, Pjpm); \
735 \
736 if (GrowInPlace(exppop1)) /* add to current leaf */ \
737 { \
738 InsertInPlace(Pleaf, exppop1, offset, Index); \
739 JU_LEAFGROWVALUEADD(Pjv, exppop1, offset); \
740 DBGCODE(JudyCheckSorted((Pjll_t) Pleaf, exppop1 + 1, cIS);) \
741 return(1); \
742 } \
743 \
744 if (exppop1 < (MaxPop1)) /* grow to new leaf */ \
745 { \
746 Pjll_t PjllnewRaw; \
747 Type Pleafnew; \
748 if ((PjllnewRaw = Alloc(exppop1 + 1, Pjpm)) == 0) return(-1); \
749 Pleafnew = (Type) P_JLL(PjllnewRaw); \
750 InsertCopy(Pleafnew, Pleaf, exppop1, offset, Index); \
751 JU_LEAFGROWVALUENEW(ValueArea, Pjv, exppop1, offset); \
752 DBGCODE(JudyCheckSorted((Pjll_t) Pleafnew, exppop1 + 1, cIS);) \
753 Free(PjllRaw, exppop1, Pjpm); \
754 (Pjp->jp_Addr) = (Word_t) PjllnewRaw; \
755 return(1); \
756 } \
757 assert(exppop1 == (MaxPop1))
758
759 // Handle linear leaf overflow (cascade): Splay or compress into smaller
760 // leaves:
761
762 #define JU_LEAFCASCADE(MaxPop1,Cascade,Free) \
763 if (Cascade(Pjp, Pjpm) == -1) return(-1); \
764 Free(PjllRaw, MaxPop1, Pjpm); \
765 goto ContinueInsWalk
766
767 // Wrapper around all of the above:
768
769 #define JU_LEAFSET(cIS,Type,MaxPop1,Search,GrowInPlace,InsertInPlace, \
770 InsertCopy,Cascade,Alloc,Free,ValueArea) \
771 { \
772 JU_LEAFPREP(cIS,Type,MaxPop1,ValueArea); \
773 JU_LEAFGROW(cIS,Type,MaxPop1,Search,ValueArea,GrowInPlace, \
774 InsertInPlace,InsertCopy,Alloc,Free); \
775 JU_LEAFCASCADE(MaxPop1,Cascade,Free); \
776 }
777
778 // END OF MACROS; LEAFL CASES START HERE:
779 //
780 // 64-bit Judy1 does not have 1-byte leaves:
781
782 #if (defined(JUDYL) || (! defined(JU_64BIT)))
783
784 case cJU_JPLEAF1:
785
786 JU_LEAFSET(1, uint8_t *, cJU_LEAF1_MAXPOP1, j__udySearchLeaf1,
787 JU_LEAF1GROWINPLACE, JU_INSERTINPLACE, JU_INSERTCOPY,
788 j__udyCascade1, j__udyAllocJLL1, j__udyFreeJLL1,
789 JL_LEAF1VALUEAREA);
790
791 #endif // (JUDYL || ! JU_64BIT)
792
793 case cJU_JPLEAF2:
794
795 JU_LEAFSET(2, uint16_t *, cJU_LEAF2_MAXPOP1, j__udySearchLeaf2,
796 JU_LEAF2GROWINPLACE, JU_INSERTINPLACE, JU_INSERTCOPY,
797 j__udyCascade2, j__udyAllocJLL2, j__udyFreeJLL2,
798 JL_LEAF2VALUEAREA);
799
800 case cJU_JPLEAF3:
801
802 JU_LEAFSET(3, uint8_t *, cJU_LEAF3_MAXPOP1, j__udySearchLeaf3,
803 JU_LEAF3GROWINPLACE, JU_INSERTINPLACE3, JU_INSERTCOPY3,
804 j__udyCascade3, j__udyAllocJLL3, j__udyFreeJLL3,
805 JL_LEAF3VALUEAREA);
806
807 #ifdef JU_64BIT
808 case cJU_JPLEAF4:
809
810 JU_LEAFSET(4, uint32_t *, cJU_LEAF4_MAXPOP1, j__udySearchLeaf4,
811 JU_LEAF4GROWINPLACE, JU_INSERTINPLACE, JU_INSERTCOPY,
812 j__udyCascade4, j__udyAllocJLL4, j__udyFreeJLL4,
813 JL_LEAF4VALUEAREA);
814
815 case cJU_JPLEAF5:
816
817 JU_LEAFSET(5, uint8_t *, cJU_LEAF5_MAXPOP1, j__udySearchLeaf5,
818 JU_LEAF5GROWINPLACE, JU_INSERTINPLACE5, JU_INSERTCOPY5,
819 j__udyCascade5, j__udyAllocJLL5, j__udyFreeJLL5,
820 JL_LEAF5VALUEAREA);
821
822 case cJU_JPLEAF6:
823
824 JU_LEAFSET(6, uint8_t *, cJU_LEAF6_MAXPOP1, j__udySearchLeaf6,
825 JU_LEAF6GROWINPLACE, JU_INSERTINPLACE6, JU_INSERTCOPY6,
826 j__udyCascade6, j__udyAllocJLL6, j__udyFreeJLL6,
827 JL_LEAF6VALUEAREA);
828
829 case cJU_JPLEAF7:
830
831 JU_LEAFSET(7, uint8_t *, cJU_LEAF7_MAXPOP1, j__udySearchLeaf7,
832 JU_LEAF7GROWINPLACE, JU_INSERTINPLACE7, JU_INSERTCOPY7,
833 j__udyCascade7, j__udyAllocJLL7, j__udyFreeJLL7,
834 JL_LEAF7VALUEAREA);
835 #endif // JU_64BIT
836
837
838 // ****************************************************************************
839 // JPLEAF_B1:
840 //
841 // 8 bit Decode | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
842 // |SubExpanse | Bit offset |
843 //
844 // Note: For JudyL, values are stored in 8 subexpanses, each a linear word
845 // array of up to 32 values each.
846
847 case cJU_JPLEAF_B1:
848 {
849 #ifdef JUDYL
850 Pjv_t PjvRaw; // pointer to value part of the leaf.
851 Pjv_t Pjv; // pointer to value part of the leaf.
852 Pjv_t PjvnewRaw; // new value area.
853 Pjv_t Pjvnew; // new value area.
854 Word_t subexp; // 1 of 8 subexpanses in bitmap.
855 Pjlb_t Pjlb; // pointer to bitmap part of the leaf.
856 BITMAPL_t bitmap; // for one subexpanse.
857 BITMAPL_t bitmask; // bit set for Indexs digit.
858 int offset; // of index in value area.
859 #endif
860
861 JU_CHECK_IF_OUTLIER(Pjp, Index, 1, Pjpm);
862
863 #ifdef JUDY1
864
865 // If Index (bit) is already set, return now:
866
867 if (JU_BITMAPTESTL(P_JLB(Pjp->jp_Addr), Index)) return(0);
868
869 // If bitmap is not full, set the new Indexs bit; otherwise convert to a Full:
870
871 if ((exppop1 = JU_JPLEAF_POP0(Pjp) + 1)
872 < cJU_JPFULLPOPU1_POP0)
873 {
874 JU_BITMAPSETL(P_JLB(Pjp->jp_Addr), Index);
875 }
876 else
877 {
878 j__udyFreeJLB1((Pjlb_t) (Pjp->jp_Addr), Pjpm); // free LeafB1.
879 Pjp->jp_Type = cJ1_JPFULLPOPU1;
880 Pjp->jp_Addr = 0;
881 }
882
883 #else // JUDYL
884
885 // This is very different from Judy1 because of the need to return a value area
886 // even for an existing Index, or manage the value area for a new Index, and
887 // because JudyL has no Full type:
888
889 // Get last byte to decode from Index, and pointer to bitmap leaf:
890
891 digit = JU_DIGITATSTATE(Index, 1);
892 Pjlb = P_JLB(Pjp->jp_Addr);
893
894 // Prepare additional values:
895
896 subexp = digit / cJU_BITSPERSUBEXPL; // which subexpanse.
897 bitmap = JU_JLB_BITMAP(Pjlb, subexp); // subexps 32-bit map.
898 PjvRaw = JL_JLB_PVALUE(Pjlb, subexp); // corresponding values.
899 Pjv = P_JV(PjvRaw); // corresponding values.
900 bitmask = JU_BITPOSMASKL(digit); // mask for Index.
901 offset = j__udyCountBitsL(bitmap & (bitmask - 1)); // of Index.
902
903 // If Index already exists, get value pointer and exit:
904
905 if (bitmap & bitmask)
906 {
907 assert(Pjv);
908 Pjpm->jpm_PValue = Pjv + offset; // existing value.
909 return(0);
910 }
911
912 // Get the total bits set = expanse population of Value area:
913
914 exppop1 = j__udyCountBitsL(bitmap);
915
916 // If the value area can grow in place, do it:
917
918 if (JL_LEAFVGROWINPLACE(exppop1))
919 {
920 JU_INSERTINPLACE(Pjv, exppop1, offset, 0);
921 JU_JLB_BITMAP(Pjlb, subexp) |= bitmask; // set Indexs bit.
922 Pjpm->jpm_PValue = Pjv + offset; // new value area.
923 return(1);
924 }
925
926 // Increase size of value area:
927
928 if ((PjvnewRaw = j__udyLAllocJV(exppop1 + 1, Pjpm))
929 == (Pjv_t) NULL) return(-1);
930 Pjvnew = P_JV(PjvnewRaw);
931
932 if (exppop1) // have existing value area.
933 {
934 assert(Pjv);
935 JU_INSERTCOPY(Pjvnew, Pjv, exppop1, offset, 0);
936 Pjpm->jpm_PValue = Pjvnew + offset;
937 j__udyLFreeJV(PjvRaw, exppop1, Pjpm); // free old values.
938 }
939 else // first index, new value area:
940 {
941 Pjpm->jpm_PValue = Pjvnew;
942 *(Pjpm->jpm_PValue) = 0;
943 }
944
945 // Set bit for new Index and place new leaf value area in bitmap:
946
947 JU_JLB_BITMAP(Pjlb, subexp) |= bitmask;
948 JL_JLB_PVALUE(Pjlb, subexp) = PjvnewRaw;
949
950 #endif // JUDYL
951
952 return(1);
953
954 } // case
955
956
957 #ifdef JUDY1
958 // ****************************************************************************
959 // JPFULLPOPU1:
960 //
961 // If Index is not an outlier, then by definition its already set.
962
963 case cJ1_JPFULLPOPU1:
964
965 JU_CHECK_IF_OUTLIER(Pjp, Index, 1, Pjpm);
966 return(0);
967 #endif
968
969
970 // ****************************************************************************
971 // JPIMMED*:
972 //
973 // This is some of the most complex code in Judy considering Judy1 versus JudyL
974 // and 32-bit versus 64-bit variations. The following comments attempt to make
975 // this clearer.
976 //
977 // Of the 2 words in a JP, for immediate indexes Judy1 can use 2 words - 1 byte
978 // = 7 [15] bytes, but JudyL can only use 1 word - 1 byte = 3 [7] bytes because
979 // the other word is needed for a value area or a pointer to a value area.
980 //
981 // For both Judy1 and JudyL, cJU_JPIMMED_*_01 indexes are in word 2; otherwise
982 // for Judy1 only, a list of 2 or more indexes starts in word 1. JudyL keeps
983 // the list in word 2 because word 1 is a pointer (to a LeafV, that is, a leaf
984 // containing only values). Furthermore, cJU_JPIMMED_*_01 indexes are stored
985 // all-but-first-byte in jp_DcdPopO, not just the Index Sizes bytes.
986 //
987 // TBD: This can be confusing because Doug didnt use data structures for it.
988 // Instead he often directly accesses Pjp for the first word and jp_DcdPopO for
989 // the second word. It would be nice to use data structs, starting with
990 // jp_1Index and jp_LIndex where possible.
991 //
992 // Maximum Immed JP types for Judy1/JudyL, depending on Index Size (cIS):
993 //
994 // 32-bit 64-bit
995 //
996 // bytes: 7/ 3 15/ 7 (Judy1/JudyL)
997 //
998 // cIS
999 // 1_ 07/03 15/07 (as in: cJ1_JPIMMED_1_07)
1000 // 2_ 03/01 07/03
1001 // 3_ 02/01 05/02
1002 // 4_ 03/01
1003 // 5_ 03/01
1004 // 6_ 02/01
1005 // 7_ 02/01
1006 //
1007 // State transitions while inserting an Index, matching the above table:
1008 // (Yes, this is very terse... Study it and it will make sense.)
1009 // (Note, parts of this diagram are repeated below for quick reference.)
1010 //
1011 // +-- reformat JP here for Judy1 only, from word-2 to word-1
1012 // |
1013 // | JUDY1 || JU_64BIT JUDY1 && JU_64BIT
1014 // V
1015 // 1_01 => 1_02 => 1_03 => [ 1_04 => ... => 1_07 => [ 1_08..15 => ]] Leaf1 (*)
1016 // 2_01 => [ 2_02 => 2_03 => [ 2_04..07 => ]] Leaf2
1017 // 3_01 => [ 3_02 => [ 3_03..05 => ]] Leaf3
1018 // JU_64BIT only:
1019 // 4_01 => [[ 4_02..03 => ]] Leaf4
1020 // 5_01 => [[ 5_02..03 => ]] Leaf5
1021 // 6_01 => [[ 6_02 => ]] Leaf6
1022 // 7_01 => [[ 7_02 => ]] Leaf7
1023 //
1024 // (*) For Judy1 & 64-bit, go directly from cJU_JPIMMED_1_15 to a LeafB1; skip
1025 // Leaf1, as described in Judy1.h regarding cJ1_JPLEAF1.
1026
1027
1028 // COMMON CODE FRAGMENTS TO MINIMIZE REDUNDANCY BELOW:
1029 //
1030 // These are necessary to support performance by function and loop unrolling
1031 // while avoiding huge amounts of nearly identical code.
1032 //
1033 // The differences between Judy1 and JudyL with respect to value area handling
1034 // are just too large for completely common code between them... Oh well, some
1035 // big ifdefs follow. However, even in the following ifdefd code, use cJU_*,
1036 // JU_*, and Judy*() instead of cJ1_* / cJL_*, J1_* / JL_*, and
1037 // Judy1*()/JudyL*(), for minimum diffs.
1038 //
1039 // Handle growth of cJU_JPIMMED_*_01 to cJU_JPIMMED_*_02, for an even or odd
1040 // Index Size (cIS), given oldIndex, Index, and Pjll in the context:
1041 //
1042 // Put oldIndex and Index in their proper order. For odd indexes, must copy
1043 // bytes.
1044
1045 #ifdef JUDY1
1046
1047 #define JU_IMMSET_01_COPY_EVEN(ignore1,ignore2) \
1048 if (oldIndex < Index) { Pjll[0] = oldIndex; Pjll[1] = Index; } \
1049 else { Pjll[0] = Index; Pjll[1] = oldIndex; }
1050
1051 #define JU_IMMSET_01_COPY_ODD(cIS,CopyWord) \
1052 if (oldIndex < Index) \
1053 { \
1054 CopyWord(Pjll + 0, oldIndex); \
1055 CopyWord(Pjll + (cIS), Index); \
1056 } \
1057 else \
1058 { \
1059 CopyWord(Pjll + 0, Index); \
1060 CopyWord(Pjll + (cIS), oldIndex); \
1061 }
1062
1063 // The "real" *_01 Copy macro:
1064 //
1065 // Trim the high byte off Index, look for a match with the old Index, and if
1066 // none, insert the new Index in the leaf in the correct place, given Pjp and
1067 // Index in the context.
1068 //
1069 // Note: A single immediate index lives in the jp_DcdPopO field, but two or
1070 // more reside starting at Pjp->jp_1Index.
1071
1072 #define JU_IMMSET_01_COPY(cIS,LeafType,NewJPType,Copy,CopyWord) \
1073 { \
1074 LeafType Pjll; \
1075 Word_t oldIndex = JU_JPDCDPOP0(Pjp); \
1076 \
1077 Index = JU_TRIMTODCDSIZE(Index); \
1078 if (oldIndex == Index) return(0); \
1079 \
1080 Pjll = (LeafType) (Pjp->jp_1Index); \
1081 Copy(cIS,CopyWord); \
1082 DBGCODE(JudyCheckSorted(Pjll, 2, cIS);) \
1083 \
1084 Pjp->jp_Type = (NewJPType); \
1085 return(1); \
1086 }
1087
1088 #else // JUDYL
1089
1090 // Variations to also handle value areas; see comments above:
1091 //
1092 // For JudyL, Pjv (start of value area) and oldValue are also in the context;
1093 // leave Pjv set to the value area for Index.
1094
1095 #define JU_IMMSET_01_COPY_EVEN(cIS,CopyWord) \
1096 if (oldIndex < Index) \
1097 { \
1098 Pjll[0] = oldIndex; \
1099 Pjv [0] = oldValue; \
1100 Pjll[1] = Index; \
1101 ++Pjv; \
1102 } \
1103 else \
1104 { \
1105 Pjll[0] = Index; \
1106 Pjll[1] = oldIndex; \
1107 Pjv [1] = oldValue; \
1108 }
1109
1110 #define JU_IMMSET_01_COPY_ODD(cIS,CopyWord) \
1111 if (oldIndex < Index) \
1112 { \
1113 CopyWord(Pjll + 0, oldIndex); \
1114 CopyWord(Pjll + (cIS), Index); \
1115 Pjv[0] = oldValue; \
1116 ++Pjv; \
1117 } \
1118 else \
1119 { \
1120 CopyWord(Pjll + 0, Index); \
1121 CopyWord(Pjll + (cIS), oldIndex); \
1122 Pjv[1] = oldValue; \
1123 }
1124
1125 // The old value area is in the first word (*Pjp), and Pjv and Pjpm are also in
1126 // the context. Also, unlike Judy1, indexes remain in word 2 (jp_LIndex),
1127 // meaning insert-in-place rather than copy.
1128 //
1129 // Return jpm_PValue pointing to Indexs value area. If Index is new, allocate
1130 // a 2-value-leaf and attach it to the JP.
1131
1132 #define JU_IMMSET_01_COPY(cIS,LeafType,NewJPType,Copy,CopyWord) \
1133 { \
1134 LeafType Pjll; \
1135 Word_t oldIndex = JU_JPDCDPOP0(Pjp); \
1136 Word_t oldValue; \
1137 Pjv_t PjvRaw; \
1138 Pjv_t Pjv; \
1139 \
1140 Index = JU_TRIMTODCDSIZE(Index); \
1141 \
1142 if (oldIndex == Index) \
1143 { \
1144 Pjpm->jpm_PValue = (Pjv_t) Pjp; \
1145 return(0); \
1146 } \
1147 \
1148 if ((PjvRaw = j__udyLAllocJV(2, Pjpm)) == (Pjv_t) NULL) \
1149 return(-1); \
1150 Pjv = P_JV(PjvRaw); \
1151 \
1152 oldValue = Pjp->jp_Addr; \
1153 (Pjp->jp_Addr) = (Word_t) PjvRaw; \
1154 Pjll = (LeafType) (Pjp->jp_LIndex); \
1155 \
1156 Copy(cIS,CopyWord); \
1157 DBGCODE(JudyCheckSorted(Pjll, 2, cIS);) \
1158 \
1159 Pjp->jp_Type = (NewJPType); \
1160 *Pjv = 0; \
1161 Pjpm->jpm_PValue = Pjv; \
1162 return(1); \
1163 }
1164
1165 // The following is a unique mix of JU_IMMSET_01() and JU_IMMSETCASCADE() for
1166 // going from cJU_JPIMMED_*_01 directly to a cJU_JPLEAF* for JudyL:
1167 //
1168 // If Index is not already set, allocate a leaf, copy the old and new indexes
1169 // into it, clear and return the new value area, and modify the current JP.
1170 // Note that jp_DcdPop is set to a pop0 of 0 for now, and incremented later.
1171
1172
1173 #define JU_IMMSET_01_CASCADE(cIS,LeafType,NewJPType,ValueArea, \
1174 Copy,CopyWord,Alloc) \
1175 { \
1176 Word_t D_P0; \
1177 LeafType PjllRaw; \
1178 LeafType Pjll; \
1179 Word_t oldIndex = JU_JPDCDPOP0(Pjp); \
1180 Word_t oldValue; \
1181 Pjv_t Pjv; \
1182 \
1183 Index = JU_TRIMTODCDSIZE(Index); \
1184 \
1185 if (oldIndex == Index) \
1186 { \
1187 Pjpm->jpm_PValue = (Pjv_t) (&(Pjp->jp_Addr)); \
1188 return(0); \
1189 } \
1190 \
1191 if ((PjllRaw = (LeafType) Alloc(2, Pjpm)) == (LeafType) NULL) \
1192 return(-1); \
1193 Pjll = (LeafType) P_JLL(PjllRaw); \
1194 Pjv = ValueArea(Pjll, 2); \
1195 \
1196 oldValue = Pjp->jp_Addr; \
1197 \
1198 Copy(cIS,CopyWord); \
1199 DBGCODE(JudyCheckSorted(Pjll, 2, cIS);) \
1200 \
1201 *Pjv = 0; \
1202 Pjpm->jpm_PValue = Pjv; \
1203 D_P0 = Index & cJU_DCDMASK(cIS); /* pop0 = 0 */ \
1204 JU_JPSETADT(Pjp, (Word_t)PjllRaw, D_P0, NewJPType); \
1205 \
1206 return(1); \
1207 }
1208
1209 #endif // JUDYL
1210
1211 // Handle growth of cJU_JPIMMED_*_[02..15]:
1212
1213 #ifdef JUDY1
1214
1215 // Insert an Index into an immediate JP that has room for more, if the Index is
1216 // not already present; given Pjp, Index, exppop1, Pjv, and Pjpm in the
1217 // context:
1218 //
1219 // Note: Use this only when the JP format doesnt change, that is, going from
1220 // cJU_JPIMMED_X_0Y to cJU_JPIMMED_X_0Z, where X >= 2 and Y+1 = Z.
1221 //
1222 // Note: Incrementing jp_Type is how to increase the Index population.
1223
1224 #define JU_IMMSETINPLACE(cIS,LeafType,BaseJPType_02,Search,InsertInPlace) \
1225 { \
1226 LeafType Pjll; \
1227 int offset; \
1228 \
1229 exppop1 = JU_JPTYPE(Pjp) - (BaseJPType_02) + 2; \
1230 offset = Search((Pjll_t) (Pjp->jp_1Index), exppop1, Index); \
1231 \
1232 JU_CHECK_IF_EXISTS(offset, ignore, Pjpm); \
1233 \
1234 Pjll = (LeafType) (Pjp->jp_1Index); \
1235 InsertInPlace(Pjll, exppop1, offset, Index); \
1236 DBGCODE(JudyCheckSorted(Pjll, exppop1 + 1, cIS);) \
1237 ++(Pjp->jp_Type); \
1238 return(1); \
1239 }
1240
1241 // Insert an Index into an immediate JP that has no room for more:
1242 //
1243 // If the Index is not already present, do a cascade (to a leaf); given Pjp,
1244 // Index, Pjv, and Pjpm in the context.
1245
1246
1247 #define JU_IMMSETCASCADE(cIS,OldPop1,LeafType,NewJPType, \
1248 ignore,Search,InsertCopy,Alloc) \
1249 { \
1250 Word_t D_P0; \
1251 Pjll_t PjllRaw; \
1252 Pjll_t Pjll; \
1253 int offset; \
1254 \
1255 offset = Search((Pjll_t) (Pjp->jp_1Index), (OldPop1), Index); \
1256 JU_CHECK_IF_EXISTS(offset, ignore, Pjpm); \
1257 \
1258 if ((PjllRaw = Alloc((OldPop1) + 1, Pjpm)) == 0) return(-1); \
1259 Pjll = P_JLL(PjllRaw); \
1260 \
1261 InsertCopy((LeafType) Pjll, (LeafType) (Pjp->jp_1Index), \
1262 OldPop1, offset, Index); \
1263 DBGCODE(JudyCheckSorted(Pjll, (OldPop1) + 1, cIS);) \
1264 \
1265 D_P0 = (Index & cJU_DCDMASK(cIS)) + (OldPop1) - 1; \
1266 JU_JPSETADT(Pjp, (Word_t)PjllRaw, D_P0, NewJPType); \
1267 return(1); \
1268 }
1269
1270 #else // JUDYL
1271
1272 // Variations to also handle value areas; see comments above:
1273 //
1274 // For JudyL, Pjv (start of value area) is also in the context.
1275 //
1276 // TBD: This code makes a true but weak assumption that a JudyL 32-bit 2-index
1277 // value area must be copied to a new 3-index value area. AND it doesnt know
1278 // anything about JudyL 64-bit cases (cJU_JPIMMED_1_0[3-7] only) where the
1279 // value area can grow in place! However, this should not break it, just slow
1280 // it down.
1281
1282 #define JU_IMMSETINPLACE(cIS,LeafType,BaseJPType_02,Search,InsertInPlace) \
1283 { \
1284 LeafType Pleaf; \
1285 int offset; \
1286 Pjv_t PjvRaw; \
1287 Pjv_t Pjv; \
1288 Pjv_t PjvnewRaw; \
1289 Pjv_t Pjvnew; \
1290 \
1291 exppop1 = JU_JPTYPE(Pjp) - (BaseJPType_02) + 2; \
1292 offset = Search((Pjll_t) (Pjp->jp_LIndex), exppop1, Index); \
1293 PjvRaw = (Pjv_t) (Pjp->jp_Addr); \
1294 Pjv = P_JV(PjvRaw); \
1295 \
1296 JU_CHECK_IF_EXISTS(offset, Pjv, Pjpm); \
1297 \
1298 if ((PjvnewRaw = j__udyLAllocJV(exppop1 + 1, Pjpm)) \
1299 == (Pjv_t) NULL) return(-1); \
1300 Pjvnew = P_JV(PjvnewRaw); \
1301 \
1302 Pleaf = (LeafType) (Pjp->jp_LIndex); \
1303 \
1304 InsertInPlace(Pleaf, exppop1, offset, Index); \
1305 /* see TBD above about this: */ \
1306 JU_INSERTCOPY(Pjvnew, Pjv, exppop1, offset, 0); \
1307 DBGCODE(JudyCheckSorted(Pleaf, exppop1 + 1, cIS);) \
1308 j__udyLFreeJV(PjvRaw, exppop1, Pjpm); \
1309 Pjp->jp_Addr = (Word_t) PjvnewRaw; \
1310 Pjpm->jpm_PValue = Pjvnew + offset; \
1311 \
1312 ++(Pjp->jp_Type); \
1313 return(1); \
1314 }
1315
1316 #define JU_IMMSETCASCADE(cIS,OldPop1,LeafType,NewJPType, \
1317 ValueArea,Search,InsertCopy,Alloc) \
1318 { \
1319 Word_t D_P0; \
1320 Pjll_t PjllRaw; \
1321 Pjll_t Pjll; \
1322 int offset; \
1323 Pjv_t PjvRaw; \
1324 Pjv_t Pjv; \
1325 Pjv_t Pjvnew; \
1326 \
1327 PjvRaw = (Pjv_t) (Pjp->jp_Addr); \
1328 Pjv = P_JV(PjvRaw); \
1329 offset = Search((Pjll_t) (Pjp->jp_LIndex), (OldPop1), Index); \
1330 JU_CHECK_IF_EXISTS(offset, Pjv, Pjpm); \
1331 \
1332 if ((PjllRaw = Alloc((OldPop1) + 1, Pjpm)) == 0) \
1333 return(-1); \
1334 Pjll = P_JLL(PjllRaw); \
1335 InsertCopy((LeafType) Pjll, (LeafType) (Pjp->jp_LIndex), \
1336 OldPop1, offset, Index); \
1337 DBGCODE(JudyCheckSorted(Pjll, (OldPop1) + 1, cIS);) \
1338 \
1339 Pjvnew = ValueArea(Pjll, (OldPop1) + 1); \
1340 JU_INSERTCOPY(Pjvnew, Pjv, OldPop1, offset, 0); \
1341 j__udyLFreeJV(PjvRaw, (OldPop1), Pjpm); \
1342 Pjpm->jpm_PValue = Pjvnew + offset; \
1343 \
1344 D_P0 = (Index & cJU_DCDMASK(cIS)) + (OldPop1) - 1; \
1345 JU_JPSETADT(Pjp, (Word_t)PjllRaw, D_P0, NewJPType); \
1346 return(1); \
1347 }
1348
1349 #endif // JUDYL
1350
1351 // Common convenience/shorthand wrappers around JU_IMMSET_01_COPY() for
1352 // even/odd index sizes:
1353
1354 #define JU_IMMSET_01( cIS, LeafType, NewJPType) \
1355 JU_IMMSET_01_COPY(cIS, LeafType, NewJPType, JU_IMMSET_01_COPY_EVEN, \
1356 ignore)
1357
1358 #define JU_IMMSET_01_ODD( cIS, NewJPType, CopyWord) \
1359 JU_IMMSET_01_COPY(cIS, uint8_t *, NewJPType, JU_IMMSET_01_COPY_ODD, \
1360 CopyWord)
1361
1362
1363 // END OF MACROS; IMMED CASES START HERE:
1364
1365 // cJU_JPIMMED_*_01 cases:
1366 //
1367 // 1_01 always leads to 1_02:
1368 //
1369 // (1_01 => 1_02 => 1_03 => [ 1_04 => ... => 1_07 => [ 1_08..15 => ]] LeafL)
1370
1371 case cJU_JPIMMED_1_01: JU_IMMSET_01(1, uint8_t *, cJU_JPIMMED_1_02);
1372
1373 // 2_01 leads to 2_02, and 3_01 leads to 3_02, except for JudyL 32-bit, where
1374 // they lead to a leaf:
1375 //
1376 // (2_01 => [ 2_02 => 2_03 => [ 2_04..07 => ]] LeafL)
1377 // (3_01 => [ 3_02 => [ 3_03..05 => ]] LeafL)
1378
1379 #if (defined(JUDY1) || defined(JU_64BIT))
1380 case cJU_JPIMMED_2_01: JU_IMMSET_01(2, uint16_t *, cJU_JPIMMED_2_02);
1381 case cJU_JPIMMED_3_01: JU_IMMSET_01_ODD (3, cJU_JPIMMED_3_02,
1382 JU_COPY3_LONG_TO_PINDEX);
1383 #else
1384 case cJU_JPIMMED_2_01:
1385 JU_IMMSET_01_CASCADE(2, uint16_t *, cJU_JPLEAF2, JL_LEAF2VALUEAREA,
1386 JU_IMMSET_01_COPY_EVEN, ignore,
1387 j__udyAllocJLL2);
1388 case cJU_JPIMMED_3_01:
1389 JU_IMMSET_01_CASCADE(3, uint8_t *, cJU_JPLEAF3, JL_LEAF3VALUEAREA,
1390 JU_IMMSET_01_COPY_ODD,
1391 JU_COPY3_LONG_TO_PINDEX, j__udyAllocJLL3);
1392 #endif
1393
1394 #ifdef JU_64BIT
1395
1396 // [4-7]_01 lead to [4-7]_02 for Judy1, and to leaves for JudyL:
1397 //
1398 // (4_01 => [[ 4_02..03 => ]] LeafL)
1399 // (5_01 => [[ 5_02..03 => ]] LeafL)
1400 // (6_01 => [[ 6_02 => ]] LeafL)
1401 // (7_01 => [[ 7_02 => ]] LeafL)
1402
1403 #ifdef JUDY1
1404 case cJU_JPIMMED_4_01: JU_IMMSET_01(4, uint32_t *, cJ1_JPIMMED_4_02);
1405 case cJU_JPIMMED_5_01: JU_IMMSET_01_ODD(5, cJ1_JPIMMED_5_02,
1406 JU_COPY5_LONG_TO_PINDEX);
1407 case cJU_JPIMMED_6_01: JU_IMMSET_01_ODD(6, cJ1_JPIMMED_6_02,
1408 JU_COPY6_LONG_TO_PINDEX);
1409 case cJU_JPIMMED_7_01: JU_IMMSET_01_ODD(7, cJ1_JPIMMED_7_02,
1410 JU_COPY7_LONG_TO_PINDEX);
1411 #else // JUDYL
1412 case cJU_JPIMMED_4_01:
1413 JU_IMMSET_01_CASCADE(4, uint32_t *, cJU_JPLEAF4, JL_LEAF4VALUEAREA,
1414 JU_IMMSET_01_COPY_EVEN, ignore,
1415 j__udyAllocJLL4);
1416 case cJU_JPIMMED_5_01:
1417 JU_IMMSET_01_CASCADE(5, uint8_t *, cJU_JPLEAF5, JL_LEAF5VALUEAREA,
1418 JU_IMMSET_01_COPY_ODD,
1419 JU_COPY5_LONG_TO_PINDEX, j__udyAllocJLL5);
1420 case cJU_JPIMMED_6_01:
1421 JU_IMMSET_01_CASCADE(6, uint8_t *, cJU_JPLEAF6, JL_LEAF6VALUEAREA,
1422 JU_IMMSET_01_COPY_ODD,
1423 JU_COPY6_LONG_TO_PINDEX, j__udyAllocJLL6);
1424 case cJU_JPIMMED_7_01:
1425 JU_IMMSET_01_CASCADE(7, uint8_t *, cJU_JPLEAF7, JL_LEAF7VALUEAREA,
1426 JU_IMMSET_01_COPY_ODD,
1427 JU_COPY7_LONG_TO_PINDEX, j__udyAllocJLL7);
1428 #endif // JUDYL
1429 #endif // JU_64BIT
1430
1431 // cJU_JPIMMED_1_* cases that can grow in place:
1432 //
1433 // (1_01 => 1_02 => 1_03 => [ 1_04 => ... => 1_07 => [ 1_08..15 => ]] LeafL)
1434
1435 case cJU_JPIMMED_1_02:
1436 #if (defined(JUDY1) || defined(JU_64BIT))
1437 case cJU_JPIMMED_1_03:
1438 case cJU_JPIMMED_1_04:
1439 case cJU_JPIMMED_1_05:
1440 case cJU_JPIMMED_1_06:
1441 #endif
1442 #if (defined(JUDY1) && defined(JU_64BIT))
1443 case cJU_JPIMMED_1_07:
1444 case cJ1_JPIMMED_1_08:
1445 case cJ1_JPIMMED_1_09:
1446 case cJ1_JPIMMED_1_10:
1447 case cJ1_JPIMMED_1_11:
1448 case cJ1_JPIMMED_1_12:
1449 case cJ1_JPIMMED_1_13:
1450 case cJ1_JPIMMED_1_14:
1451 #endif
1452 JU_IMMSETINPLACE(1, uint8_t *, cJU_JPIMMED_1_02, j__udySearchLeaf1,
1453 JU_INSERTINPLACE);
1454
1455 // cJU_JPIMMED_1_* cases that must cascade:
1456 //
1457 // (1_01 => 1_02 => 1_03 => [ 1_04 => ... => 1_07 => [ 1_08..15 => ]] LeafL)
1458
1459 #if (defined(JUDYL) && (! defined(JU_64BIT)))
1460 case cJU_JPIMMED_1_03:
1461 JU_IMMSETCASCADE(1, 3, uint8_t *, cJU_JPLEAF1, JL_LEAF1VALUEAREA,
1462 j__udySearchLeaf1, JU_INSERTCOPY,
1463 j__udyAllocJLL1);
1464 #endif
1465 #if (defined(JUDY1) && (! defined(JU_64BIT)))
1466 case cJU_JPIMMED_1_07:
1467 JU_IMMSETCASCADE(1, 7, uint8_t *, cJU_JPLEAF1, ignore,
1468 j__udySearchLeaf1, JU_INSERTCOPY,
1469 j__udyAllocJLL1);
1470
1471 #endif
1472 #if (defined(JUDYL) && defined(JU_64BIT))
1473 case cJU_JPIMMED_1_07:
1474 JU_IMMSETCASCADE(1, 7, uint8_t *, cJU_JPLEAF1, JL_LEAF1VALUEAREA,
1475 j__udySearchLeaf1, JU_INSERTCOPY,
1476 j__udyAllocJLL1);
1477
1478 #endif
1479 #if (defined(JUDY1) && defined(JU_64BIT))
1480 // Special case, as described above, go directly from Immed to LeafB1:
1481
1482 case cJ1_JPIMMED_1_15:
1483 {
1484 Word_t DcdP0;
1485 int offset;
1486 Pjlb_t PjlbRaw;
1487 Pjlb_t Pjlb;
1488
1489 offset = j__udySearchLeaf1((Pjll_t) Pjp->jp_1Index, 15, Index);
1490
1491 JU_CHECK_IF_EXISTS(offset, ignore, Pjpm);
1492
1493 // Create a bitmap leaf (special case for Judy1 64-bit only, see usage): Set
1494 // new Index in bitmap, copy an Immed1_15 to the bitmap, and set the parent JP
1495 // EXCEPT jp_DcdPopO, leaving any followup to the caller:
1496
1497 if ((PjlbRaw = j__udyAllocJLB1(Pjpm)) == (Pjlb_t) NULL)
1498 return(-1);
1499 Pjlb = P_JLB(PjlbRaw);
1500
1501 JU_BITMAPSETL(Pjlb, Index);
1502
1503 for (offset = 0; offset < 15; ++offset)
1504 JU_BITMAPSETL(Pjlb, Pjp->jp_1Index[offset]);
1505
1506 // Set jp_DcdPopO including the current pop0; incremented later:
1507 DcdP0 = (Index & cJU_DCDMASK(1)) + 15 - 1;
1508 JU_JPSETADT(Pjp, (Word_t)PjlbRaw, DcdP0, cJU_JPLEAF_B1);
1509
1510 return(1);
1511 }
1512 #endif
1513
1514 // cJU_JPIMMED_[2..7]_[02..15] cases that grow in place or cascade:
1515 //
1516 // (2_01 => [ 2_02 => 2_03 => [ 2_04..07 => ]] LeafL)
1517
1518 #if (defined(JUDY1) || defined(JU_64BIT))
1519 case cJU_JPIMMED_2_02:
1520 #endif
1521 #if (defined(JUDY1) && defined(JU_64BIT))
1522 case cJU_JPIMMED_2_03:
1523 case cJ1_JPIMMED_2_04:
1524 case cJ1_JPIMMED_2_05:
1525 case cJ1_JPIMMED_2_06:
1526 #endif
1527 #if (defined(JUDY1) || defined(JU_64BIT))
1528 JU_IMMSETINPLACE(2, uint16_t *, cJU_JPIMMED_2_02, j__udySearchLeaf2,
1529 JU_INSERTINPLACE);
1530 #endif
1531
1532 #undef OLDPOP1
1533 #if ((defined(JUDY1) && (! defined(JU_64BIT))) || (defined(JUDYL) && defined(JU_64BIT)))
1534 case cJU_JPIMMED_2_03:
1535 #define OLDPOP1 3
1536 #endif
1537 #if (defined(JUDY1) && defined(JU_64BIT))
1538 case cJ1_JPIMMED_2_07:
1539 #define OLDPOP1 7
1540 #endif
1541 #if (defined(JUDY1) || defined(JU_64BIT))
1542 JU_IMMSETCASCADE(2, OLDPOP1, uint16_t *, cJU_JPLEAF2,
1543 JL_LEAF2VALUEAREA, j__udySearchLeaf2,
1544 JU_INSERTCOPY, j__udyAllocJLL2);
1545 #endif
1546
1547 // (3_01 => [ 3_02 => [ 3_03..05 => ]] LeafL)
1548
1549 #if (defined(JUDY1) && defined(JU_64BIT))
1550 case cJU_JPIMMED_3_02:
1551 case cJ1_JPIMMED_3_03:
1552 case cJ1_JPIMMED_3_04:
1553
1554 JU_IMMSETINPLACE(3, uint8_t *, cJU_JPIMMED_3_02, j__udySearchLeaf3,
1555 JU_INSERTINPLACE3);
1556 #endif
1557
1558 #undef OLDPOP1
1559 #if ((defined(JUDY1) && (! defined(JU_64BIT))) || (defined(JUDYL) && defined(JU_64BIT)))
1560 case cJU_JPIMMED_3_02:
1561 #define OLDPOP1 2
1562 #endif
1563 #if (defined(JUDY1) && defined(JU_64BIT))
1564 case cJ1_JPIMMED_3_05:
1565 #define OLDPOP1 5
1566 #endif
1567 #if (defined(JUDY1) || defined(JU_64BIT))
1568 JU_IMMSETCASCADE(3, OLDPOP1, uint8_t *, cJU_JPLEAF3,
1569 JL_LEAF3VALUEAREA, j__udySearchLeaf3,
1570 JU_INSERTCOPY3, j__udyAllocJLL3);
1571 #endif
1572
1573 #if (defined(JUDY1) && defined(JU_64BIT))
1574
1575 // (4_01 => [[ 4_02..03 => ]] LeafL)
1576
1577 case cJ1_JPIMMED_4_02:
1578
1579 JU_IMMSETINPLACE(4, uint32_t *, cJ1_JPIMMED_4_02, j__udySearchLeaf4,
1580 JU_INSERTINPLACE);
1581
1582 case cJ1_JPIMMED_4_03:
1583
1584 JU_IMMSETCASCADE(4, 3, uint32_t *, cJU_JPLEAF4, ignore,
1585 j__udySearchLeaf4, JU_INSERTCOPY,
1586 j__udyAllocJLL4);
1587
1588 // (5_01 => [[ 5_02..03 => ]] LeafL)
1589
1590 case cJ1_JPIMMED_5_02:
1591
1592 JU_IMMSETINPLACE(5, uint8_t *, cJ1_JPIMMED_5_02, j__udySearchLeaf5,
1593 JU_INSERTINPLACE5);
1594
1595 case cJ1_JPIMMED_5_03:
1596
1597 JU_IMMSETCASCADE(5, 3, uint8_t *, cJU_JPLEAF5, ignore,
1598 j__udySearchLeaf5, JU_INSERTCOPY5,
1599 j__udyAllocJLL5);
1600
1601 // (6_01 => [[ 6_02 => ]] LeafL)
1602
1603 case cJ1_JPIMMED_6_02:
1604
1605 JU_IMMSETCASCADE(6, 2, uint8_t *, cJU_JPLEAF6, ignore,
1606 j__udySearchLeaf6, JU_INSERTCOPY6,
1607 j__udyAllocJLL6);
1608
1609 // (7_01 => [[ 7_02 => ]] LeafL)
1610
1611 case cJ1_JPIMMED_7_02:
1612
1613 JU_IMMSETCASCADE(7, 2, uint8_t *, cJU_JPLEAF7, ignore,
1614 j__udySearchLeaf7, JU_INSERTCOPY7,
1615 j__udyAllocJLL7);
1616
1617 #endif // (JUDY1 && JU_64BIT)
1618
1619
1620 // ****************************************************************************
1621 // INVALID JP TYPE:
1622
1623 default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); return(-1);
1624
1625 } // switch on JP type
1626
1627 {
1628
1629 #ifdef SUBEXPCOUNTS
1630
1631 // This code might seem strange here. However it saves some memory read time
1632 // during insert (~70nS) because a pipelined processor does not need to "stall"
1633 // waiting for the memory read to complete. Hope the compiler is not too smart
1634 // or dumb and moves the code down to where it looks like it belongs (below a
1635 // few lines).
1636
1637 Word_t SubExpCount = 0; // current subexpanse counter.
1638
1639 if (PSubExp != (PWord_t) NULL) // only if BranchB/U.
1640 SubExpCount = PSubExp[0];
1641 #endif
1642
1643 // PROCESS JP -- RECURSIVELY:
1644 //
1645 // For non-Immed JP types, if successful, post-increment the population count
1646 // at this Level.
1647
1648 retcode = j__udyInsWalk(Pjp, Index, Pjpm);
1649
1650 // Successful insert, increment JP and subexpanse count:
1651
1652 if ((JU_JPTYPE(Pjp) < cJU_JPIMMED_1_01) && (retcode == 1))
1653 {
1654 jp_t JP;
1655 Word_t DcdP0;
1656 #ifdef SUBEXPCOUNTS
1657
1658 // Note: Pjp must be a pointer to a BranchB/U:
1659
1660 if (PSubExp != (PWord_t) NULL) PSubExp[0] = SubExpCount + 1;
1661 #endif
1662
1663 JP = *Pjp;
1664 DcdP0 = JU_JPDCDPOP0(Pjp) + 1;
1665 JU_JPSETADT(Pjp, JP.jp_Addr, DcdP0, JU_JPTYPE(&JP));
1666 }
1667 }
1668 return(retcode);
1669
1670 } // j__udyInsWalk()
1671
1672
1673 // ****************************************************************************
1674 // J U D Y 1 S E T
1675 // J U D Y L I N S
1676 //
1677 // Main entry point. See the manual entry for details.
1678
1679 #ifdef JUDY1
Judy1Set(PPvoid_t PPArray,Word_t Index,PJError_t PJError)1680 FUNCTION int Judy1Set
1681 #else
1682 FUNCTION PPvoid_t JudyLIns
1683 #endif
1684 (
1685 PPvoid_t PPArray, // in which to insert.
1686 Word_t Index, // to insert.
1687 PJError_t PJError // optional, for returning error info.
1688 )
1689 {
1690 #ifdef JUDY1
1691 #define Pjv ignore // placeholders for macros.
1692 #define Pjvnew ignore
1693 #else
1694 Pjv_t Pjv; // value area in old leaf.
1695 Pjv_t Pjvnew; // value area in new leaf.
1696 #endif
1697 Pjpm_t Pjpm; // array-global info.
1698 int offset; // position in which to store new Index.
1699 Pjlw_t Pjlw;
1700
1701
1702 // CHECK FOR NULL POINTER (error by caller):
1703
1704 if (PPArray == (PPvoid_t) NULL)
1705 {
1706 JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY);
1707 JUDY1CODE(return(JERRI );)
1708 JUDYLCODE(return(PPJERR);)
1709 }
1710
1711 Pjlw = P_JLW(*PPArray); // first word of leaf.
1712
1713 // ****************************************************************************
1714 // PROCESS TOP LEVEL "JRP" BRANCHES AND LEAVES:
1715
1716 // ****************************************************************************
1717 // JRPNULL (EMPTY ARRAY): BUILD A LEAFW WITH ONE INDEX:
1718
1719 // if a valid empty array (null pointer), so create an array of population == 1:
1720
1721 if (Pjlw == (Pjlw_t)NULL)
1722 {
1723 Pjlw_t Pjlwnew;
1724
1725 Pjlwnew = j__udyAllocJLW(1);
1726 JUDY1CODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI );)
1727 JUDYLCODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, PPJERR);)
1728
1729 Pjlwnew[0] = 1 - 1; // pop0 = 0.
1730 Pjlwnew[1] = Index;
1731
1732 *PPArray = (Pvoid_t) Pjlwnew;
1733 DBGCODE(JudyCheckPop(*PPArray);)
1734
1735 JUDY1CODE(return(1); )
1736 JUDYLCODE(Pjlwnew[2] = 0; ) // value area.
1737 JUDYLCODE(return((PPvoid_t) (Pjlwnew + 2)); )
1738
1739 } // NULL JRP
1740
1741 // ****************************************************************************
1742 // LEAFW, OTHER SIZE:
1743
1744 if (JU_LEAFW_POP0(*PPArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
1745 {
1746 Pjlw_t Pjlwnew;
1747 Word_t pop1;
1748
1749 Pjlw = P_JLW(*PPArray); // first word of leaf.
1750 pop1 = Pjlw[0] + 1;
1751
1752 #ifdef JUDYL
1753 Pjv = JL_LEAFWVALUEAREA(Pjlw, pop1);
1754 #endif
1755 offset = j__udySearchLeafW(Pjlw + 1, pop1, Index);
1756
1757 if (offset >= 0) // index is already valid:
1758 {
1759 DBGCODE(JudyCheckPop(*PPArray);)
1760 JUDY1CODE(return(0); )
1761 JUDYLCODE(return((PPvoid_t) (Pjv + offset)); )
1762 }
1763
1764 offset = ~offset;
1765
1766 // Insert index in cases where no new memory is needed:
1767
1768 if (JU_LEAFWGROWINPLACE(pop1))
1769 {
1770 ++Pjlw[0]; // increase population.
1771
1772 JU_INSERTINPLACE(Pjlw + 1, pop1, offset, Index);
1773 #ifdef JUDYL
1774 JU_INSERTINPLACE(Pjv, pop1, offset, 0);
1775 #endif
1776 DBGCODE(JudyCheckPop(*PPArray);)
1777 DBGCODE(JudyCheckSorted(Pjlw + 1, pop1 + 1, cJU_ROOTSTATE);)
1778
1779 JUDY1CODE(return(1); )
1780 JUDYLCODE(return((PPvoid_t) (Pjv + offset)); )
1781 }
1782
1783 // Insert index into a new, larger leaf:
1784
1785 if (pop1 < cJU_LEAFW_MAXPOP1) // can grow to a larger leaf.
1786 {
1787 Pjlwnew = j__udyAllocJLW(pop1 + 1);
1788 JUDY1CODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI );)
1789 JUDYLCODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, PPJERR);)
1790
1791 Pjlwnew[0] = pop1; // set pop0 in new leaf.
1792
1793 JU_INSERTCOPY(Pjlwnew + 1, Pjlw + 1, pop1, offset, Index);
1794 #ifdef JUDYL
1795 Pjvnew = JL_LEAFWVALUEAREA(Pjlwnew, pop1 + 1);
1796 JU_INSERTCOPY(Pjvnew, Pjv, pop1, offset, 0);
1797 #endif
1798 DBGCODE(JudyCheckSorted(Pjlwnew + 1, pop1 + 1, cJU_ROOTSTATE);)
1799
1800 j__udyFreeJLW(Pjlw, pop1, NULL);
1801
1802 *PPArray = (Pvoid_t) Pjlwnew;
1803 DBGCODE(JudyCheckPop(*PPArray);)
1804
1805 JUDY1CODE(return(1); )
1806 JUDYLCODE(return((PPvoid_t) (Pjvnew + offset)); )
1807 }
1808
1809 assert(pop1 == cJU_LEAFW_MAXPOP1);
1810
1811 // Leaf at max size => cannot insert new index, so cascade instead:
1812 //
1813 // Upon cascading from a LEAFW leaf to the first branch, must allocate and
1814 // initialize a JPM.
1815
1816 Pjpm = j__udyAllocJPM();
1817 JUDY1CODE(JU_CHECKALLOC(Pjpm_t, Pjpm, JERRI );)
1818 JUDYLCODE(JU_CHECKALLOC(Pjpm_t, Pjpm, PPJERR);)
1819
1820 (Pjpm->jpm_Pop0) = cJU_LEAFW_MAXPOP1 - 1;
1821 (Pjpm->jpm_JP.jp_Addr) = (Word_t) Pjlw;
1822
1823 if (j__udyCascadeL(&(Pjpm->jpm_JP), Pjpm) == -1)
1824 {
1825 JU_COPY_ERRNO(PJError, Pjpm);
1826 JUDY1CODE(return(JERRI );)
1827 JUDYLCODE(return(PPJERR);)
1828 }
1829
1830 // Note: No need to pass Pjpm for memory decrement; LEAFW memory is never
1831 // counted in a JPM at all:
1832
1833 j__udyFreeJLW(Pjlw, cJU_LEAFW_MAXPOP1, NULL);
1834 *PPArray = (Pvoid_t) Pjpm;
1835
1836 } // JU_LEAFW
1837
1838 // ****************************************************************************
1839 // BRANCH:
1840
1841 {
1842 int retcode; // really only needed for Judy1, but free for JudyL.
1843
1844 Pjpm = P_JPM(*PPArray);
1845 retcode = j__udyInsWalk(&(Pjpm->jpm_JP), Index, Pjpm);
1846
1847 if (retcode == -1)
1848 {
1849 JU_COPY_ERRNO(PJError, Pjpm);
1850 JUDY1CODE(return(JERRI );)
1851 JUDYLCODE(return(PPJERR);)
1852 }
1853
1854 if (retcode == 1) ++(Pjpm->jpm_Pop0); // incr total array popu.
1855
1856 assert(((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_L)
1857 || ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_B)
1858 || ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_U));
1859 DBGCODE(JudyCheckPop(*PPArray);)
1860
1861 #ifdef JUDY1
1862 assert((retcode == 0) || (retcode == 1));
1863 return(retcode); // == JU_RET_*_JPM().
1864 #else
1865 assert(Pjpm->jpm_PValue != (Pjv_t) NULL);
1866 return((PPvoid_t) Pjpm->jpm_PValue);
1867 #endif
1868 }
1869 /*NOTREACHED*/
1870
1871 } // Judy1Set() / JudyLIns()
1872