« back to all changes in this revision
Viewing changes to src/JudyCommon/JudyGet.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/JudyGet.c
20
20
// Judy1Test() and JudyLGet() functions for Judy1 and JudyL.
21
21
// Compile with one of -DJUDY1 or -DJUDYL.
22
22
23
#if (! (JUDY1 || JUDYL))
24
Error: One of -DJUDY1 or -DJUDYL must be specified.
23
#if (! (defined(JUDY1) || defined(JUDYL)))
24
#error: One of -DJUDY1 or -DJUDYL must be specified.
25
25
#endif
26
26
27
27
#ifdef JUDY1
32
32
33
33
#include "JudyPrivate1L.h"
34
34
35
#ifdef TRACEJPR // different macro name, for "retrieval" only.
35
#ifdef TRACEJPR // different macro name, for "retrieval" only.
36
36
#include "JudyPrintJP.c"
37
37
#endif
38
38
47
47
#ifdef JUDY1
48
48
49
49
#ifdef JUDYGETINLINE
50
FUNCTION int __Judy1Test(
50
FUNCTION int j__udy1Test
51
51
#else
52
FUNCTION int Judy1Test(
52
FUNCTION int Judy1Test
53
53
#endif
54
54
55
55
#else // JUDYL
56
56
57
57
#ifdef JUDYGETINLINE
58
FUNCTION PPvoid_t __JudyLGet(
58
FUNCTION PPvoid_t j__udyLGet
59
59
#else
60
FUNCTION PPvoid_t JudyLGet(
60
FUNCTION PPvoid_t JudyLGet
61
61
#endif
62
62
63
63
#endif // JUDYL
64
64
(
65
65
#ifdef JUDYGETINLINE
66
Pvoid_t Pjpmvoid, // Pjpm in array with pop1 > 31.
67
Word_t Index) // to retrieve.
66
Pvoid_t PArray, // from which to retrieve.
67
Word_t Index // to retrieve.
68
68
#else
69
Pcvoid_t PArray, // from which to retrieve.
70
Word_t Index, // to retrieve.
71
PJError_t PJError) // optional, for returning error info.
69
Pcvoid_t PArray, // from which to retrieve.
70
Word_t Index, // to retrieve.
71
PJError_t PJError // optional, for returning error info.
72
72
#endif
73
)
73
74
{
74
Pjp_t Pjp; // current JP while walking the tree.
75
Pjpm_t Pjpm; // for global accounting.
75
Pjp_t Pjp; // current JP while walking the tree.
76
Pjpm_t Pjpm; // for global accounting.
77
uint8_t Digit; // byte just decoded from Index.
78
Word_t Pop1; // leaf population (number of indexes).
79
Pjll_t Pjll; // pointer to LeafL.
80
DBGCODE(uint8_t ParentJPType;)
81
76
82
#ifndef JUDYGETINLINE
77
uint8_t JAPtype; // type of JAP (root pointer).
78
#endif
79
uint8_t Digit; // byte just decoded from Index.
80
Word_t Pop1; // leaf population (number of indexes).
81
Pjll_t Pjll; // pointer to LeafL.
82
DBGCODE(uint8_t ParentJPType;)
83
84
#ifdef JUDYGETINLINE
85
86
Pjpm = (Pjpm_t) Pjpmvoid; // cc optimizes this out.
87
Pjp = &(Pjpm->jpm_JP); // JP to first node (always a branch).
88
89
// Most frequent subcase is a BranchU below the JPM; otherwise it must be a
90
// BranchB or BranchL:
91
92
if (Pjp->jp_Type == cJU_JPBRANCH_U) goto JudyBranchU;
93
goto ContinueWalk;
94
95
#else // ! JUDYGETINLINE
96
83
84
if (PArray == (Pcvoid_t) NULL) // empty array.
85
{
86
JUDY1CODE(return(0);)
87
JUDYLCODE(return((PPvoid_t) NULL);)
88
}
97
89
98
90
// ****************************************************************************
99
// PROCESS TOP LEVEL "JAP" BRANCHES AND LEAVES:
100
101
JAPtype = JAPTYPE(PArray);
102
103
// Use "if" statements instead of a switch to "force" the order of the "switch"
104
// so the frequent cases are faster:
105
//
106
// Most common case first:
107
108
if (JAPtype == cJU_JAPBRANCH)
109
{
110
Pjpm = P_JPM(PArray);
111
Pjp = &(Pjpm->jpm_JP); // top branch is below JPM.
112
113
// Most frequent subcase is a BranchU below the JPM; otherwise it must be a
114
// BranchB or BranchL:
115
116
if (Pjp->jp_Type == cJU_JPBRANCH_U) goto JudyBranchU;
117
goto ContinueWalk;
118
}
119
120
#if (LOW_POP && JUDYL)
121
else if (JAPtype == cJL_JAPLEAF_POPU1)
122
{
123
Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
124
125
if (Index == Pjlw[0]) return((PPvoid_t) (Pjlw + 1 + 0));
126
return((PPvoid_t) NULL);
127
}
128
else if (JAPtype == cJL_JAPLEAF_POPU2)
129
{
130
if (Pjlw[0] == Index) return((PPvoid_t) (Pjlw + 2 + 0));
131
if (Pjlw[1] == Index) return((PPvoid_t) (Pjlw + 2 + 1));
132
return((PPvoid_t) NULL);
133
}
134
#endif // (LOW_POP && JUDYL)
135
136
else if (JAPtype == cJU_JAPLEAF)
137
{
138
Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
139
int posidx; // signed offset in leaf.
140
141
Pop1 = Pjlw[0] + 1;
142
posidx = __JudySearchLeafW(Pjlw + 1, Pop1, Index);
143
144
if (posidx >= 0)
145
{
91
// PROCESS TOP LEVEL BRANCHES AND LEAF:
92
93
if (JU_LEAFW_POP0(PArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
94
{
95
Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
96
int posidx; // signed offset in leaf.
97
98
Pop1 = Pjlw[0] + 1;
99
posidx = j__udySearchLeafW(Pjlw + 1, Pop1, Index);
100
101
if (posidx >= 0)
102
{
146
103
JUDY1CODE(return(1);)
147
104
JUDYLCODE(return((PPvoid_t) (JL_LEAFWVALUEAREA(Pjlw, Pop1) + posidx));)
148
}
149
150
JUDY1CODE(return(0);)
151
JUDYLCODE(return((PPvoid_t) NULL);)
152
}
153
else if (PArray == (Pcvoid_t) NULL) // empty array.
154
{
155
JUDY1CODE(return(0);)
156
JUDYLCODE(return((PPvoid_t) NULL);)
157
}
158
159
// Any other case is an invalid root pointer (including cJU_JAPNULL with
160
// non-null address part):
161
//
162
// Note: Here, and in other places, do not fold these macros into a generic
163
// JU_ERRNO_NOTJUDY, because the following is more explicit, AND yields a
164
// different je_ErrID (line number) for each case.
165
166
JUDY1CODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDY1); return(JERRI );)
167
JUDYLCODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDYL); return(PPJERR);)
105
}
106
JUDY1CODE(return(0);)
107
JUDYLCODE(return((PPvoid_t) NULL);)
108
}
168
109
169
110
#endif // ! JUDYGETINLINE
170
111
112
Pjpm = P_JPM(PArray);
113
Pjp = &(Pjpm->jpm_JP); // top branch is below JPM.
171
114
172
115
// ****************************************************************************
173
116
// WALK THE JUDY TREE USING A STATE MACHINE:
174
117
175
ContinueWalk: // for going down one level; come here with Pjp set.
118
ContinueWalk: // for going down one level; come here with Pjp set.
176
119
177
120
#ifdef TRACEJPR
178
JudyPrintJP(Pjp, "g", __LINE__);
121
JudyPrintJP(Pjp, "g", __LINE__);
179
122
#endif
180
switch (Pjp->jp_Type)
181
{
123
switch (JU_JPTYPE(Pjp))
124
{
182
125
183
126
// Ensure the switch table starts at 0 for speed; otherwise more code is
184
127
// executed:
185
128
186
case 0: goto ReturnCorrupt; // save a little code.
129
case 0: goto ReturnCorrupt; // save a little code.
187
130
188
131
189
132
// ****************************************************************************
192
135
// Note: These are legitimate in a BranchU (only) and do not constitute a
193
136
// fault.
194
137
195
case cJU_JPNULL1:
196
case cJU_JPNULL2:
197
case cJU_JPNULL3:
138
case cJU_JPNULL1:
139
case cJU_JPNULL2:
140
case cJU_JPNULL3:
198
141
#ifdef JU_64BIT
199
case cJU_JPNULL4:
200
case cJU_JPNULL5:
201
case cJU_JPNULL6:
202
case cJU_JPNULL7:
142
case cJU_JPNULL4:
143
case cJU_JPNULL5:
144
case cJU_JPNULL6:
145
case cJU_JPNULL7:
203
146
#endif
204
assert(ParentJPType >= cJU_JPBRANCH_U2);
205
assert(ParentJPType <= cJU_JPBRANCH_U);
147
assert(ParentJPType >= cJU_JPBRANCH_U2);
148
assert(ParentJPType <= cJU_JPBRANCH_U);
206
149
JUDY1CODE(return(0);)
207
150
JUDYLCODE(return((PPvoid_t) NULL);)
208
151
214
157
// required,since this can be done at leaf level, but it costs nothing to do it
215
158
// sooner, and it aborts an unnecessary traversal sooner.
216
159
217
case cJU_JPBRANCH_L2:
218
219
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 2)) break;
220
Digit = JU_DIGITATSTATE(Index, 2);
221
goto JudyBranchL;
222
223
case cJU_JPBRANCH_L3:
224
225
#ifdef JU_64BIT // otherwise it's a no-op:
226
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 3)) break;
160
case cJU_JPBRANCH_L2:
161
162
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 2)) break;
163
Digit = JU_DIGITATSTATE(Index, 2);
164
goto JudyBranchL;
165
166
case cJU_JPBRANCH_L3:
167
168
#ifdef JU_64BIT // otherwise its a no-op:
169
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
227
170
#endif
228
Digit = JU_DIGITATSTATE(Index, 3);
229
goto JudyBranchL;
171
Digit = JU_DIGITATSTATE(Index, 3);
172
goto JudyBranchL;
230
173
231
174
#ifdef JU_64BIT
232
case cJU_JPBRANCH_L4:
233
234
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 4)) break;
235
Digit = JU_DIGITATSTATE(Index, 4);
236
goto JudyBranchL;
237
238
case cJU_JPBRANCH_L5:
239
240
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 5)) break;
241
Digit = JU_DIGITATSTATE(Index, 5);
242
goto JudyBranchL;
243
244
case cJU_JPBRANCH_L6:
245
246
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 6)) break;
247
Digit = JU_DIGITATSTATE(Index, 6);
248
goto JudyBranchL;
249
250
case cJU_JPBRANCH_L7:
251
252
// JU_DCDNOTMATCHINDEX() would be a no-op.
253
Digit = JU_DIGITATSTATE(Index, 7);
254
goto JudyBranchL;
175
case cJU_JPBRANCH_L4:
176
177
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 4)) break;
178
Digit = JU_DIGITATSTATE(Index, 4);
179
goto JudyBranchL;
180
181
case cJU_JPBRANCH_L5:
182
183
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 5)) break;
184
Digit = JU_DIGITATSTATE(Index, 5);
185
goto JudyBranchL;
186
187
case cJU_JPBRANCH_L6:
188
189
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 6)) break;
190
Digit = JU_DIGITATSTATE(Index, 6);
191
goto JudyBranchL;
192
193
case cJU_JPBRANCH_L7:
194
195
// JU_DCDNOTMATCHINDEX() would be a no-op.
196
Digit = JU_DIGITATSTATE(Index, 7);
197
goto JudyBranchL;
255
198
256
199
#endif // JU_64BIT
257
200
258
case cJU_JPBRANCH_L:
259
{
260
Pjbl_t Pjbl;
261
int posidx;
262
263
Digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
264
265
// Common code for all BranchL's; come here with Digit set:
201
case cJU_JPBRANCH_L:
202
{
203
Pjbl_t Pjbl;
204
int posidx;
205
206
Digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
207
208
// Common code for all BranchLs; come here with Digit set:
266
209
267
210
JudyBranchL:
268
Pjbl = P_JBL(Pjp->jp_Addr);
269
270
posidx = 0;
271
272
do {
273
if (Pjbl->jbl_Expanse[posidx] == Digit)
274
{ // found Digit; continue traversal:
275
DBGCODE(ParentJPType = Pjp->jp_Type;)
276
Pjp = (Pjbl->jbl_jp) + posidx;
277
goto ContinueWalk;
278
}
279
} while (++posidx != Pjbl->jbl_NumJPs);
280
281
break;
282
}
211
Pjbl = P_JBL(Pjp->jp_Addr);
212
213
posidx = 0;
214
215
do {
216
if (Pjbl->jbl_Expanse[posidx] == Digit)
217
{ // found Digit; continue traversal:
218
DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
219
Pjp = Pjbl->jbl_jp + posidx;
220
goto ContinueWalk;
221
}
222
} while (++posidx != Pjbl->jbl_NumJPs);
223
224
break;
225
}
283
226
284
227
285
228
// ****************************************************************************
286
229
// JPBRANCH_B*:
287
230
288
case cJU_JPBRANCH_B2:
289
290
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 2)) break;
291
Digit = JU_DIGITATSTATE(Index, 2);
292
goto JudyBranchB;
293
294
case cJU_JPBRANCH_B3:
295
296
#ifdef JU_64BIT // otherwise it's a no-op:
297
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 3)) break;
231
case cJU_JPBRANCH_B2:
232
233
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 2)) break;
234
Digit = JU_DIGITATSTATE(Index, 2);
235
goto JudyBranchB;
236
237
case cJU_JPBRANCH_B3:
238
239
#ifdef JU_64BIT // otherwise its a no-op:
240
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
298
241
#endif
299
Digit = JU_DIGITATSTATE(Index, 3);
300
goto JudyBranchB;
242
Digit = JU_DIGITATSTATE(Index, 3);
243
goto JudyBranchB;
301
244
302
245
303
246
#ifdef JU_64BIT
304
case cJU_JPBRANCH_B4:
305
306
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 4)) break;
307
Digit = JU_DIGITATSTATE(Index, 4);
308
goto JudyBranchB;
309
310
case cJU_JPBRANCH_B5:
311
312
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 5)) break;
313
Digit = JU_DIGITATSTATE(Index, 5);
314
goto JudyBranchB;
315
316
case cJU_JPBRANCH_B6:
317
318
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 6)) break;
319
Digit = JU_DIGITATSTATE(Index, 6);
320
goto JudyBranchB;
321
322
case cJU_JPBRANCH_B7:
323
324
// JU_DCDNOTMATCHINDEX() would be a no-op.
325
Digit = JU_DIGITATSTATE(Index, 7);
326
goto JudyBranchB;
247
case cJU_JPBRANCH_B4:
248
249
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 4)) break;
250
Digit = JU_DIGITATSTATE(Index, 4);
251
goto JudyBranchB;
252
253
case cJU_JPBRANCH_B5:
254
255
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 5)) break;
256
Digit = JU_DIGITATSTATE(Index, 5);
257
goto JudyBranchB;
258
259
case cJU_JPBRANCH_B6:
260
261
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 6)) break;
262
Digit = JU_DIGITATSTATE(Index, 6);
263
goto JudyBranchB;
264
265
case cJU_JPBRANCH_B7:
266
267
// JU_DCDNOTMATCHINDEX() would be a no-op.
268
Digit = JU_DIGITATSTATE(Index, 7);
269
goto JudyBranchB;
327
270
328
271
#endif // JU_64BIT
329
272
330
case cJU_JPBRANCH_B:
331
{
332
Pjbb_t Pjbb;
333
Word_t subexp; // in bitmap, 0..7.
334
BITMAPB_t BitMap; // for one subexpanse.
335
BITMAPB_t BitMask; // bit in BitMap for Index's Digit.
336
337
Digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
338
339
// Common code for all BranchB's; come here with Digit set:
273
case cJU_JPBRANCH_B:
274
{
275
Pjbb_t Pjbb;
276
Word_t subexp; // in bitmap, 0..7.
277
BITMAPB_t BitMap; // for one subexpanse.
278
BITMAPB_t BitMask; // bit in BitMap for Indexs Digit.
279
280
Digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);
281
282
// Common code for all BranchBs; come here with Digit set:
340
283
341
284
JudyBranchB:
342
DBGCODE(ParentJPType = Pjp->jp_Type;)
343
Pjbb = P_JBB(Pjp->jp_Addr);
344
subexp = Digit / cJU_BITSPERSUBEXPB;
345
346
BitMap = JU_JBB_BITMAP(Pjbb, subexp);
347
Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp));
348
349
BitMask = JU_BITPOSMASKB(Digit);
285
DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
286
Pjbb = P_JBB(Pjp->jp_Addr);
287
subexp = Digit / cJU_BITSPERSUBEXPB;
288
289
BitMap = JU_JBB_BITMAP(Pjbb, subexp);
290
Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp));
291
292
BitMask = JU_BITPOSMASKB(Digit);
350
293
351
294
// No JP in subexpanse for Index => Index not found:
352
295
353
if (! (BitMap & BitMask)) break;
296
if (! (BitMap & BitMask)) break;
354
297
355
298
// Count JPs in the subexpanse below the one for Index:
356
299
357
Pjp += __JudyCountBitsB(BitMap & (BitMask - 1));
358
359
goto ContinueWalk;
360
361
} // case cJU_JPBRANCH_B*
300
Pjp += j__udyCountBitsB(BitMap & (BitMask - 1));
301
302
goto ContinueWalk;
303
304
} // case cJU_JPBRANCH_B*
362
305
363
306
364
307
// ****************************************************************************
367
310
// Notice the reverse order of the cases, and falling through to the next case,
368
311
// for performance.
369
312
370
#ifdef notdef // unused, arrive here via shortcut goto:
371
case cJU_JPBRANCH_U:
372
#endif
373
374
JudyBranchU: // come here on entry to the state machine, with Pjp set.
375
376
DBGCODE(ParentJPType = Pjp->jp_Type;)
377
Pjp = JU_JBU_PJP(Pjp, Index, cJU_ROOTSTATE);
313
case cJU_JPBRANCH_U:
314
315
DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
316
Pjp = JU_JBU_PJP(Pjp, Index, cJU_ROOTSTATE);
378
317
379
318
// If not a BranchU, traverse; otherwise fall into the next case, which makes
380
// this very fast code for a large Judy array (mainly BranchU's), especially
319
// this very fast code for a large Judy array (mainly BranchUs), especially
381
320
// when branches are already in the cache, such as for prev/next:
382
321
383
322
#ifndef JU_64BIT
384
if (Pjp->jp_Type != cJU_JPBRANCH_U3) goto ContinueWalk;
323
if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U3) goto ContinueWalk;
385
324
#else
386
if (Pjp->jp_Type != cJU_JPBRANCH_U7) goto ContinueWalk;
325
if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U7) goto ContinueWalk;
387
326
#endif
388
327
389
328
#ifdef JU_64BIT
390
case cJU_JPBRANCH_U7:
391
392
// JU_DCDNOTMATCHINDEX() would be a no-op.
393
DBGCODE(ParentJPType = Pjp->jp_Type;)
394
Pjp = JU_JBU_PJP(Pjp, Index, 7);
395
396
if (Pjp->jp_Type != cJU_JPBRANCH_U6) goto ContinueWalk;
397
// and fall through.
398
399
case cJU_JPBRANCH_U6:
400
401
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 6)) break;
402
DBGCODE(ParentJPType = Pjp->jp_Type;)
403
Pjp = JU_JBU_PJP(Pjp, Index, 6);
404
405
if (Pjp->jp_Type != cJU_JPBRANCH_U5) goto ContinueWalk;
406
// and fall through.
407
408
case cJU_JPBRANCH_U5:
409
410
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 5)) break;
411
DBGCODE(ParentJPType = Pjp->jp_Type;)
412
Pjp = JU_JBU_PJP(Pjp, Index, 5);
413
414
if (Pjp->jp_Type != cJU_JPBRANCH_U4) goto ContinueWalk;
415
// and fall through.
416
417
case cJU_JPBRANCH_U4:
418
419
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 4)) break;
420
DBGCODE(ParentJPType = Pjp->jp_Type;)
421
Pjp = JU_JBU_PJP(Pjp, Index, 4);
422
423
if (Pjp->jp_Type != cJU_JPBRANCH_U3) goto ContinueWalk;
424
// and fall through.
329
case cJU_JPBRANCH_U7:
330
331
// JU_DCDNOTMATCHINDEX() would be a no-op.
332
DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
333
Pjp = JU_JBU_PJP(Pjp, Index, 7);
334
335
if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U6) goto ContinueWalk;
336
// and fall through.
337
338
case cJU_JPBRANCH_U6:
339
340
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 6)) break;
341
DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
342
Pjp = JU_JBU_PJP(Pjp, Index, 6);
343
344
if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U5) goto ContinueWalk;
345
// and fall through.
346
347
case cJU_JPBRANCH_U5:
348
349
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 5)) break;
350
DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
351
Pjp = JU_JBU_PJP(Pjp, Index, 5);
352
353
if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U4) goto ContinueWalk;
354
// and fall through.
355
356
case cJU_JPBRANCH_U4:
357
358
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 4)) break;
359
DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
360
Pjp = JU_JBU_PJP(Pjp, Index, 4);
361
362
if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U3) goto ContinueWalk;
363
// and fall through.
425
364
426
365
#endif // JU_64BIT
427
366
428
case cJU_JPBRANCH_U3:
367
case cJU_JPBRANCH_U3:
429
368
430
#ifdef JU_64BIT // otherwise it's a no-op:
431
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 3)) break;
369
#ifdef JU_64BIT // otherwise its a no-op:
370
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
432
371
#endif
433
DBGCODE(ParentJPType = Pjp->jp_Type;)
434
Pjp = JU_JBU_PJP(Pjp, Index, 3);
435
436
if (Pjp->jp_Type != cJU_JPBRANCH_U2) goto ContinueWalk;
437
// and fall through.
438
439
case cJU_JPBRANCH_U2:
440
441
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 2)) break;
442
DBGCODE(ParentJPType = Pjp->jp_Type;)
443
Pjp = JU_JBU_PJP(Pjp, Index, 2);
372
DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
373
Pjp = JU_JBU_PJP(Pjp, Index, 3);
374
375
if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U2) goto ContinueWalk;
376
// and fall through.
377
378
case cJU_JPBRANCH_U2:
379
380
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 2)) break;
381
DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
382
Pjp = JU_JBU_PJP(Pjp, Index, 2);
444
383
445
384
// Note: BranchU2 is a special case that must continue traversal to a leaf,
446
385
// immed, full, or null type:
447
386
448
goto ContinueWalk;
387
goto ContinueWalk;
449
388
450
389
451
390
// ****************************************************************************
454
393
// Note: Here the calls of JU_DCDNOTMATCHINDEX() are necessary and check
455
394
// whether Index is out of the expanse of a narrow pointer.
456
395
457
#if (JUDYL || (! JU_64BIT))
458
459
case cJU_JPLEAF1:
460
{
461
int posidx; // signed offset in leaf.
462
463
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 1)) break;
464
465
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
466
Pjll = P_JLL(Pjp->jp_Addr);
467
468
if ((posidx = __JudySearchLeaf1(Pjll, Pop1, Index)) < 0) break;
396
#if (defined(JUDYL) || (! defined(JU_64BIT)))
397
398
case cJU_JPLEAF1:
399
{
400
int posidx; // signed offset in leaf.
401
402
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 1)) break;
403
404
Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
405
Pjll = P_JLL(Pjp->jp_Addr);
406
407
if ((posidx = j__udySearchLeaf1(Pjll, Pop1, Index)) < 0) break;
469
408
470
409
JUDY1CODE(return(1);)
471
410
JUDYLCODE(return((PPvoid_t) (JL_LEAF1VALUEAREA(Pjll, Pop1) + posidx));)
472
}
411
}
473
412
474
413
#endif // (JUDYL || (! JU_64BIT))
475
414
476
case cJU_JPLEAF2:
477
{
478
int posidx; // signed offset in leaf.
479
480
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 2)) break;
481
482
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
483
Pjll = P_JLL(Pjp->jp_Addr);
484
485
if ((posidx = __JudySearchLeaf2(Pjll, Pop1, Index)) < 0) break;
415
case cJU_JPLEAF2:
416
{
417
int posidx; // signed offset in leaf.
418
419
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 2)) break;
420
421
Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
422
Pjll = P_JLL(Pjp->jp_Addr);
423
424
if ((posidx = j__udySearchLeaf2(Pjll, Pop1, Index)) < 0) break;
486
425
487
426
JUDY1CODE(return(1);)
488
427
JUDYLCODE(return((PPvoid_t) (JL_LEAF2VALUEAREA(Pjll, Pop1) + posidx));)
489
}
490
case cJU_JPLEAF3:
491
{
492
int posidx; // signed offset in leaf.
428
}
429
case cJU_JPLEAF3:
430
{
431
int posidx; // signed offset in leaf.
493
432
494
#ifdef JU_64BIT // otherwise it's a no-op:
495
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 3)) break;
433
#ifdef JU_64BIT // otherwise its a no-op:
434
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
496
435
#endif
497
436
498
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
499
Pjll = P_JLL(Pjp->jp_Addr);
437
Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
438
Pjll = P_JLL(Pjp->jp_Addr);
500
439
501
if ((posidx = __JudySearchLeaf3(Pjll, Pop1, Index)) < 0) break;
440
if ((posidx = j__udySearchLeaf3(Pjll, Pop1, Index)) < 0) break;
502
441
503
442
JUDY1CODE(return(1);)
504
443
JUDYLCODE(return((PPvoid_t) (JL_LEAF3VALUEAREA(Pjll, Pop1) + posidx));)
505
}
444
}
506
445
#ifdef JU_64BIT
507
case cJU_JPLEAF4:
508
{
509
int posidx; // signed offset in leaf.
510
511
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 4)) break;
512
513
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
514
Pjll = P_JLL(Pjp->jp_Addr);
515
516
if ((posidx = __JudySearchLeaf4(Pjll, Pop1, Index)) < 0) break;
446
case cJU_JPLEAF4:
447
{
448
int posidx; // signed offset in leaf.
449
450
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 4)) break;
451
452
Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
453
Pjll = P_JLL(Pjp->jp_Addr);
454
455
if ((posidx = j__udySearchLeaf4(Pjll, Pop1, Index)) < 0) break;
517
456
518
457
JUDY1CODE(return(1);)
519
458
JUDYLCODE(return((PPvoid_t) (JL_LEAF4VALUEAREA(Pjll, Pop1) + posidx));)
520
}
521
case cJU_JPLEAF5:
522
{
523
int posidx; // signed offset in leaf.
524
525
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 5)) break;
526
527
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
528
Pjll = P_JLL(Pjp->jp_Addr);
529
530
if ((posidx = __JudySearchLeaf5(Pjll, Pop1, Index)) < 0) break;
459
}
460
case cJU_JPLEAF5:
461
{
462
int posidx; // signed offset in leaf.
463
464
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 5)) break;
465
466
Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
467
Pjll = P_JLL(Pjp->jp_Addr);
468
469
if ((posidx = j__udySearchLeaf5(Pjll, Pop1, Index)) < 0) break;
531
470
532
471
JUDY1CODE(return(1);)
533
472
JUDYLCODE(return((PPvoid_t) (JL_LEAF5VALUEAREA(Pjll, Pop1) + posidx));)
534
}
535
536
case cJU_JPLEAF6:
537
{
538
int posidx; // signed offset in leaf.
539
540
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 6)) break;
541
542
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
543
Pjll = P_JLL(Pjp->jp_Addr);
544
545
if ((posidx = __JudySearchLeaf6(Pjll, Pop1, Index)) < 0) break;
473
}
474
475
case cJU_JPLEAF6:
476
{
477
int posidx; // signed offset in leaf.
478
479
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 6)) break;
480
481
Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
482
Pjll = P_JLL(Pjp->jp_Addr);
483
484
if ((posidx = j__udySearchLeaf6(Pjll, Pop1, Index)) < 0) break;
546
485
547
486
JUDY1CODE(return(1);)
548
487
JUDYLCODE(return((PPvoid_t) (JL_LEAF6VALUEAREA(Pjll, Pop1) + posidx));)
549
}
550
case cJU_JPLEAF7:
551
{
552
int posidx; // signed offset in leaf.
553
554
// JU_DCDNOTMATCHINDEX() would be a no-op.
555
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
556
Pjll = P_JLL(Pjp->jp_Addr);
557
558
if ((posidx = __JudySearchLeaf7(Pjll, Pop1, Index)) < 0) break;
488
}
489
case cJU_JPLEAF7:
490
{
491
int posidx; // signed offset in leaf.
492
493
// JU_DCDNOTMATCHINDEX() would be a no-op.
494
Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
495
Pjll = P_JLL(Pjp->jp_Addr);
496
497
if ((posidx = j__udySearchLeaf7(Pjll, Pop1, Index)) < 0) break;
559
498
560
499
JUDY1CODE(return(1);)
561
500
JUDYLCODE(return((PPvoid_t) (JL_LEAF7VALUEAREA(Pjll, Pop1) + posidx));)
562
}
501
}
563
502
#endif // JU_64BIT
564
503
565
504
566
505
// ****************************************************************************
567
506
// JPLEAF_B1:
568
507
569
case cJU_JPLEAF_B1:
570
{
571
Pjlb_t Pjlb;
508
case cJU_JPLEAF_B1:
509
{
510
Pjlb_t Pjlb;
572
511
#ifdef JUDYL
573
int posidx;
574
Word_t subexp; // in bitmap, 0..7.
575
BITMAPL_t BitMap; // for one subexpanse.
576
BITMAPL_t BitMask; // bit in BitMap for Index's Digit.
577
Pjv_t Pjv;
512
int posidx;
513
Word_t subexp; // in bitmap, 0..7.
514
BITMAPL_t BitMap; // for one subexpanse.
515
BITMAPL_t BitMask; // bit in BitMap for Indexs Digit.
516
Pjv_t Pjv;
578
517
#endif
579
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 1)) break;
518
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 1)) break;
580
519
581
Pjlb = P_JLB(Pjp->jp_Addr);
520
Pjlb = P_JLB(Pjp->jp_Addr);
582
521
583
522
#ifdef JUDY1
584
523
585
// Simply check if Index's bit is set in the bitmap:
524
// Simply check if Indexs bit is set in the bitmap:
586
525
587
if (JU_BITMAPTESTL(Pjlb, Index)) return(1);
588
break;
526
if (JU_BITMAPTESTL(Pjlb, Index)) return(1);
527
break;
589
528
590
529
#else // JUDYL
591
530
592
531
// JudyL is much more complicated because of value area subarrays:
593
532
594
Digit = JU_DIGITATSTATE(Index, 1);
595
subexp = Digit / cJU_BITSPERSUBEXPL;
596
BitMap = JU_JLB_BITMAP(Pjlb, subexp);
597
BitMask = JU_BITPOSMASKL(Digit);
533
Digit = JU_DIGITATSTATE(Index, 1);
534
subexp = Digit / cJU_BITSPERSUBEXPL;
535
BitMap = JU_JLB_BITMAP(Pjlb, subexp);
536
BitMask = JU_BITPOSMASKL(Digit);
598
537
599
538
// No value in subexpanse for Index => Index not found:
600
539
601
if (! (BitMap & BitMask)) break;
540
if (! (BitMap & BitMask)) break;
602
541
603
542
// Count value areas in the subexpanse below the one for Index:
604
543
605
Pjv = P_JV(JL_JLB_PVALUE(Pjlb, subexp));
606
assert(Pjv != (Pjv_t) NULL);
607
posidx = __JudyCountBitsL(BitMap & (BitMask - 1));
544
Pjv = P_JV(JL_JLB_PVALUE(Pjlb, subexp));
545
assert(Pjv != (Pjv_t) NULL);
546
posidx = j__udyCountBitsL(BitMap & (BitMask - 1));
608
547
609
return((PPvoid_t) (Pjv + posidx));
548
return((PPvoid_t) (Pjv + posidx));
610
549
611
550
#endif // JUDYL
612
551
613
} // case cJU_JPLEAF_B1
552
} // case cJU_JPLEAF_B1
614
553
615
554
#ifdef JUDY1
616
555
619
558
//
620
559
// If the Index is in the expanse, it is necessarily valid (found).
621
560
622
case cJ1_JPFULLPOPU1:
623
624
if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 1)) break;
625
return(1);
561
case cJ1_JPFULLPOPU1:
562
563
if (JU_DCDNOTMATCHINDEX(Index, Pjp, 1)) break;
564
return(1);
565
566
#ifdef notdef // for future enhancements
567
#ifdef JU_64BIT
568
569
// Note: Need ? if (JU_DCDNOTMATCHINDEX(Index, Pjp, 1)) break;
570
571
case cJ1_JPFULLPOPU1m15:
572
if (Pjp->jp_1Index[14] == (uint8_t)Index) break;
573
case cJ1_JPFULLPOPU1m14:
574
if (Pjp->jp_1Index[13] == (uint8_t)Index) break;
575
case cJ1_JPFULLPOPU1m13:
576
if (Pjp->jp_1Index[12] == (uint8_t)Index) break;
577
case cJ1_JPFULLPOPU1m12:
578
if (Pjp->jp_1Index[11] == (uint8_t)Index) break;
579
case cJ1_JPFULLPOPU1m11:
580
if (Pjp->jp_1Index[10] == (uint8_t)Index) break;
581
case cJ1_JPFULLPOPU1m10:
582
if (Pjp->jp_1Index[9] == (uint8_t)Index) break;
583
case cJ1_JPFULLPOPU1m9:
584
if (Pjp->jp_1Index[8] == (uint8_t)Index) break;
585
case cJ1_JPFULLPOPU1m8:
586
if (Pjp->jp_1Index[7] == (uint8_t)Index) break;
587
#endif
588
case cJ1_JPFULLPOPU1m7:
589
if (Pjp->jp_1Index[6] == (uint8_t)Index) break;
590
case cJ1_JPFULLPOPU1m6:
591
if (Pjp->jp_1Index[5] == (uint8_t)Index) break;
592
case cJ1_JPFULLPOPU1m5:
593
if (Pjp->jp_1Index[4] == (uint8_t)Index) break;
594
case cJ1_JPFULLPOPU1m4:
595
if (Pjp->jp_1Index[3] == (uint8_t)Index) break;
596
case cJ1_JPFULLPOPU1m3:
597
if (Pjp->jp_1Index[2] == (uint8_t)Index) break;
598
case cJ1_JPFULLPOPU1m2:
599
if (Pjp->jp_1Index[1] == (uint8_t)Index) break;
600
case cJ1_JPFULLPOPU1m1:
601
if (Pjp->jp_1Index[0] == (uint8_t)Index) break;
602
603
return(1); // found, not in exclusion list
626
604
627
605
#endif // JUDY1
628
629
// Macro used for even (1, 2, 4) sized IMMED_*_02 and up:
630
631
#define SEARCHIMMEDEVEN(LeafType,Pjp,Index,JPType) \
632
{ \
633
LeafType _Index = (Index); /* necessary for masking Index */ \
634
JUDY1CODE(LeafType *_PLeaf = (LeafType *)((Pjp)->jp_1Index);) \
635
JUDYLCODE(LeafType *_PLeaf = (LeafType *)((Pjp)->jp_LIndex);) \
636
/* if beyond end of leaf */ \
637
if ((_Index) > _PLeaf[(Pjp)->jp_Type - (JPType) + 1]) break; \
638
/* find it */ \
639
for(;;) { if (_Index <= *_PLeaf) break; _PLeaf++; } \
640
if ((_Index) == *_PLeaf) /* found ? */ \
641
{ \
642
JUDY1CODE(return(1);) \
643
JUDYLCODE(return((PPvoid_t)(P_JV((Pjp)->jp_Addr) + \
644
(_PLeaf - (LeafType *)((Pjp)->jp_LIndex))));) \
645
} \
646
break; /* exit not found */ \
647
}
648
606
#endif // notdef
649
607
650
608
// ****************************************************************************
651
609
// JPIMMED*:
652
610
//
653
// Note that the contents of jp_DcdPop0 are different for cJU_JPIMMED_*_01:
611
// Note that the contents of jp_DcdPopO are different for cJU_JPIMMED_*_01:
654
612
655
case cJU_JPIMMED_1_01:
656
case cJU_JPIMMED_2_01:
657
case cJU_JPIMMED_3_01:
613
case cJU_JPIMMED_1_01:
614
case cJU_JPIMMED_2_01:
615
case cJU_JPIMMED_3_01:
658
616
#ifdef JU_64BIT
659
case cJU_JPIMMED_4_01:
660
case cJU_JPIMMED_5_01:
661
case cJU_JPIMMED_6_01:
662
case cJU_JPIMMED_7_01:
617
case cJU_JPIMMED_4_01:
618
case cJU_JPIMMED_5_01:
619
case cJU_JPIMMED_6_01:
620
case cJU_JPIMMED_7_01:
663
621
#endif
664
if (Pjp->jp_DcdPop0 != JU_TRIMTODCDSIZE(Index)) break;
622
if (JU_JPDCDPOP0(Pjp) != JU_TRIMTODCDSIZE(Index)) break;
665
623
666
624
JUDY1CODE(return(1);)
667
625
JUDYLCODE(return((PPvoid_t) &(Pjp->jp_Addr));) // immediate value area.
668
626
669
case cJU_JPIMMED_1_02:
670
case cJU_JPIMMED_1_03:
671
#if (JUDY1 || JU_64BIT)
672
case cJU_JPIMMED_1_04:
673
case cJU_JPIMMED_1_05:
674
case cJU_JPIMMED_1_06:
675
case cJU_JPIMMED_1_07:
676
#endif
677
#if (JUDY1 && JU_64BIT)
678
case cJ1_JPIMMED_1_08:
679
case cJ1_JPIMMED_1_09:
680
case cJ1_JPIMMED_1_10:
681
case cJ1_JPIMMED_1_11:
682
case cJ1_JPIMMED_1_12:
683
case cJ1_JPIMMED_1_13:
684
case cJ1_JPIMMED_1_14:
685
case cJ1_JPIMMED_1_15:
686
#endif
687
SEARCHIMMEDEVEN(uint8_t, Pjp, Index, cJU_JPIMMED_1_02);
688
689
#if (JUDY1 || JU_64BIT)
690
case cJU_JPIMMED_2_02:
691
case cJU_JPIMMED_2_03:
692
#endif
693
#if (JUDY1 && JU_64BIT)
694
case cJ1_JPIMMED_2_04:
695
case cJ1_JPIMMED_2_05:
696
case cJ1_JPIMMED_2_06:
697
case cJ1_JPIMMED_2_07:
698
#endif
699
700
#if (JUDY1 || JU_64BIT)
701
SEARCHIMMEDEVEN(uint16_t, Pjp, Index, cJU_JPIMMED_2_02);
702
#endif
703
704
#if (JUDY1 || JU_64BIT)
705
case cJU_JPIMMED_3_02:
706
#endif
707
#if (JUDY1 && JU_64BIT)
708
case cJ1_JPIMMED_3_03:
709
case cJ1_JPIMMED_3_04:
710
case cJ1_JPIMMED_3_05:
711
#endif
712
#if (JUDY1 || JU_64BIT)
713
{
714
int posidx;
627
628
// Macros to make code more readable and avoid dup errors
629
715
630
#ifdef JUDY1
716
Pjll = (Pjll_t)(Pjp->jp_1Index);
717
#else
718
Pjv_t Pjv;
719
Pjll = (Pjll_t) (Pjp->jp_LIndex);
720
Pjv = P_JV(Pjp->jp_Addr);
721
#endif
722
Pop1 = Pjp->jp_Type - cJU_JPIMMED_3_02 + 2;
723
724
if ((posidx = __JudySearchLeaf3(Pjll, Pop1, Index)) < 0) break;
725
726
JUDY1CODE(return(1);)
727
JUDYLCODE(return((PPvoid_t) (Pjv + posidx));)
728
}
729
#endif
730
731
#if (JUDY1 && JU_64BIT)
732
733
case cJ1_JPIMMED_4_02:
734
case cJ1_JPIMMED_4_03:
735
SEARCHIMMEDEVEN(uint32_t, Pjp, Index, cJ1_JPIMMED_4_02);
736
737
case cJ1_JPIMMED_5_02:
738
case cJ1_JPIMMED_5_03:
739
740
Pop1 = Pjp->jp_Type - cJ1_JPIMMED_5_02 + 2;
741
Pjll = (Pjll_t) (Pjp->jp_1Index);
742
743
if (__JudySearchLeaf5(Pjll, Pop1, Index) < 0) break;
744
return(1);
745
746
case cJ1_JPIMMED_6_02:
747
748
Pjll = (Pjll_t) (Pjp->jp_1Index);
749
750
if (__JudySearchLeaf6(Pjll, 2, Index) < 0) break;
751
return(1);
752
753
case cJ1_JPIMMED_7_02:
754
755
Pjll = (Pjll_t) (Pjp->jp_1Index);
756
757
if (__JudySearchLeaf7(Pjll, 2, Index) < 0) break;
758
return(1);
631
632
#define CHECKINDEXNATIVE(LEAF_T, PJP, IDX, INDEX) \
633
if (((LEAF_T *)((PJP)->jp_1Index))[(IDX) - 1] == (LEAF_T)(INDEX)) \
634
return(1)
635
636
#define CHECKLEAFNONNAT(LFBTS, PJP, INDEX, IDX, COPY) \
637
{ \
638
Word_t i_ndex; \
639
uint8_t *a_ddr; \
640
a_ddr = (PJP)->jp_1Index + (((IDX) - 1) * (LFBTS)); \
641
COPY(i_ndex, a_ddr); \
642
if (i_ndex == JU_LEASTBYTES((INDEX), (LFBTS))) \
643
return(1); \
644
}
645
#endif
646
647
#ifdef JUDYL
648
649
#define CHECKINDEXNATIVE(LEAF_T, PJP, IDX, INDEX) \
650
if (((LEAF_T *)((PJP)->jp_LIndex))[(IDX) - 1] == (LEAF_T)(INDEX)) \
651
return((PPvoid_t)(P_JV((PJP)->jp_Addr) + (IDX) - 1))
652
653
#define CHECKLEAFNONNAT(LFBTS, PJP, INDEX, IDX, COPY) \
654
{ \
655
Word_t i_ndex; \
656
uint8_t *a_ddr; \
657
a_ddr = (PJP)->jp_LIndex + (((IDX) - 1) * (LFBTS)); \
658
COPY(i_ndex, a_ddr); \
659
if (i_ndex == JU_LEASTBYTES((INDEX), (LFBTS))) \
660
return((PPvoid_t)(P_JV((PJP)->jp_Addr) + (IDX) - 1)); \
661
}
662
#endif
663
664
#if (defined(JUDY1) && defined(JU_64BIT))
665
case cJ1_JPIMMED_1_15: CHECKINDEXNATIVE(uint8_t, Pjp, 15, Index);
666
case cJ1_JPIMMED_1_14: CHECKINDEXNATIVE(uint8_t, Pjp, 14, Index);
667
case cJ1_JPIMMED_1_13: CHECKINDEXNATIVE(uint8_t, Pjp, 13, Index);
668
case cJ1_JPIMMED_1_12: CHECKINDEXNATIVE(uint8_t, Pjp, 12, Index);
669
case cJ1_JPIMMED_1_11: CHECKINDEXNATIVE(uint8_t, Pjp, 11, Index);
670
case cJ1_JPIMMED_1_10: CHECKINDEXNATIVE(uint8_t, Pjp, 10, Index);
671
case cJ1_JPIMMED_1_09: CHECKINDEXNATIVE(uint8_t, Pjp, 9, Index);
672
case cJ1_JPIMMED_1_08: CHECKINDEXNATIVE(uint8_t, Pjp, 8, Index);
673
#endif
674
#if (defined(JUDY1) || defined(JU_64BIT))
675
case cJU_JPIMMED_1_07: CHECKINDEXNATIVE(uint8_t, Pjp, 7, Index);
676
case cJU_JPIMMED_1_06: CHECKINDEXNATIVE(uint8_t, Pjp, 6, Index);
677
case cJU_JPIMMED_1_05: CHECKINDEXNATIVE(uint8_t, Pjp, 5, Index);
678
case cJU_JPIMMED_1_04: CHECKINDEXNATIVE(uint8_t, Pjp, 4, Index);
679
#endif
680
case cJU_JPIMMED_1_03: CHECKINDEXNATIVE(uint8_t, Pjp, 3, Index);
681
case cJU_JPIMMED_1_02: CHECKINDEXNATIVE(uint8_t, Pjp, 2, Index);
682
CHECKINDEXNATIVE(uint8_t, Pjp, 1, Index);
683
break;
684
685
#if (defined(JUDY1) && defined(JU_64BIT))
686
case cJ1_JPIMMED_2_07: CHECKINDEXNATIVE(uint16_t, Pjp, 7, Index);
687
case cJ1_JPIMMED_2_06: CHECKINDEXNATIVE(uint16_t, Pjp, 6, Index);
688
case cJ1_JPIMMED_2_05: CHECKINDEXNATIVE(uint16_t, Pjp, 5, Index);
689
case cJ1_JPIMMED_2_04: CHECKINDEXNATIVE(uint16_t, Pjp, 4, Index);
690
#endif
691
#if (defined(JUDY1) || defined(JU_64BIT))
692
case cJU_JPIMMED_2_03: CHECKINDEXNATIVE(uint16_t, Pjp, 3, Index);
693
case cJU_JPIMMED_2_02: CHECKINDEXNATIVE(uint16_t, Pjp, 2, Index);
694
CHECKINDEXNATIVE(uint16_t, Pjp, 1, Index);
695
break;
696
#endif
697
698
#if (defined(JUDY1) && defined(JU_64BIT))
699
case cJ1_JPIMMED_3_05:
700
CHECKLEAFNONNAT(3, Pjp, Index, 5, JU_COPY3_PINDEX_TO_LONG);
701
case cJ1_JPIMMED_3_04:
702
CHECKLEAFNONNAT(3, Pjp, Index, 4, JU_COPY3_PINDEX_TO_LONG);
703
case cJ1_JPIMMED_3_03:
704
CHECKLEAFNONNAT(3, Pjp, Index, 3, JU_COPY3_PINDEX_TO_LONG);
705
#endif
706
#if (defined(JUDY1) || defined(JU_64BIT))
707
case cJU_JPIMMED_3_02:
708
CHECKLEAFNONNAT(3, Pjp, Index, 2, JU_COPY3_PINDEX_TO_LONG);
709
CHECKLEAFNONNAT(3, Pjp, Index, 1, JU_COPY3_PINDEX_TO_LONG);
710
break;
711
#endif
712
713
#if (defined(JUDY1) && defined(JU_64BIT))
714
715
case cJ1_JPIMMED_4_03: CHECKINDEXNATIVE(uint32_t, Pjp, 3, Index);
716
case cJ1_JPIMMED_4_02: CHECKINDEXNATIVE(uint32_t, Pjp, 2, Index);
717
CHECKINDEXNATIVE(uint32_t, Pjp, 1, Index);
718
break;
719
720
case cJ1_JPIMMED_5_03:
721
CHECKLEAFNONNAT(5, Pjp, Index, 3, JU_COPY5_PINDEX_TO_LONG);
722
case cJ1_JPIMMED_5_02:
723
CHECKLEAFNONNAT(5, Pjp, Index, 2, JU_COPY5_PINDEX_TO_LONG);
724
CHECKLEAFNONNAT(5, Pjp, Index, 1, JU_COPY5_PINDEX_TO_LONG);
725
break;
726
727
case cJ1_JPIMMED_6_02:
728
CHECKLEAFNONNAT(6, Pjp, Index, 2, JU_COPY6_PINDEX_TO_LONG);
729
CHECKLEAFNONNAT(6, Pjp, Index, 1, JU_COPY6_PINDEX_TO_LONG);
730
break;
731
732
case cJ1_JPIMMED_7_02:
733
CHECKLEAFNONNAT(7, Pjp, Index, 2, JU_COPY7_PINDEX_TO_LONG);
734
CHECKLEAFNONNAT(7, Pjp, Index, 1, JU_COPY7_PINDEX_TO_LONG);
735
break;
759
736
760
737
#endif // (JUDY1 && JU_64BIT)
761
738
763
740
// ****************************************************************************
764
741
// INVALID JP TYPE:
765
742
766
default:
743
default:
767
744
768
745
ReturnCorrupt:
769
746
770
#ifdef JUDYGETINLINE // Pjpm is known to be non-null:
771
JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
747
#ifdef JUDYGETINLINE // Pjpm is known to be non-null:
748
JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
772
749
#else
773
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
750
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
774
751
#endif
775
JUDY1CODE(return(JERRI );)
776
JUDYLCODE(return(PPJERR);)
752
JUDY1CODE(return(JERRI );)
753
JUDYLCODE(return(PPJERR);)
777
754
778
} // switch on JP type
755
} // switch on JP type
779
756
780
757
JUDY1CODE(return(0);)
781
758
JUDYLCODE(return((PPvoid_t) NULL);)
783
760
} // Judy1Test() / JudyLGet()
784
761
785
762
786
#ifndef JUDYGETINLINE // only compile the following function once:
763
#ifndef JUDYGETINLINE // only compile the following function once:
787
764
#ifdef DEBUG
788
765
789
766
// ****************************************************************************
796
773
// function by setting env parameter $CHECKPOP to first call at which to start
797
774
// checking. Note: This function is called both from insert and delete code.
798
775
//
799
// Note: Even though this function does nothing useful for JAP leaves, it's
776
// Note: Even though this function does nothing useful for LEAFW leaves, its
800
777
// good practice to call it anyway, and cheap too.
801
778
//
802
779
// TBD: This is a debug-only check function similar to JudyCheckSorted(), but
804
781
// file that is built both ways.
805
782
//
806
783
// TBD: As feared, enabling this code for every insert/delete makes Judy
807
// deathly slow, even for a small tree (10K indexes). It's not so bad if
808
// present but disabled (<1% slowdown measured). Still, should it be ifdef'd
784
// deathly slow, even for a small tree (10K indexes). Its not so bad if
785
// present but disabled (<1% slowdown measured). Still, should it be ifdefd
809
786
// other than DEBUG and/or called less often?
810
787
//
811
788
// TBD: Should this "population checker" be expanded to a comprehensive tree
812
// checker? It currently detects invalid JAP/JP types as well as inconsistent
813
// pop1's. Other possible checks, all based on essentially redundant data in
789
// checker? It currently detects invalid LEAFW/JP types as well as inconsistent
790
// pop1s. Other possible checks, all based on essentially redundant data in
814
791
// the Judy tree, include:
815
792
//
816
793
// - Zero LS bits in jp_Addr field.
819
796
//
820
797
// - Consistent JP types (always descending down the tree).
821
798
//
822
// - Sorted linear lists in BranchL's and leaves (using JudyCheckSorted(), but
799
// - Sorted linear lists in BranchLs and leaves (using JudyCheckSorted(), but
823
800
// ideally that function is already called wherever appropriate after any
824
801
// linear list is modified).
825
802
//
826
803
// - Any others possible?
827
804
828
#include <stdlib.h> // for getenv() and atol().
805
#include <stdlib.h> // for getenv() and atol().
829
806
830
807
static Word_t JudyCheckPopSM(Pjp_t Pjp, Word_t RootPop1);
831
808
832
809
FUNCTION void JudyCheckPop(
833
Pvoid_t PArray)
810
Pvoid_t PArray)
834
811
{
835
static bool_t checked = FALSE; // already checked env parameter.
836
static bool_t enabled = FALSE; // env parameter set.
837
static bool_t active = FALSE; // calls >= callsmin.
838
static Word_t callsmin; // start point from $CHECKPOP.
839
static Word_t calls = 0; // times called so far.
840
841
Word_t JAPtype; // JAP type part of PArray.
812
static bool_t checked = FALSE; // already checked env parameter.
813
static bool_t enabled = FALSE; // env parameter set.
814
static bool_t active = FALSE; // calls >= callsmin.
815
static Word_t callsmin; // start point from $CHECKPOP.
816
static Word_t calls = 0; // times called so far.
842
817
843
818
844
819
// CHECK FOR EXTERNAL ENABLING:
845
820
846
if (! checked) // only check once.
847
{
848
char * value; // for getenv().
849
850
checked = TRUE;
851
852
if ((value = getenv("CHECKPOP")) == (char *) NULL)
853
{
821
if (! checked) // only check once.
822
{
823
char * value; // for getenv().
824
825
checked = TRUE;
826
827
if ((value = getenv("CHECKPOP")) == (char *) NULL)
828
{
854
829
#ifdef notdef
855
// Take this out because nightly tests want to be flavor-independent; it's not
830
// Take this out because nightly tests want to be flavor-independent; its not
856
831
// OK to emit special non-error output from the debug flavor:
857
832
858
(void) puts("JudyCheckPop() present but not enabled by "
859
"$CHECKPOP env parameter; set it to the number of "
860
"calls at which to begin checking");
833
(void) puts("JudyCheckPop() present but not enabled by "
834
"$CHECKPOP env parameter; set it to the number of "
835
"calls at which to begin checking");
861
836
#endif
862
return;
863
}
864
865
callsmin = atol(value); // note: non-number evaluates to 0.
866
enabled = TRUE;
867
868
(void) printf("JudyCheckPop() present and enabled; callsmin = "
869
"%lu\n", callsmin);
870
}
871
else if (! enabled) return;
837
return;
838
}
839
840
callsmin = atol(value); // note: non-number evaluates to 0.
841
enabled = TRUE;
842
843
(void) printf("JudyCheckPop() present and enabled; callsmin = "
844
"%lu\n", callsmin);
845
}
846
else if (! enabled) return;
872
847
873
848
// Previously or just now enabled; check if non-active or newly active:
874
849
875
if (! active)
876
{
877
if (++calls < callsmin) return;
878
879
(void) printf("JudyCheckPop() activated at call %lu\n", calls);
880
active = TRUE;
881
}
882
883
884
// START AT TOP OF TREE:
885
886
JAPtype = JAPTYPE(PArray);
887
888
switch (JAPtype)
889
{
890
case cJU_JAPNULL:
891
{
892
Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
893
assert(Pjlw == (Pjlw_t) NULL); // rest of word must be null.
894
return; // valid null JAP.
895
}
896
897
#if (LOW_POP && JUDYL)
898
899
// Little or no pop checking is possible for these types, but see function
900
// header comments:
901
902
case cJL_JAPLEAF_POPU1: return;
903
case cJL_JAPLEAF_POPU2: return;
904
#endif
905
906
case cJU_JAPLEAF:
907
{
908
Pjlw_t Pjlw = P_JLW(PArray); // first word of leaf.
909
assert(*Pjlw + 1 <= cJU_JAPLEAF_MAXPOP1);
910
return;
911
}
850
if (! active)
851
{
852
if (++calls < callsmin) return;
853
854
(void) printf("JudyCheckPop() activated at call %lu\n", calls);
855
active = TRUE;
856
}
857
858
// IGNORE LEAFW AT TOP OF TREE:
859
860
if (JU_LEAFW_POP0(PArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW
861
return;
912
862
913
863
// Check JPM pop0 against tree, recursively:
914
864
//
915
865
// Note: The traversal code in JudyCheckPopSM() is simplest when the case
916
866
// statement for each JP type compares the pop1 for that JP to its subtree (if
917
// any) after traversing the subtree (that's the hard part) and adding up
918
// actual pop1's. A top branch's JP in the JPM does not have room for a
867
// any) after traversing the subtree (thats the hard part) and adding up
868
// actual pop1s. A top branchs JP in the JPM does not have room for a
919
869
// full-word pop1, so pass it in as a special case.
920
870
921
case cJU_JAPBRANCH:
922
{
923
Pjpm_t Pjpm = P_JPM(PArray);
924
(void) JudyCheckPopSM(&(Pjpm->jpm_JP), Pjpm->jpm_Pop0 + 1);
925
return;
926
}
927
}
928
929
assert(FALSE); // unrecognized JAP type => corruption.
871
{
872
Pjpm_t Pjpm = P_JPM(PArray);
873
(void) JudyCheckPopSM(&(Pjpm->jpm_JP), Pjpm->jpm_Pop0 + 1);
874
return;
875
}
930
876
931
877
} // JudyCheckPop()
932
878
936
882
//
937
883
// Recursive state machine (subroutine) for JudyCheckPop(): Given a Pjp (other
938
884
// than JPNULL*; caller should shortcut) and the root population for top-level
939
// branches, check the subtree's actual pop1 against its nominal value, and
885
// branches, check the subtrees actual pop1 against its nominal value, and
940
886
// return the total pop1 for the subtree.
941
887
//
942
888
// Note: Expect RootPop1 to be ignored at lower levels, so pass down 0, which
943
889
// should pop an assertion if this expectation is violated.
944
890
945
891
FUNCTION static Word_t JudyCheckPopSM(
946
Pjp_t Pjp, // top of subtree.
947
Word_t RootPop1) // whole array, for top-level branches only.
892
Pjp_t Pjp, // top of subtree.
893
Word_t RootPop1) // whole array, for top-level branches only.
948
894
{
949
Word_t pop1_jp; // nominal population from the JP.
950
Word_t pop1 = 0; // actual population at this level.
951
Word_t offset; // in a branch.
895
Word_t pop1_jp; // nominal population from the JP.
896
Word_t pop1 = 0; // actual population at this level.
897
Word_t offset; // in a branch.
952
898
953
#define PREPBRANCH(cPopBytes,Next) \
954
pop1_jp = JU_JPBRANCH_POP0(Pjp->jp_DcdPop0, cPopBytes) + 1; goto Next
899
#define PREPBRANCH(cPopBytes,Next) \
900
pop1_jp = JU_JPBRANCH_POP0(Pjp, cPopBytes) + 1; goto Next
955
901
956
902
assert((((Word_t) (Pjp->jp_Addr)) & 7) == 3);
957
switch (Pjp->jp_Type)
958
{
903
switch (JU_JPTYPE(Pjp))
904
{
959
905
960
case cJU_JPBRANCH_L2: PREPBRANCH(2, BranchL);
961
case cJU_JPBRANCH_L3: PREPBRANCH(3, BranchL);
906
case cJU_JPBRANCH_L2: PREPBRANCH(2, BranchL);
907
case cJU_JPBRANCH_L3: PREPBRANCH(3, BranchL);
962
908
#ifdef JU_64BIT
963
case cJU_JPBRANCH_L4: PREPBRANCH(4, BranchL);
964
case cJU_JPBRANCH_L5: PREPBRANCH(5, BranchL);
965
case cJU_JPBRANCH_L6: PREPBRANCH(6, BranchL);
966
case cJU_JPBRANCH_L7: PREPBRANCH(7, BranchL);
909
case cJU_JPBRANCH_L4: PREPBRANCH(4, BranchL);
910
case cJU_JPBRANCH_L5: PREPBRANCH(5, BranchL);
911
case cJU_JPBRANCH_L6: PREPBRANCH(6, BranchL);
912
case cJU_JPBRANCH_L7: PREPBRANCH(7, BranchL);
967
913
#endif
968
case cJU_JPBRANCH_L: pop1_jp = RootPop1;
969
{
970
Pjbl_t Pjbl;
914
case cJU_JPBRANCH_L: pop1_jp = RootPop1;
915
{
916
Pjbl_t Pjbl;
971
917
BranchL:
972
Pjbl = P_JBL(Pjp->jp_Addr);
973
974
for (offset = 0; offset < (Pjbl->jbl_NumJPs); ++offset)
975
pop1 += JudyCheckPopSM((Pjbl->jbl_jp) + offset, 0);
976
977
assert(pop1_jp == pop1);
978
return(pop1);
979
}
980
981
case cJU_JPBRANCH_B2: PREPBRANCH(2, BranchB);
982
case cJU_JPBRANCH_B3: PREPBRANCH(3, BranchB);
918
Pjbl = P_JBL(Pjp->jp_Addr);
919
920
for (offset = 0; offset < (Pjbl->jbl_NumJPs); ++offset)
921
pop1 += JudyCheckPopSM((Pjbl->jbl_jp) + offset, 0);
922
923
assert(pop1_jp == pop1);
924
return(pop1);
925
}
926
927
case cJU_JPBRANCH_B2: PREPBRANCH(2, BranchB);
928
case cJU_JPBRANCH_B3: PREPBRANCH(3, BranchB);
983
929
#ifdef JU_64BIT
984
case cJU_JPBRANCH_B4: PREPBRANCH(4, BranchB);
985
case cJU_JPBRANCH_B5: PREPBRANCH(5, BranchB);
986
case cJU_JPBRANCH_B6: PREPBRANCH(6, BranchB);
987
case cJU_JPBRANCH_B7: PREPBRANCH(7, BranchB);
930
case cJU_JPBRANCH_B4: PREPBRANCH(4, BranchB);
931
case cJU_JPBRANCH_B5: PREPBRANCH(5, BranchB);
932
case cJU_JPBRANCH_B6: PREPBRANCH(6, BranchB);
933
case cJU_JPBRANCH_B7: PREPBRANCH(7, BranchB);
988
934
#endif
989
case cJU_JPBRANCH_B: pop1_jp = RootPop1;
990
{
991
Word_t subexp;
992
Word_t jpcount;
993
Pjbb_t Pjbb;
935
case cJU_JPBRANCH_B: pop1_jp = RootPop1;
936
{
937
Word_t subexp;
938
Word_t jpcount;
939
Pjbb_t Pjbb;
994
940
BranchB:
995
Pjbb = P_JBB(Pjp->jp_Addr);
996
997
for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
998
{
999
jpcount = __JudyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp));
1000
1001
for (offset = 0; offset < jpcount; ++offset)
1002
{
1003
pop1 += JudyCheckPopSM(P_JP(JU_JBB_PJP(Pjbb, subexp))
1004
+ offset, 0);
1005
}
1006
}
1007
1008
assert(pop1_jp == pop1);
1009
return(pop1);
1010
}
1011
1012
case cJU_JPBRANCH_U2: PREPBRANCH(2, BranchU);
1013
case cJU_JPBRANCH_U3: PREPBRANCH(3, BranchU);
941
Pjbb = P_JBB(Pjp->jp_Addr);
942
943
for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
944
{
945
jpcount = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp));
946
947
for (offset = 0; offset < jpcount; ++offset)
948
{
949
pop1 += JudyCheckPopSM(P_JP(JU_JBB_PJP(Pjbb, subexp))
950
+ offset, 0);
951
}
952
}
953
954
assert(pop1_jp == pop1);
955
return(pop1);
956
}
957
958
case cJU_JPBRANCH_U2: PREPBRANCH(2, BranchU);
959
case cJU_JPBRANCH_U3: PREPBRANCH(3, BranchU);
1014
960
#ifdef JU_64BIT
1015
case cJU_JPBRANCH_U4: PREPBRANCH(4, BranchU);
1016
case cJU_JPBRANCH_U5: PREPBRANCH(5, BranchU);
1017
case cJU_JPBRANCH_U6: PREPBRANCH(6, BranchU);
1018
case cJU_JPBRANCH_U7: PREPBRANCH(7, BranchU);
961
case cJU_JPBRANCH_U4: PREPBRANCH(4, BranchU);
962
case cJU_JPBRANCH_U5: PREPBRANCH(5, BranchU);
963
case cJU_JPBRANCH_U6: PREPBRANCH(6, BranchU);
964
case cJU_JPBRANCH_U7: PREPBRANCH(7, BranchU);
1019
965
#endif
1020
case cJU_JPBRANCH_U: pop1_jp = RootPop1;
1021
{
1022
Pjbu_t Pjbu;
966
case cJU_JPBRANCH_U: pop1_jp = RootPop1;
967
{
968
Pjbu_t Pjbu;
1023
969
BranchU:
1024
Pjbu = P_JBU(Pjp->jp_Addr);
1025
1026
for (offset = 0; offset < cJU_BRANCHUNUMJPS; ++offset)
1027
{
1028
if (((Pjbu->jbu_jp[offset].jp_Type) >= cJU_JPNULL1)
1029
&& ((Pjbu->jbu_jp[offset].jp_Type) <= cJU_JPNULLMAX))
1030
{
1031
continue; // skip null JP to save time.
1032
}
1033
1034
pop1 += JudyCheckPopSM((Pjbu->jbu_jp) + offset, 0);
1035
}
1036
1037
assert(pop1_jp == pop1);
1038
return(pop1);
1039
}
970
Pjbu = P_JBU(Pjp->jp_Addr);
971
972
for (offset = 0; offset < cJU_BRANCHUNUMJPS; ++offset)
973
{
974
if (((Pjbu->jbu_jp[offset].jp_Type) >= cJU_JPNULL1)
975
&& ((Pjbu->jbu_jp[offset].jp_Type) <= cJU_JPNULLMAX))
976
{
977
continue; // skip null JP to save time.
978
}
979
980
pop1 += JudyCheckPopSM((Pjbu->jbu_jp) + offset, 0);
981
}
982
983
assert(pop1_jp == pop1);
984
return(pop1);
985
}
1040
986
1041
987
1042
988
// -- Cases below here terminate and do not recurse. --
1043
989
//
1044
// For all of these cases except JPLEAF_B1, there is no way to check the JP's
990
// For all of these cases except JPLEAF_B1, there is no way to check the JPs
1045
991
// pop1 against the object itself; just return the pop1; but for linear leaves,
1046
992
// a bounds check is possible.
1047
993
1048
#define CHECKLEAF(MaxPop1) \
1049
pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1; \
1050
assert(pop1 >= 1); \
1051
assert(pop1 <= (MaxPop1)); \
1052
return(pop1)
1053
1054
#if (JUDYL || (! JU_64BIT ))
1055
case cJU_JPLEAF1: CHECKLEAF(cJU_LEAF1_MAXPOP1);
1056
#endif
1057
case cJU_JPLEAF2: CHECKLEAF(cJU_LEAF2_MAXPOP1);
1058
case cJU_JPLEAF3: CHECKLEAF(cJU_LEAF3_MAXPOP1);
1059
#ifdef JU_64BIT
1060
case cJU_JPLEAF4: CHECKLEAF(cJU_LEAF4_MAXPOP1);
1061
case cJU_JPLEAF5: CHECKLEAF(cJU_LEAF5_MAXPOP1);
1062
case cJU_JPLEAF6: CHECKLEAF(cJU_LEAF6_MAXPOP1);
1063
case cJU_JPLEAF7: CHECKLEAF(cJU_LEAF7_MAXPOP1);
1064
#endif
1065
1066
case cJU_JPLEAF_B1:
1067
{
1068
Word_t subexp;
1069
Pjlb_t Pjlb;
1070
1071
pop1_jp = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
1072
1073
Pjlb = P_JLB(Pjp->jp_Addr);
1074
1075
for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp)
1076
pop1 += __JudyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp));
1077
1078
assert(pop1_jp == pop1);
1079
return(pop1);
1080
}
1081
1082
JUDY1CODE(case cJ1_JPFULLPOPU1: return(cJU_JPFULLPOPU1_POP0);)
1083
1084
case cJU_JPIMMED_1_01: return(1);
1085
case cJU_JPIMMED_2_01: return(1);
1086
case cJU_JPIMMED_3_01: return(1);
1087
#ifdef JU_64BIT
1088
case cJU_JPIMMED_4_01: return(1);
1089
case cJU_JPIMMED_5_01: return(1);
1090
case cJU_JPIMMED_6_01: return(1);
1091
case cJU_JPIMMED_7_01: return(1);
1092
#endif
1093
1094
case cJU_JPIMMED_1_02: return(2);
1095
case cJU_JPIMMED_1_03: return(3);
1096
#if (JUDY1 || JU_64BIT)
1097
case cJU_JPIMMED_1_04: return(4);
1098
case cJU_JPIMMED_1_05: return(5);
1099
case cJU_JPIMMED_1_06: return(6);
1100
case cJU_JPIMMED_1_07: return(7);
1101
#endif
1102
#if (JUDY1 && JU_64BIT)
1103
case cJ1_JPIMMED_1_08: return(8);
1104
case cJ1_JPIMMED_1_09: return(9);
1105
case cJ1_JPIMMED_1_10: return(10);
1106
case cJ1_JPIMMED_1_11: return(11);
1107
case cJ1_JPIMMED_1_12: return(12);
1108
case cJ1_JPIMMED_1_13: return(13);
1109
case cJ1_JPIMMED_1_14: return(14);
1110
case cJ1_JPIMMED_1_15: return(15);
1111
#endif
1112
1113
#if (JUDY1 || JU_64BIT)
1114
case cJU_JPIMMED_2_02: return(2);
1115
case cJU_JPIMMED_2_03: return(3);
1116
#endif
1117
#if (JUDY1 && JU_64BIT)
1118
case cJ1_JPIMMED_2_04: return(4);
1119
case cJ1_JPIMMED_2_05: return(5);
1120
case cJ1_JPIMMED_2_06: return(6);
1121
case cJ1_JPIMMED_2_07: return(7);
1122
#endif
1123
1124
#if (JUDY1 || JU_64BIT)
1125
case cJU_JPIMMED_3_02: return(2);
1126
#endif
1127
#if (JUDY1 && JU_64BIT)
1128
case cJ1_JPIMMED_3_03: return(3);
1129
case cJ1_JPIMMED_3_04: return(4);
1130
case cJ1_JPIMMED_3_05: return(5);
1131
1132
case cJ1_JPIMMED_4_02: return(2);
1133
case cJ1_JPIMMED_4_03: return(3);
1134
case cJ1_JPIMMED_5_02: return(2);
1135
case cJ1_JPIMMED_5_03: return(3);
1136
case cJ1_JPIMMED_6_02: return(2);
1137
case cJ1_JPIMMED_7_02: return(2);
1138
#endif
1139
1140
} // switch (Pjp->jp_Type)
1141
1142
assert(FALSE); // unrecognized JP type => corruption.
1143
return(0); // to make some compilers happy.
994
#define CHECKLEAF(MaxPop1) \
995
pop1 = JU_JPLEAF_POP0(Pjp) + 1; \
996
assert(pop1 >= 1); \
997
assert(pop1 <= (MaxPop1)); \
998
return(pop1)
999
1000
#if (defined(JUDYL) || (! defined(JU_64BIT)))
1001
case cJU_JPLEAF1: CHECKLEAF(cJU_LEAF1_MAXPOP1);
1002
#endif
1003
case cJU_JPLEAF2: CHECKLEAF(cJU_LEAF2_MAXPOP1);
1004
case cJU_JPLEAF3: CHECKLEAF(cJU_LEAF3_MAXPOP1);
1005
#ifdef JU_64BIT
1006
case cJU_JPLEAF4: CHECKLEAF(cJU_LEAF4_MAXPOP1);
1007
case cJU_JPLEAF5: CHECKLEAF(cJU_LEAF5_MAXPOP1);
1008
case cJU_JPLEAF6: CHECKLEAF(cJU_LEAF6_MAXPOP1);
1009
case cJU_JPLEAF7: CHECKLEAF(cJU_LEAF7_MAXPOP1);
1010
#endif
1011
1012
case cJU_JPLEAF_B1:
1013
{
1014
Word_t subexp;
1015
Pjlb_t Pjlb;
1016
1017
pop1_jp = JU_JPLEAF_POP0(Pjp) + 1;
1018
1019
Pjlb = P_JLB(Pjp->jp_Addr);
1020
1021
for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp)
1022
pop1 += j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp));
1023
1024
assert(pop1_jp == pop1);
1025
return(pop1);
1026
}
1027
1028
JUDY1CODE(case cJ1_JPFULLPOPU1: return(cJU_JPFULLPOPU1_POP0);)
1029
1030
case cJU_JPIMMED_1_01: return(1);
1031
case cJU_JPIMMED_2_01: return(1);
1032
case cJU_JPIMMED_3_01: return(1);
1033
#ifdef JU_64BIT
1034
case cJU_JPIMMED_4_01: return(1);
1035
case cJU_JPIMMED_5_01: return(1);
1036
case cJU_JPIMMED_6_01: return(1);
1037
case cJU_JPIMMED_7_01: return(1);
1038
#endif
1039
1040
case cJU_JPIMMED_1_02: return(2);
1041
case cJU_JPIMMED_1_03: return(3);
1042
#if (defined(JUDY1) || defined(JU_64BIT))
1043
case cJU_JPIMMED_1_04: return(4);
1044
case cJU_JPIMMED_1_05: return(5);
1045
case cJU_JPIMMED_1_06: return(6);
1046
case cJU_JPIMMED_1_07: return(7);
1047
#endif
1048
#if (defined(JUDY1) && defined(JU_64BIT))
1049
case cJ1_JPIMMED_1_08: return(8);
1050
case cJ1_JPIMMED_1_09: return(9);
1051
case cJ1_JPIMMED_1_10: return(10);
1052
case cJ1_JPIMMED_1_11: return(11);
1053
case cJ1_JPIMMED_1_12: return(12);
1054
case cJ1_JPIMMED_1_13: return(13);
1055
case cJ1_JPIMMED_1_14: return(14);
1056
case cJ1_JPIMMED_1_15: return(15);
1057
#endif
1058
1059
#if (defined(JUDY1) || defined(JU_64BIT))
1060
case cJU_JPIMMED_2_02: return(2);
1061
case cJU_JPIMMED_2_03: return(3);
1062
#endif
1063
#if (defined(JUDY1) && defined(JU_64BIT))
1064
case cJ1_JPIMMED_2_04: return(4);
1065
case cJ1_JPIMMED_2_05: return(5);
1066
case cJ1_JPIMMED_2_06: return(6);
1067
case cJ1_JPIMMED_2_07: return(7);
1068
#endif
1069
1070
#if (defined(JUDY1) || defined(JU_64BIT))
1071
case cJU_JPIMMED_3_02: return(2);
1072
#endif
1073
#if (defined(JUDY1) && defined(JU_64BIT))
1074
case cJ1_JPIMMED_3_03: return(3);
1075
case cJ1_JPIMMED_3_04: return(4);
1076
case cJ1_JPIMMED_3_05: return(5);
1077
1078
case cJ1_JPIMMED_4_02: return(2);
1079
case cJ1_JPIMMED_4_03: return(3);
1080
case cJ1_JPIMMED_5_02: return(2);
1081
case cJ1_JPIMMED_5_03: return(3);
1082
case cJ1_JPIMMED_6_02: return(2);
1083
case cJ1_JPIMMED_7_02: return(2);
1084
#endif
1085
1086
} // switch (JU_JPTYPE(Pjp))
1087
1088
assert(FALSE); // unrecognized JP type => corruption.
1089
return(0); // to make some compilers happy.
1144
1090
1145
1091
} // JudyCheckPopSM()
1146
1092
Loggerhead is a web-based interface for Breezy
Version: 2.0.1