« back to all changes in this revision
Viewing changes to src/JudyCommon/JudyDel.c
- browse files at revision 3
- compare with another revision
- download diff
- download tarball
- view history from revision 3
- Committer: Bazaar Package Importer
- Author(s): Troy Heber
- Date: 2005-03-22 06:55:53 UTC
- mfrom: (1.1.1 upstream)
- Revision ID: james.westby@ubuntu.com-20050322065553-syjpkd48r4re18dn
Tags: 1.0.1-5
* Moving LGPL link in copyright back to LGPL-2.1
* Cleanup of debian/rules: removed explicit refs to 32-bit archs, removed
unnecessary nostrip, using --man dir to install man pages, moving from
dh_movefiles to dh_install.
- files added:
- AUTHORS
- autom4te.cache
- doc/man
- doc/man/man3
- src/JudyHS
- src/obj
- test/Centrino_1.3Mhz_Plots
- files removed:
- Makefile.multi
- make_includes
- test/manual
- files modified:
- COPYING
added
removed
src/JudyCommon/JudyDel.c
39
39
//
40
40
// In general no hysteresis occurs when the data structure type remains the
41
41
// same but the allocated memory chunk for the node must shrink, because the
42
// relationship is hardwired and there's no way to know how much memory is
42
// relationship is hardwired and theres no way to know how much memory is
43
43
// allocated to a given data structure. Hysteresis = 0 in all these cases.
44
44
//
45
45
// TBD: Could this code be faster if memory chunk hysteresis were supported
48
48
// TBD: Should some of the assertions here be converted to product code that
49
49
// returns JU_ERRNO_CORRUPT?
50
50
//
51
// TBD: Doug's code had an odd mix of function-wide and limited-scope
51
// TBD: Dougs code had an odd mix of function-wide and limited-scope
52
52
// variables. Should some of the function-wide variables appear only in
53
53
// limited scopes, or more likely, vice-versa?
54
54
55
#if (! (JUDY1 || JUDYL))
56
Error: One of -DJUDY1 or -DJUDYL must be specified.
55
#if (! (defined(JUDY1) || defined(JUDYL)))
56
#error: One of -DJUDY1 or -DJUDYL must be specified.
57
57
#endif
58
58
59
59
#ifdef JUDY1
80
80
81
81
#ifdef JUDY1
82
82
83
extern int __Judy1BranchBToBranchL(Pjp_t Pjp, Pvoid_t Pjpm);
83
extern int j__udy1BranchBToBranchL(Pjp_t Pjp, Pvoid_t Pjpm);
84
84
#ifndef JU_64BIT
85
extern int __Judy1LeafB1ToLeaf1(Pjp_t, Pvoid_t);
85
extern int j__udy1LeafB1ToLeaf1(Pjp_t, Pvoid_t);
86
86
#endif
87
extern Word_t __Judy1Leaf1ToLeaf2(uint16_t *, Pjp_t, Word_t, Pvoid_t);
88
extern Word_t __Judy1Leaf2ToLeaf3(uint8_t *, Pjp_t, Word_t, Pvoid_t);
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
89
#ifndef JU_64BIT
90
extern Word_t __Judy1Leaf3ToLeafW(Pjlw_t, Pjp_t, Word_t, Pvoid_t);
90
extern Word_t j__udy1Leaf3ToLeafW(Pjlw_t, Pjp_t, Word_t, Pvoid_t);
91
91
#else
92
extern Word_t __Judy1Leaf3ToLeaf4(uint32_t *, Pjp_t, Word_t, Pvoid_t);
93
extern Word_t __Judy1Leaf4ToLeaf5(uint8_t *, Pjp_t, Word_t, Pvoid_t);
94
extern Word_t __Judy1Leaf5ToLeaf6(uint8_t *, Pjp_t, Word_t, Pvoid_t);
95
extern Word_t __Judy1Leaf6ToLeaf7(uint8_t *, Pjp_t, Word_t, Pvoid_t);
96
extern Word_t __Judy1Leaf7ToLeafW(Pjlw_t, Pjp_t, Word_t, Pvoid_t);
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
97
#endif
98
98
99
99
#else // JUDYL
100
100
101
extern int __JudyLBranchBToBranchL(Pjp_t Pjp, Pvoid_t Pjpm);
102
extern int __JudyLLeafB1ToLeaf1(Pjp_t, Pvoid_t);
103
extern Word_t __JudyLLeaf1ToLeaf2(uint16_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);
104
extern Word_t __JudyLLeaf2ToLeaf3(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);
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
105
#ifndef JU_64BIT
106
extern Word_t __JudyLLeaf3ToLeafW(Pjlw_t, Pjv_t, Pjp_t, Word_t, Pvoid_t);
106
extern Word_t j__udyLLeaf3ToLeafW(Pjlw_t, Pjv_t, Pjp_t, Word_t, Pvoid_t);
107
107
#else
108
extern Word_t __JudyLLeaf3ToLeaf4(uint32_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);
109
extern Word_t __JudyLLeaf4ToLeaf5(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);
110
extern Word_t __JudyLLeaf5ToLeaf6(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);
111
extern Word_t __JudyLLeaf6ToLeaf7(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);
112
extern Word_t __JudyLLeaf7ToLeafW(Pjlw_t, Pjv_t, Pjp_t, Word_t, Pvoid_t);
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
113
#endif
114
114
115
115
#endif // JUDYL
117
117
// For convenience in the calling code; "M1" means "minus one":
118
118
119
119
#ifndef JU_64BIT
120
#define __JudyLeafM1ToLeafW __JudyLeaf3ToLeafW
120
#define j__udyLeafM1ToLeafW j__udyLeaf3ToLeafW
121
121
#else
122
#define __JudyLeafM1ToLeafW __JudyLeaf7ToLeafW
122
#define j__udyLeafM1ToLeafW j__udyLeaf7ToLeafW
123
123
#endif
124
124
125
125
145
145
// single JP, which should be compressed into the parent branch (if there
146
146
// is one, which is not the case for a top-level branch under a JPM)
147
147
148
DBGCODE(uint8_t parentJPtype;) // parent branch JP type.
148
DBGCODE(uint8_t parentJPtype;) // parent branch JP type.
149
149
150
FUNCTION static int __JudyDelWalk(
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.
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
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.
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
169
170
170
#ifdef TRACEJP
171
JudyPrintJP(Pjp, "d", __LINE__);
171
JudyPrintJP(Pjp, "d", __LINE__);
172
172
#endif
173
173
174
switch (Pjp->jp_Type) // entry: Pjp, Index.
175
{
174
switch (JU_JPTYPE(Pjp)) // entry: Pjp, Index.
175
{
176
176
177
177
178
178
// ****************************************************************************
183
183
// Check for population too high to compress a branch to a leaf, meaning just
184
184
// descend through the branch, with a purposeful off-by-one error that
185
185
// constitutes hysteresis = 1. In other words, do not compress until the
186
// branch's CURRENT population fits in the leaf, even BEFORE deleting one
186
// branchs CURRENT population fits in the leaf, even BEFORE deleting one
187
187
// index.
188
188
//
189
189
// Next is a label for branch-type-specific common code. Variables pop1,
190
190
// level, digit, and Index are in the context.
191
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
}
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
200
201
201
// Support for generic calling of JudyLeaf*ToLeaf*() functions:
202
202
//
203
203
// Note: Cannot use JUDYLCODE() because this contains a comma.
204
204
205
205
#ifdef JUDY1
206
#define JU_PVALUEPASS // null.
206
#define JU_PVALUEPASS // null.
207
207
#else
208
#define JU_PVALUEPASS Pjv,
208
#define JU_PVALUEPASS Pjv,
209
209
#endif
210
210
211
211
// During compression to a leaf, check if a JP contains nothing but a
212
// cJU_JPIMMED_*_01, in which case shortcut calling __JudyLeaf*ToLeaf*():
212
// cJU_JPIMMED_*_01, in which case shortcut calling j__udyLeaf*ToLeaf*():
213
213
//
214
// Copy the index bytes from the jp_DcdPop0 field (with possible truncation),
214
// Copy the index bytes from the jp_DcdPopO field (with possible truncation),
215
215
// and continue the branch-JP-walk loop. Variables Pjp and Pleaf are in the
216
216
// context.
217
217
218
#define JU_BRANCH_COPY_IMMED_EVEN(cLevel,Pjp,ignore) \
219
if (((Pjp)->jp_Type) == cJU_JPIMMED_1_01 + (cLevel) - 2)\
220
{ \
221
*Pleaf++ = (Pjp)->jp_DcdPop0; \
222
JUDYLCODE(*Pjv++ = (Pjp)->jp_Addr;) \
223
continue; /* for-loop */ \
224
}
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
225
226
#define JU_BRANCH_COPY_IMMED_ODD(cLevel,Pjp,CopyIndex) \
227
if (((Pjp)->jp_Type) == cJU_JPIMMED_1_01 + (cLevel) - 2)\
228
{ \
229
CopyIndex(Pleaf, (Word_t) ((Pjp)->jp_DcdPop0)); \
230
Pleaf += (cLevel); /* index size = level */ \
231
JUDYLCODE(*Pjv++ = (Pjp)->jp_Addr;) \
232
continue; /* for-loop */ \
233
}
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
234
235
235
// Compress a BranchL into a leaf one index size larger:
236
236
//
237
237
// Allocate a new leaf, walk the JPs in the old BranchL and pack their contents
238
238
// into the new leaf (of type NewJPType), free the old BranchL, and finally
239
239
// restart the switch to delete Index from the new leaf. (Note that all
240
// BranchL's are the same size.) Variables Pjp, Pjpm, Pleaf, digit, and pop1
240
// BranchLs are the same size.) Variables Pjp, Pjpm, Pleaf, digit, and pop1
241
241
// are in the context.
242
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
__JudyFreeJBL(PjblRaw, Pjpm); \
277
\
278
(Pjp->jp_Type) = (NewJPType); \
279
(Pjp->jp_Addr) = (Word_t) PjllnewRaw; \
280
goto ContinueDelWalk; /* delete from new leaf */ \
281
}
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
282
283
283
// Overall common code for initial BranchL deletion handling:
284
284
//
286
286
// or else compressed to a leaf. Variables Index, Pjp, and pop1 are in the
287
287
// context.
288
288
289
#define JU_BRANCHL(cLevel,MaxPop1,LeafType,NewJPType, \
290
LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \
291
\
292
assert(! JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, cLevel)); \
293
assert(ParentLevel > (cLevel)); \
294
\
295
pop1 = JU_JPBRANCH_POP0(Pjp->jp_DcdPop0, 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)
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
301
302
302
303
303
// END OF MACROS, START OF CASES:
304
304
305
case cJU_JPBRANCH_L2:
306
307
JU_BRANCHL(2, cJU_LEAF2_MAXPOP1, uint16_t *, cJU_JPLEAF2,
308
__JudyLeaf1ToLeaf2, __JudyAllocJLL2, 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
__JudyLeaf2ToLeaf3, __JudyAllocJLL3, JL_LEAF3VALUEAREA,
315
JU_BRANCH_COPY_IMMED_ODD, JU_COPY3_LONG_TO_PINDEX);
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
316
317
317
#ifdef JU_64BIT
318
case cJU_JPBRANCH_L4:
319
320
JU_BRANCHL(4, cJU_LEAF4_MAXPOP1, uint32_t *, cJU_JPLEAF4,
321
__JudyLeaf3ToLeaf4, __JudyAllocJLL4, 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
__JudyLeaf4ToLeaf5, __JudyAllocJLL5, 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
__JudyLeaf5ToLeaf6, __JudyAllocJLL6, 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
__JudyLeaf6ToLeaf7, __JudyAllocJLL7, JL_LEAF7VALUEAREA,
340
JU_BRANCH_COPY_IMMED_ODD, JU_COPY7_LONG_TO_PINDEX);
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
341
#endif // JU_64BIT
342
342
343
// A top-level BranchL is different and cannot use JU_BRANCHL(): Don't try to
344
// compress to a (JAP) leaf yet, but leave this for a later deletion
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
345
// (hysteresis > 0); and the next JP type depends on the system word size; so
346
// don't 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:
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
357
358
358
359
359
// COMMON CODE FOR KEEPING AND DESCENDING THROUGH A BRANCHL:
361
361
// Come here with level and digit set.
362
362
363
363
BranchLKeep:
364
Pjbl = P_JBL(Pjp->jp_Addr);
365
numJPs = Pjbl->jbl_NumJPs;
366
assert(numJPs > 0);
367
DBGCODE(parentJPtype = Pjp->jp_Type;)
364
Pjbl = P_JBL(Pjp->jp_Addr);
365
numJPs = Pjbl->jbl_NumJPs;
366
assert(numJPs > 0);
367
DBGCODE(parentJPtype = JU_JPTYPE(Pjp);)
368
368
369
369
// Search for a match to the digit (valid Index => must find digit):
370
370
371
for (offset = 0; (Pjbl->jbl_Expanse[offset]) != digit; ++offset)
372
assert(offset < numJPs - 1);
371
for (offset = 0; (Pjbl->jbl_Expanse[offset]) != digit; ++offset)
372
assert(offset < numJPs - 1);
373
373
374
Pjp = (Pjbl->jbl_jp) + offset;
374
Pjp = (Pjbl->jbl_jp) + offset;
375
375
376
376
// If not at a (deletable) JPIMMED_*_01, continue the walk (to descend through
377
377
// the BranchL):
378
378
379
assert(level >= 2);
380
if ((Pjp->jp_Type) != cJU_JPIMMED_1_01 + level - 2) break;
379
assert(level >= 2);
380
if ((JU_JPTYPE(Pjp)) != cJU_JPIMMED_1_01 + level - 2) break;
381
381
382
382
// At JPIMMED_*_01: Ensure the index is in the right expanse, then delete the
383
383
// Immed from the BranchL:
384
384
//
385
385
// Note: A BranchL has a fixed size and format regardless of numJPs.
386
386
387
assert((Pjp->jp_DcdPop0) == 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);)
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
394
395
395
// If only one index left in the BranchL, indicate this to the caller:
396
396
397
return ((--(Pjbl->jbl_NumJPs) <= 1) ? 2 : 1);
397
return ((--(Pjbl->jbl_NumJPs) <= 1) ? 2 : 1);
398
398
399
} // case cJU_JPBRANCH_L.
399
} // case cJU_JPBRANCH_L.
400
400
401
401
402
402
// ****************************************************************************
415
415
// the new leaf. Variables Pjp, Pjpm, Pleaf, digit, and pop1 are in the
416
416
// context.
417
417
//
418
// Note: It's no accident that the interface to JU_BRANCHB_COMPRESS() is
418
// Note: Its no accident that the interface to JU_BRANCHB_COMPRESS() is
419
419
// identical to JU_BRANCHL_COMPRESS(). Only the details differ in how to
420
// traverse the branch's JPs.
420
// traverse the branchs JPs.
421
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 subexpanse's 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
__JudyFreeJBBJP(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
__JudyFreeJBB(PjbbRaw, Pjpm); \
475
\
476
(Pjp->jp_Type) = (NewJPType); \
477
(Pjp->jp_Addr) = (Word_t) PjllnewRaw; \
478
goto ContinueDelWalk; /* delete from new leaf */ \
479
}
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
480
481
481
// Overall common code for initial BranchB deletion handling:
482
482
//
484
484
// or else compressed to a leaf. Variables Index, Pjp, and pop1 are in the
485
485
// context.
486
486
487
#define JU_BRANCHB(cLevel,MaxPop1,LeafType,NewJPType, \
488
LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \
489
\
490
assert(! JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, cLevel)); \
491
assert(ParentLevel > (cLevel)); \
492
\
493
pop1 = JU_JPBRANCH_POP0(Pjp->jp_DcdPop0, 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)
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
499
500
500
501
501
// END OF MACROS, START OF CASES:
502
502
//
503
// Note: It's no accident that the macro calls for these cases is nearly
504
// identical to the code for BranchL's.
505
506
case cJU_JPBRANCH_B2:
507
508
JU_BRANCHB(2, cJU_LEAF2_MAXPOP1, uint16_t *, cJU_JPLEAF2,
509
__JudyLeaf1ToLeaf2, __JudyAllocJLL2, 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
__JudyLeaf2ToLeaf3, __JudyAllocJLL3, JL_LEAF3VALUEAREA,
516
JU_BRANCH_COPY_IMMED_ODD, JU_COPY3_LONG_TO_PINDEX);
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
517
518
518
#ifdef JU_64BIT
519
case cJU_JPBRANCH_B4:
520
521
JU_BRANCHB(4, cJU_LEAF4_MAXPOP1, uint32_t *, cJU_JPLEAF4,
522
__JudyLeaf3ToLeaf4, __JudyAllocJLL4, 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
__JudyLeaf4ToLeaf5, __JudyAllocJLL5, 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
__JudyLeaf5ToLeaf6, __JudyAllocJLL6, 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
__JudyLeaf6ToLeaf7, __JudyAllocJLL7, JL_LEAF7VALUEAREA,
541
JU_BRANCH_COPY_IMMED_ODD, JU_COPY7_LONG_TO_PINDEX);
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
542
#endif // JU_64BIT
543
543
544
// A top-level BranchB is different and cannot use JU_BRANCHB(): Don't try to
545
// compress to a (JAP) leaf yet, but leave this for a later deletion
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
546
// (hysteresis > 0); and the next JP type depends on the system word size; so
547
// don't 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 digit's bit set.
556
Pjp_t Pjp2Raw; // one subexpanse's 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:
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
564
565
565
566
566
// COMMON CODE FOR KEEPING AND DESCENDING THROUGH A BRANCHB:
568
568
// Come here with level and digit set.
569
569
570
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 => digit's bit is set.
576
DBGCODE(parentJPtype = Pjp->jp_Type;)
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
577
578
// Compute digit's offset into the bitmap, with a fast method if all bits are
578
// Compute digits offset into the bitmap, with a fast method if all bits are
579
579
// set:
580
580
581
offset = ((bitmap == (cJU_FULLBITMAPB)) ?
582
digit % cJU_BITSPERSUBEXPB :
583
__JudyCountBitsB(bitmap & JU_MASKLOWEREXC(bitmask)));
581
offset = ((bitmap == (cJU_FULLBITMAPB)) ?
582
digit % cJU_BITSPERSUBEXPB :
583
j__udyCountBitsB(bitmap & JU_MASKLOWEREXC(bitmask)));
584
584
585
Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);
586
Pjp2 = P_JP(Pjp2Raw);
587
assert(Pjp2 != (Pjp_t) NULL); // valid subexpanse pointer.
585
Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);
586
Pjp2 = P_JP(Pjp2Raw);
587
assert(Pjp2 != (Pjp_t) NULL); // valid subexpanse pointer.
588
588
589
589
// If not at a (deletable) JPIMMED_*_01, continue the walk (to descend through
590
590
// the BranchB):
591
591
592
if (((Pjp2 + offset)->jp_Type) != cJU_JPIMMED_1_01 + level - 2)
593
{
594
Pjp = Pjp2 + offset;
595
break;
596
}
592
if (JU_JPTYPE(Pjp2 + offset) != cJU_JPIMMED_1_01 + level - 2)
593
{
594
Pjp = Pjp2 + offset;
595
break;
596
}
597
597
598
598
// At JPIMMED_*_01: Ensure the index is in the right expanse, then delete the
599
599
// Immed from the BranchB:
600
600
601
assert(((Pjp2 + offset)->jp_DcdPop0)
602
== JU_TRIMTODCDSIZE(Index));
601
assert(JU_JPDCDPOP0(Pjp2 + offset)
602
== JU_TRIMTODCDSIZE(Index));
603
603
604
604
// If only one index is left in the subexpanse, free the JP array:
605
605
606
if ((numJPs = __JudyCountBitsB(bitmap)) == 1)
607
{
608
__JudyFreeJBBJP(Pjp2Raw, /* pop1 = */ 1, Pjpm);
609
JU_JBB_PJP(Pjbb, subexp) = (Pjp_t) NULL;
610
}
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
611
612
612
// Shrink JP array in-place:
613
613
614
else if (JU_BRANCHBJPGROWINPLACE(numJPs - 1))
615
{
616
assert(numJPs > 0);
617
JU_DELETEINPLACE(Pjp2, numJPs, offset, ignore);
618
}
614
else if (JU_BRANCHBJPGROWINPLACE(numJPs - 1))
615
{
616
assert(numJPs > 0);
617
JU_DELETEINPLACE(Pjp2, numJPs, offset, ignore);
618
}
619
619
620
620
// JP array would end up too large; compress it to a smaller one:
621
621
622
else
623
{
624
Pjp_t PjpnewRaw;
625
Pjp_t Pjpnew;
626
627
if ((PjpnewRaw = __JudyAllocJBBJP(numJPs - 1, Pjpm))
628
== (Pjp_t) NULL) return(-1);
629
Pjpnew = P_JP(PjpnewRaw);
630
631
JU_DELETECOPY(Pjpnew, Pjp2, numJPs, offset, ignore);
632
__JudyFreeJBBJP(Pjp2Raw, numJPs, Pjpm); // old.
633
634
JU_JBB_PJP(Pjbb, subexp) = PjpnewRaw;
635
}
636
637
// Clear digit's bit in the bitmap:
638
639
JU_JBB_BITMAP(Pjbb, subexp) ^= bitmask;
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
640
641
641
// If the current subexpanse alone is still too large for a BranchL (with
642
642
// hysteresis = 1), the delete is all done:
643
643
644
if (numJPs > cJU_BRANCHLMAXJPS) return(1);
644
if (numJPs > cJU_BRANCHLMAXJPS) return(1);
645
645
646
646
// Consider shrinking the current BranchB to a BranchL:
647
647
//
648
648
// Check the numbers of JPs in other subexpanses in the BranchL. Upon reaching
649
649
// the critical number of numJPs (which could be right at the start; again,
650
// with hysteresis = 1), it's faster to just watch for any non-empty subexpanse
650
// with hysteresis = 1), its faster to just watch for any non-empty subexpanse
651
651
// than to count bits in each subexpanse. Upon finding too many JPs, give up
652
652
// on shrinking the BranchB.
653
653
654
for (subexp2 = 0; subexp2 < cJU_NUMSUBEXPB; ++subexp2)
655
{
656
if (subexp2 == subexp) continue; // skip current subexpanse.
654
for (subexp2 = 0; subexp2 < cJU_NUMSUBEXPB; ++subexp2)
655
{
656
if (subexp2 == subexp) continue; // skip current subexpanse.
657
657
658
if ((numJPs == cJU_BRANCHLMAXJPS) ?
659
JU_JBB_BITMAP(Pjbb, subexp2) :
660
((numJPs += __JudyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp2)))
661
> cJU_BRANCHLMAXJPS))
662
{
663
return(1); // too many JPs, cannot shrink.
664
}
665
}
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
666
667
667
// Shrink current BranchB to a BranchL:
668
668
//
672
672
// this call are JU_ERRNO_NOMEM and JU_ERRNO_OVERRUN, neither of which is worth
673
673
// forwarding from this point. See also 4.1, 4.8, and 4.15 of this file.
674
674
675
(void) __JudyBranchBToBranchL(Pjp, Pjpm);
676
return(1);
675
(void) j__udyBranchBToBranchL(Pjp, Pjpm);
676
return(1);
677
677
678
} // case.
678
} // case.
679
679
680
680
681
681
// ****************************************************************************
692
692
// restart the switch to delete Index from the new leaf. Variables Pjp, Pjpm,
693
693
// digit, and pop1 are in the context.
694
694
//
695
// Note: It's no accident that the interface to JU_BRANCHU_COMPRESS() is
695
// Note: Its no accident that the interface to JU_BRANCHU_COMPRESS() is
696
696
// nearly identical to JU_BRANCHL_COMPRESS(); just NullJPType is added. The
697
// details differ in how to traverse the branch's JPs --
697
// details differ in how to traverse the branchs JPs --
698
698
//
699
699
// -- and also, what to do upon encountering a cJU_JPIMMED_*_01 JP. In
700
// BranchL's and BranchB's the JP must be deleted, but in a BranchU it's merely
700
// BranchLs and BranchBs the JP must be deleted, but in a BranchU its merely
701
701
// converted to a null JP, and this is done by other switch cases, so the "keep
702
702
// branch" situation is simpler here and JU_BRANCH_KEEP() is not used. Also,
703
// there's no code to convert a BranchU to a BranchB since counting the JPs in
703
// theres no code to convert a BranchU to a BranchB since counting the JPs in
704
704
// a BranchU is (at least presently) expensive, and besides, keeping around a
705
705
// BranchU is form of hysteresis.
706
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 ((Pjp2->jp_Type) == (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
__JudyFreeJBU(PjbuRaw, Pjpm); \
737
\
738
(Pjp->jp_Type) = (NewJPType); \
739
(Pjp->jp_Addr) = (Word_t) PjllnewRaw; \
740
goto ContinueDelWalk; /* delete from new leaf */ \
741
}
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
742
743
743
// Overall common code for initial BranchU deletion handling:
744
744
//
748
748
//
749
749
// Note: BranchU handling differs from BranchL and BranchB as described above.
750
750
751
#define JU_BRANCHU(cLevel,MaxPop1,LeafType,NullJPType,NewJPType, \
752
LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \
753
\
754
assert(! JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, cLevel)); \
755
assert(ParentLevel > (cLevel)); \
756
DBGCODE(parentJPtype = Pjp->jp_Type;) \
757
\
758
pop1 = JU_JPBRANCH_POP0(Pjp->jp_DcdPop0, 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)
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
770
771
771
772
772
// END OF MACROS, START OF CASES:
773
773
//
774
// Note: It's no accident that the macro calls for these cases is nearly
775
// identical to the code for BranchL's, with the addition of cJU_JPNULL*
776
// parameters only needed for BranchU's.
777
778
case cJU_JPBRANCH_U2:
779
780
JU_BRANCHU(2, cJU_LEAF2_MAXPOP1, uint16_t *,
781
cJU_JPNULL1, cJU_JPLEAF2,
782
__JudyLeaf1ToLeaf2, __JudyAllocJLL2, 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
__JudyLeaf2ToLeaf3, __JudyAllocJLL3, JL_LEAF3VALUEAREA,
790
JU_BRANCH_COPY_IMMED_ODD, JU_COPY3_LONG_TO_PINDEX);
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
791
792
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
__JudyLeaf3ToLeaf4, __JudyAllocJLL4, 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
__JudyLeaf4ToLeaf5, __JudyAllocJLL5, 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
__JudyLeaf5ToLeaf6, __JudyAllocJLL6, 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
__JudyLeaf6ToLeaf7, __JudyAllocJLL7, JL_LEAF7VALUEAREA,
819
JU_BRANCH_COPY_IMMED_ODD, JU_COPY7_LONG_TO_PINDEX);
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
820
#endif // JU_64BIT
821
821
822
// A top-level BranchU is different and cannot use JU_BRANCHU(): Don't try to
823
// compress to a (JAP) leaf yet, but leave this for a later deletion
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
824
// (hysteresis > 0); just descend through the BranchU:
825
825
826
case cJU_JPBRANCH_U:
827
828
DBGCODE(parentJPtype = Pjp->jp_Type;)
829
830
level = cJU_ROOTSTATE;
831
Pjp = P_JP(Pjp->jp_Addr) + JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
832
break;
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
833
834
834
835
835
// ****************************************************************************
849
849
// (Yes, this is very terse... Study it and it will make sense.)
850
850
// (Note, parts of this diagram are repeated below for quick reference.)
851
851
//
852
// reformat JP here for Judy1 only, from word-1 to word-2
853
// |
854
// JUDY1 && JU_64BIT JUDY1 || JU_64BIT |
855
// V
852
// reformat JP here for Judy1 only, from word-1 to word-2
853
// |
854
// JUDY1 && JU_64BIT JUDY1 || JU_64BIT |
855
// V
856
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
857
// Leaf2 [[ => 2_07..04 ] => 2_03 => 2_02 ] => 2_01
858
// Leaf3 [[ => 3_05..03 ] => 3_02 ] => 3_01
859
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
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
864
//
865
865
// (*) For Judy1 & 64-bit, go directly from a LeafB1 to cJU_JPIMMED_1_15; skip
866
866
// Leaf1, as described in Judy1.h regarding cJ1_JPLEAF1.
874
874
// Variables ParentLevel, pop1, PjllnewRaw, Pjllnew, Pjpm, and Index are in the
875
875
// context.
876
876
//
877
// Note: Doing an "uplevel" doesn't occur until the old leaf can be compressed
877
// Note: Doing an "uplevel" doesnt occur until the old leaf can be compressed
878
878
// up one level BEFORE deleting an index; that is, hysteresis = 1.
879
879
//
880
880
// Note: LeafType, MaxPop1, NewJPType, and Alloc refer to the up-level leaf,
881
881
// not the current leaf.
882
882
//
883
// Note: 010327: Fixed bug where the jp_DcdPop0 next-uplevel digit (byte)
883
// Note: 010327: Fixed bug where the jp_DcdPopO next-uplevel digit (byte)
884
884
// above the current Pop0 value was not being cleared. When upleveling, one
885
// digit in jp_DcdPop0 "moves" from being part of the Dcd subfield to the Pop0
885
// digit in jp_DcdPopO "moves" from being part of the Dcd subfield to the Pop0
886
886
// subfield, but since a leaf maxpop1 is known to be <= 1 byte in size, the new
887
887
// Pop0 byte should always be zero. This is easy to overlook because
888
888
// JU_JPLEAF_POP0() "knows" to only use the LSB of Pop0 (for efficiency) and
890
890
// JU_JPLEAF_POP0(), such as in JudyInsertBranch.c.
891
891
//
892
892
// TBD: Should JudyInsertBranch.c use JU_JPLEAF_POP0() rather than
893
// cJU_POP0MASK(), for efficiency? Does it know for sure it's a narrow pointer
893
// cJU_POP0MASK(), for efficiency? Does it know for sure its a narrow pointer
894
894
// under the leaf? Not necessarily.
895
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
if ((PjllnewRaw = Alloc(MaxPop1, Pjpm)) == 0) return(-1); \
905
Pjllnew = P_JLL(PjllnewRaw); \
906
JUDYLCODE(Pjv = ValueArea((LeafType) Pjllnew, MaxPop1);) \
907
\
908
(void) LeafToLeaf((LeafType) Pjllnew, JU_PVALUEPASS Pjp, \
909
Index & cJU_DCDMASK(cIS), /* TBD, Doug says */ \
910
(Pvoid_t) Pjpm); \
911
DBGCODE(JudyCheckSorted(Pjllnew, MaxPop1, cIS + 1);) \
912
\
913
(Pjp->jp_Addr) = (Word_t) PjllnewRaw; \
914
(Pjp->jp_DcdPop0) &= ~cJU_MASKATSTATE((cIS) + 1); /* see above */ \
915
(Pjp->jp_Type) = (NewJPType); \
916
goto ContinueDelWalk; /* delete from new leaf */ \
917
}
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
918
919
919
920
// For Leaf3, only support JU_LEAF_UPLEVEL on a 64-bit system, and for Leaf7,
920
921
// there is no JU_LEAF_UPLEVEL:
921
922
//
922
// Note: There's no way here to go from Leaf3 [Leaf7] to JAPLEAF on a 32-bit
923
// [64-bit] system. That's handled in the main code, because it's different in
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
924
925
// that a JPM is involved.
925
926
926
927
#ifndef JU_64BIT // 32-bit.
927
#define JU_LEAF_UPLEVEL64(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \
928
Alloc,ValueArea) // null.
928
#define JU_LEAF_UPLEVEL64(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \
929
Alloc,ValueArea) // null.
929
930
#else
930
#define JU_LEAF_UPLEVEL64(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \
931
Alloc,ValueArea) \
932
JU_LEAF_UPLEVEL (cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \
933
Alloc,ValueArea)
934
#define JU_LEAF_UPLEVEL_NONE(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \
935
Alloc,ValueArea) // null.
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.
936
937
#endif
937
938
938
939
// Compress a Leaf* with pop1 = 2, or a JPIMMED_*_02, into a JPIMMED_*_01:
943
944
// context, offset is modified to the undeleted Index, and Pjp is modified
944
945
// including jp_Addr.
945
946
946
#define JU_TOIMMED_01_EVEN(cIS,ignore1,ignore2) \
947
offset = (Pleaf[0] == JU_LEASTBYTES(Index, cIS)); /* undeleted Ind */ \
948
assert(Pleaf[offset ? 0 : 1] == JU_LEASTBYTES(Index, cIS)); \
949
(Pjp->jp_DcdPop0) = (Index & cJU_DCDMASK(cIS)) | Pleaf[offset]; \
950
JUDYLCODE((Pjp->jp_Addr) = Pjv[offset];)
951
952
#define JU_TOIMMED_01_ODD(cIS,SearchLeaf,CopyPIndex) \
953
{ \
954
Word_t tempindex; \
955
\
956
offset = SearchLeaf(Pleaf, 2, Index); \
957
assert(offset >= 0); /* Index must be valid */ \
958
CopyPIndex(tempindex, & (Pleaf[offset ? 0 : cIS])); \
959
(Pjp->jp_DcdPop0) = tempindex | (Index & cJU_DCDMASK(cIS)); \
960
JUDYLCODE((Pjp->jp_Addr) = Pjv[offset ? 0 : 1];) \
961
}
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
962
974
963
975
// Compress a Leaf* into a JPIMMED_*_0[2+]:
964
976
//
965
// This occurs as soon as it's possible, with hysteresis = 0. Variables pop1,
977
// This occurs as soon as its possible, with hysteresis = 0. Variables pop1,
966
978
// Pleaf, offset, and Pjpm are in the context.
967
979
//
968
980
// TBD: Explain why hysteresis = 0 here, rather than > 0. Probably because
975
987
976
988
#ifdef JUDY1
977
989
978
#define JU_LEAF_TOIMMED(cIS,LeafType,MaxPop1,BaseJPType,ignore1,\
979
ignore2,ignore3,ignore4, \
980
DeleteCopy,FreeLeaf) \
981
\
982
assert(pop1 > (MaxPop1)); \
983
\
984
if ((pop1 - 1) == (MaxPop1)) /* hysteresis = 0 */ \
985
{ \
986
Pjll_t PjllRaw = (Pjll_t) (Pjp->jp_Addr); \
987
DeleteCopy((LeafType) (Pjp->jp_1Index), Pleaf, pop1, offset, cIS); \
988
DBGCODE(JudyCheckSorted((Pjll_t) (Pjp->jp_1Index), pop1-1, cIS);) \
989
(Pjp->jp_Type) = (BaseJPType) - 1 + (MaxPop1) - 1; \
990
FreeLeaf(PjllRaw, pop1, Pjpm); \
991
return(1); \
992
}
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
}
993
1005
994
1006
#else // JUDYL
995
1007
996
1008
// Pjv is also in the context.
997
1009
998
#define JU_LEAF_TOIMMED(cIS,LeafType,MaxPop1,BaseJPType,ignore1,\
999
ignore2,ignore3,ignore4, \
1000
DeleteCopy,FreeLeaf) \
1001
\
1002
assert(pop1 > (MaxPop1)); \
1003
\
1004
if ((pop1 - 1) == (MaxPop1)) /* hysteresis = 0 */ \
1005
{ \
1006
Pjll_t PjllRaw = (Pjll_t) (Pjp->jp_Addr); \
1007
Pjv_t PjvnewRaw; \
1008
Pjv_t Pjvnew; \
1009
\
1010
if ((PjvnewRaw = __JudyLAllocJV(pop1 - 1, Pjpm)) \
1011
== (Pjv_t) NULL) return(-1); \
1012
JUDYLCODE(Pjvnew = P_JV(PjvnewRaw);) \
1013
\
1014
DeleteCopy((LeafType) (Pjp->jp_LIndex), Pleaf, pop1, offset, cIS); \
1015
JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, cIS); \
1016
DBGCODE(JudyCheckSorted((Pjll_t) (Pjp->jp_LIndex), pop1-1, cIS);) \
1017
FreeLeaf(PjllRaw, pop1, Pjpm); \
1018
(Pjp->jp_Addr) = (Word_t) PjvnewRaw; \
1019
(Pjp->jp_Type) = (BaseJPType) - 2 + (MaxPop1); \
1020
return(1); \
1021
}
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
}
1022
1034
1023
1035
// A complicating factor for JudyL & 32-bit is that Leaf2..3, and for JudyL &
1024
1036
// 64-bit Leaf 4..7, go directly to an Immed*_01, where the value is stored in
1029
1041
//
1030
1042
// This variant compresses a Leaf* with pop1 = 2 into a JPIMMED_*_01:
1031
1043
1032
#define JU_LEAF_TOIMMED_01(cIS,LeafType,MaxPop1,ignore,Immed01JPType, \
1033
ToImmed,SearchLeaf,CopyPIndex, \
1034
DeleteCopy,FreeLeaf) \
1035
\
1036
assert(pop1 > (MaxPop1)); \
1037
\
1038
if ((pop1 - 1) == (MaxPop1)) /* hysteresis = 0 */ \
1039
{ \
1040
Pjll_t PjllRaw = (Pjll_t) (Pjp->jp_Addr); \
1041
ToImmed(cIS, SearchLeaf, CopyPIndex); \
1042
FreeLeaf(PjllRaw, pop1, Pjpm); \
1043
(Pjp->jp_Type) = (Immed01JPType); \
1044
return(1); \
1045
}
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
}
1046
1058
#endif // JUDYL
1047
1059
1048
1060
// See comments above about these:
1049
1061
//
1050
1062
// Note: Here "23" means index size 2 or 3, and "47" means 4..7.
1051
1063
1052
#if (JUDY1 || JU_64BIT)
1053
#define JU_LEAF_TOIMMED_23(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \
1054
ToImmed,SearchLeaf,CopyPIndex, \
1055
DeleteCopy,FreeLeaf) \
1056
JU_LEAF_TOIMMED( cIS,LeafType,MaxPop1,BaseJPType,ignore1, \
1057
ignore2,ignore3,ignore4, \
1058
DeleteCopy,FreeLeaf)
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)
1059
1071
#else // JUDYL && 32-bit
1060
#define JU_LEAF_TOIMMED_23(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \
1061
ToImmed,SearchLeaf,CopyPIndex, \
1062
DeleteCopy,FreeLeaf) \
1063
JU_LEAF_TOIMMED_01(cIS,LeafType,MaxPop1,ignore,Immed01JPType, \
1064
ToImmed,SearchLeaf,CopyPIndex, \
1065
DeleteCopy,FreeLeaf)
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)
1066
1078
#endif
1067
1079
1068
1080
#ifdef JU_64BIT
1069
1081
#ifdef JUDY1
1070
#define JU_LEAF_TOIMMED_47(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \
1071
ToImmed,SearchLeaf,CopyPIndex, \
1072
DeleteCopy,FreeLeaf) \
1073
JU_LEAF_TOIMMED( cIS,LeafType,MaxPop1,BaseJPType,ignore1, \
1074
ignore2,ignore3,ignore4, \
1075
DeleteCopy,FreeLeaf)
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)
1076
1088
#else // JUDYL && 64-bit
1077
#define JU_LEAF_TOIMMED_47(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \
1078
ToImmed,SearchLeaf,CopyPIndex, \
1079
DeleteCopy,FreeLeaf) \
1080
JU_LEAF_TOIMMED_01(cIS,LeafType,MaxPop1,ignore,Immed01JPType, \
1081
ToImmed,SearchLeaf,CopyPIndex, \
1082
DeleteCopy,FreeLeaf)
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)
1083
1095
#endif // JUDYL
1084
1096
#endif // JU_64BIT
1085
1097
1089
1101
// offset, and for JudyL, Pjv, are in the context.
1090
1102
1091
1103
#ifdef JUDY1
1092
#define JU_LEAF_INPLACE(cIS,GrowInPlace,DeleteInPlace) \
1093
if (GrowInPlace(pop1 - 1)) /* hysteresis = 0 */ \
1094
{ \
1095
DeleteInPlace(Pleaf, pop1, offset, cIS); \
1096
DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \
1097
return(1); \
1098
}
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
}
1099
1111
#else
1100
#define JU_LEAF_INPLACE(cIS,GrowInPlace,DeleteInPlace) \
1101
if (GrowInPlace(pop1 - 1)) /* hysteresis = 0 */ \
1102
{ \
1103
DeleteInPlace(Pleaf, pop1, offset, cIS); \
1104
/**/ JU_DELETEINPLACE(Pjv, pop1, offset, ignore); \
1105
DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \
1106
return(1); \
1107
}
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
}
1108
1120
#endif
1109
1121
1110
1122
// Compress a Leaf* into a smaller memory object of the same JP type:
1114
1126
1115
1127
#ifdef JUDY1
1116
1128
1117
#define JU_LEAF_SHRINK(cIS,LeafType,DeleteCopy,Alloc,FreeLeaf,ValueArea) \
1118
if ((PjllnewRaw = Alloc(pop1 - 1, Pjpm)) == 0) return(-1); \
1119
Pjllnew = P_JLL(PjllnewRaw); \
1120
DeleteCopy((LeafType) Pjllnew, Pleaf, pop1, offset, cIS); \
1121
DBGCODE(JudyCheckSorted(Pjllnew, pop1 - 1, cIS);) \
1122
FreeLeaf(PleafRaw, pop1, Pjpm); \
1123
Pjp->jp_Addr = (Word_t) PjllnewRaw; \
1124
return(1)
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)
1125
1137
1126
1138
#else // JUDYL
1127
1139
1128
#define JU_LEAF_SHRINK(cIS,LeafType,DeleteCopy,Alloc,FreeLeaf,ValueArea) \
1129
{ \
1130
/**/ Pjv_t Pjvnew; \
1131
\
1132
if ((PjllnewRaw = Alloc(pop1 - 1, Pjpm)) == 0) return(-1); \
1133
Pjllnew = P_JLL(PjllnewRaw); \
1134
/**/ Pjvnew = ValueArea(Pjllnew, pop1 - 1); \
1135
DeleteCopy((LeafType) Pjllnew, Pleaf, pop1, offset, cIS); \
1136
/**/ JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, cIS); \
1137
DBGCODE(JudyCheckSorted(Pjllnew, pop1 - 1, cIS);) \
1138
FreeLeaf(PleafRaw, pop1, Pjpm); \
1139
Pjp->jp_Addr = (Word_t) PjllnewRaw; \
1140
return(1); \
1141
}
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
}
1142
1154
#endif // JUDYL
1143
1155
1144
1156
// Overall common code for Leaf* deletion handling:
1152
1164
// Variables Pjp, pop1, Index, and offset are in the context.
1153
1165
// The *Up parameters refer to a leaf one level up, if there is any.
1154
1166
1155
#define JU_LEAF(cIS, \
1156
UpLevel, \
1157
LeafTypeUp,MaxPop1Up,LeafJPTypeUp,LeafToLeaf, \
1158
AllocUp,ValueAreaUp, \
1159
LeafToImmed,ToImmed,CopyPIndex, \
1160
LeafType,ImmedMaxPop1,ImmedBaseJPType,Immed01JPType, \
1161
SearchLeaf,GrowInPlace,DeleteInPlace,DeleteCopy, \
1162
Alloc,FreeLeaf,ValueArea) \
1163
{ \
1164
Pjll_t PleafRaw; \
1165
LeafType Pleaf; \
1166
\
1167
assert(! JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, cIS)); \
1168
assert(ParentLevel > (cIS)); \
1169
\
1170
PleafRaw = (Pjll_t) (Pjp->jp_Addr); \
1171
Pleaf = (LeafType) P_JLL(PleafRaw); \
1172
pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1; \
1173
\
1174
UpLevel(cIS, LeafTypeUp, MaxPop1Up, LeafJPTypeUp, \
1175
LeafToLeaf, AllocUp, ValueAreaUp); \
1176
\
1177
offset = SearchLeaf(Pleaf, pop1, Index); \
1178
assert(offset >= 0); /* Index must be valid */ \
1179
JUDYLCODE(Pjv = ValueArea(Pleaf, pop1);) \
1180
\
1181
LeafToImmed(cIS, LeafType, ImmedMaxPop1, \
1182
ImmedBaseJPType, Immed01JPType, \
1183
ToImmed, SearchLeaf, CopyPIndex, \
1184
DeleteCopy, FreeLeaf); \
1185
\
1186
JU_LEAF_INPLACE(cIS, GrowInPlace, DeleteInPlace); \
1187
\
1188
JU_LEAF_SHRINK(cIS, LeafType, DeleteCopy, Alloc, FreeLeaf, \
1189
ValueArea); \
1190
}
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
}
1191
1203
1192
1204
// END OF MACROS, START OF CASES:
1193
1205
//
1194
1206
// (*) Leaf1 [[ => 1_15..08 ] => 1_07 => ... => 1_04 ] => 1_03 => 1_02 => 1_01
1195
1207
1196
#if (JUDYL || (! JU_64BIT))
1197
case cJU_JPLEAF1:
1208
#if (defined(JUDYL) || (! defined(JU_64BIT)))
1209
case cJU_JPLEAF1:
1198
1210
1199
JU_LEAF(1,
1200
JU_LEAF_UPLEVEL, uint16_t *, cJU_LEAF2_MAXPOP1, cJU_JPLEAF2,
1201
__JudyLeaf1ToLeaf2, __JudyAllocJLL2, JL_LEAF2VALUEAREA,
1202
JU_LEAF_TOIMMED, ignore, ignore,
1203
uint8_t *, cJU_IMMED1_MAXPOP1,
1204
cJU_JPIMMED_1_02, cJU_JPIMMED_1_01, __JudySearchLeaf1,
1205
JU_LEAF1GROWINPLACE, JU_DELETEINPLACE, JU_DELETECOPY,
1206
__JudyAllocJLL1, __JudyFreeJLL1, JL_LEAF1VALUEAREA);
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);
1207
1219
#endif
1208
1220
1209
1221
// A complicating factor is that for JudyL & 32-bit, a Leaf2 must go directly
1210
1222
// to an Immed 2_01 and a Leaf3 must go directly to an Immed 3_01:
1211
1223
//
1212
1224
// Leaf2 [[ => 2_07..04 ] => 2_03 => 2_02 ] => 2_01
1213
// Leaf3 [[ => 3_05..03 ] => 3_02 ] => 3_01
1225
// Leaf3 [[ => 3_05..03 ] => 3_02 ] => 3_01
1214
1226
//
1215
1227
// Hence use JU_LEAF_TOIMMED_23 instead of JU_LEAF_TOIMMED in the cases below,
1216
1228
// and also the parameters ToImmed and, for odd index sizes, CopyPIndex, are
1217
1229
// required.
1218
1230
1219
case cJU_JPLEAF2:
1231
case cJU_JPLEAF2:
1220
1232
1221
JU_LEAF(2,
1222
JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF3_MAXPOP1, cJU_JPLEAF3,
1223
__JudyLeaf2ToLeaf3, __JudyAllocJLL3, JL_LEAF3VALUEAREA,
1224
JU_LEAF_TOIMMED_23, JU_TOIMMED_01_EVEN, ignore,
1225
uint16_t *, cJU_IMMED2_MAXPOP1,
1226
cJU_JPIMMED_2_02, cJU_JPIMMED_2_01, __JudySearchLeaf2,
1227
JU_LEAF2GROWINPLACE, JU_DELETEINPLACE, JU_DELETECOPY,
1228
__JudyAllocJLL2, __JudyFreeJLL2, JL_LEAF2VALUEAREA);
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);
1229
1241
1230
1242
// On 32-bit there is no transition to "uplevel" for a Leaf3, so use
1231
1243
// JU_LEAF_UPLEVEL64 instead of JU_LEAF_UPLEVEL:
1232
1244
1233
case cJU_JPLEAF3:
1245
case cJU_JPLEAF3:
1234
1246
1235
JU_LEAF(3,
1236
JU_LEAF_UPLEVEL64, uint32_t *, cJU_LEAF4_MAXPOP1,
1237
cJU_JPLEAF4,
1238
__JudyLeaf3ToLeaf4, __JudyAllocJLL4, JL_LEAF4VALUEAREA,
1239
JU_LEAF_TOIMMED_23,
1240
JU_TOIMMED_01_ODD, JU_COPY3_PINDEX_TO_LONG,
1241
uint8_t *, cJU_IMMED3_MAXPOP1,
1242
cJU_JPIMMED_3_02, cJU_JPIMMED_3_01, __JudySearchLeaf3,
1243
JU_LEAF3GROWINPLACE, JU_DELETEINPLACE_ODD,
1244
JU_DELETECOPY_ODD,
1245
__JudyAllocJLL3, __JudyFreeJLL3, JL_LEAF3VALUEAREA);
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);
1246
1258
1247
1259
#ifdef JU_64BIT
1248
1260
1256
1268
//
1257
1269
// Hence use JU_LEAF_TOIMMED_47 instead of JU_LEAF_TOIMMED in the cases below.
1258
1270
1259
case cJU_JPLEAF4:
1260
1261
JU_LEAF(4,
1262
JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF5_MAXPOP1, cJU_JPLEAF5,
1263
__JudyLeaf4ToLeaf5, __JudyAllocJLL5, JL_LEAF5VALUEAREA,
1264
JU_LEAF_TOIMMED_47, JU_TOIMMED_01_EVEN, ignore,
1265
uint32_t *, cJU_IMMED4_MAXPOP1,
1266
cJ1_JPIMMED_4_02, cJU_JPIMMED_4_01, __JudySearchLeaf4,
1267
JU_LEAF4GROWINPLACE, JU_DELETEINPLACE, JU_DELETECOPY,
1268
__JudyAllocJLL4, __JudyFreeJLL4, JL_LEAF4VALUEAREA);
1269
1270
case cJU_JPLEAF5:
1271
1272
JU_LEAF(5,
1273
JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF6_MAXPOP1, cJU_JPLEAF6,
1274
__JudyLeaf5ToLeaf6, __JudyAllocJLL6, JL_LEAF6VALUEAREA,
1275
JU_LEAF_TOIMMED_47,
1276
JU_TOIMMED_01_ODD, JU_COPY5_PINDEX_TO_LONG,
1277
uint8_t *, cJU_IMMED5_MAXPOP1,
1278
cJ1_JPIMMED_5_02, cJU_JPIMMED_5_01, __JudySearchLeaf5,
1279
JU_LEAF5GROWINPLACE, JU_DELETEINPLACE_ODD,
1280
JU_DELETECOPY_ODD,
1281
__JudyAllocJLL5, __JudyFreeJLL5, JL_LEAF5VALUEAREA);
1282
1283
case cJU_JPLEAF6:
1284
1285
JU_LEAF(6,
1286
JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF7_MAXPOP1, cJU_JPLEAF7,
1287
__JudyLeaf6ToLeaf7, __JudyAllocJLL7, JL_LEAF7VALUEAREA,
1288
JU_LEAF_TOIMMED_47,
1289
JU_TOIMMED_01_ODD, JU_COPY6_PINDEX_TO_LONG,
1290
uint8_t *, cJU_IMMED6_MAXPOP1,
1291
cJ1_JPIMMED_6_02, cJU_JPIMMED_6_01, __JudySearchLeaf6,
1292
JU_LEAF6GROWINPLACE, JU_DELETEINPLACE_ODD,
1293
JU_DELETECOPY_ODD,
1294
__JudyAllocJLL6, __JudyFreeJLL6, JL_LEAF6VALUEAREA);
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);
1295
1307
1296
1308
// There is no transition to "uplevel" for a Leaf7, so use JU_LEAF_UPLEVEL_NONE
1297
1309
// instead of JU_LEAF_UPLEVEL, and ignore all of the parameters to that macro:
1298
1310
1299
case cJU_JPLEAF7:
1311
case cJU_JPLEAF7:
1300
1312
1301
JU_LEAF(7,
1302
JU_LEAF_UPLEVEL_NONE, ignore1, ignore2, ignore3, ignore4,
1303
ignore5, ignore6,
1304
JU_LEAF_TOIMMED_47,
1305
JU_TOIMMED_01_ODD, JU_COPY7_PINDEX_TO_LONG,
1306
uint8_t *, cJU_IMMED7_MAXPOP1,
1307
cJ1_JPIMMED_7_02, cJU_JPIMMED_7_01, __JudySearchLeaf7,
1308
JU_LEAF7GROWINPLACE, JU_DELETEINPLACE_ODD,
1309
JU_DELETECOPY_ODD,
1310
__JudyAllocJLL7, __JudyFreeJLL7, JL_LEAF7VALUEAREA);
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);
1311
1323
#endif // JU_64BIT
1312
1324
1313
1325
1314
1326
// ****************************************************************************
1315
1327
// BITMAP LEAF:
1316
1328
1317
case cJU_JPLEAF_B1:
1318
{
1329
case cJU_JPLEAF_B1:
1330
{
1319
1331
#ifdef JUDYL
1320
Pjv_t PjvnewRaw; // new value area.
1321
Pjv_t Pjvnew;
1322
Word_t subexp; // 1 of 8 subexpanses in bitmap.
1323
Pjlb_t Pjlb; // pointer to bitmap part of the leaf.
1324
BITMAPL_t bitmap; // for one subexpanse.
1325
BITMAPL_t bitmask; // bit set for Index's digit.
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.
1326
1338
#endif
1327
assert(! JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 1));
1328
assert(ParentLevel > 1);
1329
// valid Index:
1330
assert(JU_BITMAPTESTL(P_JLB(Pjp->jp_Addr), Index));
1331
1332
pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
1333
1334
// Like a Leaf1, see if it's under a narrow pointer and can become a Leaf2
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
1335
1347
// (hysteresis = 1):
1336
1348
1337
JU_LEAF_UPLEVEL(1, uint16_t *, cJU_LEAF2_MAXPOP1, cJU_JPLEAF2,
1338
__JudyLeaf1ToLeaf2, __JudyAllocJLL2,
1339
JL_LEAF2VALUEAREA);
1349
JU_LEAF_UPLEVEL(1, uint16_t *, cJU_LEAF2_MAXPOP1, cJU_JPLEAF2,
1350
j__udyLeaf1ToLeaf2, j__udyAllocJLL2,
1351
JL_LEAF2VALUEAREA);
1340
1352
1341
#if (JUDY1 && JU_64BIT)
1353
#if (defined(JUDY1) && defined(JU_64BIT))
1342
1354
1343
1355
// Handle the unusual special case, on Judy1 64-bit only, where a LeafB1 goes
1344
1356
// directly to a JPIMMED_1_15; as described in comments in Judy1.h and
1345
1357
// JudyIns.c. Copy 1-byte indexes from old LeafB1 to the Immed:
1346
1358
1347
if ((pop1 - 1) == cJU_IMMED1_MAXPOP1) // hysteresis = 0.
1348
{
1349
Pjlb_t PjlbRaw; // bitmap in old leaf.
1350
Pjlb_t Pjlb;
1351
uint8_t * Pleafnew; // JPIMMED as a pointer.
1352
Word_t ldigit; // larger than uint8_t.
1353
1354
PjlbRaw = (Pjlb_t) (Pjp->jp_Addr);
1355
Pjlb = P_JLB(PjlbRaw);
1356
Pleafnew = Pjp->jp_1Index;
1357
1358
JU_BITMAPCLEARL(Pjlb, Index); // unset Index's bit.
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.
1359
1371
1360
1372
// TBD: This is very slow, there must be a better way:
1361
1373
1362
for (ldigit = 0; ldigit < cJU_BRANCHUNUMJPS; ++ldigit)
1363
{
1364
if (JU_BITMAPTESTL(Pjlb, ldigit))
1365
{
1366
*Pleafnew++ = ldigit;
1367
assert(Pleafnew - (Pjp->jp_1Index)
1368
<= cJU_IMMED1_MAXPOP1);
1369
}
1370
}
1371
1372
DBGCODE(JudyCheckSorted((Pjll_t) (Pjp->jp_1Index),
1373
cJU_IMMED1_MAXPOP1, 1);)
1374
__JudyFreeJLB1(PjlbRaw, Pjpm);
1375
1376
Pjp->jp_Type = cJ1_JPIMMED_1_15;
1377
return(1);
1378
}
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
}
1379
1391
1380
1392
#else // (JUDYL || (! JU_64BIT))
1381
1393
1387
1399
// the critical assumption that the tree is always kept in least-compressed
1388
1400
// form.
1389
1401
1390
if (pop1 == cJU_LEAF1_MAXPOP1) // hysteresis = 1.
1391
{
1392
if (__JudyLeafB1ToLeaf1(Pjp, Pjpm) == -1) return(-1);
1393
goto ContinueDelWalk; // delete Index in new Leaf1.
1394
}
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
}
1395
1407
#endif // (JUDYL || (! JU_64BIT))
1396
1408
1397
1409
#ifdef JUDY1
1398
// unset Index's bit:
1410
// unset Indexs bit:
1399
1411
1400
JU_BITMAPCLEARL(P_JLB(Pjp->jp_Addr), Index);
1412
JU_BITMAPCLEARL(P_JLB(Pjp->jp_Addr), Index);
1401
1413
#else // JUDYL
1402
1414
1403
1415
// This is very different from Judy1 because of the need to manage the value
1405
1417
//
1406
1418
// Get last byte to decode from Index, and pointer to bitmap leaf:
1407
1419
1408
digit = JU_DIGITATSTATE(Index, 1);
1409
Pjlb = P_JLB(Pjp->jp_Addr);
1420
digit = JU_DIGITATSTATE(Index, 1);
1421
Pjlb = P_JLB(Pjp->jp_Addr);
1410
1422
1411
1423
// Prepare additional values:
1412
1424
1413
subexp = digit / cJU_BITSPERSUBEXPL; // which subexpanse.
1414
bitmap = JU_JLB_BITMAP(Pjlb, subexp); // subexp's 32-bit map.
1415
PjvRaw = JL_JLB_PVALUE(Pjlb, subexp); // corresponding values.
1416
Pjv = P_JV(PjvRaw);
1417
bitmask = JU_BITPOSMASKL(digit); // mask for Index.
1418
1419
assert(bitmap & bitmask); // Index must be valid.
1420
1421
if (bitmap == cJU_FULLBITMAPL) // full bitmap, take shortcut:
1422
{
1423
pop1 = cJU_BITSPERSUBEXPL;
1424
offset = digit % cJU_BITSPERSUBEXPL;
1425
}
1426
else // compute subexpanse pop1 and value area offset:
1427
{
1428
pop1 = __JudyCountBitsL(bitmap);
1429
offset = __JudyCountBitsL(bitmap & (bitmask - 1));
1430
}
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
}
1431
1443
1432
1444
// Handle solitary Index remaining in subexpanse:
1433
1445
1434
if (pop1 == 1)
1435
{
1436
__JudyLFreeJV(PjvRaw, 1, Pjpm);
1437
1438
JL_JLB_PVALUE(Pjlb, subexp) = (Pjv_t) NULL;
1439
JU_JLB_BITMAP(Pjlb, subexp) = 0;
1440
1441
return(1);
1442
}
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
}
1443
1455
1444
1456
// Shrink value area in place or move to a smaller value area:
1445
1457
1446
if (JL_LEAFVGROWINPLACE(pop1 - 1)) // hysteresis = 0.
1447
{
1448
JU_DELETEINPLACE(Pjv, pop1, offset, ignore);
1449
}
1450
else
1451
{
1452
if ((PjvnewRaw = __JudyLAllocJV(pop1 - 1, Pjpm))
1453
== (Pjv_t) NULL) return(-1);
1454
Pjvnew = P_JV(PjvnewRaw);
1455
1456
JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, ignore);
1457
__JudyLFreeJV(PjvRaw, pop1, Pjpm);
1458
JL_JLB_PVALUE(Pjlb, subexp) = (Pjv_t) PjvnewRaw;
1459
}
1460
1461
JU_JLB_BITMAP(Pjlb, subexp) ^= bitmask; // clear Index's bit.
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.
1462
1474
1463
1475
#endif // JUDYL
1464
1476
1465
return(1);
1477
return(1);
1466
1478
1467
} // case.
1479
} // case.
1468
1480
1469
1481
1470
1482
#ifdef JUDY1
1477
1489
// Note: Earlier the second assertion below said, "== 2", but in fact the
1478
1490
// parent could be at a higher level if a fullpop is under a narrow pointer.
1479
1491
1480
case cJ1_JPFULLPOPU1:
1481
{
1482
Pjlb_t PjlbRaw;
1483
Pjlb_t Pjlb;
1484
Word_t subexp;
1485
1486
assert(! JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 2));
1487
assert(ParentLevel > 1); // see above.
1488
1489
if ((PjlbRaw = __JudyAllocJLB1(Pjpm)) == (Pjlb_t) NULL)
1490
return(-1);
1491
Pjlb = P_JLB(PjlbRaw);
1492
1493
// Fully populate the leaf, then unset Index's bit:
1494
1495
for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp)
1496
JU_JLB_BITMAP(Pjlb, subexp) = cJU_FULLBITMAPL;
1497
1498
JU_BITMAPCLEARL(Pjlb, Index);
1499
1500
(Pjp->jp_Addr) = (Word_t) PjlbRaw;
1501
(Pjp->jp_Type) = cJU_JPLEAF_B1;
1502
1503
return(1);
1504
}
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
}
1505
1517
#endif // JUDY1
1506
1518
1507
1519
1508
1520
// ****************************************************************************
1509
1521
// IMMEDIATE JP:
1510
1522
//
1511
// If there's just the one Index in the Immed, convert the JP to a JPNULL*
1523
// If theres just the one Index in the Immed, convert the JP to a JPNULL*
1512
1524
// (should only happen in a BranchU); otherwise delete the Index from the
1513
1525
// Immed. See the state transitions table elsewhere in this file for a summary
1514
1526
// of which Immed types must be handled. Hysteresis = 0; none is possible with
1520
1532
//
1521
1533
// Variables Pjp and parentJPtype are in the context.
1522
1534
//
1523
// Note: cJU_JPIMMED_*_01 should only be encountered in BranchU's, not in
1524
// BranchL's or BranchB's (where it's improper to merely modify the JP to be a
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
1525
1537
// null JP); that is, BranchL and BranchB code should have already handled
1526
1538
// any cJU_JPIMMED_*_01 by different means.
1527
1539
1528
#define JU_IMMED_01(NewJPType,ParentJPType) \
1529
\
1530
assert(parentJPtype == (ParentJPType)); \
1531
assert((Pjp->jp_DcdPop0) == JU_TRIMTODCDSIZE(Index)); \
1532
\
1533
(Pjp->jp_Type) = (NewJPType); \
1534
(Pjp->jp_DcdPop0) = 0; \
1535
(Pjp->jp_Addr) = 0; \
1536
return(1)
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)
1537
1546
1538
1547
// Convert cJ*_JPIMMED_*_02 to cJU_JPIMMED_*_01:
1539
1548
//
1540
1549
// Move the undeleted Index, whichever does not match the least bytes of Index,
1541
1550
// from undecoded-bytes-only (in jp_1Index or jp_LIndex as appropriate) to
1542
// jp_DcdPop0 (full-field). Pjp, Index, and offset are in the context.
1543
1544
#define JU_IMMED_02(cIS,LeafType,NewJPType) \
1545
{ \
1546
LeafType Pleaf; \
1547
\
1548
assert((ParentLevel - 1) == (cIS)); \
1549
JUDY1CODE(Pleaf = (LeafType) (Pjp->jp_1Index);) \
1550
JUDYLCODE(Pleaf = (LeafType) (Pjp->jp_LIndex);) \
1551
JUDYLCODE(PjvRaw = (Pjv_t) (Pjp->jp_Addr);) \
1552
JUDYLCODE(Pjv = P_JV(PjvRaw);) \
1553
JU_TOIMMED_01_EVEN(cIS, ignore, ignore); \
1554
JUDYLCODE(__JudyLFreeJV(PjvRaw, 2, Pjpm);) \
1555
(Pjp->jp_Type) = (NewJPType); \
1556
return(1); \
1557
}
1558
1559
#if (JUDY1 || JU_64BIT)
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))
1560
1569
1561
1570
// Variation for "odd" cJ*_JPIMMED_*_02 JP types, which are very different from
1562
1571
// "even" types because they use leaf search code and odd-copy macros:
1563
1572
//
1564
1573
// Note: JudyL 32-bit has no "odd" JPIMMED_*_02 types.
1565
1574
1566
#define JU_IMMED_02_ODD(cIS,NewJPType,SearchLeaf,CopyPIndex) \
1567
{ \
1568
uint8_t * Pleaf; \
1569
\
1570
assert((ParentLevel - 1) == (cIS)); \
1571
JUDY1CODE(Pleaf = (uint8_t *) (Pjp->jp_1Index);) \
1572
JUDYLCODE(Pleaf = (uint8_t *) (Pjp->jp_LIndex);) \
1573
JUDYLCODE(PjvRaw = (Pjv_t) (Pjp->jp_Addr);) \
1574
JUDYLCODE(Pjv = P_JV(PjvRaw);) \
1575
JU_TOIMMED_01_ODD(cIS, SearchLeaf, CopyPIndex); \
1576
JUDYLCODE(__JudyLFreeJV(PjvRaw, 2, Pjpm);) \
1577
(Pjp->jp_Type) = (NewJPType); \
1578
return(1); \
1579
}
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
}
1580
1589
#endif // (JUDY1 || JU_64BIT)
1581
1590
1582
1591
// Core code for deleting one Index (and for JudyL, its value area) from a
1585
1594
// Variables Pleaf, pop1, and offset are in the context.
1586
1595
1587
1596
#ifdef JUDY1
1588
#define JU_IMMED_DEL(cIS,DeleteInPlace) \
1589
DeleteInPlace(Pleaf, pop1, offset, cIS); \
1590
DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);)
1597
#define JU_IMMED_DEL(cIS,DeleteInPlace) \
1598
DeleteInPlace(Pleaf, pop1, offset, cIS); \
1599
DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);)
1591
1600
1592
1601
#else // JUDYL
1593
1602
1594
1603
// For JudyL the value area might need to be shrunk:
1595
1604
1596
#define JU_IMMED_DEL(cIS,DeleteInPlace) \
1597
\
1598
if (JL_LEAFVGROWINPLACE(pop1 - 1)) /* hysteresis = 0 */ \
1599
{ \
1600
DeleteInPlace( Pleaf, pop1, offset, cIS); \
1601
JU_DELETEINPLACE(Pjv, pop1, offset, ignore); \
1602
DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \
1603
} \
1604
else \
1605
{ \
1606
Pjv_t PjvnewRaw; \
1607
Pjv_t Pjvnew; \
1608
\
1609
if ((PjvnewRaw = __JudyLAllocJV(pop1 - 1, Pjpm)) \
1610
== (Pjv_t) NULL) return(-1); \
1611
Pjvnew = P_JV(PjvnewRaw); \
1612
\
1613
DeleteInPlace(Pleaf, pop1, offset, cIS); \
1614
JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, ignore); \
1615
DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \
1616
__JudyLFreeJV(PjvRaw, pop1, Pjpm); \
1617
\
1618
(Pjp->jp_Addr) = (Word_t) PjvnewRaw; \
1619
}
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
}
1620
1629
#endif // JUDYL
1621
1630
1622
1631
// Delete one Index from a larger Immed where no restructuring is required:
1623
1632
//
1624
1633
// Variables pop1, Pjp, offset, and Index are in the context.
1625
1634
1626
#define JU_IMMED(cIS,LeafType,BaseJPType,SearchLeaf,DeleteInPlace) \
1627
{ \
1628
LeafType Pleaf; \
1629
\
1630
assert((ParentLevel - 1) == (cIS)); \
1631
JUDY1CODE(Pleaf = (LeafType) (Pjp->jp_1Index);) \
1632
JUDYLCODE(Pleaf = (LeafType) (Pjp->jp_LIndex);) \
1633
JUDYLCODE(PjvRaw = (Pjv_t) (Pjp->jp_Addr);) \
1634
JUDYLCODE(Pjv = P_JV(PjvRaw);) \
1635
pop1 = (Pjp->jp_Type) - (BaseJPType) + 2; \
1636
offset = SearchLeaf(Pleaf, pop1, Index); \
1637
assert(offset >= 0); /* Index must be valid */ \
1638
\
1639
JU_IMMED_DEL(cIS, DeleteInPlace); \
1640
--(Pjp->jp_Type); \
1641
return(1); \
1642
}
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
}
1643
1652
1644
1653
1645
1654
// END OF MACROS, START OF CASES:
1646
1655
1647
1656
// Single Index remains in Immed; convert JP to null:
1648
1657
1649
case cJU_JPIMMED_1_01: JU_IMMED_01(cJU_JPNULL1, cJU_JPBRANCH_U2);
1650
case cJU_JPIMMED_2_01: JU_IMMED_01(cJU_JPNULL2, cJU_JPBRANCH_U3);
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);
1651
1660
#ifndef JU_64BIT
1652
case cJU_JPIMMED_3_01: JU_IMMED_01(cJU_JPNULL3, cJU_JPBRANCH_U);
1661
case cJU_JPIMMED_3_01: JU_IMMED_01(cJU_JPNULL3, cJU_JPBRANCH_U);
1653
1662
#else
1654
case cJU_JPIMMED_3_01: JU_IMMED_01(cJU_JPNULL3, cJU_JPBRANCH_U4);
1655
case cJU_JPIMMED_4_01: JU_IMMED_01(cJU_JPNULL4, cJU_JPBRANCH_U5);
1656
case cJU_JPIMMED_5_01: JU_IMMED_01(cJU_JPNULL5, cJU_JPBRANCH_U6);
1657
case cJU_JPIMMED_6_01: JU_IMMED_01(cJU_JPNULL6, cJU_JPBRANCH_U7);
1658
case cJU_JPIMMED_7_01: JU_IMMED_01(cJU_JPNULL7, cJU_JPBRANCH_U);
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);
1659
1668
#endif
1660
1669
1661
1670
// Multiple Indexes remain in the Immed JP; delete the specified Index:
1662
1671
1663
case cJU_JPIMMED_1_02:
1664
1665
JU_IMMED_02(1, uint8_t *, cJU_JPIMMED_1_01);
1666
1667
case cJU_JPIMMED_1_03:
1668
#if (JUDY1 || JU_64BIT)
1669
case cJU_JPIMMED_1_04:
1670
case cJU_JPIMMED_1_05:
1671
case cJU_JPIMMED_1_06:
1672
case cJU_JPIMMED_1_07:
1673
#endif
1674
#if (JUDY1 && JU_64BIT)
1675
case cJ1_JPIMMED_1_08:
1676
case cJ1_JPIMMED_1_09:
1677
case cJ1_JPIMMED_1_10:
1678
case cJ1_JPIMMED_1_11:
1679
case cJ1_JPIMMED_1_12:
1680
case cJ1_JPIMMED_1_13:
1681
case cJ1_JPIMMED_1_14:
1682
case cJ1_JPIMMED_1_15:
1683
#endif
1684
JU_IMMED(1, uint8_t *, cJU_JPIMMED_1_02,
1685
__JudySearchLeaf1, JU_DELETEINPLACE);
1686
1687
#if (JUDY1 || JU_64BIT)
1688
case cJU_JPIMMED_2_02:
1689
1690
JU_IMMED_02(2, uint16_t *, cJU_JPIMMED_2_01);
1691
1692
case cJU_JPIMMED_2_03:
1693
#endif
1694
#if (JUDY1 && JU_64BIT)
1695
case cJ1_JPIMMED_2_04:
1696
case cJ1_JPIMMED_2_05:
1697
case cJ1_JPIMMED_2_06:
1698
case cJ1_JPIMMED_2_07:
1699
#endif
1700
#if (JUDY1 || JU_64BIT)
1701
JU_IMMED(2, uint16_t *, cJU_JPIMMED_2_02,
1702
__JudySearchLeaf2, JU_DELETEINPLACE);
1703
1704
case cJU_JPIMMED_3_02:
1705
1706
JU_IMMED_02_ODD(3, cJU_JPIMMED_3_01,
1707
__JudySearchLeaf3, JU_COPY3_PINDEX_TO_LONG);
1708
1709
#endif
1710
1711
#if (JUDY1 && JU_64BIT)
1712
case cJ1_JPIMMED_3_03:
1713
case cJ1_JPIMMED_3_04:
1714
case cJ1_JPIMMED_3_05:
1715
1716
JU_IMMED(3, uint8_t *, cJU_JPIMMED_3_02,
1717
__JudySearchLeaf3, JU_DELETEINPLACE_ODD);
1718
1719
case cJ1_JPIMMED_4_02:
1720
1721
JU_IMMED_02(4, uint32_t *, cJU_JPIMMED_4_01);
1722
1723
case cJ1_JPIMMED_4_03:
1724
1725
JU_IMMED(4, uint32_t *, cJ1_JPIMMED_4_02,
1726
__JudySearchLeaf4, JU_DELETEINPLACE);
1727
1728
case cJ1_JPIMMED_5_02:
1729
1730
JU_IMMED_02_ODD(5, cJU_JPIMMED_5_01,
1731
__JudySearchLeaf5, JU_COPY5_PINDEX_TO_LONG);
1732
1733
case cJ1_JPIMMED_5_03:
1734
1735
JU_IMMED(5, uint8_t *, cJ1_JPIMMED_5_02,
1736
__JudySearchLeaf5, JU_DELETEINPLACE_ODD);
1737
1738
case cJ1_JPIMMED_6_02:
1739
1740
JU_IMMED_02_ODD(6, cJU_JPIMMED_6_01,
1741
__JudySearchLeaf6, JU_COPY6_PINDEX_TO_LONG);
1742
1743
case cJ1_JPIMMED_7_02:
1744
1745
JU_IMMED_02_ODD(7, cJU_JPIMMED_7_01,
1746
__JudySearchLeaf7, JU_COPY7_PINDEX_TO_LONG);
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);
1747
1756
1748
1757
#endif // (JUDY1 && JU_64BIT)
1749
1758
1751
1760
// ****************************************************************************
1752
1761
// INVALID JP TYPE:
1753
1762
1754
default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); return(-1);
1763
default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); return(-1);
1755
1764
1756
} // switch
1765
} // switch
1757
1766
1758
1767
1759
1768
// PROCESS JP -- RECURSIVELY:
1763
1772
// JP in the BranchL to the parent (hysteresis = 0), which implicitly creates a
1764
1773
// narrow pointer if there was not already one in the hierarchy.
1765
1774
1766
assert(level);
1767
retcode = __JudyDelWalk(Pjp, Index, level, Pjpm);
1768
assert(retcode != 0); // should never happen.
1769
1770
if ((Pjp->jp_Type) < cJU_JPIMMED_1_01) // not an Immed.
1771
{
1772
switch (retcode)
1773
{
1774
case 1: --(Pjp->jp_DcdPop0); break; // decrement count.
1775
1776
case 2: // collapse BranchL to single JP; see above:
1777
{
1778
Pjbl_t PjblRaw = (Pjbl_t) (Pjp->jp_Addr);
1779
Pjbl_t Pjbl = P_JBL(PjblRaw);
1780
1781
*Pjp = Pjbl->jbl_jp[0];
1782
__JudyFreeJBL(PjblRaw, Pjpm);
1783
retcode = 1;
1784
}
1785
}
1786
}
1787
1788
return(retcode);
1789
1790
} // __JudyDelWalk()
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()
1791
1807
1792
1808
1793
1809
// ****************************************************************************
1797
1813
// Main entry point. See the manual entry for details.
1798
1814
1799
1815
#ifdef JUDY1
1800
FUNCTION int Judy1Unset (
1816
FUNCTION int Judy1Unset
1801
1817
#else
1802
FUNCTION int JudyLDel (
1818
FUNCTION int JudyLDel
1803
1819
#endif
1804
PPvoid_t PPArray, // in which to delete.
1805
Word_t Index, // to delete.
1806
PJError_t PJError) // optional, for returning error info.
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
)
1807
1825
{
1808
Word_t pop1; // population of leaf.
1809
int offset; // at which to delete Index.
1810
JUDY1CODE(int retcode;) // return code from Judy1Test().
1826
Word_t pop1; // population of leaf.
1827
int offset; // at which to delete Index.
1828
JUDY1CODE(int retcode;) // return code from Judy1Test().
1811
1829
JUDYLCODE(PPvoid_t PPvalue;) // pointer from JudyLGet().
1812
1830
1813
1831
1814
1832
// CHECK FOR NULL ARRAY POINTER (error by caller):
1815
1833
1816
1834
if (PPArray == (PPvoid_t) NULL)
1817
{
1818
JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY);
1819
return(JERRI);
1820
}
1835
{
1836
JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY);
1837
return(JERRI);
1838
}
1821
1839
1822
1840
1823
1841
// CHECK IF INDEX IS INVALID:
1824
1842
//
1825
// If so, there's nothing to do. This saves a lot of time. Pass through
1843
// If so, theres nothing to do. This saves a lot of time. Pass through
1826
1844
// PJError, if any, from the "get" function.
1827
1845
1828
1846
#ifdef JUDY1
1829
if ((retcode = Judy1Test(*PPArray, Index, PJError)) == JERRI)
1830
return (JERRI);
1847
if ((retcode = Judy1Test(*PPArray, Index, PJError)) == JERRI)
1848
return (JERRI);
1831
1849
1832
if (retcode == 0) return(0);
1850
if (retcode == 0) return(0);
1833
1851
#else
1834
if ((PPvalue = JudyLGet(*PPArray, Index, PJError)) == PPJERR)
1835
return (JERRI);
1852
if ((PPvalue = JudyLGet(*PPArray, Index, PJError)) == PPJERR)
1853
return (JERRI);
1836
1854
1837
if (PPvalue == (PPvoid_t) NULL) return(0);
1855
if (PPvalue == (PPvoid_t) NULL) return(0);
1838
1856
#endif
1839
1857
1840
1858
1841
1859
// ****************************************************************************
1842
// PROCESS TOP LEVEL (JAP) BRANCHES AND LEAVES:
1843
1844
ContinueDel: // for modifying state without recursing.
1845
1846
switch (JAPTYPE(*PPArray))
1847
{
1848
1849
#if (LOW_POP && JUDYL)
1850
1851
// ****************************************************************************
1852
// JAPLEAF_POPU1:
1853
//
1854
// Check if Index is in the array (should always be). If so, free the leaf and
1855
// modify the root pointer. Hysteresis = 0; none is possible.
1856
1857
case cJL_JAPLEAF_POPU1:
1858
{
1859
Pjlw_t Pjlw = P_JLW(*PPArray); // first word of leaf.
1860
assert(Pjlw[0] == Index);
1861
1862
__JudyFreeJLW(Pjlw, /* pop1 = */ 1, (Pjpm_t) NULL);
1863
1864
*PPArray = (Pvoid_t) NULL; // mark Judy array (JAP) as empty.
1865
DBGCODE(JudyCheckPop(*PPArray);)
1866
return(1);
1867
}
1868
1869
1870
// ****************************************************************************
1871
// JAPLEAF_POPU2:
1872
//
1873
// TBD: It is still debatable whether it is faster to have POPU2 types. It
1874
// needs to be measured. This is a lot of fuss for a 2-element array. -- Doug
1875
1876
case cJL_JAPLEAF_POPU2:
1877
{
1878
1879
// Save the non-deleted Index (whichever it is) and convert the leaf to a
1880
// CJL_JAPLEAF_POPU1 (which is smaller). Hysteresis = 0; none is possible.
1881
//
1882
// TBD: Once again, this would be much cleaner using a data structure.
1883
1884
Pjlw_t Pjlw = P_JLW(*PPArray); // first word of leaf.
1885
Pjlw_t Pjlwnew = __JudyAllocJLW(2 - 1);
1886
JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI);
1887
1888
offset = (Index == Pjlw[0]); // 0 or 1 == undeleted Index.
1889
Pjlwnew[0] = Pjlw[0 + offset]; // undeleted Index.
1890
Pjlwnew[1] = Pjlw[2 + offset]; // its value area.
1891
1892
__JudyFreeJLW(Pjlw, /* pop1 = */ 2, (Pjpm_t) NULL);
1893
1894
*PPArray = (Pvoid_t) ((Word_t) Pjlwnew | cJL_JAPLEAF_POPU1);
1895
DBGCODE(JudyCheckPop(*PPArray);)
1896
return(1);
1897
1898
} // case cJL_JAPLEAF_POPU2.
1899
1900
#endif // (LOW_POP && JUDYL)
1901
1902
1903
// ****************************************************************************
1904
// JAP LEAF, OTHER SIZE:
1860
// PROCESS TOP LEVEL (LEAFW) BRANCHES AND LEAVES:
1861
1862
// ****************************************************************************
1863
// LEAFW LEAF, OTHER SIZE:
1905
1864
//
1906
1865
// Shrink or convert the leaf as necessary. Hysteresis = 0; none is possible.
1907
1866
1908
case cJU_JAPLEAF:
1909
{
1910
JUDYLCODE(Pjv_t Pjv;) // current value area.
1911
JUDYLCODE(Pjv_t Pjvnew;) // value area in new leaf.
1912
Pjlw_t Pjlw = P_JLW(*PPArray); // first word of leaf.
1913
Pjlw_t Pjlwnew; // replacement leaf.
1914
pop1 = Pjlw[0] + 1; // first word of leaf is pop0.
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.
1915
1874
1916
1875
// Delete single (last) Index from array:
1917
1876
1918
if (pop1 == 1)
1919
{
1920
__JudyFreeJLW(Pjlw, /* pop1 = */ 1, (Pjpm_t) NULL);
1921
*PPArray = (Pvoid_t) NULL;
1922
return(1);
1923
}
1877
if (pop1 == 1)
1878
{
1879
j__udyFreeJLW(Pjlw, /* pop1 = */ 1, (Pjpm_t) NULL);
1880
*PPArray = (Pvoid_t) NULL;
1881
return(1);
1882
}
1924
1883
1925
1884
// Locate Index in compressible leaf:
1926
1885
1927
offset = __JudySearchLeafW(Pjlw + 1, pop1, Index);
1928
assert(offset >= 0); // Index must be valid.
1886
offset = j__udySearchLeafW(Pjlw + 1, pop1, Index);
1887
assert(offset >= 0); // Index must be valid.
1929
1888
1930
1889
JUDYLCODE(Pjv = JL_LEAFWVALUEAREA(Pjlw, pop1);)
1931
1890
1935
1894
// place from pop1." Also, Pjlw points to the count word, so skip that for
1936
1895
// doing the deletion.
1937
1896
1938
if (JU_LEAFWGROWINPLACE(pop1 - 1))
1939
{
1940
JU_DELETEINPLACE(Pjlw + 1, pop1, offset, ignore);
1897
if (JU_LEAFWGROWINPLACE(pop1 - 1))
1898
{
1899
JU_DELETEINPLACE(Pjlw + 1, pop1, offset, ignore);
1941
1900
#ifdef JUDYL // also delete from value area:
1942
JU_DELETEINPLACE(Pjv, pop1, offset, ignore);
1901
JU_DELETEINPLACE(Pjv, pop1, offset, ignore);
1943
1902
#endif
1944
DBGCODE(JudyCheckSorted((Pjll_t) (Pjlw + 1), pop1 - 1,
1945
cJU_ROOTSTATE);)
1946
--(Pjlw[0]); // decrement population.
1947
DBGCODE(JudyCheckPop(*PPArray);)
1948
return(1);
1949
}
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
}
1950
1909
1951
1910
// Allocate new leaf for use in either case below:
1952
1911
1953
Pjlwnew = __JudyAllocJLW(pop1 - 1);
1954
JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI);
1955
1956
#if (LOW_POP && JUDYL)
1957
// Shrink leaf to a cJL_JAPLEAF_POPU2:
1958
//
1959
// Note: The "3" below is equal to pop1, but faster because it's a constant.
1960
1961
if ((pop1 - 1) == 2)
1962
{
1963
JU_DELETECOPY(Pjlwnew + 0, Pjlw + 1, 3, offset, ignore);
1964
JU_DELETECOPY(Pjlwnew + 2, Pjv, 3, offset, ignore);
1965
DBGCODE(JudyCheckSorted(Pjlwnew, 2, cJU_ROOTSTATE);)
1966
1967
__JudyFreeJLW(Pjlw, pop1, (Pjpm_t) NULL);
1968
1969
*PPArray = (Pvoid_t) ((Word_t) Pjlwnew | cJL_JAPLEAF_POPU2);
1970
DBGCODE(JudyCheckPop(*PPArray);)
1971
return(1);
1972
}
1973
#endif // (LOW_POP && JUDYL)
1974
1975
// Shrink to smaller JAPLEAF:
1912
Pjlwnew = j__udyAllocJLW(pop1 - 1);
1913
JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI);
1914
1915
// Shrink to smaller LEAFW:
1976
1916
//
1977
1917
// Note: Skip the first word = pop0 in each leaf.
1978
1918
1979
Pjlwnew[0] = (pop1 - 1) - 1;
1980
JU_DELETECOPY(Pjlwnew + 1, Pjlw + 1, pop1, offset, ignore);
1919
Pjlwnew[0] = (pop1 - 1) - 1;
1920
JU_DELETECOPY(Pjlwnew + 1, Pjlw + 1, pop1, offset, ignore);
1981
1921
1982
1922
#ifdef JUDYL // also delete from value area:
1983
Pjvnew = JL_LEAFWVALUEAREA(Pjlwnew, pop1 - 1);
1984
JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, ignore);
1923
Pjvnew = JL_LEAFWVALUEAREA(Pjlwnew, pop1 - 1);
1924
JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, ignore);
1985
1925
#endif
1986
DBGCODE(JudyCheckSorted(Pjlwnew + 1, pop1 - 1, cJU_ROOTSTATE);)
1987
1988
__JudyFreeJLW(Pjlw, pop1, (Pjpm_t) NULL);
1989
1990
*PPArray = (Pvoid_t) ((Word_t) Pjlwnew | cJU_JAPLEAF);
1991
DBGCODE(JudyCheckPop(*PPArray);)
1992
return(1);
1993
1994
} // case cJU_JAPLEAF.
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
1995
1937
1996
1938
1997
1939
// ****************************************************************************
1998
// JAP BRANCH:
1940
// JRP BRANCH:
1999
1941
//
2000
1942
// Traverse through the JPM to do the deletion unless the population is small
2001
// enough to convert immediately to a JAPLEAF.
1943
// enough to convert immediately to a LEAFW.
2002
1944
2003
case cJU_JAPBRANCH:
2004
{
2005
Pjpm_t Pjpm;
2006
Pjp_t Pjp; // top-level JP to process.
2007
Word_t digit; // in a branch.
2008
JUDYLCODE(Pjv_t Pjv;) // to value area.
2009
Pjlw_t Pjlwnew; // replacement leaf.
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.
2010
1951
DBGCODE(Pjlw_t Pjlwnew_orig;)
2011
1952
2012
Pjpm = P_JPM(*PPArray); // top object in array (tree).
2013
Pjp = &(Pjpm->jpm_JP); // next object (first branch or leaf).
2014
2015
assert(((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_L)
2016
|| ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_B)
2017
|| ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_U));
2018
2019
2020
// CANNOT COMPRESS TO A JAPLEAF => WALK THE TREE (THE NORMAL CASE):
2021
//
2022
// Hysteresis = 1, that is, do not compress to a leaf the first time it could
2023
// actually be done.
2024
//
2025
// Note: Recursive code in __JudyDelWalk() knows how to collapse a lower-level
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
2026
1963
// BranchL containing a single JP into the parent JP as a narrow pointer, but
2027
// the code here can't do that for a top-level BranchL. The result can be
2028
// PArray -> JPM -> JAPBranchL containing a single JP. This situation is
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
2029
1966
// unavoidable because a JPM cannot contain a narrow pointer; the BranchL is
2030
1967
// required in order to hold the top digit decoded, and it does not collapse to
2031
// a JAPLEAF until the population is low enough.
1968
// a LEAFW until the population is low enough.
2032
1969
//
2033
1970
// TBD: Should we add a topdigit field to JPMs so they can hold narrow
2034
1971
// pointers?
2035
1972
2036
if ((Pjpm->jpm_Pop0 + 1) > cJU_JAPLEAF_MAXPOP1) // see above.
2037
{
2038
if (__JudyDelWalk(Pjp, Index, cJU_ROOTSTATE, Pjpm) == -1)
2039
{
2040
JU_COPY_ERRNO(PJError, Pjpm);
2041
return(JERRI);
2042
}
2043
2044
--(Pjpm->jpm_Pop0); // success; decrement total population.
2045
DBGCODE(JudyCheckPop(*PPArray);)
2046
return(1);
2047
}
2048
2049
2050
// COMPRESS A BRANCH[LBU] TO A JAPLEAF:
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:
2051
1988
//
2052
// Then start over to delete the Index from the new leaf. In other words,
2053
// "compress and then delete."
2054
2055
assert((Pjpm->jpm_Pop0) + 1 == cJU_JAPLEAF_MAXPOP1);
2056
2057
Pjlwnew = __JudyAllocJLW(cJU_JAPLEAF_MAXPOP1);
2058
JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI);
1989
Pjlwnew = j__udyAllocJLW(cJU_LEAFW_MAXPOP1);
1990
JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI);
2059
1991
2060
1992
// Plug leaf into root pointer and set population count:
2061
1993
2062
*PPArray = (Pvoid_t) ((Word_t) Pjlwnew | cJU_JAPLEAF);
1994
//// *PPArray = (Pvoid_t) ((Word_t) Pjlwnew | cJU_LEAFW);
1995
*PPArray = (Pvoid_t) Pjlwnew;
2063
1996
#ifdef JUDYL // prepare value area:
2064
Pjv = JL_LEAFWVALUEAREA(Pjlwnew, cJU_JAPLEAF_MAXPOP1);
1997
Pjv = JL_LEAFWVALUEAREA(Pjlwnew, cJU_LEAFW_MAXPOP1);
2065
1998
#endif
2066
*Pjlwnew++ = cJU_JAPLEAF_MAXPOP1 - 1; // set pop0.
2067
DBGCODE(Pjlwnew_orig = Pjlwnew;)
2068
2069
switch (Pjp->jp_Type)
2070
{
2071
2072
2073
// JPBRANCH_L: Copy each JP's indexes to the new JAPLEAF and free the old
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
2074
2006
// branch:
2075
2007
2076
case cJU_JPBRANCH_L:
2077
{
2078
Pjbl_t PjblRaw = (Pjbl_t) (Pjp->jp_Addr);
2079
Pjbl_t Pjbl = P_JBL(PjblRaw);
2080
2081
for (offset = 0; offset < Pjbl->jbl_NumJPs; ++offset)
2082
{
2083
pop1 = __JudyLeafM1ToLeafW(Pjlwnew, JU_PVALUEPASS
2084
(Pjbl->jbl_jp) + offset,
2085
JU_DIGITTOSTATE(Pjbl->jbl_Expanse[offset],
2086
cJU_BYTESPERWORD),
2087
(Pvoid_t) Pjpm);
2088
Pjlwnew += pop1; // advance through indexes.
2089
JUDYLCODE(Pjv += pop1;) // advance through values.
2090
}
2091
__JudyFreeJBL(PjblRaw, Pjpm);
2092
2093
assert(Pjlwnew == Pjlwnew_orig + cJU_JAPLEAF_MAXPOP1);
2094
break; // delete Index from new JAPLEAF.
2095
}
2096
2097
2098
// JPBRANCH_B: Copy each JP's indexes to the new JAPLEAF and free the old
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
2099
2030
// branch, including each JP subarray:
2100
2031
2101
case cJU_JPBRANCH_B:
2102
{
2103
Pjbb_t PjbbRaw = (Pjbb_t) (Pjp->jp_Addr);
2104
Pjbb_t Pjbb = P_JBB(PjbbRaw);
2105
Word_t subexp; // current subexpanse number.
2106
BITMAPB_t bitmap; // portion for this subexpanse.
2107
Pjp_t Pjp2Raw; // one subexpanse's subarray.
2108
Pjp_t Pjp2;
2109
2110
for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
2111
{
2112
if ((bitmap = JU_JBB_BITMAP(Pjbb, subexp)) == 0)
2113
continue; // skip empty subexpanse.
2114
2115
digit = subexp * cJU_BITSPERSUBEXPB;
2116
Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);
2117
Pjp2 = P_JP(Pjp2Raw);
2118
assert(Pjp2 != (Pjp_t) NULL);
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);
2119
2050
2120
2051
// Walk through bits for all possible sub-subexpanses (digits); increment
2121
2052
// offset for each populated subexpanse; until no more set bits:
2122
2053
2123
for (offset = 0; bitmap != 0; bitmap >>= 1, ++digit)
2124
{
2125
if (! (bitmap & 1)) // skip empty sub-subexpanse.
2126
continue;
2127
2128
pop1 = __JudyLeafM1ToLeafW(Pjlwnew, JU_PVALUEPASS
2129
Pjp2 + offset,
2130
JU_DIGITTOSTATE(digit, cJU_BYTESPERWORD),
2131
(Pvoid_t) Pjpm);
2132
Pjlwnew += pop1; // advance through indexes.
2133
JUDYLCODE(Pjv += pop1;) // advance through values.
2134
++offset;
2135
}
2136
__JudyFreeJBBJP(Pjp2Raw, /* pop1 = */ offset, Pjpm);
2137
}
2138
__JudyFreeJBB(PjbbRaw, Pjpm);
2139
2140
assert(Pjlwnew == Pjlwnew_orig + cJU_JAPLEAF_MAXPOP1);
2141
break; // delete Index from new JAPLEAF.
2142
2143
} // case cJU_JPBRANCH_B.
2144
2145
2146
// JPBRANCH_U: Copy each JP's indexes to the new JAPLEAF and free the old
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
2147
2078
// branch:
2148
2079
2149
case cJU_JPBRANCH_U:
2150
{
2151
Pjbu_t PjbuRaw = (Pjbu_t) (Pjp->jp_Addr);
2152
Pjbu_t Pjbu = P_JBU(PjbuRaw);
2153
Word_t ldigit; // larger than uint8_t.
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.
2154
2085
2155
for (Pjp = Pjbu->jbu_jp, ldigit = 0;
2156
ldigit < cJU_BRANCHUNUMJPS;
2157
++Pjp, ++ldigit)
2158
{
2086
for (Pjp = Pjbu->jbu_jp, ldigit = 0;
2087
ldigit < cJU_BRANCHUNUMJPS;
2088
++Pjp, ++ldigit)
2089
{
2159
2090
2160
2091
// Shortcuts, to save a little time for possibly big branches:
2161
2092
2162
if ((Pjp->jp_Type) == cJU_JPNULLMAX) // skip null JP.
2163
continue;
2093
if ((JU_JPTYPE(Pjp)) == cJU_JPNULLMAX) // skip null JP.
2094
continue;
2164
2095
2165
2096
// TBD: Should the following shortcut also be used in BranchL and BranchB
2166
2097
// code?
2167
2098
2168
2099
#ifndef JU_64BIT
2169
if ((Pjp->jp_Type) == cJU_JPIMMED_3_01)
2100
if ((JU_JPTYPE(Pjp)) == cJU_JPIMMED_3_01)
2170
2101
#else
2171
if ((Pjp->jp_Type) == cJU_JPIMMED_7_01)
2102
if ((JU_JPTYPE(Pjp)) == cJU_JPIMMED_7_01)
2172
2103
#endif
2173
{ // single Immed:
2174
*Pjlwnew++ = JU_DIGITTOSTATE(ldigit, cJU_BYTESPERWORD)
2175
| (Pjp->jp_DcdPop0); // rebuild Index.
2104
{ // single Immed:
2105
*Pjlwnew++ = JU_DIGITTOSTATE(ldigit, cJU_BYTESPERWORD)
2106
| JU_JPDCDPOP0(Pjp); // rebuild Index.
2176
2107
#ifdef JUDYL
2177
*Pjv++ = Pjp->jp_Addr; // copy value area.
2108
*Pjv++ = Pjp->jp_Addr; // copy value area.
2178
2109
#endif
2179
continue;
2180
}
2181
2182
pop1 = __JudyLeafM1ToLeafW(Pjlwnew, JU_PVALUEPASS
2183
Pjp, JU_DIGITTOSTATE(ldigit, cJU_BYTESPERWORD),
2184
(Pvoid_t) Pjpm);
2185
Pjlwnew += pop1; // advance through indexes.
2186
JUDYLCODE(Pjv += pop1;) // advance through values.
2187
}
2188
__JudyFreeJBU(PjbuRaw, Pjpm);
2189
2190
assert(Pjlwnew == Pjlwnew_orig + cJU_JAPLEAF_MAXPOP1);
2191
break; // delete Index from new JAPLEAF.
2192
2193
} // case cJU_JPBRANCH_U.
2194
2195
2196
// INVALID JP TYPE UNDER A JAPBRANCH:
2197
2198
default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
2199
return(JERRI);
2200
2201
} // end switch on sub-JP type.
2202
2203
DBGCODE(JudyCheckSorted((Pjll_t) Pjlwnew_orig, cJU_JAPLEAF_MAXPOP1,
2204
cJU_ROOTSTATE);)
2205
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);)
2206
2136
2207
2137
// FREE JPM (no longer needed):
2208
2138
2209
__JudyFreeJPM(Pjpm, (Pjpm_t) NULL);
2210
DBGCODE(JudyCheckPop(*PPArray);)
2211
goto ContinueDel; // delete Index from new leaf.
2212
2213
} // end case cJU_JAPBRANCH.
2214
2215
2216
// INVALID ROOT (JAP) POINTER:
2217
2218
default:
2219
JUDY1CODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDY1);)
2220
JUDYLCODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDYL);)
2221
return(JERRI);
2222
2223
} // switch on JP type.
2224
2225
/*NOTREACHED*/
2139
j__udyFreeJPM(Pjpm, (Pjpm_t) NULL);
2140
DBGCODE(JudyCheckPop(*PPArray);)
2141
return(1);
2142
2143
}
2144
/*NOTREACHED*/
2226
2145
2227
2146
} // Judy1Unset() / JudyLDel()
Loggerhead is a web-based interface for Breezy
Version: 2.0.1