1 // Copyright (C) 2000 - 2002 Hewlett-Packard Company
2 //
3 // This program is free software; you can redistribute it and/or modify it
4 // under the term of the GNU Lesser General Public License as published by the
5 // Free Software Foundation; either version 2 of the License, or (at your
6 // option) any later version.
7 //
8 // This program is distributed in the hope that it will be useful, but WITHOUT
9 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
11 // for more details.
12 //
13 // You should have received a copy of the GNU Lesser General Public License
14 // along with this program; if not, write to the Free Software Foundation,
15 // Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16 // _________________
17
18 // @(#) $Revision: 4.68 $ $Source: /judy/src/JudyCommon/JudyDel.c $
19 //
20 // Judy1Unset() and JudyLDel() functions for Judy1 and JudyL.
21 // Compile with one of -DJUDY1 or -DJUDYL.
22 //
23 // About HYSTERESIS: In the Judy code, hysteresis means leaving around a
24 // nominally suboptimal (not maximally compressed) data structure after a
25 // deletion. As a result, the shape of the tree for two identical index sets
26 // can differ depending on the insert/delete path taken to arrive at the index
27 // sets. The purpose is to minimize worst-case behavior (thrashing) that could
28 // result from a series of intermixed insertions and deletions. It also makes
29 // for MUCH simpler code, because instead of performing, "delete and then
30 // compress," it can say, "compress and then delete," where due to hysteresis,
31 // compression is not even attempted until the object IS compressible.
32 //
33 // In some cases the code has no choice and it must "ungrow" a data structure
34 // across a "phase transition" boundary without hysteresis. In other cases the
35 // amount (such as "hysteresis = 1") is indicated by the number of JP deletions
36 // (in branches) or index deletions (in leaves) that can occur in succession
37 // before compressing the data structure. (It appears that hysteresis <= 1 in
38 // all cases.)
39 //
40 // In general no hysteresis occurs when the data structure type remains the
41 // same but the allocated memory chunk for the node must shrink, because the
42 // relationship is hardwired and theres no way to know how much memory is
43 // allocated to a given data structure. Hysteresis = 0 in all these cases.
44 //
45 // TBD: Could this code be faster if memory chunk hysteresis were supported
46 // somehow along with data structure type hysteresis?
47 //
48 // TBD: Should some of the assertions here be converted to product code that
49 // returns JU_ERRNO_CORRUPT?
50 //
51 // TBD: Dougs code had an odd mix of function-wide and limited-scope
52 // variables. Should some of the function-wide variables appear only in
53 // limited scopes, or more likely, vice-versa?
54
55 #if (! (defined(JUDY1) || defined(JUDYL)))
56 #error: One of -DJUDY1 or -DJUDYL must be specified.
57 #endif
58
59 #ifdef JUDY1
60 #include "Judy1.h"
61 #else
62 #include "JudyL.h"
63 #endif
64
65 #include "JudyPrivate1L.h"
66
67 DBGCODE(extern void JudyCheckPop(Pvoid_t PArray);)
68 DBGCODE(extern void JudyCheckSorted(Pjll_t Pjll, Word_t Pop1, long IndexSize);)
69
70 #ifdef TRACEJP
71 #include "JudyPrintJP.c"
72 #endif
73
74 // These are defined to generic values in JudyCommon/JudyPrivateTypes.h:
75 //
76 // TBD: These should be exported from a header file, but perhaps not, as they
77 // are only used here, and exported from JudyDecascade.c, which is a separate
78 // file for profiling reasons (to prevent inlining), but which potentially
79 // could be merged with this file, either in SoftCM or at compile-time:
80
81 #ifdef JUDY1
82
83 extern int j__udy1BranchBToBranchL(Pjp_t Pjp, Pvoid_t Pjpm);
84 #ifndef JU_64BIT
85 extern int j__udy1LeafB1ToLeaf1(Pjp_t, Pvoid_t);
86 #endif
87 extern Word_t j__udy1Leaf1ToLeaf2(uint16_t *, Pjp_t, Word_t, Pvoid_t);
88 extern Word_t j__udy1Leaf2ToLeaf3(uint8_t *, Pjp_t, Word_t, Pvoid_t);
89 #ifndef JU_64BIT
90 extern Word_t j__udy1Leaf3ToLeafW(Pjlw_t, Pjp_t, Word_t, Pvoid_t);
91 #else
92 extern Word_t j__udy1Leaf3ToLeaf4(uint32_t *, Pjp_t, Word_t, Pvoid_t);
93 extern Word_t j__udy1Leaf4ToLeaf5(uint8_t *, Pjp_t, Word_t, Pvoid_t);
94 extern Word_t j__udy1Leaf5ToLeaf6(uint8_t *, Pjp_t, Word_t, Pvoid_t);
95 extern Word_t j__udy1Leaf6ToLeaf7(uint8_t *, Pjp_t, Word_t, Pvoid_t);
96 extern Word_t j__udy1Leaf7ToLeafW(Pjlw_t, Pjp_t, Word_t, Pvoid_t);
97 #endif
98
99 #else // JUDYL
100
101 extern int j__udyLBranchBToBranchL(Pjp_t Pjp, Pvoid_t Pjpm);
102 extern int j__udyLLeafB1ToLeaf1(Pjp_t, Pvoid_t);
103 extern Word_t j__udyLLeaf1ToLeaf2(uint16_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);
104 extern Word_t j__udyLLeaf2ToLeaf3(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);
105 #ifndef JU_64BIT
106 extern Word_t j__udyLLeaf3ToLeafW(Pjlw_t, Pjv_t, Pjp_t, Word_t, Pvoid_t);
107 #else
108 extern Word_t j__udyLLeaf3ToLeaf4(uint32_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);
109 extern Word_t j__udyLLeaf4ToLeaf5(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);
110 extern Word_t j__udyLLeaf5ToLeaf6(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);
111 extern Word_t j__udyLLeaf6ToLeaf7(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);
112 extern Word_t j__udyLLeaf7ToLeafW(Pjlw_t, Pjv_t, Pjp_t, Word_t, Pvoid_t);
113 #endif
114
115 #endif // JUDYL
116
117 // For convenience in the calling code; "M1" means "minus one":
118
119 #ifndef JU_64BIT
120 #define j__udyLeafM1ToLeafW j__udyLeaf3ToLeafW
121 #else
122 #define j__udyLeafM1ToLeafW j__udyLeaf7ToLeafW
123 #endif
124
125
126 // ****************************************************************************
127 // __ J U D Y D E L W A L K
128 //
129 // Given a pointer to a JP, an Index known to be valid, the number of bytes
130 // left to decode (== level in the tree), and a pointer to a global JPM, walk a
131 // Judy (sub)tree to do an unset/delete of that index, and possibly modify the
132 // JPM. This function is only called internally, and recursively. Unlike
133 // Judy1Test() and JudyLGet(), the extra time required for recursion should be
134 // negligible compared with the total.
135 //
136 // Return values:
137 //
138 // -1 error; details in JPM
139 //
140 // 0 Index already deleted (should never happen, Index is known to be valid)
141 //
142 // 1 previously valid Index deleted
143 //
144 // 2 same as 1, but in addition the JP now points to a BranchL containing a
145 // single JP, which should be compressed into the parent branch (if there
146 // is one, which is not the case for a top-level branch under a JPM)
147
DBGCODE(uint8_t parentJPtype;)148 DBGCODE(uint8_t parentJPtype;) // parent branch JP type.
149
150 FUNCTION static int j__udyDelWalk(
151 Pjp_t Pjp, // current JP under which to delete.
152 Word_t Index, // to delete.
153 Word_t ParentLevel, // of parent branch.
154 Pjpm_t Pjpm) // for returning info to top level.
155 {
156 Word_t pop1; // of a leaf.
157 Word_t level; // of a leaf.
158 uint8_t digit; // from Index, in current branch.
159 Pjll_t PjllnewRaw; // address of newly allocated leaf.
160 Pjll_t Pjllnew;
161 int offset; // within a branch.
162 int retcode; // return code: -1, 0, 1, 2.
163 JUDYLCODE(Pjv_t PjvRaw;) // value area.
164 JUDYLCODE(Pjv_t Pjv;)
165
166 DBGCODE(level = 0;)
167
168 ContinueDelWalk: // for modifying state without recursing.
169
170 #ifdef TRACEJP
171 JudyPrintJP(Pjp, "d", __LINE__);
172 #endif
173
174 switch (JU_JPTYPE(Pjp)) // entry: Pjp, Index.
175 {
176
177
178 // ****************************************************************************
179 // LINEAR BRANCH:
180 //
181 // MACROS FOR COMMON CODE:
182 //
183 // Check for population too high to compress a branch to a leaf, meaning just
184 // descend through the branch, with a purposeful off-by-one error that
185 // constitutes hysteresis = 1. In other words, do not compress until the
186 // branchs CURRENT population fits in the leaf, even BEFORE deleting one
187 // index.
188 //
189 // Next is a label for branch-type-specific common code. Variables pop1,
190 // level, digit, and Index are in the context.
191
192 #define JU_BRANCH_KEEP(cLevel,MaxPop1,Next) \
193 if (pop1 > (MaxPop1)) /* hysteresis = 1 */ \
194 { \
195 assert((cLevel) >= 2); \
196 level = (cLevel); \
197 digit = JU_DIGITATSTATE(Index, cLevel); \
198 goto Next; \
199 }
200
201 // Support for generic calling of JudyLeaf*ToLeaf*() functions:
202 //
203 // Note: Cannot use JUDYLCODE() because this contains a comma.
204
205 #ifdef JUDY1
206 #define JU_PVALUEPASS // null.
207 #else
208 #define JU_PVALUEPASS Pjv,
209 #endif
210
211 // During compression to a leaf, check if a JP contains nothing but a
212 // cJU_JPIMMED_*_01, in which case shortcut calling j__udyLeaf*ToLeaf*():
213 //
214 // Copy the index bytes from the jp_DcdPopO field (with possible truncation),
215 // and continue the branch-JP-walk loop. Variables Pjp and Pleaf are in the
216 // context.
217
218 #define JU_BRANCH_COPY_IMMED_EVEN(cLevel,Pjp,ignore) \
219 if (JU_JPTYPE(Pjp) == cJU_JPIMMED_1_01 + (cLevel) - 2) \
220 { \
221 *Pleaf++ = JU_JPDCDPOP0(Pjp); \
222 JUDYLCODE(*Pjv++ = (Pjp)->jp_Addr;) \
223 continue; /* for-loop */ \
224 }
225
226 #define JU_BRANCH_COPY_IMMED_ODD(cLevel,Pjp,CopyIndex) \
227 if (JU_JPTYPE(Pjp) == cJU_JPIMMED_1_01 + (cLevel) - 2) \
228 { \
229 CopyIndex(Pleaf, (Word_t) (JU_JPDCDPOP0(Pjp))); \
230 Pleaf += (cLevel); /* index size = level */ \
231 JUDYLCODE(*Pjv++ = (Pjp)->jp_Addr;) \
232 continue; /* for-loop */ \
233 }
234
235 // Compress a BranchL into a leaf one index size larger:
236 //
237 // Allocate a new leaf, walk the JPs in the old BranchL and pack their contents
238 // into the new leaf (of type NewJPType), free the old BranchL, and finally
239 // restart the switch to delete Index from the new leaf. (Note that all
240 // BranchLs are the same size.) Variables Pjp, Pjpm, Pleaf, digit, and pop1
241 // are in the context.
242
243 #define JU_BRANCHL_COMPRESS(cLevel,LeafType,MaxPop1,NewJPType, \
244 LeafToLeaf,Alloc,ValueArea, \
245 CopyImmed,CopyIndex) \
246 { \
247 LeafType Pleaf; \
248 Pjbl_t PjblRaw; \
249 Pjbl_t Pjbl; \
250 Word_t numJPs; \
251 \
252 if ((PjllnewRaw = Alloc(MaxPop1, Pjpm)) == 0) return(-1); \
253 Pjllnew = P_JLL(PjllnewRaw); \
254 Pleaf = (LeafType) Pjllnew; \
255 JUDYLCODE(Pjv = ValueArea(Pleaf, MaxPop1);) \
256 \
257 PjblRaw = (Pjbl_t) (Pjp->jp_Addr); \
258 Pjbl = P_JBL(PjblRaw); \
259 numJPs = Pjbl->jbl_NumJPs; \
260 \
261 for (offset = 0; offset < numJPs; ++offset) \
262 { \
263 CopyImmed(cLevel, (Pjbl->jbl_jp) + offset, CopyIndex); \
264 \
265 pop1 = LeafToLeaf(Pleaf, JU_PVALUEPASS \
266 (Pjbl->jbl_jp) + offset, \
267 JU_DIGITTOSTATE(Pjbl->jbl_Expanse[offset], \
268 cLevel), (Pvoid_t) Pjpm); \
269 Pleaf = (LeafType) (((Word_t) Pleaf) + ((cLevel) * pop1)); \
270 JUDYLCODE(Pjv += pop1;) \
271 } \
272 assert(((((Word_t) Pleaf) - ((Word_t) Pjllnew)) / (cLevel)) == (MaxPop1)); \
273 JUDYLCODE(assert((Pjv - ValueArea(Pjllnew, MaxPop1)) == (MaxPop1));) \
274 DBGCODE(JudyCheckSorted(Pjllnew, MaxPop1, cLevel);) \
275 \
276 j__udyFreeJBL(PjblRaw, Pjpm); \
277 \
278 Pjp->jp_Type = (NewJPType); \
279 Pjp->jp_Addr = (Word_t) PjllnewRaw; \
280 goto ContinueDelWalk; /* delete from new leaf */ \
281 }
282
283 // Overall common code for initial BranchL deletion handling:
284 //
285 // Assert that Index is in the branch, then see if the BranchL should be kept
286 // or else compressed to a leaf. Variables Index, Pjp, and pop1 are in the
287 // context.
288
289 #define JU_BRANCHL(cLevel,MaxPop1,LeafType,NewJPType, \
290 LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \
291 \
292 assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, cLevel)); \
293 assert(ParentLevel > (cLevel)); \
294 \
295 pop1 = JU_JPBRANCH_POP0(Pjp, cLevel) + 1; \
296 JU_BRANCH_KEEP(cLevel, MaxPop1, BranchLKeep); \
297 assert(pop1 == (MaxPop1)); \
298 \
299 JU_BRANCHL_COMPRESS(cLevel, LeafType, MaxPop1, NewJPType, \
300 LeafToLeaf, Alloc, ValueArea, CopyImmed, CopyIndex)
301
302
303 // END OF MACROS, START OF CASES:
304
305 case cJU_JPBRANCH_L2:
306
307 JU_BRANCHL(2, cJU_LEAF2_MAXPOP1, uint16_t *, cJU_JPLEAF2,
308 j__udyLeaf1ToLeaf2, j__udyAllocJLL2, JL_LEAF2VALUEAREA,
309 JU_BRANCH_COPY_IMMED_EVEN, ignore);
310
311 case cJU_JPBRANCH_L3:
312
313 JU_BRANCHL(3, cJU_LEAF3_MAXPOP1, uint8_t *, cJU_JPLEAF3,
314 j__udyLeaf2ToLeaf3, j__udyAllocJLL3, JL_LEAF3VALUEAREA,
315 JU_BRANCH_COPY_IMMED_ODD, JU_COPY3_LONG_TO_PINDEX);
316
317 #ifdef JU_64BIT
318 case cJU_JPBRANCH_L4:
319
320 JU_BRANCHL(4, cJU_LEAF4_MAXPOP1, uint32_t *, cJU_JPLEAF4,
321 j__udyLeaf3ToLeaf4, j__udyAllocJLL4, JL_LEAF4VALUEAREA,
322 JU_BRANCH_COPY_IMMED_EVEN, ignore);
323
324 case cJU_JPBRANCH_L5:
325
326 JU_BRANCHL(5, cJU_LEAF5_MAXPOP1, uint8_t *, cJU_JPLEAF5,
327 j__udyLeaf4ToLeaf5, j__udyAllocJLL5, JL_LEAF5VALUEAREA,
328 JU_BRANCH_COPY_IMMED_ODD, JU_COPY5_LONG_TO_PINDEX);
329
330 case cJU_JPBRANCH_L6:
331
332 JU_BRANCHL(6, cJU_LEAF6_MAXPOP1, uint8_t *, cJU_JPLEAF6,
333 j__udyLeaf5ToLeaf6, j__udyAllocJLL6, JL_LEAF6VALUEAREA,
334 JU_BRANCH_COPY_IMMED_ODD, JU_COPY6_LONG_TO_PINDEX);
335
336 case cJU_JPBRANCH_L7:
337
338 JU_BRANCHL(7, cJU_LEAF7_MAXPOP1, uint8_t *, cJU_JPLEAF7,
339 j__udyLeaf6ToLeaf7, j__udyAllocJLL7, JL_LEAF7VALUEAREA,
340 JU_BRANCH_COPY_IMMED_ODD, JU_COPY7_LONG_TO_PINDEX);
341 #endif // JU_64BIT
342
343 // A top-level BranchL is different and cannot use JU_BRANCHL(): Dont try to
344 // compress to a (LEAFW) leaf yet, but leave this for a later deletion
345 // (hysteresis > 0); and the next JP type depends on the system word size; so
346 // dont use JU_BRANCH_KEEP():
347
348 case cJU_JPBRANCH_L:
349 {
350 Pjbl_t Pjbl;
351 Word_t numJPs;
352
353 level = cJU_ROOTSTATE;
354 digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
355
356 // fall through:
357
358
359 // COMMON CODE FOR KEEPING AND DESCENDING THROUGH A BRANCHL:
360 //
361 // Come here with level and digit set.
362
363 BranchLKeep:
364 Pjbl = P_JBL(Pjp->jp_Addr);
365 numJPs = Pjbl->jbl_NumJPs;
366 assert(numJPs > 0);
367 DBGCODE(parentJPtype = JU_JPTYPE(Pjp);)
368
369 // Search for a match to the digit (valid Index => must find digit):
370
371 for (offset = 0; (Pjbl->jbl_Expanse[offset]) != digit; ++offset)
372 assert(offset < numJPs - 1);
373
374 Pjp = (Pjbl->jbl_jp) + offset;
375
376 // If not at a (deletable) JPIMMED_*_01, continue the walk (to descend through
377 // the BranchL):
378
379 assert(level >= 2);
380 if ((JU_JPTYPE(Pjp)) != cJU_JPIMMED_1_01 + level - 2) break;
381
382 // At JPIMMED_*_01: Ensure the index is in the right expanse, then delete the
383 // Immed from the BranchL:
384 //
385 // Note: A BranchL has a fixed size and format regardless of numJPs.
386
387 assert(JU_JPDCDPOP0(Pjp) == JU_TRIMTODCDSIZE(Index));
388
389 JU_DELETEINPLACE(Pjbl->jbl_Expanse, numJPs, offset, ignore);
390 JU_DELETEINPLACE(Pjbl->jbl_jp, numJPs, offset, ignore);
391
392 DBGCODE(JudyCheckSorted((Pjll_t) (Pjbl->jbl_Expanse),
393 numJPs - 1, 1);)
394
395 // If only one index left in the BranchL, indicate this to the caller:
396
397 return ((--(Pjbl->jbl_NumJPs) <= 1) ? 2 : 1);
398
399 } // case cJU_JPBRANCH_L.
400
401
402 // ****************************************************************************
403 // BITMAP BRANCH:
404 //
405 // MACROS FOR COMMON CODE:
406 //
407 // Note the reuse of common macros here, defined earlier: JU_BRANCH_KEEP(),
408 // JU_PVALUE*.
409 //
410 // Compress a BranchB into a leaf one index size larger:
411 //
412 // Allocate a new leaf, walk the JPs in the old BranchB (one bitmap subexpanse
413 // at a time) and pack their contents into the new leaf (of type NewJPType),
414 // free the old BranchB, and finally restart the switch to delete Index from
415 // the new leaf. Variables Pjp, Pjpm, Pleaf, digit, and pop1 are in the
416 // context.
417 //
418 // Note: Its no accident that the interface to JU_BRANCHB_COMPRESS() is
419 // identical to JU_BRANCHL_COMPRESS(). Only the details differ in how to
420 // traverse the branchs JPs.
421
422 #define JU_BRANCHB_COMPRESS(cLevel,LeafType,MaxPop1,NewJPType, \
423 LeafToLeaf,Alloc,ValueArea, \
424 CopyImmed,CopyIndex) \
425 { \
426 LeafType Pleaf; \
427 Pjbb_t PjbbRaw; /* BranchB to compress */ \
428 Pjbb_t Pjbb; \
429 Word_t subexp; /* current subexpanse number */ \
430 BITMAPB_t bitmap; /* portion for this subexpanse */ \
431 Pjp_t Pjp2Raw; /* one subexpanses subarray */ \
432 Pjp_t Pjp2; \
433 \
434 if ((PjllnewRaw = Alloc(MaxPop1, Pjpm)) == 0) return(-1); \
435 Pjllnew = P_JLL(PjllnewRaw); \
436 Pleaf = (LeafType) Pjllnew; \
437 JUDYLCODE(Pjv = ValueArea(Pleaf, MaxPop1);) \
438 \
439 PjbbRaw = (Pjbb_t) (Pjp->jp_Addr); \
440 Pjbb = P_JBB(PjbbRaw); \
441 \
442 for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp) \
443 { \
444 if ((bitmap = JU_JBB_BITMAP(Pjbb, subexp)) == 0) \
445 continue; /* empty subexpanse */ \
446 \
447 digit = subexp * cJU_BITSPERSUBEXPB; \
448 Pjp2Raw = JU_JBB_PJP(Pjbb, subexp); \
449 Pjp2 = P_JP(Pjp2Raw); \
450 assert(Pjp2 != (Pjp_t) NULL); \
451 \
452 for (offset = 0; bitmap != 0; bitmap >>= 1, ++digit) \
453 { \
454 if (! (bitmap & 1)) \
455 continue; /* empty sub-subexpanse */ \
456 \
457 ++offset; /* before any continue */ \
458 \
459 CopyImmed(cLevel, Pjp2 + offset - 1, CopyIndex); \
460 \
461 pop1 = LeafToLeaf(Pleaf, JU_PVALUEPASS \
462 Pjp2 + offset - 1, \
463 JU_DIGITTOSTATE(digit, cLevel), \
464 (Pvoid_t) Pjpm); \
465 Pleaf = (LeafType) (((Word_t) Pleaf) + ((cLevel) * pop1)); \
466 JUDYLCODE(Pjv += pop1;) \
467 } \
468 j__udyFreeJBBJP(Pjp2Raw, /* pop1 = */ offset, Pjpm); \
469 } \
470 assert(((((Word_t) Pleaf) - ((Word_t) Pjllnew)) / (cLevel)) == (MaxPop1)); \
471 JUDYLCODE(assert((Pjv - ValueArea(Pjllnew, MaxPop1)) == (MaxPop1));) \
472 DBGCODE(JudyCheckSorted(Pjllnew, MaxPop1, cLevel);) \
473 \
474 j__udyFreeJBB(PjbbRaw, Pjpm); \
475 \
476 Pjp->jp_Type = (NewJPType); \
477 Pjp->jp_Addr = (Word_t) PjllnewRaw; \
478 goto ContinueDelWalk; /* delete from new leaf */ \
479 }
480
481 // Overall common code for initial BranchB deletion handling:
482 //
483 // Assert that Index is in the branch, then see if the BranchB should be kept
484 // or else compressed to a leaf. Variables Index, Pjp, and pop1 are in the
485 // context.
486
487 #define JU_BRANCHB(cLevel,MaxPop1,LeafType,NewJPType, \
488 LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \
489 \
490 assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, cLevel)); \
491 assert(ParentLevel > (cLevel)); \
492 \
493 pop1 = JU_JPBRANCH_POP0(Pjp, cLevel) + 1; \
494 JU_BRANCH_KEEP(cLevel, MaxPop1, BranchBKeep); \
495 assert(pop1 == (MaxPop1)); \
496 \
497 JU_BRANCHB_COMPRESS(cLevel, LeafType, MaxPop1, NewJPType, \
498 LeafToLeaf, Alloc, ValueArea, CopyImmed, CopyIndex)
499
500
501 // END OF MACROS, START OF CASES:
502 //
503 // Note: Its no accident that the macro calls for these cases is nearly
504 // identical to the code for BranchLs.
505
506 case cJU_JPBRANCH_B2:
507
508 JU_BRANCHB(2, cJU_LEAF2_MAXPOP1, uint16_t *, cJU_JPLEAF2,
509 j__udyLeaf1ToLeaf2, j__udyAllocJLL2, JL_LEAF2VALUEAREA,
510 JU_BRANCH_COPY_IMMED_EVEN, ignore);
511
512 case cJU_JPBRANCH_B3:
513
514 JU_BRANCHB(3, cJU_LEAF3_MAXPOP1, uint8_t *, cJU_JPLEAF3,
515 j__udyLeaf2ToLeaf3, j__udyAllocJLL3, JL_LEAF3VALUEAREA,
516 JU_BRANCH_COPY_IMMED_ODD, JU_COPY3_LONG_TO_PINDEX);
517
518 #ifdef JU_64BIT
519 case cJU_JPBRANCH_B4:
520
521 JU_BRANCHB(4, cJU_LEAF4_MAXPOP1, uint32_t *, cJU_JPLEAF4,
522 j__udyLeaf3ToLeaf4, j__udyAllocJLL4, JL_LEAF4VALUEAREA,
523 JU_BRANCH_COPY_IMMED_EVEN, ignore);
524
525 case cJU_JPBRANCH_B5:
526
527 JU_BRANCHB(5, cJU_LEAF5_MAXPOP1, uint8_t *, cJU_JPLEAF5,
528 j__udyLeaf4ToLeaf5, j__udyAllocJLL5, JL_LEAF5VALUEAREA,
529 JU_BRANCH_COPY_IMMED_ODD, JU_COPY5_LONG_TO_PINDEX);
530
531 case cJU_JPBRANCH_B6:
532
533 JU_BRANCHB(6, cJU_LEAF6_MAXPOP1, uint8_t *, cJU_JPLEAF6,
534 j__udyLeaf5ToLeaf6, j__udyAllocJLL6, JL_LEAF6VALUEAREA,
535 JU_BRANCH_COPY_IMMED_ODD, JU_COPY6_LONG_TO_PINDEX);
536
537 case cJU_JPBRANCH_B7:
538
539 JU_BRANCHB(7, cJU_LEAF7_MAXPOP1, uint8_t *, cJU_JPLEAF7,
540 j__udyLeaf6ToLeaf7, j__udyAllocJLL7, JL_LEAF7VALUEAREA,
541 JU_BRANCH_COPY_IMMED_ODD, JU_COPY7_LONG_TO_PINDEX);
542 #endif // JU_64BIT
543
544 // A top-level BranchB is different and cannot use JU_BRANCHB(): Dont try to
545 // compress to a (LEAFW) leaf yet, but leave this for a later deletion
546 // (hysteresis > 0); and the next JP type depends on the system word size; so
547 // dont use JU_BRANCH_KEEP():
548
549 case cJU_JPBRANCH_B:
550 {
551 Pjbb_t Pjbb; // BranchB to modify.
552 Word_t subexp; // current subexpanse number.
553 Word_t subexp2; // in second-level loop.
554 BITMAPB_t bitmap; // portion for this subexpanse.
555 BITMAPB_t bitmask; // with digits bit set.
556 Pjp_t Pjp2Raw; // one subexpanses subarray.
557 Pjp_t Pjp2;
558 Word_t numJPs; // in one subexpanse.
559
560 level = cJU_ROOTSTATE;
561 digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
562
563 // fall through:
564
565
566 // COMMON CODE FOR KEEPING AND DESCENDING THROUGH A BRANCHB:
567 //
568 // Come here with level and digit set.
569
570 BranchBKeep:
571 Pjbb = P_JBB(Pjp->jp_Addr);
572 subexp = digit / cJU_BITSPERSUBEXPB;
573 bitmap = JU_JBB_BITMAP(Pjbb, subexp);
574 bitmask = JU_BITPOSMASKB(digit);
575 assert(bitmap & bitmask); // Index valid => digits bit is set.
576 DBGCODE(parentJPtype = JU_JPTYPE(Pjp);)
577
578 // Compute digits offset into the bitmap, with a fast method if all bits are
579 // set:
580
581 offset = ((bitmap == (cJU_FULLBITMAPB)) ?
582 digit % cJU_BITSPERSUBEXPB :
583 j__udyCountBitsB(bitmap & JU_MASKLOWEREXC(bitmask)));
584
585 Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);
586 Pjp2 = P_JP(Pjp2Raw);
587 assert(Pjp2 != (Pjp_t) NULL); // valid subexpanse pointer.
588
589 // If not at a (deletable) JPIMMED_*_01, continue the walk (to descend through
590 // the BranchB):
591
592 if (JU_JPTYPE(Pjp2 + offset) != cJU_JPIMMED_1_01 + level - 2)
593 {
594 Pjp = Pjp2 + offset;
595 break;
596 }
597
598 // At JPIMMED_*_01: Ensure the index is in the right expanse, then delete the
599 // Immed from the BranchB:
600
601 assert(JU_JPDCDPOP0(Pjp2 + offset)
602 == JU_TRIMTODCDSIZE(Index));
603
604 // If only one index is left in the subexpanse, free the JP array:
605
606 if ((numJPs = j__udyCountBitsB(bitmap)) == 1)
607 {
608 j__udyFreeJBBJP(Pjp2Raw, /* pop1 = */ 1, Pjpm);
609 JU_JBB_PJP(Pjbb, subexp) = (Pjp_t) NULL;
610 }
611
612 // Shrink JP array in-place:
613
614 else if (JU_BRANCHBJPGROWINPLACE(numJPs - 1))
615 {
616 assert(numJPs > 0);
617 JU_DELETEINPLACE(Pjp2, numJPs, offset, ignore);
618 }
619
620 // JP array would end up too large; compress it to a smaller one:
621
622 else
623 {
624 Pjp_t PjpnewRaw;
625 Pjp_t Pjpnew;
626
627 if ((PjpnewRaw = j__udyAllocJBBJP(numJPs - 1, Pjpm))
628 == (Pjp_t) NULL) return(-1);
629 Pjpnew = P_JP(PjpnewRaw);
630
631 JU_DELETECOPY(Pjpnew, Pjp2, numJPs, offset, ignore);
632 j__udyFreeJBBJP(Pjp2Raw, numJPs, Pjpm); // old.
633
634 JU_JBB_PJP(Pjbb, subexp) = PjpnewRaw;
635 }
636
637 // Clear digits bit in the bitmap:
638
639 JU_JBB_BITMAP(Pjbb, subexp) ^= bitmask;
640
641 // If the current subexpanse alone is still too large for a BranchL (with
642 // hysteresis = 1), the delete is all done:
643
644 if (numJPs > cJU_BRANCHLMAXJPS) return(1);
645
646 // Consider shrinking the current BranchB to a BranchL:
647 //
648 // Check the numbers of JPs in other subexpanses in the BranchL. Upon reaching
649 // the critical number of numJPs (which could be right at the start; again,
650 // with hysteresis = 1), its faster to just watch for any non-empty subexpanse
651 // than to count bits in each subexpanse. Upon finding too many JPs, give up
652 // on shrinking the BranchB.
653
654 for (subexp2 = 0; subexp2 < cJU_NUMSUBEXPB; ++subexp2)
655 {
656 if (subexp2 == subexp) continue; // skip current subexpanse.
657
658 if ((numJPs == cJU_BRANCHLMAXJPS) ?
659 JU_JBB_BITMAP(Pjbb, subexp2) :
660 ((numJPs += j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp2)))
661 > cJU_BRANCHLMAXJPS))
662 {
663 return(1); // too many JPs, cannot shrink.
664 }
665 }
666
667 // Shrink current BranchB to a BranchL:
668 //
669 // Note: In this rare case, ignore the return value, do not pass it to the
670 // caller, because the deletion is already successfully completed and the
671 // caller(s) must decrement population counts. The only errors expected from
672 // this call are JU_ERRNO_NOMEM and JU_ERRNO_OVERRUN, neither of which is worth
673 // forwarding from this point. See also 4.1, 4.8, and 4.15 of this file.
674
675 (void) j__udyBranchBToBranchL(Pjp, Pjpm);
676 return(1);
677
678 } // case.
679
680
681 // ****************************************************************************
682 // UNCOMPRESSED BRANCH:
683 //
684 // MACROS FOR COMMON CODE:
685 //
686 // Note the reuse of common macros here, defined earlier: JU_PVALUE*.
687 //
688 // Compress a BranchU into a leaf one index size larger:
689 //
690 // Allocate a new leaf, walk the JPs in the old BranchU and pack their contents
691 // into the new leaf (of type NewJPType), free the old BranchU, and finally
692 // restart the switch to delete Index from the new leaf. Variables Pjp, Pjpm,
693 // digit, and pop1 are in the context.
694 //
695 // Note: Its no accident that the interface to JU_BRANCHU_COMPRESS() is
696 // nearly identical to JU_BRANCHL_COMPRESS(); just NullJPType is added. The
697 // details differ in how to traverse the branchs JPs --
698 //
699 // -- and also, what to do upon encountering a cJU_JPIMMED_*_01 JP. In
700 // BranchLs and BranchBs the JP must be deleted, but in a BranchU its merely
701 // converted to a null JP, and this is done by other switch cases, so the "keep
702 // branch" situation is simpler here and JU_BRANCH_KEEP() is not used. Also,
703 // theres no code to convert a BranchU to a BranchB since counting the JPs in
704 // a BranchU is (at least presently) expensive, and besides, keeping around a
705 // BranchU is form of hysteresis.
706
707 #define JU_BRANCHU_COMPRESS(cLevel,LeafType,MaxPop1,NullJPType,NewJPType, \
708 LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \
709 { \
710 LeafType Pleaf; \
711 Pjbu_t PjbuRaw = (Pjbu_t) (Pjp->jp_Addr); \
712 Pjp_t Pjp2 = JU_JBU_PJP0(Pjp); \
713 Word_t ldigit; /* larger than uint8_t */ \
714 \
715 if ((PjllnewRaw = Alloc(MaxPop1, Pjpm)) == 0) return(-1); \
716 Pjllnew = P_JLL(PjllnewRaw); \
717 Pleaf = (LeafType) Pjllnew; \
718 JUDYLCODE(Pjv = ValueArea(Pleaf, MaxPop1);) \
719 \
720 for (ldigit = 0; ldigit < cJU_BRANCHUNUMJPS; ++ldigit, ++Pjp2) \
721 { \
722 /* fast-process common types: */ \
723 if (JU_JPTYPE(Pjp2) == (NullJPType)) continue; \
724 CopyImmed(cLevel, Pjp2, CopyIndex); \
725 \
726 pop1 = LeafToLeaf(Pleaf, JU_PVALUEPASS Pjp2, \
727 JU_DIGITTOSTATE(ldigit, cLevel), \
728 (Pvoid_t) Pjpm); \
729 Pleaf = (LeafType) (((Word_t) Pleaf) + ((cLevel) * pop1)); \
730 JUDYLCODE(Pjv += pop1;) \
731 } \
732 assert(((((Word_t) Pleaf) - ((Word_t) Pjllnew)) / (cLevel)) == (MaxPop1)); \
733 JUDYLCODE(assert((Pjv - ValueArea(Pjllnew, MaxPop1)) == (MaxPop1));) \
734 DBGCODE(JudyCheckSorted(Pjllnew, MaxPop1, cLevel);) \
735 \
736 j__udyFreeJBU(PjbuRaw, Pjpm); \
737 \
738 Pjp->jp_Type = (NewJPType); \
739 Pjp->jp_Addr = (Word_t) PjllnewRaw; \
740 goto ContinueDelWalk; /* delete from new leaf */ \
741 }
742
743 // Overall common code for initial BranchU deletion handling:
744 //
745 // Assert that Index is in the branch, then see if a BranchU should be kept or
746 // else compressed to a leaf. Variables level, Index, Pjp, and pop1 are in the
747 // context.
748 //
749 // Note: BranchU handling differs from BranchL and BranchB as described above.
750
751 #define JU_BRANCHU(cLevel,MaxPop1,LeafType,NullJPType,NewJPType, \
752 LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \
753 \
754 assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, cLevel)); \
755 assert(ParentLevel > (cLevel)); \
756 DBGCODE(parentJPtype = JU_JPTYPE(Pjp);) \
757 \
758 pop1 = JU_JPBRANCH_POP0(Pjp, cLevel) + 1; \
759 \
760 if (pop1 > (MaxPop1)) /* hysteresis = 1 */ \
761 { \
762 level = (cLevel); \
763 Pjp = P_JP(Pjp->jp_Addr) + JU_DIGITATSTATE(Index, cLevel);\
764 break; /* descend to next level */ \
765 } \
766 assert(pop1 == (MaxPop1)); \
767 \
768 JU_BRANCHU_COMPRESS(cLevel, LeafType, MaxPop1, NullJPType, NewJPType, \
769 LeafToLeaf, Alloc, ValueArea, CopyImmed, CopyIndex)
770
771
772 // END OF MACROS, START OF CASES:
773 //
774 // Note: Its no accident that the macro calls for these cases is nearly
775 // identical to the code for BranchLs, with the addition of cJU_JPNULL*
776 // parameters only needed for BranchUs.
777
778 case cJU_JPBRANCH_U2:
779
780 JU_BRANCHU(2, cJU_LEAF2_MAXPOP1, uint16_t *,
781 cJU_JPNULL1, cJU_JPLEAF2,
782 j__udyLeaf1ToLeaf2, j__udyAllocJLL2, JL_LEAF2VALUEAREA,
783 JU_BRANCH_COPY_IMMED_EVEN, ignore);
784
785 case cJU_JPBRANCH_U3:
786
787 JU_BRANCHU(3, cJU_LEAF3_MAXPOP1, uint8_t *,
788 cJU_JPNULL2, cJU_JPLEAF3,
789 j__udyLeaf2ToLeaf3, j__udyAllocJLL3, JL_LEAF3VALUEAREA,
790 JU_BRANCH_COPY_IMMED_ODD, JU_COPY3_LONG_TO_PINDEX);
791
792 #ifdef JU_64BIT
793 case cJU_JPBRANCH_U4:
794
795 JU_BRANCHU(4, cJU_LEAF4_MAXPOP1, uint32_t *,
796 cJU_JPNULL3, cJU_JPLEAF4,
797 j__udyLeaf3ToLeaf4, j__udyAllocJLL4, JL_LEAF4VALUEAREA,
798 JU_BRANCH_COPY_IMMED_EVEN, ignore);
799
800 case cJU_JPBRANCH_U5:
801
802 JU_BRANCHU(5, cJU_LEAF5_MAXPOP1, uint8_t *,
803 cJU_JPNULL4, cJU_JPLEAF5,
804 j__udyLeaf4ToLeaf5, j__udyAllocJLL5, JL_LEAF5VALUEAREA,
805 JU_BRANCH_COPY_IMMED_ODD, JU_COPY5_LONG_TO_PINDEX);
806
807 case cJU_JPBRANCH_U6:
808
809 JU_BRANCHU(6, cJU_LEAF6_MAXPOP1, uint8_t *,
810 cJU_JPNULL5, cJU_JPLEAF6,
811 j__udyLeaf5ToLeaf6, j__udyAllocJLL6, JL_LEAF6VALUEAREA,
812 JU_BRANCH_COPY_IMMED_ODD, JU_COPY6_LONG_TO_PINDEX);
813
814 case cJU_JPBRANCH_U7:
815
816 JU_BRANCHU(7, cJU_LEAF7_MAXPOP1, uint8_t *,
817 cJU_JPNULL6, cJU_JPLEAF7,
818 j__udyLeaf6ToLeaf7, j__udyAllocJLL7, JL_LEAF7VALUEAREA,
819 JU_BRANCH_COPY_IMMED_ODD, JU_COPY7_LONG_TO_PINDEX);
820 #endif // JU_64BIT
821
822 // A top-level BranchU is different and cannot use JU_BRANCHU(): Dont try to
823 // compress to a (LEAFW) leaf yet, but leave this for a later deletion
824 // (hysteresis > 0); just descend through the BranchU:
825
826 case cJU_JPBRANCH_U:
827
828 DBGCODE(parentJPtype = JU_JPTYPE(Pjp);)
829
830 level = cJU_ROOTSTATE;
831 Pjp = P_JP(Pjp->jp_Addr) + JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
832 break;
833
834
835 // ****************************************************************************
836 // LINEAR LEAF:
837 //
838 // State transitions while deleting an Index, the inverse of the similar table
839 // that appears in JudyIns.c:
840 //
841 // Note: In JudyIns.c this table is not needed and does not appear until the
842 // Immed handling code; because once a Leaf is reached upon growing the tree,
843 // the situation remains simpler, but for deleting indexes, the complexity
844 // arises when leaves must compress to Immeds.
845 //
846 // Note: There are other transitions possible too, not shown here, such as to
847 // a leaf one level higher.
848 //
849 // (Yes, this is very terse... Study it and it will make sense.)
850 // (Note, parts of this diagram are repeated below for quick reference.)
851 //
852 // reformat JP here for Judy1 only, from word-1 to word-2
853 // |
854 // JUDY1 && JU_64BIT JUDY1 || JU_64BIT |
855 // V
856 // (*) Leaf1 [[ => 1_15..08 ] => 1_07 => ... => 1_04 ] => 1_03 => 1_02 => 1_01
857 // Leaf2 [[ => 2_07..04 ] => 2_03 => 2_02 ] => 2_01
858 // Leaf3 [[ => 3_05..03 ] => 3_02 ] => 3_01
859 // JU_64BIT only:
860 // Leaf4 [[ => 4_03..02 ]] => 4_01
861 // Leaf5 [[ => 5_03..02 ]] => 5_01
862 // Leaf6 [[ => 6_02 ]] => 6_01
863 // Leaf7 [[ => 7_02 ]] => 7_01
864 //
865 // (*) For Judy1 & 64-bit, go directly from a LeafB1 to cJU_JPIMMED_1_15; skip
866 // Leaf1, as described in Judy1.h regarding cJ1_JPLEAF1.
867 //
868 // MACROS FOR COMMON CODE:
869 //
870 // (De)compress a LeafX into a LeafY one index size (cIS) larger (X+1 = Y):
871 //
872 // This is only possible when the current leaf is under a narrow pointer
873 // ((ParentLevel - 1) > cIS) and its population fits in a higher-level leaf.
874 // Variables ParentLevel, pop1, PjllnewRaw, Pjllnew, Pjpm, and Index are in the
875 // context.
876 //
877 // Note: Doing an "uplevel" doesnt occur until the old leaf can be compressed
878 // up one level BEFORE deleting an index; that is, hysteresis = 1.
879 //
880 // Note: LeafType, MaxPop1, NewJPType, and Alloc refer to the up-level leaf,
881 // not the current leaf.
882 //
883 // Note: 010327: Fixed bug where the jp_DcdPopO next-uplevel digit (byte)
884 // above the current Pop0 value was not being cleared. When upleveling, one
885 // digit in jp_DcdPopO "moves" from being part of the Dcd subfield to the Pop0
886 // subfield, but since a leaf maxpop1 is known to be <= 1 byte in size, the new
887 // Pop0 byte should always be zero. This is easy to overlook because
888 // JU_JPLEAF_POP0() "knows" to only use the LSB of Pop0 (for efficiency) and
889 // ignore the other bytes... Until someone uses cJU_POP0MASK() instead of
890 // JU_JPLEAF_POP0(), such as in JudyInsertBranch.c.
891 //
892 // TBD: Should JudyInsertBranch.c use JU_JPLEAF_POP0() rather than
893 // cJU_POP0MASK(), for efficiency? Does it know for sure its a narrow pointer
894 // under the leaf? Not necessarily.
895
896 #define JU_LEAF_UPLEVEL(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \
897 Alloc,ValueArea) \
898 \
899 assert(((ParentLevel - 1) == (cIS)) || (pop1 >= (MaxPop1))); \
900 \
901 if (((ParentLevel - 1) > (cIS)) /* under narrow pointer */ \
902 && (pop1 == (MaxPop1))) /* hysteresis = 1 */ \
903 { \
904 Word_t D_cdP0; \
905 if ((PjllnewRaw = Alloc(MaxPop1, Pjpm)) == 0) return(-1); \
906 Pjllnew = P_JLL(PjllnewRaw); \
907 JUDYLCODE(Pjv = ValueArea((LeafType) Pjllnew, MaxPop1);) \
908 \
909 (void) LeafToLeaf((LeafType) Pjllnew, JU_PVALUEPASS Pjp, \
910 Index & cJU_DCDMASK(cIS), /* TBD, Doug says */ \
911 (Pvoid_t) Pjpm); \
912 DBGCODE(JudyCheckSorted(Pjllnew, MaxPop1, cIS + 1);) \
913 \
914 D_cdP0 = (~cJU_MASKATSTATE((cIS) + 1)) & JU_JPDCDPOP0(Pjp); \
915 JU_JPSETADT(Pjp, (Word_t)PjllnewRaw, D_cdP0, NewJPType); \
916 goto ContinueDelWalk; /* delete from new leaf */ \
917 }
918
919
920 // For Leaf3, only support JU_LEAF_UPLEVEL on a 64-bit system, and for Leaf7,
921 // there is no JU_LEAF_UPLEVEL:
922 //
923 // Note: Theres no way here to go from Leaf3 [Leaf7] to LEAFW on a 32-bit
924 // [64-bit] system. Thats handled in the main code, because its different in
925 // that a JPM is involved.
926
927 #ifndef JU_64BIT // 32-bit.
928 #define JU_LEAF_UPLEVEL64(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \
929 Alloc,ValueArea) // null.
930 #else
931 #define JU_LEAF_UPLEVEL64(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \
932 Alloc,ValueArea) \
933 JU_LEAF_UPLEVEL (cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \
934 Alloc,ValueArea)
935 #define JU_LEAF_UPLEVEL_NONE(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \
936 Alloc,ValueArea) // null.
937 #endif
938
939 // Compress a Leaf* with pop1 = 2, or a JPIMMED_*_02, into a JPIMMED_*_01:
940 //
941 // Copy whichever Index is NOT being deleted (and assert that the other one is
942 // found; Index must be valid). This requires special handling of the Index
943 // bytes (and value area). Variables Pjp, Index, offset, and Pleaf are in the
944 // context, offset is modified to the undeleted Index, and Pjp is modified
945 // including jp_Addr.
946
947
948 #define JU_TOIMMED_01_EVEN(cIS,ignore1,ignore2) \
949 { \
950 Word_t D_cdP0; \
951 Word_t A_ddr = 0; \
952 uint8_t T_ype = JU_JPTYPE(Pjp); \
953 offset = (Pleaf[0] == JU_LEASTBYTES(Index, cIS)); /* undeleted Ind */ \
954 assert(Pleaf[offset ? 0 : 1] == JU_LEASTBYTES(Index, cIS)); \
955 D_cdP0 = (Index & cJU_DCDMASK(cIS)) | Pleaf[offset]; \
956 JUDYLCODE(A_ddr = Pjv[offset];) \
957 JU_JPSETADT(Pjp, A_ddr, D_cdP0, T_ype); \
958 }
959
960 #define JU_TOIMMED_01_ODD(cIS,SearchLeaf,CopyPIndex) \
961 { \
962 Word_t D_cdP0; \
963 Word_t A_ddr = 0; \
964 uint8_t T_ype = JU_JPTYPE(Pjp); \
965 \
966 offset = SearchLeaf(Pleaf, 2, Index); \
967 assert(offset >= 0); /* Index must be valid */ \
968 CopyPIndex(D_cdP0, & (Pleaf[offset ? 0 : cIS])); \
969 D_cdP0 |= Index & cJU_DCDMASK(cIS); \
970 JUDYLCODE(A_ddr = Pjv[offset ? 0 : 1];) \
971 JU_JPSETADT(Pjp, A_ddr, D_cdP0, T_ype); \
972 }
973
974
975 // Compress a Leaf* into a JPIMMED_*_0[2+]:
976 //
977 // This occurs as soon as its possible, with hysteresis = 0. Variables pop1,
978 // Pleaf, offset, and Pjpm are in the context.
979 //
980 // TBD: Explain why hysteresis = 0 here, rather than > 0. Probably because
981 // the insert code assumes if the population is small enough, an Immed is used,
982 // not a leaf.
983 //
984 // The differences between Judy1 and JudyL with respect to value area handling
985 // are just too large for completely common code between them... Oh well, some
986 // big ifdefs follow.
987
988 #ifdef JUDY1
989
990 #define JU_LEAF_TOIMMED(cIS,LeafType,MaxPop1,BaseJPType,ignore1,\
991 ignore2,ignore3,ignore4, \
992 DeleteCopy,FreeLeaf) \
993 \
994 assert(pop1 > (MaxPop1)); \
995 \
996 if ((pop1 - 1) == (MaxPop1)) /* hysteresis = 0 */ \
997 { \
998 Pjll_t PjllRaw = (Pjll_t) (Pjp->jp_Addr); \
999 DeleteCopy((LeafType) (Pjp->jp_1Index), Pleaf, pop1, offset, cIS); \
1000 DBGCODE(JudyCheckSorted((Pjll_t) (Pjp->jp_1Index), pop1-1, cIS);) \
1001 Pjp->jp_Type = (BaseJPType) - 1 + (MaxPop1) - 1; \
1002 FreeLeaf(PjllRaw, pop1, Pjpm); \
1003 return(1); \
1004 }
1005
1006 #else // JUDYL
1007
1008 // Pjv is also in the context.
1009
1010 #define JU_LEAF_TOIMMED(cIS,LeafType,MaxPop1,BaseJPType,ignore1,\
1011 ignore2,ignore3,ignore4, \
1012 DeleteCopy,FreeLeaf) \
1013 \
1014 assert(pop1 > (MaxPop1)); \
1015 \
1016 if ((pop1 - 1) == (MaxPop1)) /* hysteresis = 0 */ \
1017 { \
1018 Pjll_t PjllRaw = (Pjll_t) (Pjp->jp_Addr); \
1019 Pjv_t PjvnewRaw; \
1020 Pjv_t Pjvnew; \
1021 \
1022 if ((PjvnewRaw = j__udyLAllocJV(pop1 - 1, Pjpm)) \
1023 == (Pjv_t) NULL) return(-1); \
1024 JUDYLCODE(Pjvnew = P_JV(PjvnewRaw);) \
1025 \
1026 DeleteCopy((LeafType) (Pjp->jp_LIndex), Pleaf, pop1, offset, cIS); \
1027 JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, cIS); \
1028 DBGCODE(JudyCheckSorted((Pjll_t) (Pjp->jp_LIndex), pop1-1, cIS);) \
1029 FreeLeaf(PjllRaw, pop1, Pjpm); \
1030 Pjp->jp_Addr = (Word_t) PjvnewRaw; \
1031 Pjp->jp_Type = (BaseJPType) - 2 + (MaxPop1); \
1032 return(1); \
1033 }
1034
1035 // A complicating factor for JudyL & 32-bit is that Leaf2..3, and for JudyL &
1036 // 64-bit Leaf 4..7, go directly to an Immed*_01, where the value is stored in
1037 // jp_Addr and not in a separate LeafV. For efficiency, use the following
1038 // macro in cases where it can apply; it is rigged to do the right thing.
1039 // Unfortunately, this requires the calling code to "know" the transition table
1040 // and call the right macro.
1041 //
1042 // This variant compresses a Leaf* with pop1 = 2 into a JPIMMED_*_01:
1043
1044 #define JU_LEAF_TOIMMED_01(cIS,LeafType,MaxPop1,ignore,Immed01JPType, \
1045 ToImmed,SearchLeaf,CopyPIndex, \
1046 DeleteCopy,FreeLeaf) \
1047 \
1048 assert(pop1 > (MaxPop1)); \
1049 \
1050 if ((pop1 - 1) == (MaxPop1)) /* hysteresis = 0 */ \
1051 { \
1052 Pjll_t PjllRaw = (Pjll_t) (Pjp->jp_Addr); \
1053 ToImmed(cIS, SearchLeaf, CopyPIndex); \
1054 FreeLeaf(PjllRaw, pop1, Pjpm); \
1055 Pjp->jp_Type = (Immed01JPType); \
1056 return(1); \
1057 }
1058 #endif // JUDYL
1059
1060 // See comments above about these:
1061 //
1062 // Note: Here "23" means index size 2 or 3, and "47" means 4..7.
1063
1064 #if (defined(JUDY1) || defined(JU_64BIT))
1065 #define JU_LEAF_TOIMMED_23(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \
1066 ToImmed,SearchLeaf,CopyPIndex, \
1067 DeleteCopy,FreeLeaf) \
1068 JU_LEAF_TOIMMED( cIS,LeafType,MaxPop1,BaseJPType,ignore1, \
1069 ignore2,ignore3,ignore4, \
1070 DeleteCopy,FreeLeaf)
1071 #else // JUDYL && 32-bit
1072 #define JU_LEAF_TOIMMED_23(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \
1073 ToImmed,SearchLeaf,CopyPIndex, \
1074 DeleteCopy,FreeLeaf) \
1075 JU_LEAF_TOIMMED_01(cIS,LeafType,MaxPop1,ignore,Immed01JPType, \
1076 ToImmed,SearchLeaf,CopyPIndex, \
1077 DeleteCopy,FreeLeaf)
1078 #endif
1079
1080 #ifdef JU_64BIT
1081 #ifdef JUDY1
1082 #define JU_LEAF_TOIMMED_47(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \
1083 ToImmed,SearchLeaf,CopyPIndex, \
1084 DeleteCopy,FreeLeaf) \
1085 JU_LEAF_TOIMMED( cIS,LeafType,MaxPop1,BaseJPType,ignore1, \
1086 ignore2,ignore3,ignore4, \
1087 DeleteCopy,FreeLeaf)
1088 #else // JUDYL && 64-bit
1089 #define JU_LEAF_TOIMMED_47(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \
1090 ToImmed,SearchLeaf,CopyPIndex, \
1091 DeleteCopy,FreeLeaf) \
1092 JU_LEAF_TOIMMED_01(cIS,LeafType,MaxPop1,ignore,Immed01JPType, \
1093 ToImmed,SearchLeaf,CopyPIndex, \
1094 DeleteCopy,FreeLeaf)
1095 #endif // JUDYL
1096 #endif // JU_64BIT
1097
1098 // Compress a Leaf* in place:
1099 //
1100 // Here hysteresis = 0 (no memory is wasted). Variables pop1, Pleaf, and
1101 // offset, and for JudyL, Pjv, are in the context.
1102
1103 #ifdef JUDY1
1104 #define JU_LEAF_INPLACE(cIS,GrowInPlace,DeleteInPlace) \
1105 if (GrowInPlace(pop1 - 1)) /* hysteresis = 0 */ \
1106 { \
1107 DeleteInPlace(Pleaf, pop1, offset, cIS); \
1108 DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \
1109 return(1); \
1110 }
1111 #else
1112 #define JU_LEAF_INPLACE(cIS,GrowInPlace,DeleteInPlace) \
1113 if (GrowInPlace(pop1 - 1)) /* hysteresis = 0 */ \
1114 { \
1115 DeleteInPlace(Pleaf, pop1, offset, cIS); \
1116 /**/ JU_DELETEINPLACE(Pjv, pop1, offset, ignore); \
1117 DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \
1118 return(1); \
1119 }
1120 #endif
1121
1122 // Compress a Leaf* into a smaller memory object of the same JP type:
1123 //
1124 // Variables PjllnewRaw, Pjllnew, Pleafpop1, Pjpm, PleafRaw, Pleaf, and offset
1125 // are in the context.
1126
1127 #ifdef JUDY1
1128
1129 #define JU_LEAF_SHRINK(cIS,LeafType,DeleteCopy,Alloc,FreeLeaf,ValueArea) \
1130 if ((PjllnewRaw = Alloc(pop1 - 1, Pjpm)) == 0) return(-1); \
1131 Pjllnew = P_JLL(PjllnewRaw); \
1132 DeleteCopy((LeafType) Pjllnew, Pleaf, pop1, offset, cIS); \
1133 DBGCODE(JudyCheckSorted(Pjllnew, pop1 - 1, cIS);) \
1134 FreeLeaf(PleafRaw, pop1, Pjpm); \
1135 Pjp->jp_Addr = (Word_t) PjllnewRaw; \
1136 return(1)
1137
1138 #else // JUDYL
1139
1140 #define JU_LEAF_SHRINK(cIS,LeafType,DeleteCopy,Alloc,FreeLeaf,ValueArea) \
1141 { \
1142 /**/ Pjv_t Pjvnew; \
1143 \
1144 if ((PjllnewRaw = Alloc(pop1 - 1, Pjpm)) == 0) return(-1); \
1145 Pjllnew = P_JLL(PjllnewRaw); \
1146 /**/ Pjvnew = ValueArea(Pjllnew, pop1 - 1); \
1147 DeleteCopy((LeafType) Pjllnew, Pleaf, pop1, offset, cIS); \
1148 /**/ JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, cIS); \
1149 DBGCODE(JudyCheckSorted(Pjllnew, pop1 - 1, cIS);) \
1150 FreeLeaf(PleafRaw, pop1, Pjpm); \
1151 Pjp->jp_Addr = (Word_t) PjllnewRaw; \
1152 return(1); \
1153 }
1154 #endif // JUDYL
1155
1156 // Overall common code for Leaf* deletion handling:
1157 //
1158 // See if the leaf can be:
1159 // - (de)compressed to one a level higher (JU_LEAF_UPLEVEL()), or if not,
1160 // - compressed to an Immediate JP (JU_LEAF_TOIMMED()), or if not,
1161 // - shrunk in place (JU_LEAF_INPLACE()), or if none of those, then
1162 // - shrink the leaf to a smaller chunk of memory (JU_LEAF_SHRINK()).
1163 //
1164 // Variables Pjp, pop1, Index, and offset are in the context.
1165 // The *Up parameters refer to a leaf one level up, if there is any.
1166
1167 #define JU_LEAF(cIS, \
1168 UpLevel, \
1169 LeafTypeUp,MaxPop1Up,LeafJPTypeUp,LeafToLeaf, \
1170 AllocUp,ValueAreaUp, \
1171 LeafToImmed,ToImmed,CopyPIndex, \
1172 LeafType,ImmedMaxPop1,ImmedBaseJPType,Immed01JPType, \
1173 SearchLeaf,GrowInPlace,DeleteInPlace,DeleteCopy, \
1174 Alloc,FreeLeaf,ValueArea) \
1175 { \
1176 Pjll_t PleafRaw; \
1177 LeafType Pleaf; \
1178 \
1179 assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, cIS)); \
1180 assert(ParentLevel > (cIS)); \
1181 \
1182 PleafRaw = (Pjll_t) (Pjp->jp_Addr); \
1183 Pleaf = (LeafType) P_JLL(PleafRaw); \
1184 pop1 = JU_JPLEAF_POP0(Pjp) + 1; \
1185 \
1186 UpLevel(cIS, LeafTypeUp, MaxPop1Up, LeafJPTypeUp, \
1187 LeafToLeaf, AllocUp, ValueAreaUp); \
1188 \
1189 offset = SearchLeaf(Pleaf, pop1, Index); \
1190 assert(offset >= 0); /* Index must be valid */ \
1191 JUDYLCODE(Pjv = ValueArea(Pleaf, pop1);) \
1192 \
1193 LeafToImmed(cIS, LeafType, ImmedMaxPop1, \
1194 ImmedBaseJPType, Immed01JPType, \
1195 ToImmed, SearchLeaf, CopyPIndex, \
1196 DeleteCopy, FreeLeaf); \
1197 \
1198 JU_LEAF_INPLACE(cIS, GrowInPlace, DeleteInPlace); \
1199 \
1200 JU_LEAF_SHRINK(cIS, LeafType, DeleteCopy, Alloc, FreeLeaf, \
1201 ValueArea); \
1202 }
1203
1204 // END OF MACROS, START OF CASES:
1205 //
1206 // (*) Leaf1 [[ => 1_15..08 ] => 1_07 => ... => 1_04 ] => 1_03 => 1_02 => 1_01
1207
1208 #if (defined(JUDYL) || (! defined(JU_64BIT)))
1209 case cJU_JPLEAF1:
1210
1211 JU_LEAF(1,
1212 JU_LEAF_UPLEVEL, uint16_t *, cJU_LEAF2_MAXPOP1, cJU_JPLEAF2,
1213 j__udyLeaf1ToLeaf2, j__udyAllocJLL2, JL_LEAF2VALUEAREA,
1214 JU_LEAF_TOIMMED, ignore, ignore,
1215 uint8_t *, cJU_IMMED1_MAXPOP1,
1216 cJU_JPIMMED_1_02, cJU_JPIMMED_1_01, j__udySearchLeaf1,
1217 JU_LEAF1GROWINPLACE, JU_DELETEINPLACE, JU_DELETECOPY,
1218 j__udyAllocJLL1, j__udyFreeJLL1, JL_LEAF1VALUEAREA);
1219 #endif
1220
1221 // A complicating factor is that for JudyL & 32-bit, a Leaf2 must go directly
1222 // to an Immed 2_01 and a Leaf3 must go directly to an Immed 3_01:
1223 //
1224 // Leaf2 [[ => 2_07..04 ] => 2_03 => 2_02 ] => 2_01
1225 // Leaf3 [[ => 3_05..03 ] => 3_02 ] => 3_01
1226 //
1227 // Hence use JU_LEAF_TOIMMED_23 instead of JU_LEAF_TOIMMED in the cases below,
1228 // and also the parameters ToImmed and, for odd index sizes, CopyPIndex, are
1229 // required.
1230
1231 case cJU_JPLEAF2:
1232
1233 JU_LEAF(2,
1234 JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF3_MAXPOP1, cJU_JPLEAF3,
1235 j__udyLeaf2ToLeaf3, j__udyAllocJLL3, JL_LEAF3VALUEAREA,
1236 JU_LEAF_TOIMMED_23, JU_TOIMMED_01_EVEN, ignore,
1237 uint16_t *, cJU_IMMED2_MAXPOP1,
1238 cJU_JPIMMED_2_02, cJU_JPIMMED_2_01, j__udySearchLeaf2,
1239 JU_LEAF2GROWINPLACE, JU_DELETEINPLACE, JU_DELETECOPY,
1240 j__udyAllocJLL2, j__udyFreeJLL2, JL_LEAF2VALUEAREA);
1241
1242 // On 32-bit there is no transition to "uplevel" for a Leaf3, so use
1243 // JU_LEAF_UPLEVEL64 instead of JU_LEAF_UPLEVEL:
1244
1245 case cJU_JPLEAF3:
1246
1247 JU_LEAF(3,
1248 JU_LEAF_UPLEVEL64, uint32_t *, cJU_LEAF4_MAXPOP1,
1249 cJU_JPLEAF4,
1250 j__udyLeaf3ToLeaf4, j__udyAllocJLL4, JL_LEAF4VALUEAREA,
1251 JU_LEAF_TOIMMED_23,
1252 JU_TOIMMED_01_ODD, JU_COPY3_PINDEX_TO_LONG,
1253 uint8_t *, cJU_IMMED3_MAXPOP1,
1254 cJU_JPIMMED_3_02, cJU_JPIMMED_3_01, j__udySearchLeaf3,
1255 JU_LEAF3GROWINPLACE, JU_DELETEINPLACE_ODD,
1256 JU_DELETECOPY_ODD,
1257 j__udyAllocJLL3, j__udyFreeJLL3, JL_LEAF3VALUEAREA);
1258
1259 #ifdef JU_64BIT
1260
1261 // A complicating factor is that for JudyL & 64-bit, a Leaf[4-7] must go
1262 // directly to an Immed [4-7]_01:
1263 //
1264 // Leaf4 [[ => 4_03..02 ]] => 4_01
1265 // Leaf5 [[ => 5_03..02 ]] => 5_01
1266 // Leaf6 [[ => 6_02 ]] => 6_01
1267 // Leaf7 [[ => 7_02 ]] => 7_01
1268 //
1269 // Hence use JU_LEAF_TOIMMED_47 instead of JU_LEAF_TOIMMED in the cases below.
1270
1271 case cJU_JPLEAF4:
1272
1273 JU_LEAF(4,
1274 JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF5_MAXPOP1, cJU_JPLEAF5,
1275 j__udyLeaf4ToLeaf5, j__udyAllocJLL5, JL_LEAF5VALUEAREA,
1276 JU_LEAF_TOIMMED_47, JU_TOIMMED_01_EVEN, ignore,
1277 uint32_t *, cJU_IMMED4_MAXPOP1,
1278 cJ1_JPIMMED_4_02, cJU_JPIMMED_4_01, j__udySearchLeaf4,
1279 JU_LEAF4GROWINPLACE, JU_DELETEINPLACE, JU_DELETECOPY,
1280 j__udyAllocJLL4, j__udyFreeJLL4, JL_LEAF4VALUEAREA);
1281
1282 case cJU_JPLEAF5:
1283
1284 JU_LEAF(5,
1285 JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF6_MAXPOP1, cJU_JPLEAF6,
1286 j__udyLeaf5ToLeaf6, j__udyAllocJLL6, JL_LEAF6VALUEAREA,
1287 JU_LEAF_TOIMMED_47,
1288 JU_TOIMMED_01_ODD, JU_COPY5_PINDEX_TO_LONG,
1289 uint8_t *, cJU_IMMED5_MAXPOP1,
1290 cJ1_JPIMMED_5_02, cJU_JPIMMED_5_01, j__udySearchLeaf5,
1291 JU_LEAF5GROWINPLACE, JU_DELETEINPLACE_ODD,
1292 JU_DELETECOPY_ODD,
1293 j__udyAllocJLL5, j__udyFreeJLL5, JL_LEAF5VALUEAREA);
1294
1295 case cJU_JPLEAF6:
1296
1297 JU_LEAF(6,
1298 JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF7_MAXPOP1, cJU_JPLEAF7,
1299 j__udyLeaf6ToLeaf7, j__udyAllocJLL7, JL_LEAF7VALUEAREA,
1300 JU_LEAF_TOIMMED_47,
1301 JU_TOIMMED_01_ODD, JU_COPY6_PINDEX_TO_LONG,
1302 uint8_t *, cJU_IMMED6_MAXPOP1,
1303 cJ1_JPIMMED_6_02, cJU_JPIMMED_6_01, j__udySearchLeaf6,
1304 JU_LEAF6GROWINPLACE, JU_DELETEINPLACE_ODD,
1305 JU_DELETECOPY_ODD,
1306 j__udyAllocJLL6, j__udyFreeJLL6, JL_LEAF6VALUEAREA);
1307
1308 // There is no transition to "uplevel" for a Leaf7, so use JU_LEAF_UPLEVEL_NONE
1309 // instead of JU_LEAF_UPLEVEL, and ignore all of the parameters to that macro:
1310
1311 case cJU_JPLEAF7:
1312
1313 JU_LEAF(7,
1314 JU_LEAF_UPLEVEL_NONE, ignore1, ignore2, ignore3, ignore4,
1315 ignore5, ignore6,
1316 JU_LEAF_TOIMMED_47,
1317 JU_TOIMMED_01_ODD, JU_COPY7_PINDEX_TO_LONG,
1318 uint8_t *, cJU_IMMED7_MAXPOP1,
1319 cJ1_JPIMMED_7_02, cJU_JPIMMED_7_01, j__udySearchLeaf7,
1320 JU_LEAF7GROWINPLACE, JU_DELETEINPLACE_ODD,
1321 JU_DELETECOPY_ODD,
1322 j__udyAllocJLL7, j__udyFreeJLL7, JL_LEAF7VALUEAREA);
1323 #endif // JU_64BIT
1324
1325
1326 // ****************************************************************************
1327 // BITMAP LEAF:
1328
1329 case cJU_JPLEAF_B1:
1330 {
1331 #ifdef JUDYL
1332 Pjv_t PjvnewRaw; // new value area.
1333 Pjv_t Pjvnew;
1334 Word_t subexp; // 1 of 8 subexpanses in bitmap.
1335 Pjlb_t Pjlb; // pointer to bitmap part of the leaf.
1336 BITMAPL_t bitmap; // for one subexpanse.
1337 BITMAPL_t bitmask; // bit set for Indexs digit.
1338 #endif
1339 assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, 1));
1340 assert(ParentLevel > 1);
1341 // valid Index:
1342 assert(JU_BITMAPTESTL(P_JLB(Pjp->jp_Addr), Index));
1343
1344 pop1 = JU_JPLEAF_POP0(Pjp) + 1;
1345
1346 // Like a Leaf1, see if its under a narrow pointer and can become a Leaf2
1347 // (hysteresis = 1):
1348
1349 JU_LEAF_UPLEVEL(1, uint16_t *, cJU_LEAF2_MAXPOP1, cJU_JPLEAF2,
1350 j__udyLeaf1ToLeaf2, j__udyAllocJLL2,
1351 JL_LEAF2VALUEAREA);
1352
1353 #if (defined(JUDY1) && defined(JU_64BIT))
1354
1355 // Handle the unusual special case, on Judy1 64-bit only, where a LeafB1 goes
1356 // directly to a JPIMMED_1_15; as described in comments in Judy1.h and
1357 // JudyIns.c. Copy 1-byte indexes from old LeafB1 to the Immed:
1358
1359 if ((pop1 - 1) == cJU_IMMED1_MAXPOP1) // hysteresis = 0.
1360 {
1361 Pjlb_t PjlbRaw; // bitmap in old leaf.
1362 Pjlb_t Pjlb;
1363 uint8_t * Pleafnew; // JPIMMED as a pointer.
1364 Word_t ldigit; // larger than uint8_t.
1365
1366 PjlbRaw = (Pjlb_t) (Pjp->jp_Addr);
1367 Pjlb = P_JLB(PjlbRaw);
1368 Pleafnew = Pjp->jp_1Index;
1369
1370 JU_BITMAPCLEARL(Pjlb, Index); // unset Indexs bit.
1371
1372 // TBD: This is very slow, there must be a better way:
1373
1374 for (ldigit = 0; ldigit < cJU_BRANCHUNUMJPS; ++ldigit)
1375 {
1376 if (JU_BITMAPTESTL(Pjlb, ldigit))
1377 {
1378 *Pleafnew++ = ldigit;
1379 assert(Pleafnew - (Pjp->jp_1Index)
1380 <= cJU_IMMED1_MAXPOP1);
1381 }
1382 }
1383
1384 DBGCODE(JudyCheckSorted((Pjll_t) (Pjp->jp_1Index),
1385 cJU_IMMED1_MAXPOP1, 1);)
1386 j__udyFreeJLB1(PjlbRaw, Pjpm);
1387
1388 Pjp->jp_Type = cJ1_JPIMMED_1_15;
1389 return(1);
1390 }
1391
1392 #else // (JUDYL || (! JU_64BIT))
1393
1394 // Compress LeafB1 to a Leaf1:
1395 //
1396 // Note: 4.37 of this file contained alternate code for Judy1 only that simply
1397 // cleared the bit and allowed the LeafB1 to go below cJU_LEAF1_MAXPOP1. This
1398 // was the ONLY case where a malloc failure was not fatal; however, it violated
1399 // the critical assumption that the tree is always kept in least-compressed
1400 // form.
1401
1402 if (pop1 == cJU_LEAF1_MAXPOP1) // hysteresis = 1.
1403 {
1404 if (j__udyLeafB1ToLeaf1(Pjp, Pjpm) == -1) return(-1);
1405 goto ContinueDelWalk; // delete Index in new Leaf1.
1406 }
1407 #endif // (JUDYL || (! JU_64BIT))
1408
1409 #ifdef JUDY1
1410 // unset Indexs bit:
1411
1412 JU_BITMAPCLEARL(P_JLB(Pjp->jp_Addr), Index);
1413 #else // JUDYL
1414
1415 // This is very different from Judy1 because of the need to manage the value
1416 // area:
1417 //
1418 // Get last byte to decode from Index, and pointer to bitmap leaf:
1419
1420 digit = JU_DIGITATSTATE(Index, 1);
1421 Pjlb = P_JLB(Pjp->jp_Addr);
1422
1423 // Prepare additional values:
1424
1425 subexp = digit / cJU_BITSPERSUBEXPL; // which subexpanse.
1426 bitmap = JU_JLB_BITMAP(Pjlb, subexp); // subexps 32-bit map.
1427 PjvRaw = JL_JLB_PVALUE(Pjlb, subexp); // corresponding values.
1428 Pjv = P_JV(PjvRaw);
1429 bitmask = JU_BITPOSMASKL(digit); // mask for Index.
1430
1431 assert(bitmap & bitmask); // Index must be valid.
1432
1433 if (bitmap == cJU_FULLBITMAPL) // full bitmap, take shortcut:
1434 {
1435 pop1 = cJU_BITSPERSUBEXPL;
1436 offset = digit % cJU_BITSPERSUBEXPL;
1437 }
1438 else // compute subexpanse pop1 and value area offset:
1439 {
1440 pop1 = j__udyCountBitsL(bitmap);
1441 offset = j__udyCountBitsL(bitmap & (bitmask - 1));
1442 }
1443
1444 // Handle solitary Index remaining in subexpanse:
1445
1446 if (pop1 == 1)
1447 {
1448 j__udyLFreeJV(PjvRaw, 1, Pjpm);
1449
1450 JL_JLB_PVALUE(Pjlb, subexp) = (Pjv_t) NULL;
1451 JU_JLB_BITMAP(Pjlb, subexp) = 0;
1452
1453 return(1);
1454 }
1455
1456 // Shrink value area in place or move to a smaller value area:
1457
1458 if (JL_LEAFVGROWINPLACE(pop1 - 1)) // hysteresis = 0.
1459 {
1460 JU_DELETEINPLACE(Pjv, pop1, offset, ignore);
1461 }
1462 else
1463 {
1464 if ((PjvnewRaw = j__udyLAllocJV(pop1 - 1, Pjpm))
1465 == (Pjv_t) NULL) return(-1);
1466 Pjvnew = P_JV(PjvnewRaw);
1467
1468 JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, ignore);
1469 j__udyLFreeJV(PjvRaw, pop1, Pjpm);
1470 JL_JLB_PVALUE(Pjlb, subexp) = (Pjv_t) PjvnewRaw;
1471 }
1472
1473 JU_JLB_BITMAP(Pjlb, subexp) ^= bitmask; // clear Indexs bit.
1474
1475 #endif // JUDYL
1476
1477 return(1);
1478
1479 } // case.
1480
1481
1482 #ifdef JUDY1
1483
1484 // ****************************************************************************
1485 // FULL POPULATION LEAF:
1486 //
1487 // Convert to a LeafB1 and delete the index. Hysteresis = 0; none is possible.
1488 //
1489 // Note: Earlier the second assertion below said, "== 2", but in fact the
1490 // parent could be at a higher level if a fullpop is under a narrow pointer.
1491
1492 case cJ1_JPFULLPOPU1:
1493 {
1494 Pjlb_t PjlbRaw;
1495 Pjlb_t Pjlb;
1496 Word_t subexp;
1497
1498 assert(! JU_DCDNOTMATCHINDEX(Index, Pjp, 2));
1499 assert(ParentLevel > 1); // see above.
1500
1501 if ((PjlbRaw = j__udyAllocJLB1(Pjpm)) == (Pjlb_t) NULL)
1502 return(-1);
1503 Pjlb = P_JLB(PjlbRaw);
1504
1505 // Fully populate the leaf, then unset Indexs bit:
1506
1507 for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp)
1508 JU_JLB_BITMAP(Pjlb, subexp) = cJU_FULLBITMAPL;
1509
1510 JU_BITMAPCLEARL(Pjlb, Index);
1511
1512 Pjp->jp_Addr = (Word_t) PjlbRaw;
1513 Pjp->jp_Type = cJU_JPLEAF_B1;
1514
1515 return(1);
1516 }
1517 #endif // JUDY1
1518
1519
1520 // ****************************************************************************
1521 // IMMEDIATE JP:
1522 //
1523 // If theres just the one Index in the Immed, convert the JP to a JPNULL*
1524 // (should only happen in a BranchU); otherwise delete the Index from the
1525 // Immed. See the state transitions table elsewhere in this file for a summary
1526 // of which Immed types must be handled. Hysteresis = 0; none is possible with
1527 // Immeds.
1528 //
1529 // MACROS FOR COMMON CODE:
1530 //
1531 // Single Index remains in cJU_JPIMMED_*_01; convert JP to null:
1532 //
1533 // Variables Pjp and parentJPtype are in the context.
1534 //
1535 // Note: cJU_JPIMMED_*_01 should only be encountered in BranchUs, not in
1536 // BranchLs or BranchBs (where its improper to merely modify the JP to be a
1537 // null JP); that is, BranchL and BranchB code should have already handled
1538 // any cJU_JPIMMED_*_01 by different means.
1539
1540 #define JU_IMMED_01(NewJPType,ParentJPType) \
1541 \
1542 assert(parentJPtype == (ParentJPType)); \
1543 assert(JU_JPDCDPOP0(Pjp) == JU_TRIMTODCDSIZE(Index)); \
1544 JU_JPSETADT(Pjp, 0, 0, NewJPType); \
1545 return(1)
1546
1547 // Convert cJ*_JPIMMED_*_02 to cJU_JPIMMED_*_01:
1548 //
1549 // Move the undeleted Index, whichever does not match the least bytes of Index,
1550 // from undecoded-bytes-only (in jp_1Index or jp_LIndex as appropriate) to
1551 // jp_DcdPopO (full-field). Pjp, Index, and offset are in the context.
1552
1553 #define JU_IMMED_02(cIS,LeafType,NewJPType) \
1554 { \
1555 LeafType Pleaf; \
1556 \
1557 assert((ParentLevel - 1) == (cIS)); \
1558 JUDY1CODE(Pleaf = (LeafType) (Pjp->jp_1Index);) \
1559 JUDYLCODE(Pleaf = (LeafType) (Pjp->jp_LIndex);) \
1560 JUDYLCODE(PjvRaw = (Pjv_t) (Pjp->jp_Addr);) \
1561 JUDYLCODE(Pjv = P_JV(PjvRaw);) \
1562 JU_TOIMMED_01_EVEN(cIS, ignore, ignore); \
1563 JUDYLCODE(j__udyLFreeJV(PjvRaw, 2, Pjpm);) \
1564 Pjp->jp_Type = (NewJPType); \
1565 return(1); \
1566 }
1567
1568 #if (defined(JUDY1) || defined(JU_64BIT))
1569
1570 // Variation for "odd" cJ*_JPIMMED_*_02 JP types, which are very different from
1571 // "even" types because they use leaf search code and odd-copy macros:
1572 //
1573 // Note: JudyL 32-bit has no "odd" JPIMMED_*_02 types.
1574
1575 #define JU_IMMED_02_ODD(cIS,NewJPType,SearchLeaf,CopyPIndex) \
1576 { \
1577 uint8_t * Pleaf; \
1578 \
1579 assert((ParentLevel - 1) == (cIS)); \
1580 JUDY1CODE(Pleaf = (uint8_t *) (Pjp->jp_1Index);) \
1581 JUDYLCODE(Pleaf = (uint8_t *) (Pjp->jp_LIndex);) \
1582 JUDYLCODE(PjvRaw = (Pjv_t) (Pjp->jp_Addr);) \
1583 JUDYLCODE(Pjv = P_JV(PjvRaw);) \
1584 JU_TOIMMED_01_ODD(cIS, SearchLeaf, CopyPIndex); \
1585 JUDYLCODE(j__udyLFreeJV(PjvRaw, 2, Pjpm);) \
1586 Pjp->jp_Type = (NewJPType); \
1587 return(1); \
1588 }
1589 #endif // (JUDY1 || JU_64BIT)
1590
1591 // Core code for deleting one Index (and for JudyL, its value area) from a
1592 // larger Immed:
1593 //
1594 // Variables Pleaf, pop1, and offset are in the context.
1595
1596 #ifdef JUDY1
1597 #define JU_IMMED_DEL(cIS,DeleteInPlace) \
1598 DeleteInPlace(Pleaf, pop1, offset, cIS); \
1599 DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);)
1600
1601 #else // JUDYL
1602
1603 // For JudyL the value area might need to be shrunk:
1604
1605 #define JU_IMMED_DEL(cIS,DeleteInPlace) \
1606 \
1607 if (JL_LEAFVGROWINPLACE(pop1 - 1)) /* hysteresis = 0 */ \
1608 { \
1609 DeleteInPlace( Pleaf, pop1, offset, cIS); \
1610 JU_DELETEINPLACE(Pjv, pop1, offset, ignore); \
1611 DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \
1612 } \
1613 else \
1614 { \
1615 Pjv_t PjvnewRaw; \
1616 Pjv_t Pjvnew; \
1617 \
1618 if ((PjvnewRaw = j__udyLAllocJV(pop1 - 1, Pjpm)) \
1619 == (Pjv_t) NULL) return(-1); \
1620 Pjvnew = P_JV(PjvnewRaw); \
1621 \
1622 DeleteInPlace(Pleaf, pop1, offset, cIS); \
1623 JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, ignore); \
1624 DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \
1625 j__udyLFreeJV(PjvRaw, pop1, Pjpm); \
1626 \
1627 (Pjp->jp_Addr) = (Word_t) PjvnewRaw; \
1628 }
1629 #endif // JUDYL
1630
1631 // Delete one Index from a larger Immed where no restructuring is required:
1632 //
1633 // Variables pop1, Pjp, offset, and Index are in the context.
1634
1635 #define JU_IMMED(cIS,LeafType,BaseJPType,SearchLeaf,DeleteInPlace) \
1636 { \
1637 LeafType Pleaf; \
1638 \
1639 assert((ParentLevel - 1) == (cIS)); \
1640 JUDY1CODE(Pleaf = (LeafType) (Pjp->jp_1Index);) \
1641 JUDYLCODE(Pleaf = (LeafType) (Pjp->jp_LIndex);) \
1642 JUDYLCODE(PjvRaw = (Pjv_t) (Pjp->jp_Addr);) \
1643 JUDYLCODE(Pjv = P_JV(PjvRaw);) \
1644 pop1 = (JU_JPTYPE(Pjp)) - (BaseJPType) + 2; \
1645 offset = SearchLeaf(Pleaf, pop1, Index); \
1646 assert(offset >= 0); /* Index must be valid */ \
1647 \
1648 JU_IMMED_DEL(cIS, DeleteInPlace); \
1649 --(Pjp->jp_Type); \
1650 return(1); \
1651 }
1652
1653
1654 // END OF MACROS, START OF CASES:
1655
1656 // Single Index remains in Immed; convert JP to null:
1657
1658 case cJU_JPIMMED_1_01: JU_IMMED_01(cJU_JPNULL1, cJU_JPBRANCH_U2);
1659 case cJU_JPIMMED_2_01: JU_IMMED_01(cJU_JPNULL2, cJU_JPBRANCH_U3);
1660 #ifndef JU_64BIT
1661 case cJU_JPIMMED_3_01: JU_IMMED_01(cJU_JPNULL3, cJU_JPBRANCH_U);
1662 #else
1663 case cJU_JPIMMED_3_01: JU_IMMED_01(cJU_JPNULL3, cJU_JPBRANCH_U4);
1664 case cJU_JPIMMED_4_01: JU_IMMED_01(cJU_JPNULL4, cJU_JPBRANCH_U5);
1665 case cJU_JPIMMED_5_01: JU_IMMED_01(cJU_JPNULL5, cJU_JPBRANCH_U6);
1666 case cJU_JPIMMED_6_01: JU_IMMED_01(cJU_JPNULL6, cJU_JPBRANCH_U7);
1667 case cJU_JPIMMED_7_01: JU_IMMED_01(cJU_JPNULL7, cJU_JPBRANCH_U);
1668 #endif
1669
1670 // Multiple Indexes remain in the Immed JP; delete the specified Index:
1671
1672 case cJU_JPIMMED_1_02:
1673
1674 JU_IMMED_02(1, uint8_t *, cJU_JPIMMED_1_01);
1675
1676 case cJU_JPIMMED_1_03:
1677 #if (defined(JUDY1) || defined(JU_64BIT))
1678 case cJU_JPIMMED_1_04:
1679 case cJU_JPIMMED_1_05:
1680 case cJU_JPIMMED_1_06:
1681 case cJU_JPIMMED_1_07:
1682 #endif
1683 #if (defined(JUDY1) && defined(JU_64BIT))
1684 case cJ1_JPIMMED_1_08:
1685 case cJ1_JPIMMED_1_09:
1686 case cJ1_JPIMMED_1_10:
1687 case cJ1_JPIMMED_1_11:
1688 case cJ1_JPIMMED_1_12:
1689 case cJ1_JPIMMED_1_13:
1690 case cJ1_JPIMMED_1_14:
1691 case cJ1_JPIMMED_1_15:
1692 #endif
1693 JU_IMMED(1, uint8_t *, cJU_JPIMMED_1_02,
1694 j__udySearchLeaf1, JU_DELETEINPLACE);
1695
1696 #if (defined(JUDY1) || defined(JU_64BIT))
1697 case cJU_JPIMMED_2_02:
1698
1699 JU_IMMED_02(2, uint16_t *, cJU_JPIMMED_2_01);
1700
1701 case cJU_JPIMMED_2_03:
1702 #endif
1703 #if (defined(JUDY1) && defined(JU_64BIT))
1704 case cJ1_JPIMMED_2_04:
1705 case cJ1_JPIMMED_2_05:
1706 case cJ1_JPIMMED_2_06:
1707 case cJ1_JPIMMED_2_07:
1708 #endif
1709 #if (defined(JUDY1) || defined(JU_64BIT))
1710 JU_IMMED(2, uint16_t *, cJU_JPIMMED_2_02,
1711 j__udySearchLeaf2, JU_DELETEINPLACE);
1712
1713 case cJU_JPIMMED_3_02:
1714
1715 JU_IMMED_02_ODD(3, cJU_JPIMMED_3_01,
1716 j__udySearchLeaf3, JU_COPY3_PINDEX_TO_LONG);
1717
1718 #endif
1719
1720 #if (defined(JUDY1) && defined(JU_64BIT))
1721 case cJ1_JPIMMED_3_03:
1722 case cJ1_JPIMMED_3_04:
1723 case cJ1_JPIMMED_3_05:
1724
1725 JU_IMMED(3, uint8_t *, cJU_JPIMMED_3_02,
1726 j__udySearchLeaf3, JU_DELETEINPLACE_ODD);
1727
1728 case cJ1_JPIMMED_4_02:
1729
1730 JU_IMMED_02(4, uint32_t *, cJU_JPIMMED_4_01);
1731
1732 case cJ1_JPIMMED_4_03:
1733
1734 JU_IMMED(4, uint32_t *, cJ1_JPIMMED_4_02,
1735 j__udySearchLeaf4, JU_DELETEINPLACE);
1736
1737 case cJ1_JPIMMED_5_02:
1738
1739 JU_IMMED_02_ODD(5, cJU_JPIMMED_5_01,
1740 j__udySearchLeaf5, JU_COPY5_PINDEX_TO_LONG);
1741
1742 case cJ1_JPIMMED_5_03:
1743
1744 JU_IMMED(5, uint8_t *, cJ1_JPIMMED_5_02,
1745 j__udySearchLeaf5, JU_DELETEINPLACE_ODD);
1746
1747 case cJ1_JPIMMED_6_02:
1748
1749 JU_IMMED_02_ODD(6, cJU_JPIMMED_6_01,
1750 j__udySearchLeaf6, JU_COPY6_PINDEX_TO_LONG);
1751
1752 case cJ1_JPIMMED_7_02:
1753
1754 JU_IMMED_02_ODD(7, cJU_JPIMMED_7_01,
1755 j__udySearchLeaf7, JU_COPY7_PINDEX_TO_LONG);
1756
1757 #endif // (JUDY1 && JU_64BIT)
1758
1759
1760 // ****************************************************************************
1761 // INVALID JP TYPE:
1762
1763 default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); return(-1);
1764
1765 } // switch
1766
1767
1768 // PROCESS JP -- RECURSIVELY:
1769 //
1770 // For non-Immed JP types, if successful, post-decrement the population count
1771 // at this level, or collapse a BranchL if necessary by copying the remaining
1772 // JP in the BranchL to the parent (hysteresis = 0), which implicitly creates a
1773 // narrow pointer if there was not already one in the hierarchy.
1774
1775 assert(level);
1776 retcode = j__udyDelWalk(Pjp, Index, level, Pjpm);
1777 assert(retcode != 0); // should never happen.
1778
1779 if ((JU_JPTYPE(Pjp)) < cJU_JPIMMED_1_01) // not an Immed.
1780 {
1781 switch (retcode)
1782 {
1783 case 1:
1784 {
1785 jp_t JP = *Pjp;
1786 Word_t DcdP0;
1787
1788 DcdP0 = JU_JPDCDPOP0(Pjp) - 1; // decrement count.
1789 JU_JPSETADT(Pjp, JP.jp_Addr, DcdP0, JU_JPTYPE(&JP));
1790 break;
1791 }
1792 case 2: // collapse BranchL to single JP; see above:
1793 {
1794 Pjbl_t PjblRaw = (Pjbl_t) (Pjp->jp_Addr);
1795 Pjbl_t Pjbl = P_JBL(PjblRaw);
1796
1797 *Pjp = Pjbl->jbl_jp[0];
1798 j__udyFreeJBL(PjblRaw, Pjpm);
1799 retcode = 1;
1800 }
1801 }
1802 }
1803
1804 return(retcode);
1805
1806 } // j__udyDelWalk()
1807
1808
1809 // ****************************************************************************
1810 // J U D Y 1 U N S E T
1811 // J U D Y L D E L
1812 //
1813 // Main entry point. See the manual entry for details.
1814
1815 #ifdef JUDY1
Judy1Unset(PPvoid_t PPArray,Word_t Index,PJError_t PJError)1816 FUNCTION int Judy1Unset
1817 #else
1818 FUNCTION int JudyLDel
1819 #endif
1820 (
1821 PPvoid_t PPArray, // in which to delete.
1822 Word_t Index, // to delete.
1823 PJError_t PJError // optional, for returning error info.
1824 )
1825 {
1826 Word_t pop1; // population of leaf.
1827 int offset; // at which to delete Index.
1828 JUDY1CODE(int retcode;) // return code from Judy1Test().
1829 JUDYLCODE(PPvoid_t PPvalue;) // pointer from JudyLGet().
1830
1831
1832 // CHECK FOR NULL ARRAY POINTER (error by caller):
1833
1834 if (PPArray == (PPvoid_t) NULL)
1835 {
1836 JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY);
1837 return(JERRI);
1838 }
1839
1840
1841 // CHECK IF INDEX IS INVALID:
1842 //
1843 // If so, theres nothing to do. This saves a lot of time. Pass through
1844 // PJError, if any, from the "get" function.
1845
1846 #ifdef JUDY1
1847 if ((retcode = Judy1Test(*PPArray, Index, PJError)) == JERRI)
1848 return (JERRI);
1849
1850 if (retcode == 0) return(0);
1851 #else
1852 if ((PPvalue = JudyLGet(*PPArray, Index, PJError)) == PPJERR)
1853 return (JERRI);
1854
1855 if (PPvalue == (PPvoid_t) NULL) return(0);
1856 #endif
1857
1858
1859 // ****************************************************************************
1860 // PROCESS TOP LEVEL (LEAFW) BRANCHES AND LEAVES:
1861
1862 // ****************************************************************************
1863 // LEAFW LEAF, OTHER SIZE:
1864 //
1865 // Shrink or convert the leaf as necessary. Hysteresis = 0; none is possible.
1866
1867 if (JU_LEAFW_POP0(*PPArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
1868 {
1869 JUDYLCODE(Pjv_t Pjv;) // current value area.
1870 JUDYLCODE(Pjv_t Pjvnew;) // value area in new leaf.
1871 Pjlw_t Pjlw = P_JLW(*PPArray); // first word of leaf.
1872 Pjlw_t Pjlwnew; // replacement leaf.
1873 pop1 = Pjlw[0] + 1; // first word of leaf is pop0.
1874
1875 // Delete single (last) Index from array:
1876
1877 if (pop1 == 1)
1878 {
1879 j__udyFreeJLW(Pjlw, /* pop1 = */ 1, (Pjpm_t) NULL);
1880 *PPArray = (Pvoid_t) NULL;
1881 return(1);
1882 }
1883
1884 // Locate Index in compressible leaf:
1885
1886 offset = j__udySearchLeafW(Pjlw + 1, pop1, Index);
1887 assert(offset >= 0); // Index must be valid.
1888
1889 JUDYLCODE(Pjv = JL_LEAFWVALUEAREA(Pjlw, pop1);)
1890
1891 // Delete Index in-place:
1892 //
1893 // Note: "Grow in place from pop1 - 1" is the logical inverse of, "shrink in
1894 // place from pop1." Also, Pjlw points to the count word, so skip that for
1895 // doing the deletion.
1896
1897 if (JU_LEAFWGROWINPLACE(pop1 - 1))
1898 {
1899 JU_DELETEINPLACE(Pjlw + 1, pop1, offset, ignore);
1900 #ifdef JUDYL // also delete from value area:
1901 JU_DELETEINPLACE(Pjv, pop1, offset, ignore);
1902 #endif
1903 DBGCODE(JudyCheckSorted((Pjll_t) (Pjlw + 1), pop1 - 1,
1904 cJU_ROOTSTATE);)
1905 --(Pjlw[0]); // decrement population.
1906 DBGCODE(JudyCheckPop(*PPArray);)
1907 return(1);
1908 }
1909
1910 // Allocate new leaf for use in either case below:
1911
1912 Pjlwnew = j__udyAllocJLW(pop1 - 1);
1913 JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI);
1914
1915 // Shrink to smaller LEAFW:
1916 //
1917 // Note: Skip the first word = pop0 in each leaf.
1918
1919 Pjlwnew[0] = (pop1 - 1) - 1;
1920 JU_DELETECOPY(Pjlwnew + 1, Pjlw + 1, pop1, offset, ignore);
1921
1922 #ifdef JUDYL // also delete from value area:
1923 Pjvnew = JL_LEAFWVALUEAREA(Pjlwnew, pop1 - 1);
1924 JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, ignore);
1925 #endif
1926 DBGCODE(JudyCheckSorted(Pjlwnew + 1, pop1 - 1, cJU_ROOTSTATE);)
1927
1928 j__udyFreeJLW(Pjlw, pop1, (Pjpm_t) NULL);
1929
1930 //// *PPArray = (Pvoid_t) Pjlwnew | cJU_LEAFW);
1931 *PPArray = (Pvoid_t) Pjlwnew;
1932 DBGCODE(JudyCheckPop(*PPArray);)
1933 return(1);
1934
1935 }
1936 else
1937
1938
1939 // ****************************************************************************
1940 // JRP BRANCH:
1941 //
1942 // Traverse through the JPM to do the deletion unless the population is small
1943 // enough to convert immediately to a LEAFW.
1944
1945 {
1946 Pjpm_t Pjpm;
1947 Pjp_t Pjp; // top-level JP to process.
1948 Word_t digit; // in a branch.
1949 JUDYLCODE(Pjv_t Pjv;) // to value area.
1950 Pjlw_t Pjlwnew; // replacement leaf.
1951 DBGCODE(Pjlw_t Pjlwnew_orig;)
1952
1953 Pjpm = P_JPM(*PPArray); // top object in array (tree).
1954 Pjp = &(Pjpm->jpm_JP); // next object (first branch or leaf).
1955
1956 assert(((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_L)
1957 || ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_B)
1958 || ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_U));
1959
1960 // WALK THE TREE
1961 //
1962 // Note: Recursive code in j__udyDelWalk() knows how to collapse a lower-level
1963 // BranchL containing a single JP into the parent JP as a narrow pointer, but
1964 // the code here cant do that for a top-level BranchL. The result can be
1965 // PArray -> JPM -> BranchL containing a single JP. This situation is
1966 // unavoidable because a JPM cannot contain a narrow pointer; the BranchL is
1967 // required in order to hold the top digit decoded, and it does not collapse to
1968 // a LEAFW until the population is low enough.
1969 //
1970 // TBD: Should we add a topdigit field to JPMs so they can hold narrow
1971 // pointers?
1972
1973 if (j__udyDelWalk(Pjp, Index, cJU_ROOTSTATE, Pjpm) == -1)
1974 {
1975 JU_COPY_ERRNO(PJError, Pjpm);
1976 return(JERRI);
1977 }
1978
1979 --(Pjpm->jpm_Pop0); // success; decrement total population.
1980
1981 if ((Pjpm->jpm_Pop0 + 1) != cJU_LEAFW_MAXPOP1)
1982 {
1983 DBGCODE(JudyCheckPop(*PPArray);)
1984 return(1);
1985 }
1986
1987 // COMPRESS A BRANCH[LBU] TO A LEAFW:
1988 //
1989 Pjlwnew = j__udyAllocJLW(cJU_LEAFW_MAXPOP1);
1990 JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI);
1991
1992 // Plug leaf into root pointer and set population count:
1993
1994 //// *PPArray = (Pvoid_t) ((Word_t) Pjlwnew | cJU_LEAFW);
1995 *PPArray = (Pvoid_t) Pjlwnew;
1996 #ifdef JUDYL // prepare value area:
1997 Pjv = JL_LEAFWVALUEAREA(Pjlwnew, cJU_LEAFW_MAXPOP1);
1998 #endif
1999 *Pjlwnew++ = cJU_LEAFW_MAXPOP1 - 1; // set pop0.
2000 DBGCODE(Pjlwnew_orig = Pjlwnew;)
2001
2002 switch (JU_JPTYPE(Pjp))
2003 {
2004
2005 // JPBRANCH_L: Copy each JPs indexes to the new LEAFW and free the old
2006 // branch:
2007
2008 case cJU_JPBRANCH_L:
2009 {
2010 Pjbl_t PjblRaw = (Pjbl_t) (Pjp->jp_Addr);
2011 Pjbl_t Pjbl = P_JBL(PjblRaw);
2012
2013 for (offset = 0; offset < Pjbl->jbl_NumJPs; ++offset)
2014 {
2015 pop1 = j__udyLeafM1ToLeafW(Pjlwnew, JU_PVALUEPASS
2016 (Pjbl->jbl_jp) + offset,
2017 JU_DIGITTOSTATE(Pjbl->jbl_Expanse[offset],
2018 cJU_BYTESPERWORD),
2019 (Pvoid_t) Pjpm);
2020 Pjlwnew += pop1; // advance through indexes.
2021 JUDYLCODE(Pjv += pop1;) // advance through values.
2022 }
2023 j__udyFreeJBL(PjblRaw, Pjpm);
2024
2025 assert(Pjlwnew == Pjlwnew_orig + cJU_LEAFW_MAXPOP1);
2026 break; // delete Index from new LEAFW.
2027 }
2028
2029 // JPBRANCH_B: Copy each JPs indexes to the new LEAFW and free the old
2030 // branch, including each JP subarray:
2031
2032 case cJU_JPBRANCH_B:
2033 {
2034 Pjbb_t PjbbRaw = (Pjbb_t) (Pjp->jp_Addr);
2035 Pjbb_t Pjbb = P_JBB(PjbbRaw);
2036 Word_t subexp; // current subexpanse number.
2037 BITMAPB_t bitmap; // portion for this subexpanse.
2038 Pjp_t Pjp2Raw; // one subexpanses subarray.
2039 Pjp_t Pjp2;
2040
2041 for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
2042 {
2043 if ((bitmap = JU_JBB_BITMAP(Pjbb, subexp)) == 0)
2044 continue; // skip empty subexpanse.
2045
2046 digit = subexp * cJU_BITSPERSUBEXPB;
2047 Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);
2048 Pjp2 = P_JP(Pjp2Raw);
2049 assert(Pjp2 != (Pjp_t) NULL);
2050
2051 // Walk through bits for all possible sub-subexpanses (digits); increment
2052 // offset for each populated subexpanse; until no more set bits:
2053
2054 for (offset = 0; bitmap != 0; bitmap >>= 1, ++digit)
2055 {
2056 if (! (bitmap & 1)) // skip empty sub-subexpanse.
2057 continue;
2058
2059 pop1 = j__udyLeafM1ToLeafW(Pjlwnew, JU_PVALUEPASS
2060 Pjp2 + offset,
2061 JU_DIGITTOSTATE(digit, cJU_BYTESPERWORD),
2062 (Pvoid_t) Pjpm);
2063 Pjlwnew += pop1; // advance through indexes.
2064 JUDYLCODE(Pjv += pop1;) // advance through values.
2065 ++offset;
2066 }
2067 j__udyFreeJBBJP(Pjp2Raw, /* pop1 = */ offset, Pjpm);
2068 }
2069 j__udyFreeJBB(PjbbRaw, Pjpm);
2070
2071 assert(Pjlwnew == Pjlwnew_orig + cJU_LEAFW_MAXPOP1);
2072 break; // delete Index from new LEAFW.
2073
2074 } // case cJU_JPBRANCH_B.
2075
2076
2077 // JPBRANCH_U: Copy each JPs indexes to the new LEAFW and free the old
2078 // branch:
2079
2080 case cJU_JPBRANCH_U:
2081 {
2082 Pjbu_t PjbuRaw = (Pjbu_t) (Pjp->jp_Addr);
2083 Pjbu_t Pjbu = P_JBU(PjbuRaw);
2084 Word_t ldigit; // larger than uint8_t.
2085
2086 for (Pjp = Pjbu->jbu_jp, ldigit = 0;
2087 ldigit < cJU_BRANCHUNUMJPS;
2088 ++Pjp, ++ldigit)
2089 {
2090
2091 // Shortcuts, to save a little time for possibly big branches:
2092
2093 if ((JU_JPTYPE(Pjp)) == cJU_JPNULLMAX) // skip null JP.
2094 continue;
2095
2096 // TBD: Should the following shortcut also be used in BranchL and BranchB
2097 // code?
2098
2099 #ifndef JU_64BIT
2100 if ((JU_JPTYPE(Pjp)) == cJU_JPIMMED_3_01)
2101 #else
2102 if ((JU_JPTYPE(Pjp)) == cJU_JPIMMED_7_01)
2103 #endif
2104 { // single Immed:
2105 *Pjlwnew++ = JU_DIGITTOSTATE(ldigit, cJU_BYTESPERWORD)
2106 | JU_JPDCDPOP0(Pjp); // rebuild Index.
2107 #ifdef JUDYL
2108 *Pjv++ = Pjp->jp_Addr; // copy value area.
2109 #endif
2110 continue;
2111 }
2112
2113 pop1 = j__udyLeafM1ToLeafW(Pjlwnew, JU_PVALUEPASS
2114 Pjp, JU_DIGITTOSTATE(ldigit, cJU_BYTESPERWORD),
2115 (Pvoid_t) Pjpm);
2116 Pjlwnew += pop1; // advance through indexes.
2117 JUDYLCODE(Pjv += pop1;) // advance through values.
2118 }
2119 j__udyFreeJBU(PjbuRaw, Pjpm);
2120
2121 assert(Pjlwnew == Pjlwnew_orig + cJU_LEAFW_MAXPOP1);
2122 break; // delete Index from new LEAFW.
2123
2124 } // case cJU_JPBRANCH_U.
2125
2126
2127 // INVALID JP TYPE in jpm_t struct
2128
2129 default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
2130 return(JERRI);
2131
2132 } // end switch on sub-JP type.
2133
2134 DBGCODE(JudyCheckSorted((Pjll_t) Pjlwnew_orig, cJU_LEAFW_MAXPOP1,
2135 cJU_ROOTSTATE);)
2136
2137 // FREE JPM (no longer needed):
2138
2139 j__udyFreeJPM(Pjpm, (Pjpm_t) NULL);
2140 DBGCODE(JudyCheckPop(*PPArray);)
2141 return(1);
2142
2143 }
2144 /*NOTREACHED*/
2145
2146 } // Judy1Unset() / JudyLDel()
2147