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