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.10 $ $Source: /judy/src/JudyCommon/JudySearchLeafOdd.c $
20
// This source file contains the body of a __JudySearchLeaf*() function for an
21
// "odd" index size (BPI): 3, 5, 6, or 7 bytes. You can think of this file
22
// as a huge macro for generating efficient code for different sized indexes
23
// but always following the same template. Unlike a real macro, this separate
24
// file can contain comments and is easier to read and maintain.
26
// This code must be #include'd by another source file, possibly multiple
27
// times, each time with the standard __JudySearchLeaf*() parameters present:
33
// and the following macros redefined appropriately for the including function:
35
// BPI bytes per index
36
// IPC indexes per cache line
37
// IPG indexes per index group
38
// WPG words per index group
39
// MASK for BPI LSB of a word
40
// GET_* macros for getting an aligned index
41
// IPG_BIG set if IPG = 8; otherwise unset
42
// JU_COPY_PINDEX_TO_LONG one of JU_COPY*_PINDEX_TO_LONG
45
#ifndef BRUTE_FORCE // ========================================================
47
PWord_t Pword = (PWord_t) Pjll; // first word of index group.
48
Word_t offset = 0; // offset of index in leaf.
49
Word_t testindex; // aligned copy to check against Index.
51
assert((LeafPop1 * BPI) <= (cJU_BYTESPERCL * 2)); // <= 2 cache lines.
52
DBGCODE(JudyCheckSorted(Pjll, LeafPop1, (long) BPI);)
55
// HANDLE LEAF POPULATION GREATER THAN ONE CACHE LINE:
57
// Extract a BPI-byte Index near the end of the first cache line to compare.
58
// If it's too low, move to the following Index, which must be left-aligned in
59
// a word, which establishes which previous Index to use for comparison. In
60
// other words, the comparison point is not actually the cache line boundary,
61
// but the last word at or prior to it where an index ends at a word boundary.
63
// TBD: In rare cases this moves to the next "virtual" cache line when in fact
64
// the leaf fits entirely in a single real cache line. Is this a problem?
66
Index &= MASK; // look for last BPI bytes only.
70
// first virtual cache line, last index group, first word:
71
Pword += ((IPC * BPI) / cJU_BYTESPERWORD) - WPG;
72
testindex = GET_LIG; // last index in group.
74
if (Index <= testindex) // match, if any, in first cache line:
76
Pword = (PWord_t) Pjll; // reset to start.
77
LeafPop1 = IPC; // truncate.
79
else // match, if any, in second cache line:
81
Pword += WPG; // first word of next index group.
82
LeafPop1 -= IPC; // skip first virtual cache line.
88
// SEARCH FOR INDEX GROUP IN ONE CACHE LINE:
90
// Test and skip one index group (WPG words) at a time, using the (aligned)
91
// last of IPG indexes in each group. This is a serial search, but because it
92
// checks IPG indexes at a time, it compares well with a binary search for this
93
// small of an object.
95
while (LeafPop1 >= IPG) // whole index group remains.
97
testindex = GET_LIG; // check last index in group.
99
if (Index <= testindex) // in this group, if present.
101
if (Index == testindex) // found desired Index...
102
return(offset + IPG - 1); // is last in this group.
104
break; // match, if any, is in this group.
107
Pword += WPG; // next index group:
113
// SEARCH ONE INDEX GROUP:
115
// Now the search is narrowed to a small group of indexes with a known
116
// alignment (hidden in the GET_*() macros), where the last index in the group
117
// is known to be too high or does not exist. Pword points to the first word
118
// of the group, and offset is the base-0 ordinal of the first index in the
119
// group. Note that LeafPop1 might be < IPG, that is, this might not be a full
122
// TBD: This section "knows" (embodies) the value of IPG for 32/64-bit. In
123
// other words, using the cases below for speed, rather than a loop, depends on
124
// specific values of IPG.
126
// Shorthand macro for testing the index at Offset2 in an index group using a
127
// specified GET_* macro. If an absent index (Index > testindex) or a matching
128
// index (Index == testindex) is not found at this Offset2, each case falls
129
// through into the next one (lower Offset2).
131
#define CHECKINDEX(GET,Offset2) \
133
if (Index > testindex) return(~(offset + (Offset2) + 1)); \
134
if (Index == testindex) return( offset + (Offset2))
138
default: // case 4 [8]: fall through to check previous index:
140
case 7: CHECKINDEX(GET_6, 6);
141
case 6: CHECKINDEX(GET_5, 5);
142
case 5: CHECKINDEX(GET_4, 4);
143
case 4: CHECKINDEX(GET_3, 3);
145
case 3: CHECKINDEX(GET_2, 2);
146
case 2: CHECKINDEX(GET_1, 1);
147
case 1: CHECKINDEX(GET_0, 0);
148
case 0: break; // none left => not found.
151
return(~offset); // Index not found.
153
#else // BRUTE_FORCE ==========================================================
155
// BRUTE FORCE = LINEAR SEARCH:
157
// Scanning every index, including copying it to an aligned word for comparison
158
// with Index, is slower than the grouping method used above.
160
uint8_t * Pleaf = (uint8_t *) Pjll; // first byte of leaf.
161
Word_t testindex; // aligned copy to check against Index.
162
Word_t LeafIndexes = LeafPop1;
164
DBGCODE(JudyCheckSorted(Pjll, LeafPop1, (long) BPI);)
166
Index &= MASK; // look for last BPI bytes only.
169
JU_COPY_PINDEX_TO_LONG(testindex, Pleaf);
171
if (Index <= testindex)
173
if (Index == testindex) return(LeafIndexes - LeafPop1);
181
return(~(LeafIndexes - LeafPop1)); // Index not found.
183
#endif // BRUTE_FORCE
185
} // JudySearchLeafOdd.c function body
added
removed
src/JudyCommon/JudySearchLeafOdd.c
