← Back to branch summary

~airpollution/fluidity/fluidity_airpollution

« back to all changes in this revision

Viewing changes to libjudy/src/Judy1/Judy1Test.c

  • Committer: ziyouzhj
  • Date: 2013-12-09 16:51:29 UTC
  • Revision ID: ziyouzhj@gmail.com-20131209165129-ucoetc3u0atyy05c
airpolution

Show diffs side-by-side

added added

removed removed

Lines of Context:
libjudy/src/Judy1/Judy1Test.c
 
1
// Copyright (C) 2000 - 2002 Hewlett-Packard Company
 
2
//
 
3
// This program is free software; you can redistribute it and/or modify it
 
4
// under the term of the GNU Lesser General Public License as published by the
 
5
// Free Software Foundation; either version 2 of the License, or (at your
 
6
// option) any later version.
 
7
//
 
8
// This program is distributed in the hope that it will be useful, but WITHOUT
 
9
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 
10
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
 
11
// for more details.
 
12
//
 
13
// You should have received a copy of the GNU Lesser General Public License
 
14
// along with this program; if not, write to the Free Software Foundation,
 
15
// Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
// _________________
 
17
 
 
18
// @(#) $Revision: 4.43 $ $Source: /judy/src/JudyCommon/JudyGet.c $
 
19
//
 
20
// Judy1Test() and JudyLGet() functions for Judy1 and JudyL.
 
21
// Compile with one of -DJUDY1 or -DJUDYL.
 
22
 
 
23
#if (! (defined(JUDY1) || defined(JUDYL)))
 
24
#error:  One of -DJUDY1 or -DJUDYL must be specified.
 
25
#endif
 
26
 
 
27
#ifdef JUDY1
 
28
#include "Judy1.h"
 
29
#else
 
30
#include "JudyL.h"
 
31
#endif
 
32
 
 
33
#include "JudyPrivate1L.h"
 
34
 
 
35
#ifdef TRACEJPR                 // different macro name, for "retrieval" only.
 
36
#include "JudyPrintJP.c"
 
37
#endif
 
38
 
 
39
 
 
40
// ****************************************************************************
 
41
// J U D Y   1   T E S T
 
42
// J U D Y   L   G E T
 
43
//
 
44
// See the manual entry for details.  Note support for "shortcut" entries to
 
45
// trees known to start with a JPM.
 
46
 
 
47
#ifdef JUDY1
 
48
 
 
49
#ifdef JUDYGETINLINE
 
50
FUNCTION int j__udy1Test
 
51
#else
 
52
FUNCTION int Judy1Test
 
53
#endif
 
54
 
 
55
#else  // JUDYL
 
56
 
 
57
#ifdef JUDYGETINLINE
 
58
FUNCTION PPvoid_t j__udyLGet
 
59
#else
 
60
FUNCTION PPvoid_t JudyLGet
 
61
#endif
 
62
 
 
63
#endif // JUDYL
 
64
        (
 
65
#ifdef JUDYGETINLINE
 
66
        Pvoid_t   PArray,       // from which to retrieve.
 
67
        Word_t    Index         // to retrieve.
 
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.
 
72
#endif
 
73
        )
 
74
{
 
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
 
 
82
#ifndef JUDYGETINLINE
 
83
 
 
84
        if (PArray == (Pcvoid_t) NULL)  // empty array.
 
85
        {
 
86
  JUDY1CODE(return(0);)
 
87
  JUDYLCODE(return((PPvoid_t) NULL);)
 
88
        }
 
89
 
 
90
// ****************************************************************************
 
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
            {
 
103
      JUDY1CODE(return(1);)
 
104
      JUDYLCODE(return((PPvoid_t) (JL_LEAFWVALUEAREA(Pjlw, Pop1) + posidx));)
 
105
            }
 
106
  JUDY1CODE(return(0);)
 
107
  JUDYLCODE(return((PPvoid_t) NULL);)
 
108
        }
 
109
 
 
110
#endif // ! JUDYGETINLINE
 
111
 
 
112
        Pjpm = P_JPM(PArray);
 
113
        Pjp = &(Pjpm->jpm_JP);  // top branch is below JPM.
 
114
 
 
115
// ****************************************************************************
 
116
// WALK THE JUDY TREE USING A STATE MACHINE:
 
117
 
 
118
ContinueWalk:           // for going down one level; come here with Pjp set.
 
119
 
 
120
#ifdef TRACEJPR
 
121
        JudyPrintJP(Pjp, "g", __LINE__);
 
122
#endif
 
123
        switch (JU_JPTYPE(Pjp))
 
124
        {
 
125
 
 
126
// Ensure the switch table starts at 0 for speed; otherwise more code is
 
127
// executed:
 
128
 
 
129
        case 0: goto ReturnCorrupt;     // save a little code.
 
130
 
 
131
 
 
132
// ****************************************************************************
 
133
// JPNULL*:
 
134
//
 
135
// Note:  These are legitimate in a BranchU (only) and do not constitute a
 
136
// fault.
 
137
 
 
138
        case cJU_JPNULL1:
 
139
        case cJU_JPNULL2:
 
140
        case cJU_JPNULL3:
 
141
#ifdef JU_64BIT
 
142
        case cJU_JPNULL4:
 
143
        case cJU_JPNULL5:
 
144
        case cJU_JPNULL6:
 
145
        case cJU_JPNULL7:
 
146
#endif
 
147
            assert(ParentJPType >= cJU_JPBRANCH_U2);
 
148
            assert(ParentJPType <= cJU_JPBRANCH_U);
 
149
      JUDY1CODE(return(0);)
 
150
      JUDYLCODE(return((PPvoid_t) NULL);)
 
151
 
 
152
 
 
153
// ****************************************************************************
 
154
// JPBRANCH_L*:
 
155
//
 
156
// Note:  The use of JU_DCDNOTMATCHINDEX() in branches is not strictly
 
157
// required,since this can be done at leaf level, but it costs nothing to do it
 
158
// sooner, and it aborts an unnecessary traversal sooner.
 
159
 
 
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;
 
170
#endif
 
171
            Digit = JU_DIGITATSTATE(Index, 3);
 
172
            goto JudyBranchL;
 
173
 
 
174
#ifdef JU_64BIT
 
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;
 
198
 
 
199
#endif // JU_64BIT
 
200
 
 
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:
 
209
 
 
210
JudyBranchL:
 
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
        }
 
226
 
 
227
 
 
228
// ****************************************************************************
 
229
// JPBRANCH_B*:
 
230
 
 
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;
 
241
#endif
 
242
            Digit = JU_DIGITATSTATE(Index, 3);
 
243
            goto JudyBranchB;
 
244
 
 
245
 
 
246
#ifdef JU_64BIT
 
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;
 
270
 
 
271
#endif // JU_64BIT
 
272
 
 
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:
 
283
 
 
284
JudyBranchB:
 
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);
 
293
 
 
294
// No JP in subexpanse for Index => Index not found:
 
295
 
 
296
            if (! (BitMap & BitMask)) break;
 
297
 
 
298
// Count JPs in the subexpanse below the one for Index:
 
299
 
 
300
            Pjp += j__udyCountBitsB(BitMap & (BitMask - 1));
 
301
 
 
302
            goto ContinueWalk;
 
303
 
 
304
        } // case cJU_JPBRANCH_B*
 
305
 
 
306
 
 
307
// ****************************************************************************
 
308
// JPBRANCH_U*:
 
309
//
 
310
// Notice the reverse order of the cases, and falling through to the next case,
 
311
// for performance.
 
312
 
 
313
        case cJU_JPBRANCH_U:
 
314
 
 
315
            DBGCODE(ParentJPType = JU_JPTYPE(Pjp);)
 
316
            Pjp = JU_JBU_PJP(Pjp, Index, cJU_ROOTSTATE);
 
317
 
 
318
// If not a BranchU, traverse; otherwise fall into the next case, which makes
 
319
// this very fast code for a large Judy array (mainly BranchUs), especially
 
320
// when branches are already in the cache, such as for prev/next:
 
321
 
 
322
#ifndef JU_64BIT
 
323
            if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U3) goto ContinueWalk;
 
324
#else
 
325
            if (JU_JPTYPE(Pjp) != cJU_JPBRANCH_U7) goto ContinueWalk;
 
326
#endif
 
327
 
 
328
#ifdef JU_64BIT
 
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.
 
364
 
 
365
#endif // JU_64BIT
 
366
 
 
367
        case cJU_JPBRANCH_U3:
 
368
 
 
369
#ifdef JU_64BIT // otherwise its a no-op:
 
370
            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
 
371
#endif
 
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);
 
383
 
 
384
// Note:  BranchU2 is a special case that must continue traversal to a leaf,
 
385
// immed, full, or null type:
 
386
 
 
387
            goto ContinueWalk;
 
388
 
 
389
 
 
390
// ****************************************************************************
 
391
// JPLEAF*:
 
392
//
 
393
// Note:  Here the calls of JU_DCDNOTMATCHINDEX() are necessary and check
 
394
// whether Index is out of the expanse of a narrow pointer.
 
395
 
 
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;
 
408
 
 
409
  JUDY1CODE(return(1);)
 
410
  JUDYLCODE(return((PPvoid_t) (JL_LEAF1VALUEAREA(Pjll, Pop1) + posidx));)
 
411
        }
 
412
 
 
413
#endif // (JUDYL || (! JU_64BIT))
 
414
 
 
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;
 
425
 
 
426
  JUDY1CODE(return(1);)
 
427
  JUDYLCODE(return((PPvoid_t) (JL_LEAF2VALUEAREA(Pjll, Pop1) + posidx));)
 
428
        }
 
429
        case cJU_JPLEAF3:
 
430
        {
 
431
            int posidx;         // signed offset in leaf.
 
432
 
 
433
#ifdef JU_64BIT // otherwise its a no-op:
 
434
            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 3)) break;
 
435
#endif
 
436
 
 
437
            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
 
438
            Pjll = P_JLL(Pjp->jp_Addr);
 
439
 
 
440
            if ((posidx = j__udySearchLeaf3(Pjll, Pop1, Index)) < 0) break;
 
441
 
 
442
  JUDY1CODE(return(1);)
 
443
  JUDYLCODE(return((PPvoid_t) (JL_LEAF3VALUEAREA(Pjll, Pop1) + posidx));)
 
444
        }
 
445
#ifdef JU_64BIT
 
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;
 
456
 
 
457
  JUDY1CODE(return(1);)
 
458
  JUDYLCODE(return((PPvoid_t) (JL_LEAF4VALUEAREA(Pjll, Pop1) + posidx));)
 
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;
 
470
 
 
471
  JUDY1CODE(return(1);)
 
472
  JUDYLCODE(return((PPvoid_t) (JL_LEAF5VALUEAREA(Pjll, Pop1) + posidx));)
 
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;
 
485
 
 
486
  JUDY1CODE(return(1);)
 
487
  JUDYLCODE(return((PPvoid_t) (JL_LEAF6VALUEAREA(Pjll, Pop1) + posidx));)
 
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;
 
498
 
 
499
  JUDY1CODE(return(1);)
 
500
  JUDYLCODE(return((PPvoid_t) (JL_LEAF7VALUEAREA(Pjll, Pop1) + posidx));)
 
501
        }
 
502
#endif // JU_64BIT
 
503
 
 
504
 
 
505
// ****************************************************************************
 
506
// JPLEAF_B1:
 
507
 
 
508
        case cJU_JPLEAF_B1:
 
509
        {
 
510
            Pjlb_t    Pjlb;
 
511
#ifdef JUDYL
 
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;
 
517
#endif
 
518
            if (JU_DCDNOTMATCHINDEX(Index, Pjp, 1)) break;
 
519
 
 
520
            Pjlb = P_JLB(Pjp->jp_Addr);
 
521
 
 
522
#ifdef JUDY1
 
523
 
 
524
// Simply check if Indexs bit is set in the bitmap:
 
525
 
 
526
            if (JU_BITMAPTESTL(Pjlb, Index)) return(1);
 
527
            break;
 
528
 
 
529
#else // JUDYL
 
530
 
 
531
// JudyL is much more complicated because of value area subarrays:
 
532
 
 
533
            Digit   = JU_DIGITATSTATE(Index, 1);
 
534
            subexp  = Digit / cJU_BITSPERSUBEXPL;
 
535
            BitMap  = JU_JLB_BITMAP(Pjlb, subexp);
 
536
            BitMask = JU_BITPOSMASKL(Digit);
 
537
 
 
538
// No value in subexpanse for Index => Index not found:
 
539
 
 
540
            if (! (BitMap & BitMask)) break;
 
541
 
 
542
// Count value areas in the subexpanse below the one for Index:
 
543
 
 
544
            Pjv = P_JV(JL_JLB_PVALUE(Pjlb, subexp));
 
545
            assert(Pjv != (Pjv_t) NULL);
 
546
            posidx = j__udyCountBitsL(BitMap & (BitMask - 1));
 
547
 
 
548
            return((PPvoid_t) (Pjv + posidx));
 
549
 
 
550
#endif // JUDYL
 
551
 
 
552
        } // case cJU_JPLEAF_B1
 
553
 
 
554
#ifdef JUDY1
 
555
 
 
556
// ****************************************************************************
 
557
// JPFULLPOPU1:
 
558
//
 
559
// If the Index is in the expanse, it is necessarily valid (found).
 
560
 
 
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
 
604
 
 
605
#endif // JUDY1
 
606
#endif //  notdef
 
607
 
 
608
// ****************************************************************************
 
609
// JPIMMED*:
 
610
//
 
611
// Note that the contents of jp_DcdPopO are different for cJU_JPIMMED_*_01:
 
612
 
 
613
        case cJU_JPIMMED_1_01:
 
614
        case cJU_JPIMMED_2_01:
 
615
        case cJU_JPIMMED_3_01:
 
616
#ifdef JU_64BIT
 
617
        case cJU_JPIMMED_4_01:
 
618
        case cJU_JPIMMED_5_01:
 
619
        case cJU_JPIMMED_6_01:
 
620
        case cJU_JPIMMED_7_01:
 
621
#endif
 
622
            if (JU_JPDCDPOP0(Pjp) != JU_TRIMTODCDSIZE(Index)) break;
 
623
 
 
624
  JUDY1CODE(return(1);)
 
625
  JUDYLCODE(return((PPvoid_t) &(Pjp->jp_Addr));)  // immediate value area.
 
626
 
 
627
 
 
628
//   Macros to make code more readable and avoid dup errors
 
629
 
 
630
#ifdef JUDY1
 
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;
 
736
 
 
737
#endif // (JUDY1 && JU_64BIT)
 
738
 
 
739
 
 
740
// ****************************************************************************
 
741
// INVALID JP TYPE:
 
742
 
 
743
        default:
 
744
 
 
745
ReturnCorrupt:
 
746
 
 
747
#ifdef JUDYGETINLINE    // Pjpm is known to be non-null:
 
748
            JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);
 
749
#else
 
750
            JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
 
751
#endif
 
752
            JUDY1CODE(return(JERRI );)
 
753
            JUDYLCODE(return(PPJERR);)
 
754
 
 
755
        } // switch on JP type
 
756
 
 
757
JUDY1CODE(return(0);)
 
758
JUDYLCODE(return((PPvoid_t) NULL);)
 
759
 
 
760
} // Judy1Test() / JudyLGet()
 
761
 
 
762
 
 
763
#ifndef JUDYGETINLINE   // only compile the following function once:
 
764
#ifdef DEBUG
 
765
 
 
766
// ****************************************************************************
 
767
// J U D Y   C H E C K   P O P
 
768
//
 
769
// Given a pointer to a Judy array, traverse the entire array to ensure
 
770
// population counts add up correctly.  This can catch various coding errors.
 
771
//
 
772
// Since walking the entire tree is probably time-consuming, enable this
 
773
// function by setting env parameter $CHECKPOP to first call at which to start
 
774
// checking.  Note:  This function is called both from insert and delete code.
 
775
//
 
776
// Note:  Even though this function does nothing useful for LEAFW leaves, its
 
777
// good practice to call it anyway, and cheap too.
 
778
//
 
779
// TBD:  This is a debug-only check function similar to JudyCheckSorted(), but
 
780
// since it walks the tree it is Judy1/JudyL-specific and must live in a source
 
781
// file that is built both ways.
 
782
//
 
783
// TBD:  As feared, enabling this code for every insert/delete makes Judy
 
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
 
786
// other than DEBUG and/or called less often?
 
787
//
 
788
// TBD:  Should this "population checker" be expanded to a comprehensive tree
 
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
 
791
// the Judy tree, include:
 
792
//
 
793
// - Zero LS bits in jp_Addr field.
 
794
//
 
795
// - Correct Dcd bits.
 
796
//
 
797
// - Consistent JP types (always descending down the tree).
 
798
//
 
799
// - Sorted linear lists in BranchLs and leaves (using JudyCheckSorted(), but
 
800
//   ideally that function is already called wherever appropriate after any
 
801
//   linear list is modified).
 
802
//
 
803
// - Any others possible?
 
804
 
 
805
#include <stdlib.h>             // for getenv() and atol().
 
806
 
 
807
static Word_t JudyCheckPopSM(Pjp_t Pjp, Word_t RootPop1);
 
808
 
 
809
FUNCTION void JudyCheckPop(
 
810
        Pvoid_t PArray)
 
811
{
 
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.
 
817
 
 
818
 
 
819
// CHECK FOR EXTERNAL ENABLING:
 
820
 
 
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
            {
 
829
#ifdef notdef
 
830
// Take this out because nightly tests want to be flavor-independent; its not
 
831
// OK to emit special non-error output from the debug flavor:
 
832
 
 
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");
 
836
#endif
 
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;
 
847
 
 
848
// Previously or just now enabled; check if non-active or newly active:
 
849
 
 
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;
 
862
 
 
863
// Check JPM pop0 against tree, recursively:
 
864
//
 
865
// Note:  The traversal code in JudyCheckPopSM() is simplest when the case
 
866
// statement for each JP type compares the pop1 for that JP to its subtree (if
 
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
 
869
// full-word pop1, so pass it in as a special case.
 
870
 
 
871
        {
 
872
            Pjpm_t Pjpm = P_JPM(PArray);
 
873
            (void) JudyCheckPopSM(&(Pjpm->jpm_JP), Pjpm->jpm_Pop0 + 1);
 
874
            return;
 
875
        }
 
876
 
 
877
} // JudyCheckPop()
 
878
 
 
879
 
 
880
// ****************************************************************************
 
881
// J U D Y   C H E C K   P O P   S M
 
882
//
 
883
// Recursive state machine (subroutine) for JudyCheckPop():  Given a Pjp (other
 
884
// than JPNULL*; caller should shortcut) and the root population for top-level
 
885
// branches, check the subtrees actual pop1 against its nominal value, and
 
886
// return the total pop1 for the subtree.
 
887
//
 
888
// Note:  Expect RootPop1 to be ignored at lower levels, so pass down 0, which
 
889
// should pop an assertion if this expectation is violated.
 
890
 
 
891
FUNCTION static Word_t JudyCheckPopSM(
 
892
        Pjp_t  Pjp,             // top of subtree.
 
893
        Word_t RootPop1)        // whole array, for top-level branches only.
 
894
{
 
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.
 
898
 
 
899
#define PREPBRANCH(cPopBytes,Next) \
 
900
        pop1_jp = JU_JPBRANCH_POP0(Pjp, cPopBytes) + 1; goto Next
 
901
 
 
902
assert((((Word_t) (Pjp->jp_Addr)) & 7) == 3);
 
903
        switch (JU_JPTYPE(Pjp))
 
904
        {
 
905
 
 
906
        case cJU_JPBRANCH_L2: PREPBRANCH(2, BranchL);
 
907
        case cJU_JPBRANCH_L3: PREPBRANCH(3, BranchL);
 
908
#ifdef JU_64BIT
 
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);
 
913
#endif
 
914
        case cJU_JPBRANCH_L:  pop1_jp = RootPop1;
 
915
        {
 
916
            Pjbl_t Pjbl;
 
917
BranchL:
 
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);
 
929
#ifdef JU_64BIT
 
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);
 
934
#endif
 
935
        case cJU_JPBRANCH_B:  pop1_jp = RootPop1;
 
936
        {
 
937
            Word_t subexp;
 
938
            Word_t jpcount;
 
939
            Pjbb_t Pjbb;
 
940
BranchB:
 
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);
 
960
#ifdef JU_64BIT
 
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);
 
965
#endif
 
966
        case cJU_JPBRANCH_U:  pop1_jp = RootPop1;
 
967
        {
 
968
            Pjbu_t Pjbu;
 
969
BranchU:
 
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
        }
 
986
 
 
987
 
 
988
// -- Cases below here terminate and do not recurse. --
 
989
//
 
990
// For all of these cases except JPLEAF_B1, there is no way to check the JPs
 
991
// pop1 against the object itself; just return the pop1; but for linear leaves,
 
992
// a bounds check is possible.
 
993
 
 
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.
 
1090
 
 
1091
} // JudyCheckPopSM()
 
1092
 
 
1093
#endif // DEBUG
 
1094
#endif // ! JUDYGETINLINE