1
// Copyright (C) 2000 - 2002 Hewlett-Packard Company
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.
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
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
18
// @(#) $Revision: 4.35 $ $Source: /judy/src/JudyCommon/JudySearchLeaf.c $
20
// At least in some contexts, this source file is #include'd by others for
21
// inlining, so ensure it only happens once:
23
#ifndef _JUDYSEARCHLEAF
24
#define _JUDYSEARCHLEAF
26
// JUDY LINEAR LEAF SEARCH AND BIT COUNTING FUNCTIONS.
28
// TBD: Despite the names of some of these functions, they only search linear
29
// leaves, not bitmap leaves; and they are also used to search the index list
30
// portion of linear branches (Branch2..7), and one-byte immediates (Immed1*).
31
// Consider renaming them to __JudySearchLin*().
33
// Search function return values:
35
// All the search functions below return the position (offset, base 0) in the
36
// source array of the index passed in. If the index is not found, the return
37
// value is the the ones-complement of the sought index's ideal position. For
40
// array: 10 20 30 40 50
42
// Index to search for returned value
43
// ------------------- --------------
51
// The caller should check for result >= 0 for a match. To get the position
52
// (offset) in which an absent index belongs, just take the ones-complement
56
#include "JudyPrivate.h"
57
#include "JudyPrivateBranch.h"
59
DBGCODE(void JudyCheckSorted(Pjll_t Pjll, Word_t Pop1, long IndexSize);)
61
// Leaf search function return types here depend on compilation context:
64
#define RETURN_TYPE static int
66
#define RETURN_TYPE int
71
// ****************************************************************************
72
// __ J U D Y S E A R C H L E A F 1
74
// Search a 1-byte-Index linear leaf (cJ*_JPLEAF1) for the specified Index.
75
// The return value is described in file header comments.
77
// Note: Although Judy1 on 64-bit systems does not have Leaf1's, this function
78
// is also used to search BranchL's and Immed1*'s, as noted in file header
81
FUNCTION RETURN_TYPE __JudySearchLeaf1(
82
Pjll_t Pjll, // to linear Leaf1 to search.
83
Word_t LeafPop1, // number of valid indexes.
84
Word_t Index) // to find.
86
Index &= MASK1; // look for last BPI1 bytes only.
88
#undef PLEAF_T // in case previously set.
89
#define PLEAF_T uint8_t * // for JudySearchLeafEven.c.
97
#include "JudySearchLeafEven.c"
99
} // __JudySearchLeaf1()
102
// ****************************************************************************
103
// __ J U D Y S E A R C H L E A F 2
105
// Search a 2-byte-Index linear leaf (cJ*_JPLEAF2, or the index list in a
106
// cJ*_JPBRANCH_L2) for the specified Index. The return value is described in
107
// file header comments.
109
FUNCTION RETURN_TYPE __JudySearchLeaf2(
110
Pjll_t Pjll, // to linear Leaf2 to search.
111
Word_t LeafPop1, // number of valid indexes.
112
Word_t Index) // to find.
114
Index &= MASK2; // look for last BPI2 bytes only.
116
#undef PLEAF_T // in case previously set.
117
#define PLEAF_T uint16_t * // for JudySearchLeafEven.c.
125
#include "JudySearchLeafEven.c"
127
} // __JudySearchLeaf2()
129
#endif // JU_NOINLINE
131
// ****************************************************************************
132
// __ J U D Y S E A R C H L E A F 3
134
// Search a 3-byte-Index linear leaf (cJ*_JPLEAF3, or the index list in a
135
// cJ*_JPBRANCH_L3) for the specified Index. The return value is described in
136
// file header comments.
138
FUNCTION RETURN_TYPE __JudySearchLeaf3(
139
Pjll_t Pjll, // to linear Leaf3 to search.
140
Word_t LeafPop1, // number of valid indexes.
141
Word_t Index) // to find.
143
#undef BPI // in case previously set.
148
#define BPI BPI3 // for JudySearchLeafOdd.c.
171
#define GET_LIG GET3_LIG
173
// Unfortunately IPG itself is an expression the compiler can't seem to handle,
174
// so define IPG_BIG here explicitly, though this contains knowledge of IPG
179
#define IPG_BIG 1 // set to 1 for "#if".
182
#undef JU_COPY_PINDEX_TO_LONG
183
#define JU_COPY_PINDEX_TO_LONG(LI,PI) JU_COPY3_PINDEX_TO_LONG(LI,PI)
185
#include "JudySearchLeafOdd.c"
187
} // __JudySearchLeaf3()
194
// ****************************************************************************
195
// __ J U D Y S E A R C H L E A F 4
197
// Search a 4-byte-Index linear leaf (cJ*_JPLEAF4, or the index list in a
198
// cJ*_JPBRANCH_L4) for the specified Index. The return value is described in
199
// file header comments.
201
FUNCTION RETURN_TYPE __JudySearchLeaf4(
202
Pjll_t Pjll, // to linear Leaf4 to search.
203
Word_t LeafPop1, // number of valid indexes.
204
Word_t Index) // to find.
206
Index &= MASK4; // look for last BPI4 bytes only.
208
#undef PLEAF_T // in case previously set.
209
#define PLEAF_T uint32_t * // for JudySearchLeafEven.c.
217
#include "JudySearchLeafEven.c"
219
} // __JudySearchLeaf4()
221
#endif // JU_NOINLINE
224
// ****************************************************************************
225
// __ J U D Y S E A R C H L E A F 5
227
// Search a 5-byte-Index linear leaf (cJ*_JPLEAF5, or the index list in a
228
// cJ*_JPBRANCH_L5) for the specified Index. The return value is described in
229
// file header comments.
231
FUNCTION RETURN_TYPE __JudySearchLeaf5(
232
Pjll_t Pjll, // to linear Leaf5 to search.
233
Word_t LeafPop1, // number of valid indexes.
234
Word_t Index) // to find.
236
#undef BPI // in case previously set.
241
#define BPI BPI5 // for JudySearchLeafOdd.c.
262
#define GET_LIG GET5_LIG
264
// Unfortunately IPG itself is an expression the compiler can't seem to handle,
265
// so define IPG_BIG here explicitly, though this contains knowledge of IPG
269
#define IPG_BIG 1 // set to 1 for "#if".
271
#undef JU_COPY_PINDEX_TO_LONG
272
#define JU_COPY_PINDEX_TO_LONG(LI,PI) JU_COPY5_PINDEX_TO_LONG(LI,PI)
274
#include "JudySearchLeafOdd.c"
276
} // __JudySearchLeaf5()
279
// ****************************************************************************
280
// __ J U D Y S E A R C H L E A F 6
282
// Search a 6-byte-Index linear leaf (cJ*_JPLEAF6, or the index list in a
283
// cJ*_JPBRANCH_L6) for the specified Index. The return value is described in
284
// file header comments.
286
FUNCTION RETURN_TYPE __JudySearchLeaf6(
287
Pjll_t Pjll, // to linear Leaf6 to search.
288
Word_t LeafPop1, // number of valid indexes.
289
Word_t Index) // to find.
291
#undef BPI // in case previously set.
296
#define BPI BPI6 // for JudySearchLeafOdd.c.
309
#define GET_LIG GET6_LIG
311
// Unfortunately IPG itself is an expression the compiler can't seem to handle,
312
// so unset IPG_BIG here explicitly, though this contains knowledge of IPG
317
#undef JU_COPY_PINDEX_TO_LONG
318
#define JU_COPY_PINDEX_TO_LONG(LI,PI) JU_COPY6_PINDEX_TO_LONG(LI,PI)
320
#include "JudySearchLeafOdd.c"
322
} // __JudySearchLeaf6()
325
// ****************************************************************************
326
// __ J U D Y S E A R C H L E A F 7
328
// Search a 7-byte-Index linear leaf (cJ*_JPLEAF7, or the index list in a
329
// cJ*_JPBRANCH_L7) for the specified Index. The return value is described in
330
// file header comments.
332
FUNCTION RETURN_TYPE __JudySearchLeaf7(
333
Pjll_t Pjll, // to linear Leaf7 to search.
334
Word_t LeafPop1, // number of valid indexes.
335
Word_t Index) // to find.
337
#undef BPI // in case previously set.
342
#define BPI BPI7 // for JudySearchLeafOdd.c.
363
#define GET_LIG GET7_LIG
365
// Unfortunately IPG itself is an expression the compiler can't seem to handle,
366
// so define IPG_BIG here explicitly, though this contains knowledge of IPG
370
#define IPG_BIG 1 // set to 1 for "#if".
372
#undef JU_COPY_PINDEX_TO_LONG
373
#define JU_COPY_PINDEX_TO_LONG(LI,PI) JU_COPY7_PINDEX_TO_LONG(LI,PI)
375
#include "JudySearchLeafOdd.c"
377
} // __JudySearchLeaf7()
384
// ****************************************************************************
385
// __ J U D Y S E A R C H L E A F W
387
// Search a root-level leaf (cJ*_JAPLEAF, index size = Word_t) for the
388
// specified Index. The return value is described in file header comments.
390
FUNCTION RETURN_TYPE __JudySearchLeafW(
391
Pjlw_t Pjlw, // to linear LeafW to search.
392
Word_t LeafPop1, // number of valid indexes.
393
Word_t Index) // to find.
395
#undef PLEAF_T // in case previously set.
396
#define PLEAF_T Pjlw_t // for JudySearchLeafEven.c.
404
Pjll_t Pjll = (Pjll_t) Pjlw;
406
#include "JudySearchLeafEven.c"
408
} // __JudySearchLeafW()
411
// ****************************************************************************
412
// __ J U D Y C O U N T B I T S B
414
// Return the number of bits set in "Word", for a bitmap branch.
416
// Note: Bitmap branches have maximum bitmap size = 32 bits.
418
FUNCTION BITMAPB_t __JudyCountBitsB(BITMAPB_t word)
420
word = (word & 0x55555555) + ((word & 0xAAAAAAAA) >> 1);
421
word = (word & 0x33333333) + ((word & 0xCCCCCCCC) >> 2);
422
word = (word & 0x0F0F0F0F) + ((word & 0xF0F0F0F0) >> 4); // >= 8 bits.
423
#if defined(BITMAP_BRANCH16x16) || defined(BITMAP_BRANCH32x8)
424
word = (word & 0x00FF00FF) + ((word & 0xFF00FF00) >> 8); // >= 16 bits.
426
#ifdef BITMAP_BRANCH32x8
427
word = (word & 0x0000FFFF) + ((word & 0xFFFF0000) >> 16); // >= 32 bits.
431
} // __JudyCountBitsB()
434
// ****************************************************************************
435
// __ J U D Y C O U N T B I T S L
437
// Return the number of bits set in "Word", for a bitmap leaf.
439
// Note: Bitmap branches have maximum bitmap size = 32 bits.
441
// Note: Need both 32-bit and 64-bit versions of __JudyCountBitsL() because
442
// bitmap leaves can have 64-bit bitmaps.
444
FUNCTION BITMAPL_t __JudyCountBitsL(BITMAPL_t word)
448
word = (word & 0x55555555) + ((word & 0xAAAAAAAA) >> 1);
449
word = (word & 0x33333333) + ((word & 0xCCCCCCCC) >> 2);
450
word = (word & 0x0F0F0F0F) + ((word & 0xF0F0F0F0) >> 4); // >= 8 bits.
451
#if defined(BITMAP_LEAF16x16) || defined(BITMAP_LEAF32x8)
452
word = (word & 0x00FF00FF) + ((word & 0xFF00FF00) >> 8); // >= 16 bits.
454
#ifdef BITMAP_LEAF32x8
455
word = (word & 0x0000FFFF) + ((word & 0xFFFF0000) >> 16); // >= 32 bits.
460
word = (word & 0x5555555555555555) + ((word & 0xAAAAAAAAAAAAAAAA) >> 1);
461
word = (word & 0x3333333333333333) + ((word & 0xCCCCCCCCCCCCCCCC) >> 2);
462
word = (word & 0x0F0F0F0F0F0F0F0F) + ((word & 0xF0F0F0F0F0F0F0F0) >> 4);
463
#if defined(BITMAP_LEAF16x16) || defined(BITMAP_LEAF32x8) || defined(BITMAP_LEAF64x4)
464
word = (word & 0x00FF00FF00FF00FF) + ((word & 0xFF00FF00FF00FF00) >> 8);
466
#if defined(BITMAP_LEAF32x8) || defined(BITMAP_LEAF64x4)
467
word = (word & 0x0000FFFF0000FFFF) + ((word & 0xFFFF0000FFFF0000) >>16);
469
#ifdef BITMAP_LEAF64x4
470
word = (word & 0x00000000FFFFFFFF) + ((word & 0xFFFFFFFF00000000) >>32);
476
} // __JudyCountBitsL()
478
#endif // JU_NOINLINE
483
// ****************************************************************************
484
// J U D Y C H E C K S O R T E D
486
// Given a pointer to a packed list of Pop1 N-byte indexes (N = IndexSize),
487
// assert that the list is in order.
489
FUNCTION void JudyCheckSorted(
490
Pjll_t Pjll, // leaf or list to check.
491
Word_t Pop1, // number of indexes to check.
492
long IndexSize) // bytes per index in list.
495
// Macros for common code:
497
// Check a list of "even"-sized indexes, counting backwards from last to first:
499
// Pjll and Pop1 are in the context.
501
#define JU_CHECKSORTED(PType) \
503
assert(((PType) Pjll)[Pop1 - 1] < ((PType) Pjll)[Pop1]); \
506
// Check a list of "odd"-sized indexes, which requires first copying each one
507
// to an aligned word:
509
// Pjll, Pop1, and IndexSize are in the context.
511
#define JU_CHECKSORTED_ODD(CopyIndex) \
517
CopyIndex(indexlow, (uint8_t *) Pjll); \
519
for (offset = 1; offset < Pop1; ++offset) \
521
CopyIndex(indexhigh, \
522
((uint8_t *) Pjll) + (offset * IndexSize)); \
523
assert(indexlow < indexhigh); \
524
indexlow = indexhigh; \
531
case 1: JU_CHECKSORTED(uint8_t *);
532
case 2: JU_CHECKSORTED(uint16_t *);
533
case 3: JU_CHECKSORTED_ODD(JU_COPY3_PINDEX_TO_LONG);
534
case 4: JU_CHECKSORTED(uint32_t *);
536
case 5: JU_CHECKSORTED_ODD(JU_COPY5_PINDEX_TO_LONG);
537
case 6: JU_CHECKSORTED_ODD(JU_COPY6_PINDEX_TO_LONG);
538
case 7: JU_CHECKSORTED_ODD(JU_COPY7_PINDEX_TO_LONG);
539
case 8: JU_CHECKSORTED(Pjlw_t);
541
default: assert(FALSE); // invalid IndexSize.
544
} // JudyCheckSorted()
548
#endif // _JUDYSEARCHLEAF
added
removed
src/JudyCommon/JudySearchLeaf.c
