1 #ifndef _JUDYPRIVATE_INCLUDED
2 #define _JUDYPRIVATE_INCLUDED
3 // _________________
4 //
5 // Copyright (C) 2000 - 2002 Hewlett-Packard Company
6 //
7 // This program is free software; you can redistribute it and/or modify it
8 // under the term of the GNU Lesser General Public License as published by the
9 // Free Software Foundation; either version 2 of the License, or (at your
10 // option) any later version.
11 //
12 // This program is distributed in the hope that it will be useful, but WITHOUT
13 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
15 // for more details.
16 //
17 // You should have received a copy of the GNU Lesser General Public License
18 // along with this program; if not, write to the Free Software Foundation,
19 // Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 // _________________
21
22 // Header file for all Judy sources, for global but private (non-exported)
23 // declarations.
24
25 #include "Judy.h"
26
27 // ****************************************************************************
28 // A VERY BRIEF EXPLANATION OF A JUDY ARRAY
29 //
30 // A Judy array is, effectively, a digital tree (or Trie) with 256 element
31 // branches (nodes), and with "compression tricks" applied to low-population
32 // branches or leaves to save a lot of memory at the cost of relatively little
33 // CPU time or cache fills.
34 //
35 // In the actual implementation, a Judy array is level-less, and traversing the
36 // "tree" actually means following the states in a state machine (SM) as
37 // directed by the Index. A Judy array is referred to here as an "SM", rather
38 // than as a "tree"; having "states", rather than "levels".
39 //
40 // Each branch or leaf in the SM decodes a portion ("digit") of the original
41 // Index; with 256-way branches there are 8 bits per digit. There are 3 kinds
42 // of branches, called: Linear, Bitmap and Uncompressed, of which the first 2
43 // are compressed to contain no NULL entries.
44 //
45 // An Uncompressed branch has a 1.0 cache line fill cost to decode 8 bits of
46 // (digit, part of an Index), but it might contain many NULL entries, and is
47 // therefore inefficient with memory if lightly populated.
48 //
49 // A Linear branch has a ~1.75 cache line fill cost when at maximum population.
50 // A Bitmap branch has ~2.0 cache line fills. Linear and Bitmap branches are
51 // converted to Uncompressed branches when the additional memory can be
52 // amortized with larger populations. Higher-state branches have higher
53 // priority to be converted.
54 //
55 // Linear branches can hold 28 elements (based on detailed analysis) -- thus 28
56 // expanses. A Linear branch is converted to a Bitmap branch when the 29th
57 // expanse is required.
58 //
59 // A Bitmap branch could hold 256 expanses, but is forced to convert to an
60 // Uncompressed branch when 185 expanses are required. Hopefully, it is
61 // converted before that because of population growth (again, based on detailed
62 // analysis and heuristics in the code).
63 //
64 // A path through the SM terminates to a leaf when the Index (or key)
65 // population in the expanse below a pointer will fit into 1 or 2 cache lines
66 // (~31..255 Indexes). A maximum-population Leaf has ~1.5 cache line fill
67 // cost.
68 //
69 // Leaves are sorted arrays of Indexes, where the Index Sizes (IS) are: 0, 1,
70 // 8, 16, 24, 32, [40, 48, 56, 64] bits. The IS depends on the "density"
71 // (population/expanse) of the values in the Leaf. Zero bits are possible if
72 // population == expanse in the SM (that is, a full small expanse).
73 //
74 // Elements of a branches are called Judy Pointers (JPs). Each JP object
75 // points to the next object in the SM, plus, a JP can decode an additional
76 // 2[6] bytes of an Index, but at the cost of "narrowing" the expanse
77 // represented by the next object in the SM. A "narrow" JP (one which has
78 // decode bytes/digits) is a way of skipping states in the SM.
79 //
80 // Although counterintuitive, we think a Judy SM is optimal when the Leaves are
81 // stored at MINIMUM compression (narrowing, or use of Decode bytes). If more
82 // aggressive compression was used, decompression of a leaf be required to
83 // insert an index. Additional compression would save a little memory but not
84 // help performance significantly.
85
86
87 #ifdef A_PICTURE_IS_WORTH_1000_WORDS
88 *******************************************************************************
89
90 JUDY 32-BIT STATE MACHINE (SM) EXAMPLE, FOR INDEX = 0x02040103
91
92 The Index used in this example is purposely chosen to allow small, simple
93 examples below; each 1-byte "digit" from the Index has a small numeric value
94 that fits in one column. In the drawing below:
95
96 JRP == Judy Root Pointer;
97
98 C == 1 byte of a 1..3 byte Population (count of Indexes) below this
99 pointer. Since this is shared with the Decode field, the combined
100 sizes must be 3[7], that is, 1 word less 1 byte for the JP Type.
101
102 The 1-byte field jp_Type is represented as:
103
104 1..3 == Number of bytes in the population (Pop0) word of the Branch or Leaf
105 below the pointer (note: 1..7 on 64-bit); indicates:
106 - number of bytes in Decode field == 3 - this number;
107 - number of bytes remaining to decode.
108 Note: The maximum is 3, not 4, because the 1st byte of the Index is
109 always decoded digitally in the top branch.
110 -B- == JP points to a Branch (there are many kinds of Branches).
111 -L- == JP points to a Leaf (there are many kinds of Leaves).
112
113 (2) == Digit of Index decoded by position offset in branch (really
114 0..0xff).
115
116 4* == Digit of Index necessary for decoding a "narrow" pointer, in a
117 Decode field; replaces 1 missing branch (really 0..0xff).
118
119 4+ == Digit of Index NOT necessary for decoding a "narrow" pointer, but
120 used for fast traversal of the SM by Judy1Test() and JudyLGet()
121 (see the code) (really 0..0xff).
122
123 0 == Byte in a JPs Pop0 field that is always ignored, because a leaf
124 can never contain more than 256 Indexes (Pop0 <= 255).
125
126 +----- == A Branch or Leaf; drawn open-ended to remind you that it could
127 | have up to 256 columns.
128 +-----
129
130 |
131 | == Pointer to next Branch or Leaf.
132 V
133
134 |
135 O == A state is skipped by using a "narrow" pointer.
136 |
137
138 < 1 > == Digit (Index) shown as an example is not necessarily in the
139 position shown; is sorted in order with neighbor Indexes.
140 (Really 0..0xff.)
141
142 Note that this example shows every possibly topology to reach a leaf in a
143 32-bit Judy SM, although this is a very subtle point!
144
145 STATE or`
146 LEVEL
147 +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
148 |RJP| |RJP| |RJP| |RJP| |RJP| |RJP| |RJP| |RJP|
149 L---+ B---+ B---+ B---+ B---+ B---+ B---+ B---+
150 | | | | | | | |
151 | | | | | | | |
152 V V (2) V (2) V (2) V (2) V (2) V (2) V (2)
153 +------ +------ +------ +------ +------ +------ +------ +------
154 Four |< 2 > | 0 | 4* | C | 4* | 4* | C | C
155 byte |< 4 > | 0 | 0 | C | 1* | C | C | C 4
156 Index|< 1 > | C | C | C | C | C | C | C
157 Leaf |< 3 > | 3 | 2 | 3 | 1 | 2 | 3 | 3
158 +------ +--L--- +--L--- +--B--- +--L--- +--B--- +--B--- +--B---
159 | | | | | | |
160 / | / | | / /
161 / | / | | / /
162 | | | | | | |
163 V | V (4) | | V (4) V (4)
164 +------ | +------ | | +------ +------
165 Three |< 4 > | | 4+ | | | 4+ | 4+
166 byte Index|< 1 > O | 0 O O | 1* | C 3
167 Leaf |< 3 > | | C | | | C | C
168 +------ | | 2 | | | 1 | 2
169 / +----L- | | +----L- +----B-
170 / | | | | |
171 | / | / / /
172 | / | / / /
173 | / | | / /
174 | / | | / /
175 | | | | | |
176 V V | V(1) | V(1)
177 +------ +------ | +------ | +------
178 Two byte |< 1 > |< 1 > | | 4+ | | 4+
179 Index Leaf |< 3 > |< 3 > O | 1+ O | 1+ 2
180 +------ +------ / | C | | C
181 / | 1 | | 1
182 | +-L---- | +-L----
183 | | | |
184 | / | /
185 | | | |
186 V V V V
187 +------ +------ +------ +------
188 One byte Index Leaf |< 3 > |< 3 > |< 3 > |< 3 > 1
189 +------ +------ +------ +------
190
191
192 #endif // A_PICTURE_IS_WORTH_1000_WORDS
193
194
195 // ****************************************************************************
196 // MISCELLANEOUS GLOBALS:
197 //
198 // PLATFORM-SPECIFIC CONVENIENCE MACROS:
199 //
200 // These are derived from context (set by cc or in system header files) or
201 // based on JU_<PLATFORM> macros from make_includes/platform.*.mk. We decided
202 // on 011018 that any macro reliably derivable from context (cc or headers) for
203 // ALL platforms supported by Judy is based on that derivation, but ANY
204 // exception means to stop using the external macro completely and derive from
205 // JU_<PLATFORM> instead.
206
207 // Other miscellaneous stuff:
208
209 #ifndef _BOOL_T
210 #define _BOOL_T
211 typedef int bool_t;
212 #endif
213
214 #define FUNCTION // null; easy to find functions.
215
216 #ifndef TRUE
217 #define TRUE 1
218 #endif
219
220 #ifndef FALSE
221 #define FALSE 0
222 #endif
223
224 #ifdef TRACE // turn on all other tracing in the code:
225 #define TRACEJP 1 // JP traversals in JudyIns.c and JudyDel.c.
226 #define TRACEJPR 1 // JP traversals in retrieval code, JudyGet.c.
227 #define TRACECF 1 // cache fills in JudyGet.c.
228 #define TRACEMI 1 // malloc calls in JudyMallocIF.c.
229 #define TRACEMF 1 // malloc calls at a lower level in JudyMalloc.c.
230 #endif
231
232 #ifndef inline
233 #define inline __inline__
234 #endif
235
236 // SUPPORT FOR DEBUG-ONLY CODE:
237 //
238 // By convention, use -DDEBUG to enable both debug-only code AND assertions in
239 // the Judy sources.
240 //
241 // Invert the sense of assertions, so they are off unless explicitly requested,
242 // in a uniform way.
243 //
244 // Note: It is NOT appropriate to put this in Judy.h; it would mess up
245 // application code.
246
247 #ifndef DEBUG
248 #define NDEBUG 1 // must be 1 for "#if".
249 #endif
250
251 // Shorthand notations to avoid #ifdefs for single-line conditional statements:
252 //
253 // Warning: These cannot be used around compiler directives, such as
254 // "#include", nor in the case where Code contains a comma other than nested
255 // within parentheses or quotes.
256
257 #define DBGCODE(Code) /* nothing */
258
259 #ifdef JUDY1
260 #define JUDY1CODE(Code) Code
261 #define JUDYLCODE(Code) // null.
262 #endif
263
264 #ifdef JUDYL
265 #define JUDYLCODE(Code) Code
266 #define JUDY1CODE(Code) // null.
267 #endif
268
269 #include <assert.h>
270
271 // ****************************************************************************
272 // FUNDAMENTAL CONSTANTS FOR MACHINE
273 // ****************************************************************************
274
275 // Machine (CPU) cache line size:
276 //
277 // NOTE: A leaf size of 2 cache lines maximum is the target (optimal) for
278 // Judy. Its hard to obtain a machines cache line size at compile time, but
279 // if the machine has an unexpected cache line size, its not devastating if
280 // the following constants end up causing leaves that are 1 cache line in size,
281 // or even 4 cache lines in size. The assumed 32-bit system has 16-word =
282 // 64-byte cache lines, and the assumed 64-bit system has 16-word = 128-byte
283 // cache lines.
284
285 #ifdef JU_64BIT
286 #define cJU_BYTESPERCL 128 // cache line size in bytes.
287 #else
288 #define cJU_BYTESPERCL 64 // cache line size in bytes.
289 #endif
290
291 // Bits Per Byte:
292
293 #define cJU_BITSPERBYTE 0x8
294
295 // Bytes Per Word and Bits Per Word, latter assuming sizeof(byte) is 8 bits:
296 //
297 // Expect 32 [64] bits per word.
298
299 #define cJU_BYTESPERWORD (sizeof(Word_t))
300 #define cJU_BITSPERWORD (sizeof(Word_t) * cJU_BITSPERBYTE)
301
302 #define JU_BYTESTOWORDS(BYTES) \
303 (((BYTES) + cJU_BYTESPERWORD - 1) / cJU_BYTESPERWORD)
304
305 // A word that is all-ones, normally equal to -1UL, but safer with ~0:
306
307 #define cJU_ALLONES (~ ( Word_t ) 0UL)
308
309 // Note, these are forward references, but thats OK:
310
311 #define cJU_FULLBITMAPB ((BITMAPB_t) cJU_ALLONES)
312 #define cJU_FULLBITMAPL ((BITMAPL_t) cJU_ALLONES)
313
314
315 // ****************************************************************************
316 // MISCELLANEOUS JUDY-SPECIFIC DECLARATIONS
317 // ****************************************************************************
318
319 // ROOT STATE:
320 //
321 // State at the start of the Judy SM, based on 1 byte decoded per state; equal
322 // to the number of bytes per Index to decode.
323
324 #define cJU_ROOTSTATE (sizeof(Word_t))
325
326
327 // SUBEXPANSES PER STATE:
328 //
329 // Number of subexpanses per state traversed, which is the number of JPs in a
330 // branch (actual or theoretical) and the number of bits in a bitmap.
331
332 #define cJU_SUBEXPPERSTATE 256
333
334
335 // LEAF AND VALUE POINTERS:
336 //
337 // Some other basic object types are in declared in JudyPrivateBranch.h
338 // (Pjbl_t, Pjbb_t, Pjbu_t, Pjp_t) or are Judy1/L-specific (Pjlb_t). The
339 // few remaining types are declared below.
340 //
341 // Note: Leaf pointers are cast to different-sized objects depending on the
342 // leafs level, but are at least addresses (not just numbers), so use void *
343 // (Pvoid_t), not PWord_t or Word_t for them, except use Pjlw_t for whole-word
344 // (top-level, root-level) leaves. Value areas, however, are always whole
345 // words.
346 //
347 // Furthermore, use Pjll_t only for generic leaf pointers (for various size
348 // LeafLs). Use Pjlw_t for LeafWs. Use Pleaf (with type uint8_t *, uint16_t
349 // *, etc) when the leaf index size is known.
350
351 typedef PWord_t Pjlw_t; // pointer to root-level leaf (whole-word indexes).
352 typedef Pvoid_t Pjll_t; // pointer to lower-level linear leaf.
353
354 #ifdef JUDYL
355 typedef PWord_t Pjv_t; // pointer to JudyL value area.
356 #endif
357
358
359 // POINTER PREPARATION MACROS:
360 //
361 // These macros are used to strip malloc-namespace-type bits from a pointer +
362 // malloc-type word (which references any Judy mallocd object that might be
363 // obtained from other than a direct call of malloc()), prior to dereferencing
364 // the pointer as an address. The malloc-type bits allow Judy mallocd objects
365 // to come from different "malloc() namespaces".
366 //
367 // (root pointer) (JRP, see above)
368 // jp.jp_Addr generic pointer to next-level node, except when used
369 // as a JudyL Immed01 value area
370 // JU_JBB_PJP macro hides jbbs_Pjp (pointer to JP subarray)
371 // JL_JLB_PVALUE macro hides jLlbs_PValue (pointer to value subarray)
372 //
373 // When setting one of these fields or passing an address to j__udyFree*(), the
374 // "raw" memory address is used; otherwise the memory address must be passed
375 // through one of the macros below before its dereferenced.
376 //
377 // Note: After much study, the typecasts below appear in the macros rather
378 // than at the point of use, which is both simpler and allows the compiler to
379 // do type-checking.
380
381
382 #define P_JLW( ADDR) ((Pjlw_t) (ADDR)) // root leaf.
383 #define P_JPM( ADDR) ((Pjpm_t) (ADDR)) // root JPM.
384 #define P_JBL( ADDR) ((Pjbl_t) (ADDR)) // BranchL.
385 #define P_JBB( ADDR) ((Pjbb_t) (ADDR)) // BranchB.
386 #define P_JBU( ADDR) ((Pjbu_t) (ADDR)) // BranchU.
387 #define P_JLL( ADDR) ((Pjll_t) (ADDR)) // LeafL.
388 #define P_JLB( ADDR) ((Pjlb_t) (ADDR)) // LeafB1.
389 #define P_JP( ADDR) ((Pjp_t) (ADDR)) // JP.
390
391 #ifdef JUDYL
392 #define P_JV( ADDR) ((Pjv_t) (ADDR)) // &value.
393 #endif
394
395
396 // LEAST BYTES:
397 //
398 // Mask for least bytes of a word, and a macro to perform this mask on an
399 // Index.
400 //
401 // Note: This macro has been problematic in the past to get right and to make
402 // portable. Its not OK on all systems to shift by the full word size. This
403 // macro should allow shifting by 1..N bytes, where N is the word size, but
404 // should produce a compiler warning if the macro is called with Bytes == 0.
405 //
406 // Warning: JU_LEASTBYTESMASK() is not a constant macro unless Bytes is a
407 // constant; otherwise it is a variable shift, which is expensive on some
408 // processors.
409
410 #define JU_LEASTBYTESMASK(BYTES) \
411 (((Word_t)0x100 << (cJU_BITSPERBYTE * ((BYTES) - 1))) - 1)
412
413 #define JU_LEASTBYTES(INDEX,BYTES) ((INDEX) & JU_LEASTBYTESMASK(BYTES))
414
415
416 // BITS IN EACH BITMAP SUBEXPANSE FOR BITMAP BRANCH AND LEAF:
417 //
418 // The bits per bitmap subexpanse times the number of subexpanses equals a
419 // constant (cJU_SUBEXPPERSTATE). You can also think of this as a compile-time
420 // choice of "aspect ratio" for bitmap branches and leaves (which can be set
421 // independently for each).
422 //
423 // A default aspect ratio is hardwired here if not overridden at compile time,
424 // such as by "EXTCCOPTS=-DBITMAP_BRANCH16x16 make".
425
426 #if (! (defined(BITMAP_BRANCH8x32) || defined(BITMAP_BRANCH16x16) || defined(BITMAP_BRANCH32x8)))
427 #define BITMAP_BRANCH32x8 1 // 32 bits per subexpanse, 8 subexpanses.
428 #endif
429
430 #ifdef BITMAP_BRANCH8x32
431 #define BITMAPB_t uint8_t
432 #endif
433
434 #ifdef BITMAP_BRANCH16x16
435 #define BITMAPB_t uint16_t
436 #endif
437
438 #ifdef BITMAP_BRANCH32x8
439 #define BITMAPB_t uint32_t
440 #endif
441
442 // Note: For bitmap leaves, BITMAP_LEAF64x4 is only valid for 64 bit:
443 //
444 // Note: Choice of aspect ratio mostly matters for JudyL bitmap leaves. For
445 // Judy1 the choice doesnt matter much -- the code generated for different
446 // BITMAP_LEAF* values choices varies, but correctness and performance are the
447 // same.
448
449 #ifndef JU_64BIT
450
451 #if (! (defined(BITMAP_LEAF8x32) || defined(BITMAP_LEAF16x16) || defined(BITMAP_LEAF32x8)))
452 #define BITMAP_LEAF32x8 // 32 bits per subexpanse, 8 subexpanses.
453 #endif
454
455 #else // 32BIT
456
457 #if (! (defined(BITMAP_LEAF8x32) || defined(BITMAP_LEAF16x16) || defined(BITMAP_LEAF32x8) || defined(BITMAP_LEAF64x4)))
458 #define BITMAP_LEAF64x4 // 64 bits per subexpanse, 4 subexpanses.
459
460 #endif
461 #endif // JU_64BIT
462
463 #ifdef BITMAP_LEAF8x32
464 #define BITMAPL_t uint8_t
465 #endif
466
467 #ifdef BITMAP_LEAF16x16
468 #define BITMAPL_t uint16_t
469 #endif
470
471 #ifdef BITMAP_LEAF32x8
472 #define BITMAPL_t uint32_t
473 #endif
474
475 #ifdef BITMAP_LEAF64x4
476 #define BITMAPL_t uint64_t
477 #endif
478
479
480 // EXPORTED DATA AND FUNCTIONS:
481
482 #ifdef JUDY1
483 extern const uint8_t j__1_BranchBJPPopToWords[];
484 #endif
485
486 #ifdef JUDYL
487 extern const uint8_t j__L_BranchBJPPopToWords[];
488 #endif
489
490 // Fast LeafL search routine used for inlined code:
491
492 #if (! defined(SEARCH_BINARY)) || (! defined(SEARCH_LINEAR))
493 // default a binary search leaf method
494 #define SEARCH_BINARY 1
495 //#define SEARCH_LINEAR 1
496 #endif
497
498 #ifdef SEARCH_LINEAR
499
500 #define SEARCHLEAFNATIVE(LEAFTYPE,ADDR,POP1,INDEX) \
501 LEAFTYPE *P_leaf = (LEAFTYPE *)(ADDR); \
502 LEAFTYPE I_ndex = (INDEX); /* with masking */ \
503 if (I_ndex > P_leaf[(POP1) - 1]) return(~(POP1)); \
504 while(I_ndex > *P_leaf) P_leaf++; \
505 if (I_ndex == *P_leaf) return(P_leaf - (LEAFTYPE *)(ADDR)); \
506 return(~(P_leaf - (LEAFTYPE *)(ADDR)));
507
508
509 #define SEARCHLEAFNONNAT(ADDR,POP1,INDEX,LFBTS,COPYINDEX) \
510 { \
511 uint8_t *P_leaf, *P_leafEnd; \
512 Word_t i_ndex; \
513 Word_t I_ndex = JU_LEASTBYTES((INDEX), (LFBTS)); \
514 Word_t p_op1; \
515 \
516 P_leaf = (uint8_t *)(ADDR); \
517 P_leafEnd = P_leaf + ((POP1) * (LFBTS)); \
518 \
519 do { \
520 JU_COPY3_PINDEX_TO_LONG(i_ndex, P_leaf); \
521 if (I_ndex <= i_ndex) break; \
522 P_leaf += (LFBTS); \
523 } while (P_leaf < P_leafEnd); \
524 \
525 p_op1 = (P_leaf - (uint8_t *) (ADDR)) / (LFBTS); \
526 if (I_ndex == i_ndex) return(p_op1); \
527 return(~p_op1); \
528 }
529 #endif // SEARCH_LINEAR
530
531 #ifdef SEARCH_BINARY
532
533 #define SEARCHLEAFNATIVE(LEAFTYPE,ADDR,POP1,INDEX) \
534 LEAFTYPE *P_leaf = (LEAFTYPE *)(ADDR); \
535 LEAFTYPE I_ndex = (LEAFTYPE)INDEX; /* truncate hi bits */ \
536 Word_t l_ow = cJU_ALLONES; \
537 Word_t m_id; \
538 Word_t h_igh = POP1; \
539 \
540 while ((h_igh - l_ow) > 1UL) \
541 { \
542 m_id = (h_igh + l_ow) / 2; \
543 if (P_leaf[m_id] > I_ndex) \
544 h_igh = m_id; \
545 else \
546 l_ow = m_id; \
547 } \
548 if (l_ow == cJU_ALLONES || P_leaf[l_ow] != I_ndex) \
549 return(~h_igh); \
550 return(l_ow)
551
552
553 #define SEARCHLEAFNONNAT(ADDR,POP1,INDEX,LFBTS,COPYINDEX) \
554 uint8_t *P_leaf = (uint8_t *)(ADDR); \
555 Word_t l_ow = cJU_ALLONES; \
556 Word_t m_id; \
557 Word_t h_igh = POP1; \
558 Word_t I_ndex = JU_LEASTBYTES((INDEX), (LFBTS)); \
559 Word_t i_ndex; \
560 \
561 I_ndex = JU_LEASTBYTES((INDEX), (LFBTS)); \
562 \
563 while ((h_igh - l_ow) > 1UL) \
564 { \
565 m_id = (h_igh + l_ow) / 2; \
566 COPYINDEX(i_ndex, &P_leaf[m_id * (LFBTS)]); \
567 if (i_ndex > I_ndex) \
568 h_igh = m_id; \
569 else \
570 l_ow = m_id; \
571 } \
572 if (l_ow == cJU_ALLONES) return(~h_igh); \
573 \
574 COPYINDEX(i_ndex, &P_leaf[l_ow * (LFBTS)]); \
575 if (i_ndex != I_ndex) return(~h_igh); \
576 return(l_ow)
577
578 #endif // SEARCH_BINARY
579
580 // Fast way to count bits set in 8..32[64]-bit int:
581 //
582 // For performance, j__udyCountBits*() are written to take advantage of
583 // platform-specific features where available.
584 //
585
586 #ifdef JU_NOINLINE
587
588 extern BITMAPB_t j__udyCountBitsB(BITMAPB_t word);
589 extern BITMAPL_t j__udyCountBitsL(BITMAPL_t word);
590
591 // Compiler supports inline
592
593 #elif defined(JU_HPUX_IPF)
594
595 #define j__udyCountBitsB(WORD) _Asm_popcnt(WORD)
596 #define j__udyCountBitsL(WORD) _Asm_popcnt(WORD)
597
598 #elif defined(JU_LINUX_IPF)
599
j__udyCountBitsB(BITMAPB_t word)600 static inline BITMAPB_t j__udyCountBitsB(BITMAPB_t word)
601 {
602 BITMAPB_t result;
603 __asm__ ("popcnt %0=%1" : "=r" (result) : "r" (word));
604 return(result);
605 }
606
j__udyCountBitsL(BITMAPL_t word)607 static inline BITMAPL_t j__udyCountBitsL(BITMAPL_t word)
608 {
609 BITMAPL_t result;
610 __asm__ ("popcnt %0=%1" : "=r" (result) : "r" (word));
611 return(result);
612 }
613
614
615 #else // No instructions available, use inline code
616
617 // ****************************************************************************
618 // __ J U D Y C O U N T B I T S B
619 //
620 // Return the number of bits set in "Word", for a bitmap branch.
621 //
622 // Note: Bitmap branches have maximum bitmap size = 32 bits.
623
624 #ifdef JU_WIN
j__udyCountBitsB(BITMAPB_t word)625 static __inline BITMAPB_t j__udyCountBitsB(BITMAPB_t word)
626 #else
627 static inline BITMAPB_t j__udyCountBitsB(BITMAPB_t word)
628 #endif
629 {
630 word = (word & 0x55555555) + ((word & 0xAAAAAAAA) >> 1);
631 word = (word & 0x33333333) + ((word & 0xCCCCCCCC) >> 2);
632 word = (word & 0x0F0F0F0F) + ((word & 0xF0F0F0F0) >> 4); // >= 8 bits.
633 #if defined(BITMAP_BRANCH16x16) || defined(BITMAP_BRANCH32x8)
634 word = (word & 0x00FF00FF) + ((word & 0xFF00FF00) >> 8); // >= 16 bits.
635 #endif
636
637 #ifdef BITMAP_BRANCH32x8
638 word = (word & 0x0000FFFF) + ((word & 0xFFFF0000) >> 16); // >= 32 bits.
639 #endif
640 return(word);
641
642 } // j__udyCountBitsB()
643
644
645 // ****************************************************************************
646 // __ J U D Y C O U N T B I T S L
647 //
648 // Return the number of bits set in "Word", for a bitmap leaf.
649 //
650 // Note: Bitmap branches have maximum bitmap size = 32 bits.
651
652 // Note: Need both 32-bit and 64-bit versions of j__udyCountBitsL() because
653 // bitmap leaves can have 64-bit bitmaps.
654
655 #ifdef JU_WIN
j__udyCountBitsL(BITMAPL_t word)656 static __inline BITMAPL_t j__udyCountBitsL(BITMAPL_t word)
657 #else
658 static inline BITMAPL_t j__udyCountBitsL(BITMAPL_t word)
659 #endif
660 {
661 #ifndef JU_64BIT
662
663 word = (word & 0x55555555) + ((word & 0xAAAAAAAA) >> 1);
664 word = (word & 0x33333333) + ((word & 0xCCCCCCCC) >> 2);
665 word = (word & 0x0F0F0F0F) + ((word & 0xF0F0F0F0) >> 4); // >= 8 bits.
666 #if defined(BITMAP_LEAF16x16) || defined(BITMAP_LEAF32x8)
667 word = (word & 0x00FF00FF) + ((word & 0xFF00FF00) >> 8); // >= 16 bits.
668 #endif
669 #ifdef BITMAP_LEAF32x8
670 word = (word & 0x0000FFFF) + ((word & 0xFFFF0000) >> 16); // >= 32 bits.
671 #endif
672
673 #else // JU_64BIT
674
675 word = (word & 0x5555555555555555) + ((word & 0xAAAAAAAAAAAAAAAA) >> 1);
676 word = (word & 0x3333333333333333) + ((word & 0xCCCCCCCCCCCCCCCC) >> 2);
677 word = (word & 0x0F0F0F0F0F0F0F0F) + ((word & 0xF0F0F0F0F0F0F0F0) >> 4);
678 #if defined(BITMAP_LEAF16x16) || defined(BITMAP_LEAF32x8) || defined(BITMAP_LEAF64x4)
679 word = (word & 0x00FF00FF00FF00FF) + ((word & 0xFF00FF00FF00FF00) >> 8);
680 #endif
681 #if defined(BITMAP_LEAF32x8) || defined(BITMAP_LEAF64x4)
682 word = (word & 0x0000FFFF0000FFFF) + ((word & 0xFFFF0000FFFF0000) >>16);
683 #endif
684 #ifdef BITMAP_LEAF64x4
685 word = (word & 0x00000000FFFFFFFF) + ((word & 0xFFFFFFFF00000000) >>32);
686 #endif
687 #endif // JU_64BIT
688
689 return(word);
690
691 } // j__udyCountBitsL()
692
693 #endif // Compiler supports inline
694
695 // GET POP0:
696 //
697 // Get from jp_DcdPopO the Pop0 for various JP Types.
698 //
699 // Notes:
700 //
701 // - Different macros require different parameters...
702 //
703 // - There are no simple macros for cJU_BRANCH* Types because their
704 // populations must be added up and dont reside in an already-calculated
705 // place. (TBD: This is no longer true, now its in the JPM.)
706 //
707 // - cJU_JPIMM_POP0() is not defined because it would be redundant because the
708 // Pop1 is already encoded in each enum name.
709 //
710 // - A linear or bitmap leaf Pop0 cannot exceed cJU_SUBEXPPERSTATE - 1 (Pop0 =
711 // 0..255), so use a simpler, faster macro for it than for other JP Types.
712 //
713 // - Avoid any complex calculations that would slow down the compiled code.
714 // Assume these macros are only called for the appropriate JP Types.
715 // Unfortunately theres no way to trigger an assertion here if the JP type
716 // is incorrect for the macro, because these are merely expressions, not
717 // statements.
718
719 #define JU_LEAFW_POP0(JRP) (*P_JLW(JRP))
720 #define cJU_JPFULLPOPU1_POP0 (cJU_SUBEXPPERSTATE - 1)
721
722 // GET JP Type:
723 // Since bit fields greater than 32 bits are not supported in some compilers
724 // the jp_DcdPopO field is expanded to include the jp_Type in the high 8 bits
725 // of the Word_t.
726 // First the read macro:
727
728 #define JU_JPTYPE(PJP) ((PJP)->jp_Type)
729
730 #define JU_JPLEAF_POP0(PJP) ((PJP)->jp_DcdP0[sizeof(Word_t) - 2])
731
732 #ifdef JU_64BIT
733
734 #define JU_JPDCDPOP0(PJP) \
735 ((Word_t)(PJP)->jp_DcdP0[0] << 48 | \
736 (Word_t)(PJP)->jp_DcdP0[1] << 40 | \
737 (Word_t)(PJP)->jp_DcdP0[2] << 32 | \
738 (Word_t)(PJP)->jp_DcdP0[3] << 24 | \
739 (Word_t)(PJP)->jp_DcdP0[4] << 16 | \
740 (Word_t)(PJP)->jp_DcdP0[5] << 8 | \
741 (Word_t)(PJP)->jp_DcdP0[6])
742
743
744 #define JU_JPSETADT(PJP,ADDR,DCDPOP0,TYPE) \
745 { \
746 (PJP)->jp_Addr = (ADDR); \
747 (PJP)->jp_DcdP0[0] = (uint8_t)((Word_t)(DCDPOP0) >> 48); \
748 (PJP)->jp_DcdP0[1] = (uint8_t)((Word_t)(DCDPOP0) >> 40); \
749 (PJP)->jp_DcdP0[2] = (uint8_t)((Word_t)(DCDPOP0) >> 32); \
750 (PJP)->jp_DcdP0[3] = (uint8_t)((Word_t)(DCDPOP0) >> 24); \
751 (PJP)->jp_DcdP0[4] = (uint8_t)((Word_t)(DCDPOP0) >> 16); \
752 (PJP)->jp_DcdP0[5] = (uint8_t)((Word_t)(DCDPOP0) >> 8); \
753 (PJP)->jp_DcdP0[6] = (uint8_t)((Word_t)(DCDPOP0)); \
754 (PJP)->jp_Type = (TYPE); \
755 }
756
757 #else // 32 Bit
758
759 #define JU_JPDCDPOP0(PJP) \
760 ((Word_t)(PJP)->jp_DcdP0[0] << 16 | \
761 (Word_t)(PJP)->jp_DcdP0[1] << 8 | \
762 (Word_t)(PJP)->jp_DcdP0[2])
763
764
765 #define JU_JPSETADT(PJP,ADDR,DCDPOP0,TYPE) \
766 { \
767 (PJP)->jp_Addr = (ADDR); \
768 (PJP)->jp_DcdP0[0] = (uint8_t)((Word_t)(DCDPOP0) >> 16); \
769 (PJP)->jp_DcdP0[1] = (uint8_t)((Word_t)(DCDPOP0) >> 8); \
770 (PJP)->jp_DcdP0[2] = (uint8_t)((Word_t)(DCDPOP0)); \
771 (PJP)->jp_Type = (TYPE); \
772 }
773
774 #endif // 32 Bit
775
776 // NUMBER OF BITS IN A BRANCH OR LEAF BITMAP AND SUBEXPANSE:
777 //
778 // Note: cJU_BITSPERBITMAP must be the same as the number of JPs in a branch.
779
780 #define cJU_BITSPERBITMAP cJU_SUBEXPPERSTATE
781
782 // Bitmaps are accessed in units of "subexpanses":
783
784 #define cJU_BITSPERSUBEXPB (sizeof(BITMAPB_t) * cJU_BITSPERBYTE)
785 #define cJU_NUMSUBEXPB (cJU_BITSPERBITMAP / cJU_BITSPERSUBEXPB)
786
787 #define cJU_BITSPERSUBEXPL (sizeof(BITMAPL_t) * cJU_BITSPERBYTE)
788 #define cJU_NUMSUBEXPL (cJU_BITSPERBITMAP / cJU_BITSPERSUBEXPL)
789
790
791 // MASK FOR A SPECIFIED BIT IN A BITMAP:
792 //
793 // Warning: If BitNum is a variable, this results in a variable shift that is
794 // expensive, at least on some processors. Use with caution.
795 //
796 // Warning: BitNum must be less than cJU_BITSPERWORD, that is, 0 ..
797 // cJU_BITSPERWORD - 1, to avoid a truncated shift on some machines.
798 //
799 // TBD: Perhaps use an array[32] of masks instead of calculating them.
800
801 #define JU_BITPOSMASKB(BITNUM) ((Word_t)1 << ((BITNUM) % cJU_BITSPERSUBEXPB))
802 #define JU_BITPOSMASKL(BITNUM) ((Word_t)1 << ((BITNUM) % cJU_BITSPERSUBEXPL))
803
804
805 // TEST/SET/CLEAR A BIT IN A BITMAP LEAF:
806 //
807 // Test if a byte-sized Digit (portion of Index) has a corresponding bit set in
808 // a bitmap, or set a byte-sized Digits bit into a bitmap, by looking up the
809 // correct subexpanse and then checking/setting the correct bit.
810 //
811 // Note: Mask higher bits, if any, for the convenience of the user of this
812 // macro, in case they pass a full Index, not just a digit. If the caller has
813 // a true 8-bit digit, make it of type uint8_t and the compiler should skip the
814 // unnecessary mask step.
815
816 #define JU_SUBEXPL(DIGIT) (((DIGIT) / cJU_BITSPERSUBEXPL) & (cJU_NUMSUBEXPL-1))
817
818 #define JU_BITMAPTESTL(PJLB, INDEX) \
819 (JU_JLB_BITMAP(PJLB, JU_SUBEXPL(INDEX)) & JU_BITPOSMASKL(INDEX))
820
821 #define JU_BITMAPSETL(PJLB, INDEX) \
822 (JU_JLB_BITMAP(PJLB, JU_SUBEXPL(INDEX)) |= JU_BITPOSMASKL(INDEX))
823
824 #define JU_BITMAPCLEARL(PJLB, INDEX) \
825 (JU_JLB_BITMAP(PJLB, JU_SUBEXPL(INDEX)) ^= JU_BITPOSMASKL(INDEX))
826
827
828 // MAP BITMAP BIT OFFSET TO DIGIT:
829 //
830 // Given a digit variable to set, a bitmap branch or leaf subexpanse (base 0),
831 // the bitmap (BITMAP*_t) for that subexpanse, and an offset (Nth set bit in
832 // the bitmap, base 0), compute the digit (also base 0) corresponding to the
833 // subexpanse and offset by counting all bits in the bitmap until offset+1 set
834 // bits are seen. Avoid expensive variable shifts. Offset should be less than
835 // the number of set bits in the bitmap; assert this.
836 //
837 // If theres a better way to do this, I dont know what it is.
838
839 #define JU_BITMAPDIGITB(DIGIT,SUBEXP,BITMAP,OFFSET) \
840 { \
841 BITMAPB_t bitmap = (BITMAP); int remain = (OFFSET); \
842 (DIGIT) = (SUBEXP) * cJU_BITSPERSUBEXPB; \
843 \
844 while ((remain -= (bitmap & 1)) >= 0) \
845 { \
846 bitmap >>= 1; ++(DIGIT); \
847 assert((DIGIT) < ((SUBEXP) + 1) * cJU_BITSPERSUBEXPB); \
848 } \
849 }
850
851 #define JU_BITMAPDIGITL(DIGIT,SUBEXP,BITMAP,OFFSET) \
852 { \
853 BITMAPL_t bitmap = (BITMAP); int remain = (OFFSET); \
854 (DIGIT) = (SUBEXP) * cJU_BITSPERSUBEXPL; \
855 \
856 while ((remain -= (bitmap & 1)) >= 0) \
857 { \
858 bitmap >>= 1; ++(DIGIT); \
859 assert((DIGIT) < ((SUBEXP) + 1) * cJU_BITSPERSUBEXPL); \
860 } \
861 }
862
863
864 // MASKS FOR PORTIONS OF 32-BIT WORDS:
865 //
866 // These are useful for bitmap subexpanses.
867 //
868 // "LOWER"/"HIGHER" means bits representing lower/higher-valued Indexes. The
869 // exact order of bits in the word is explicit here but is hidden from the
870 // caller.
871 //
872 // "EXC" means exclusive of the specified bit; "INC" means inclusive.
873 //
874 // In each case, BitPos is either "JU_BITPOSMASK*(BitNum)", or a variable saved
875 // from an earlier call of that macro; either way, it must be a 32-bit word
876 // with a single bit set. In the first case, assume the compiler is smart
877 // enough to optimize out common subexpressions.
878 //
879 // The expressions depend on unsigned decimal math that should be universal.
880
881 #define JU_MASKLOWEREXC( BITPOS) ((BITPOS) - 1)
882 #define JU_MASKLOWERINC( BITPOS) (JU_MASKLOWEREXC(BITPOS) | (BITPOS))
883 #define JU_MASKHIGHERINC(BITPOS) (-(BITPOS))
884 #define JU_MASKHIGHEREXC(BITPOS) (JU_MASKHIGHERINC(BITPOS) ^ (BITPOS))
885
886
887 // ****************************************************************************
888 // SUPPORT FOR NATIVE INDEX SIZES
889 // ****************************************************************************
890 //
891 // Copy a series of generic objects (uint8_t, uint16_t, uint32_t, Word_t) from
892 // one place to another.
893
894 #define JU_COPYMEM(PDST,PSRC,POP1) \
895 { \
896 Word_t i_ndex = 0; \
897 assert((POP1) > 0); \
898 do { (PDST)[i_ndex] = (PSRC)[i_ndex]; } \
899 while (++i_ndex < (POP1)); \
900 }
901
902
903 // ****************************************************************************
904 // SUPPORT FOR NON-NATIVE INDEX SIZES
905 // ****************************************************************************
906 //
907 // Copy a 3-byte Index pointed by a uint8_t * to a Word_t:
908 //
909 #define JU_COPY3_PINDEX_TO_LONG(DESTLONG,PINDEX) \
910 DESTLONG = (Word_t)(PINDEX)[0] << 16; \
911 DESTLONG += (Word_t)(PINDEX)[1] << 8; \
912 DESTLONG += (Word_t)(PINDEX)[2]
913
914 // Copy a Word_t to a 3-byte Index pointed at by a uint8_t *:
915
916 #define JU_COPY3_LONG_TO_PINDEX(PINDEX,SOURCELONG) \
917 (PINDEX)[0] = (uint8_t)((SOURCELONG) >> 16); \
918 (PINDEX)[1] = (uint8_t)((SOURCELONG) >> 8); \
919 (PINDEX)[2] = (uint8_t)((SOURCELONG))
920
921 #ifdef JU_64BIT
922
923 // Copy a 5-byte Index pointed by a uint8_t * to a Word_t:
924 //
925 #define JU_COPY5_PINDEX_TO_LONG(DESTLONG,PINDEX) \
926 DESTLONG = (Word_t)(PINDEX)[0] << 32; \
927 DESTLONG += (Word_t)(PINDEX)[1] << 24; \
928 DESTLONG += (Word_t)(PINDEX)[2] << 16; \
929 DESTLONG += (Word_t)(PINDEX)[3] << 8; \
930 DESTLONG += (Word_t)(PINDEX)[4]
931
932 // Copy a Word_t to a 5-byte Index pointed at by a uint8_t *:
933
934 #define JU_COPY5_LONG_TO_PINDEX(PINDEX,SOURCELONG) \
935 (PINDEX)[0] = (uint8_t)((SOURCELONG) >> 32); \
936 (PINDEX)[1] = (uint8_t)((SOURCELONG) >> 24); \
937 (PINDEX)[2] = (uint8_t)((SOURCELONG) >> 16); \
938 (PINDEX)[3] = (uint8_t)((SOURCELONG) >> 8); \
939 (PINDEX)[4] = (uint8_t)((SOURCELONG))
940
941 // Copy a 6-byte Index pointed by a uint8_t * to a Word_t:
942 //
943 #define JU_COPY6_PINDEX_TO_LONG(DESTLONG,PINDEX) \
944 DESTLONG = (Word_t)(PINDEX)[0] << 40; \
945 DESTLONG += (Word_t)(PINDEX)[1] << 32; \
946 DESTLONG += (Word_t)(PINDEX)[2] << 24; \
947 DESTLONG += (Word_t)(PINDEX)[3] << 16; \
948 DESTLONG += (Word_t)(PINDEX)[4] << 8; \
949 DESTLONG += (Word_t)(PINDEX)[5]
950
951 // Copy a Word_t to a 6-byte Index pointed at by a uint8_t *:
952
953 #define JU_COPY6_LONG_TO_PINDEX(PINDEX,SOURCELONG) \
954 (PINDEX)[0] = (uint8_t)((SOURCELONG) >> 40); \
955 (PINDEX)[1] = (uint8_t)((SOURCELONG) >> 32); \
956 (PINDEX)[2] = (uint8_t)((SOURCELONG) >> 24); \
957 (PINDEX)[3] = (uint8_t)((SOURCELONG) >> 16); \
958 (PINDEX)[4] = (uint8_t)((SOURCELONG) >> 8); \
959 (PINDEX)[5] = (uint8_t)((SOURCELONG))
960
961 // Copy a 7-byte Index pointed by a uint8_t * to a Word_t:
962 //
963 #define JU_COPY7_PINDEX_TO_LONG(DESTLONG,PINDEX) \
964 DESTLONG = (Word_t)(PINDEX)[0] << 48; \
965 DESTLONG += (Word_t)(PINDEX)[1] << 40; \
966 DESTLONG += (Word_t)(PINDEX)[2] << 32; \
967 DESTLONG += (Word_t)(PINDEX)[3] << 24; \
968 DESTLONG += (Word_t)(PINDEX)[4] << 16; \
969 DESTLONG += (Word_t)(PINDEX)[5] << 8; \
970 DESTLONG += (Word_t)(PINDEX)[6]
971
972 // Copy a Word_t to a 7-byte Index pointed at by a uint8_t *:
973
974 #define JU_COPY7_LONG_TO_PINDEX(PINDEX,SOURCELONG) \
975 (PINDEX)[0] = (uint8_t)((SOURCELONG) >> 48); \
976 (PINDEX)[1] = (uint8_t)((SOURCELONG) >> 40); \
977 (PINDEX)[2] = (uint8_t)((SOURCELONG) >> 32); \
978 (PINDEX)[3] = (uint8_t)((SOURCELONG) >> 24); \
979 (PINDEX)[4] = (uint8_t)((SOURCELONG) >> 16); \
980 (PINDEX)[5] = (uint8_t)((SOURCELONG) >> 8); \
981 (PINDEX)[6] = (uint8_t)((SOURCELONG))
982
983 #endif // JU_64BIT
984
985 // ****************************************************************************
986 // COMMON CODE FRAGMENTS (MACROS)
987 // ****************************************************************************
988 //
989 // These code chunks are shared between various source files.
990
991
992 // SET (REPLACE) ONE DIGIT IN AN INDEX:
993 //
994 // To avoid endian issues, use masking and ORing, which operates in a
995 // big-endian register, rather than treating the Index as an array of bytes,
996 // though that would be simpler, but would operate in endian-specific memory.
997 //
998 // TBD: This contains two variable shifts, is that bad?
999
1000 #define JU_SETDIGIT(INDEX,DIGIT,STATE) \
1001 (INDEX) = ((INDEX) & (~cJU_MASKATSTATE(STATE))) \
1002 | (((Word_t) (DIGIT)) \
1003 << (((STATE) - 1) * cJU_BITSPERBYTE))
1004
1005 // Fast version for single LSB:
1006
1007 #define JU_SETDIGIT1(INDEX,DIGIT) (INDEX) = ((INDEX) & ~0xff) | (DIGIT)
1008
1009
1010 // SET (REPLACE) "N" LEAST DIGITS IN AN INDEX:
1011
1012 #define JU_SETDIGITS(INDEX,INDEX2,cSTATE) \
1013 (INDEX) = ((INDEX ) & (~JU_LEASTBYTESMASK(cSTATE))) \
1014 | ((INDEX2) & ( JU_LEASTBYTESMASK(cSTATE)))
1015
1016 // COPY DECODE BYTES FROM JP TO INDEX:
1017 //
1018 // Modify Index digit(s) to match the bytes in jp_DcdPopO in case one or more
1019 // branches are skipped and the digits are significant. Its probably faster
1020 // to just do this unconditionally than to check if its necessary.
1021 //
1022 // To avoid endian issues, use masking and ORing, which operates in a
1023 // big-endian register, rather than treating the Index as an array of bytes,
1024 // though that would be simpler, but would operate in endian-specific memory.
1025 //
1026 // WARNING: Must not call JU_LEASTBYTESMASK (via cJU_DCDMASK) with Bytes =
1027 // cJU_ROOTSTATE or a bad mask is generated, but there are no Dcd bytes to copy
1028 // in this case anyway. In fact there are no Dcd bytes unless State <
1029 // cJU_ROOTSTATE - 1, so dont call this macro except in those cases.
1030 //
1031 // TBD: It would be nice to validate jp_DcdPopO against known digits to ensure
1032 // no corruption, but this is non-trivial.
1033
1034 #define JU_SETDCD(INDEX,PJP,cSTATE) \
1035 (INDEX) = ((INDEX) & ~cJU_DCDMASK(cSTATE)) \
1036 | (JU_JPDCDPOP0(PJP) & cJU_DCDMASK(cSTATE))
1037
1038 // INSERT/DELETE AN INDEX IN-PLACE IN MEMORY:
1039 //
1040 // Given a pointer to an array of "even" (native), same-sized objects
1041 // (indexes), the current population of the array, an offset in the array, and
1042 // a new Index to insert, "shift up" the array elements (Indexes) above the
1043 // insertion point and insert the new Index. Assume there is sufficient memory
1044 // to do this.
1045 //
1046 // In these macros, "i_offset" is an index offset, and "b_off" is a byte
1047 // offset for odd Index sizes.
1048 //
1049 // Note: Endian issues only arise fro insertion, not deletion, and even for
1050 // insertion, they are transparent when native (even) objects are used, and
1051 // handled explicitly for odd (non-native) Index sizes.
1052 //
1053 // Note: The following macros are tricky enough that there is some test code
1054 // for them appended to this file.
1055
1056 #define JU_INSERTINPLACE(PARRAY,POP1,OFFSET,INDEX) \
1057 assert((long) (POP1) > 0); \
1058 assert((Word_t) (OFFSET) <= (Word_t) (POP1)); \
1059 { \
1060 Word_t i_offset = (POP1); \
1061 \
1062 while (i_offset-- > (OFFSET)) \
1063 (PARRAY)[i_offset + 1] = (PARRAY)[i_offset]; \
1064 \
1065 (PARRAY)[OFFSET] = (INDEX); \
1066 }
1067
1068
1069 // Variation for non-native Indexes, where cIS = Index Size
1070 // and PByte must point to a uint8_t (byte); shift byte-by-byte:
1071 //
1072
1073 #define JU_INSERTINPLACE3(PBYTE,POP1,OFFSET,INDEX) \
1074 { \
1075 Word_t i_off = POP1; \
1076 \
1077 while (i_off-- > (OFFSET)) \
1078 { \
1079 Word_t i_dx = i_off * 3; \
1080 (PBYTE)[i_dx + 0 + 3] = (PBYTE)[i_dx + 0]; \
1081 (PBYTE)[i_dx + 1 + 3] = (PBYTE)[i_dx + 1]; \
1082 (PBYTE)[i_dx + 2 + 3] = (PBYTE)[i_dx + 2]; \
1083 } \
1084 JU_COPY3_LONG_TO_PINDEX(&((PBYTE)[(OFFSET) * 3]), INDEX); \
1085 }
1086
1087 #ifdef JU_64BIT
1088
1089 #define JU_INSERTINPLACE5(PBYTE,POP1,OFFSET,INDEX) \
1090 { \
1091 Word_t i_off = POP1; \
1092 \
1093 while (i_off-- > (OFFSET)) \
1094 { \
1095 Word_t i_dx = i_off * 5; \
1096 (PBYTE)[i_dx + 0 + 5] = (PBYTE)[i_dx + 0]; \
1097 (PBYTE)[i_dx + 1 + 5] = (PBYTE)[i_dx + 1]; \
1098 (PBYTE)[i_dx + 2 + 5] = (PBYTE)[i_dx + 2]; \
1099 (PBYTE)[i_dx + 3 + 5] = (PBYTE)[i_dx + 3]; \
1100 (PBYTE)[i_dx + 4 + 5] = (PBYTE)[i_dx + 4]; \
1101 } \
1102 JU_COPY5_LONG_TO_PINDEX(&((PBYTE)[(OFFSET) * 5]), INDEX); \
1103 }
1104
1105 #define JU_INSERTINPLACE6(PBYTE,POP1,OFFSET,INDEX) \
1106 { \
1107 Word_t i_off = POP1; \
1108 \
1109 while (i_off-- > (OFFSET)) \
1110 { \
1111 Word_t i_dx = i_off * 6; \
1112 (PBYTE)[i_dx + 0 + 6] = (PBYTE)[i_dx + 0]; \
1113 (PBYTE)[i_dx + 1 + 6] = (PBYTE)[i_dx + 1]; \
1114 (PBYTE)[i_dx + 2 + 6] = (PBYTE)[i_dx + 2]; \
1115 (PBYTE)[i_dx + 3 + 6] = (PBYTE)[i_dx + 3]; \
1116 (PBYTE)[i_dx + 4 + 6] = (PBYTE)[i_dx + 4]; \
1117 (PBYTE)[i_dx + 5 + 6] = (PBYTE)[i_dx + 5]; \
1118 } \
1119 JU_COPY6_LONG_TO_PINDEX(&((PBYTE)[(OFFSET) * 6]), INDEX); \
1120 }
1121
1122 #define JU_INSERTINPLACE7(PBYTE,POP1,OFFSET,INDEX) \
1123 { \
1124 Word_t i_off = POP1; \
1125 \
1126 while (i_off-- > (OFFSET)) \
1127 { \
1128 Word_t i_dx = i_off * 7; \
1129 (PBYTE)[i_dx + 0 + 7] = (PBYTE)[i_dx + 0]; \
1130 (PBYTE)[i_dx + 1 + 7] = (PBYTE)[i_dx + 1]; \
1131 (PBYTE)[i_dx + 2 + 7] = (PBYTE)[i_dx + 2]; \
1132 (PBYTE)[i_dx + 3 + 7] = (PBYTE)[i_dx + 3]; \
1133 (PBYTE)[i_dx + 4 + 7] = (PBYTE)[i_dx + 4]; \
1134 (PBYTE)[i_dx + 5 + 7] = (PBYTE)[i_dx + 5]; \
1135 (PBYTE)[i_dx + 6 + 7] = (PBYTE)[i_dx + 6]; \
1136 } \
1137 JU_COPY7_LONG_TO_PINDEX(&((PBYTE)[(OFFSET) * 7]), INDEX); \
1138 }
1139 #endif // JU_64BIT
1140
1141 // Counterparts to the above for deleting an Index:
1142 //
1143 // "Shift down" the array elements starting at the Index to be deleted.
1144
1145 #define JU_DELETEINPLACE(PARRAY,POP1,OFFSET,IGNORE) \
1146 assert((long) (POP1) > 0); \
1147 assert((Word_t) (OFFSET) < (Word_t) (POP1)); \
1148 { \
1149 Word_t i_offset = (OFFSET); \
1150 \
1151 while (++i_offset < (POP1)) \
1152 (PARRAY)[i_offset - 1] = (PARRAY)[i_offset]; \
1153 }
1154
1155 // Variation for odd-byte-sized (non-native) Indexes, where cIS = Index Size
1156 // and PByte must point to a uint8_t (byte); copy byte-by-byte:
1157 //
1158 // Note: If cIS == 1, JU_DELETEINPLACE_ODD == JU_DELETEINPLACE.
1159 //
1160 // Note: There are no endian issues here because bytes are just shifted as-is,
1161 // not converted to/from an Index.
1162
1163 #define JU_DELETEINPLACE_ODD(PBYTE,POP1,OFFSET,cIS) \
1164 assert((long) (POP1) > 0); \
1165 assert((Word_t) (OFFSET) < (Word_t) (POP1)); \
1166 { \
1167 Word_t b_off = (((OFFSET) + 1) * (cIS)) - 1; \
1168 \
1169 while (++b_off < ((POP1) * (cIS))) \
1170 (PBYTE)[b_off - (cIS)] = (PBYTE)[b_off]; \
1171 }
1172
1173
1174 // INSERT/DELETE AN INDEX WHILE COPYING OTHERS:
1175 //
1176 // Copy PSource[] to PDest[], where PSource[] has Pop1 elements (Indexes),
1177 // inserting Index at PDest[Offset]. Unlike JU_*INPLACE*() above, these macros
1178 // are used when moving Indexes from one memory object to another.
1179
1180 #define JU_INSERTCOPY(PDEST,PSOURCE,POP1,OFFSET,INDEX) \
1181 assert((long) (POP1) > 0); \
1182 assert((Word_t) (OFFSET) <= (Word_t) (POP1)); \
1183 { \
1184 Word_t i_offset; \
1185 \
1186 for (i_offset = 0; i_offset < (OFFSET); ++i_offset) \
1187 (PDEST)[i_offset] = (PSOURCE)[i_offset]; \
1188 \
1189 (PDEST)[i_offset] = (INDEX); \
1190 \
1191 for (/* null */; i_offset < (POP1); ++i_offset) \
1192 (PDEST)[i_offset + 1] = (PSOURCE)[i_offset]; \
1193 }
1194
1195 #define JU_INSERTCOPY3(PDEST,PSOURCE,POP1,OFFSET,INDEX) \
1196 assert((long) (POP1) > 0); \
1197 assert((Word_t) (OFFSET) <= (Word_t) (POP1)); \
1198 { \
1199 Word_t o_ff; \
1200 \
1201 for (o_ff = 0; o_ff < (OFFSET); o_ff++) \
1202 { \
1203 Word_t i_dx = o_ff * 3; \
1204 (PDEST)[i_dx + 0] = (PSOURCE)[i_dx + 0]; \
1205 (PDEST)[i_dx + 1] = (PSOURCE)[i_dx + 1]; \
1206 (PDEST)[i_dx + 2] = (PSOURCE)[i_dx + 2]; \
1207 } \
1208 JU_COPY3_LONG_TO_PINDEX(&((PDEST)[(OFFSET) * 3]), INDEX); \
1209 \
1210 for (/* null */; o_ff < (POP1); o_ff++) \
1211 { \
1212 Word_t i_dx = o_ff * 3; \
1213 (PDEST)[i_dx + 0 + 3] = (PSOURCE)[i_dx + 0]; \
1214 (PDEST)[i_dx + 1 + 3] = (PSOURCE)[i_dx + 1]; \
1215 (PDEST)[i_dx + 2 + 3] = (PSOURCE)[i_dx + 2]; \
1216 } \
1217 }
1218
1219 #ifdef JU_64BIT
1220
1221 #define JU_INSERTCOPY5(PDEST,PSOURCE,POP1,OFFSET,INDEX) \
1222 assert((long) (POP1) > 0); \
1223 assert((Word_t) (OFFSET) <= (Word_t) (POP1)); \
1224 { \
1225 Word_t o_ff; \
1226 \
1227 for (o_ff = 0; o_ff < (OFFSET); o_ff++) \
1228 { \
1229 Word_t i_dx = o_ff * 5; \
1230 (PDEST)[i_dx + 0] = (PSOURCE)[i_dx + 0]; \
1231 (PDEST)[i_dx + 1] = (PSOURCE)[i_dx + 1]; \
1232 (PDEST)[i_dx + 2] = (PSOURCE)[i_dx + 2]; \
1233 (PDEST)[i_dx + 3] = (PSOURCE)[i_dx + 3]; \
1234 (PDEST)[i_dx + 4] = (PSOURCE)[i_dx + 4]; \
1235 } \
1236 JU_COPY5_LONG_TO_PINDEX(&((PDEST)[(OFFSET) * 5]), INDEX); \
1237 \
1238 for (/* null */; o_ff < (POP1); o_ff++) \
1239 { \
1240 Word_t i_dx = o_ff * 5; \
1241 (PDEST)[i_dx + 0 + 5] = (PSOURCE)[i_dx + 0]; \
1242 (PDEST)[i_dx + 1 + 5] = (PSOURCE)[i_dx + 1]; \
1243 (PDEST)[i_dx + 2 + 5] = (PSOURCE)[i_dx + 2]; \
1244 (PDEST)[i_dx + 3 + 5] = (PSOURCE)[i_dx + 3]; \
1245 (PDEST)[i_dx + 4 + 5] = (PSOURCE)[i_dx + 4]; \
1246 } \
1247 }
1248
1249 #define JU_INSERTCOPY6(PDEST,PSOURCE,POP1,OFFSET,INDEX) \
1250 assert((long) (POP1) > 0); \
1251 assert((Word_t) (OFFSET) <= (Word_t) (POP1)); \
1252 { \
1253 Word_t o_ff; \
1254 \
1255 for (o_ff = 0; o_ff < (OFFSET); o_ff++) \
1256 { \
1257 Word_t i_dx = o_ff * 6; \
1258 (PDEST)[i_dx + 0] = (PSOURCE)[i_dx + 0]; \
1259 (PDEST)[i_dx + 1] = (PSOURCE)[i_dx + 1]; \
1260 (PDEST)[i_dx + 2] = (PSOURCE)[i_dx + 2]; \
1261 (PDEST)[i_dx + 3] = (PSOURCE)[i_dx + 3]; \
1262 (PDEST)[i_dx + 4] = (PSOURCE)[i_dx + 4]; \
1263 (PDEST)[i_dx + 5] = (PSOURCE)[i_dx + 5]; \
1264 } \
1265 JU_COPY6_LONG_TO_PINDEX(&((PDEST)[(OFFSET) * 6]), INDEX); \
1266 \
1267 for (/* null */; o_ff < (POP1); o_ff++) \
1268 { \
1269 Word_t i_dx = o_ff * 6; \
1270 (PDEST)[i_dx + 0 + 6] = (PSOURCE)[i_dx + 0]; \
1271 (PDEST)[i_dx + 1 + 6] = (PSOURCE)[i_dx + 1]; \
1272 (PDEST)[i_dx + 2 + 6] = (PSOURCE)[i_dx + 2]; \
1273 (PDEST)[i_dx + 3 + 6] = (PSOURCE)[i_dx + 3]; \
1274 (PDEST)[i_dx + 4 + 6] = (PSOURCE)[i_dx + 4]; \
1275 (PDEST)[i_dx + 5 + 6] = (PSOURCE)[i_dx + 5]; \
1276 } \
1277 }
1278
1279 #define JU_INSERTCOPY7(PDEST,PSOURCE,POP1,OFFSET,INDEX) \
1280 assert((long) (POP1) > 0); \
1281 assert((Word_t) (OFFSET) <= (Word_t) (POP1)); \
1282 { \
1283 Word_t o_ff; \
1284 \
1285 for (o_ff = 0; o_ff < (OFFSET); o_ff++) \
1286 { \
1287 Word_t i_dx = o_ff * 7; \
1288 (PDEST)[i_dx + 0] = (PSOURCE)[i_dx + 0]; \
1289 (PDEST)[i_dx + 1] = (PSOURCE)[i_dx + 1]; \
1290 (PDEST)[i_dx + 2] = (PSOURCE)[i_dx + 2]; \
1291 (PDEST)[i_dx + 3] = (PSOURCE)[i_dx + 3]; \
1292 (PDEST)[i_dx + 4] = (PSOURCE)[i_dx + 4]; \
1293 (PDEST)[i_dx + 5] = (PSOURCE)[i_dx + 5]; \
1294 (PDEST)[i_dx + 6] = (PSOURCE)[i_dx + 6]; \
1295 } \
1296 JU_COPY7_LONG_TO_PINDEX(&((PDEST)[(OFFSET) * 7]), INDEX); \
1297 \
1298 for (/* null */; o_ff < (POP1); o_ff++) \
1299 { \
1300 Word_t i_dx = o_ff * 7; \
1301 (PDEST)[i_dx + 0 + 7] = (PSOURCE)[i_dx + 0]; \
1302 (PDEST)[i_dx + 1 + 7] = (PSOURCE)[i_dx + 1]; \
1303 (PDEST)[i_dx + 2 + 7] = (PSOURCE)[i_dx + 2]; \
1304 (PDEST)[i_dx + 3 + 7] = (PSOURCE)[i_dx + 3]; \
1305 (PDEST)[i_dx + 4 + 7] = (PSOURCE)[i_dx + 4]; \
1306 (PDEST)[i_dx + 5 + 7] = (PSOURCE)[i_dx + 5]; \
1307 (PDEST)[i_dx + 6 + 7] = (PSOURCE)[i_dx + 6]; \
1308 } \
1309 }
1310
1311 #endif // JU_64BIT
1312
1313 // Counterparts to the above for deleting an Index:
1314
1315 #define JU_DELETECOPY(PDEST,PSOURCE,POP1,OFFSET,IGNORE) \
1316 assert((long) (POP1) > 0); \
1317 assert((Word_t) (OFFSET) < (Word_t) (POP1)); \
1318 { \
1319 Word_t i_offset; \
1320 \
1321 for (i_offset = 0; i_offset < (OFFSET); ++i_offset) \
1322 (PDEST)[i_offset] = (PSOURCE)[i_offset]; \
1323 \
1324 for (++i_offset; i_offset < (POP1); ++i_offset) \
1325 (PDEST)[i_offset - 1] = (PSOURCE)[i_offset]; \
1326 }
1327
1328 // Variation for odd-byte-sized (non-native) Indexes, where cIS = Index Size;
1329 // copy byte-by-byte:
1330 //
1331 // Note: There are no endian issues here because bytes are just shifted as-is,
1332 // not converted to/from an Index.
1333 //
1334 // Note: If cIS == 1, JU_DELETECOPY_ODD == JU_DELETECOPY, at least in concept.
1335
1336 #define JU_DELETECOPY_ODD(PDEST,PSOURCE,POP1,OFFSET,cIS) \
1337 assert((long) (POP1) > 0); \
1338 assert((Word_t) (OFFSET) < (Word_t) (POP1)); \
1339 { \
1340 uint8_t *_Pdest = (uint8_t *) (PDEST); \
1341 uint8_t *_Psource = (uint8_t *) (PSOURCE); \
1342 Word_t b_off; \
1343 \
1344 for (b_off = 0; b_off < ((OFFSET) * (cIS)); ++b_off) \
1345 *_Pdest++ = *_Psource++; \
1346 \
1347 _Psource += (cIS); \
1348 \
1349 for (b_off += (cIS); b_off < ((POP1) * (cIS)); ++b_off) \
1350 *_Pdest++ = *_Psource++; \
1351 }
1352
1353
1354 // GENERIC RETURN CODE HANDLING FOR JUDY1 (NO VALUE AREAS) AND JUDYL (VALUE
1355 // AREAS):
1356 //
1357 // This common code hides Judy1 versus JudyL details of how to return various
1358 // conditions, including a pointer to a value area for JudyL.
1359 //
1360 // First, define an internal variation of JERR called JERRI (I = int) to make
1361 // lint happy. We accidentally shipped to 11.11 OEUR with all functions that
1362 // return int or Word_t using JERR, which is type Word_t, for errors. Lint
1363 // complains about this for functions that return int. So, internally use
1364 // JERRI for error returns from the int functions. Experiments show that
1365 // callers which compare int Foo() to (Word_t) JERR (~0UL) are OK, since JERRI
1366 // sign-extends to match JERR.
1367
1368 #define JERRI ((int) ~0) // see above.
1369
1370 #ifdef JUDY1
1371
1372 #define JU_RET_FOUND return(1)
1373 #define JU_RET_NOTFOUND return(0)
1374
1375 // For Judy1, these all "fall through" to simply JU_RET_FOUND, since there is no
1376 // value area pointer to return:
1377
1378 #define JU_RET_FOUND_LEAFW(PJLW,POP1,OFFSET) JU_RET_FOUND
1379
1380 #define JU_RET_FOUND_JPM(Pjpm) JU_RET_FOUND
1381 #define JU_RET_FOUND_PVALUE(Pjv,OFFSET) JU_RET_FOUND
1382 #ifndef JU_64BIT
1383 #define JU_RET_FOUND_LEAF1(Pjll,POP1,OFFSET) JU_RET_FOUND
1384 #endif
1385 #define JU_RET_FOUND_LEAF2(Pjll,POP1,OFFSET) JU_RET_FOUND
1386 #define JU_RET_FOUND_LEAF3(Pjll,POP1,OFFSET) JU_RET_FOUND
1387 #ifdef JU_64BIT
1388 #define JU_RET_FOUND_LEAF4(Pjll,POP1,OFFSET) JU_RET_FOUND
1389 #define JU_RET_FOUND_LEAF5(Pjll,POP1,OFFSET) JU_RET_FOUND
1390 #define JU_RET_FOUND_LEAF6(Pjll,POP1,OFFSET) JU_RET_FOUND
1391 #define JU_RET_FOUND_LEAF7(Pjll,POP1,OFFSET) JU_RET_FOUND
1392 #endif
1393 #define JU_RET_FOUND_IMM_01(Pjp) JU_RET_FOUND
1394 #define JU_RET_FOUND_IMM(Pjp,OFFSET) JU_RET_FOUND
1395
1396 // Note: No JudyL equivalent:
1397
1398 #define JU_RET_FOUND_FULLPOPU1 JU_RET_FOUND
1399 #define JU_RET_FOUND_LEAF_B1(PJLB,SUBEXP,OFFSET) JU_RET_FOUND
1400
1401 #else // JUDYL
1402
1403 // JU_RET_FOUND // see below; must NOT be defined for JudyL.
1404 #define JU_RET_NOTFOUND return((PPvoid_t) NULL)
1405
1406 // For JudyL, the location of the value area depends on the JP type and other
1407 // factors:
1408 //
1409 // TBD: The value areas should be accessed via data structures, here and in
1410 // Dougs code, not by hard-coded address calculations.
1411 //
1412 // This is useful in insert/delete code when the value area is returned from
1413 // lower levels in the JPM:
1414
1415 #define JU_RET_FOUND_JPM(Pjpm) return((PPvoid_t) ((Pjpm)->jpm_PValue))
1416
1417 // This is useful in insert/delete code when the value area location is already
1418 // computed:
1419
1420 #define JU_RET_FOUND_PVALUE(Pjv,OFFSET) return((PPvoid_t) ((Pjv) + OFFSET))
1421
1422 #define JU_RET_FOUND_LEAFW(PJLW,POP1,OFFSET) \
1423 return((PPvoid_t) (JL_LEAFWVALUEAREA(PJLW, POP1) + (OFFSET)))
1424
1425 #define JU_RET_FOUND_LEAF1(Pjll,POP1,OFFSET) \
1426 return((PPvoid_t) (JL_LEAF1VALUEAREA(Pjll, POP1) + (OFFSET)))
1427 #define JU_RET_FOUND_LEAF2(Pjll,POP1,OFFSET) \
1428 return((PPvoid_t) (JL_LEAF2VALUEAREA(Pjll, POP1) + (OFFSET)))
1429 #define JU_RET_FOUND_LEAF3(Pjll,POP1,OFFSET) \
1430 return((PPvoid_t) (JL_LEAF3VALUEAREA(Pjll, POP1) + (OFFSET)))
1431 #ifdef JU_64BIT
1432 #define JU_RET_FOUND_LEAF4(Pjll,POP1,OFFSET) \
1433 return((PPvoid_t) (JL_LEAF4VALUEAREA(Pjll, POP1) + (OFFSET)))
1434 #define JU_RET_FOUND_LEAF5(Pjll,POP1,OFFSET) \
1435 return((PPvoid_t) (JL_LEAF5VALUEAREA(Pjll, POP1) + (OFFSET)))
1436 #define JU_RET_FOUND_LEAF6(Pjll,POP1,OFFSET) \
1437 return((PPvoid_t) (JL_LEAF6VALUEAREA(Pjll, POP1) + (OFFSET)))
1438 #define JU_RET_FOUND_LEAF7(Pjll,POP1,OFFSET) \
1439 return((PPvoid_t) (JL_LEAF7VALUEAREA(Pjll, POP1) + (OFFSET)))
1440 #endif
1441
1442 // Note: Here jp_Addr is a value area itself and not an address, so P_JV() is
1443 // not needed:
1444
1445 #define JU_RET_FOUND_IMM_01(PJP) return((PPvoid_t) (&((PJP)->jp_Addr)))
1446
1447 // Note: Here jp_Addr is a pointer to a separately-mallocd value area, so
1448 // P_JV() is required; likewise for JL_JLB_PVALUE:
1449
1450 #define JU_RET_FOUND_IMM(PJP,OFFSET) \
1451 return((PPvoid_t) (P_JV((PJP)->jp_Addr) + (OFFSET)))
1452
1453 #define JU_RET_FOUND_LEAF_B1(PJLB,SUBEXP,OFFSET) \
1454 return((PPvoid_t) (P_JV(JL_JLB_PVALUE(PJLB, SUBEXP)) + (OFFSET)))
1455
1456 #endif // JUDYL
1457
1458
1459 // GENERIC ERROR HANDLING:
1460 //
1461 // This is complicated by variations in the needs of the callers of these
1462 // macros. Only use JU_SET_ERRNO() for PJError, because it can be null; use
1463 // JU_SET_ERRNO_NONNULL() for Pjpm, which is never null, and also in other
1464 // cases where the pointer is known not to be null (to save dead branches).
1465 //
1466 // Note: Most cases of JU_ERRNO_OVERRUN or JU_ERRNO_CORRUPT should result in
1467 // an assertion failure in debug code, so they are more likely to be caught, so
1468 // do that here in each macro.
1469
1470 #define JU_SET_ERRNO(PJError, JErrno) \
1471 { \
1472 assert((JErrno) != JU_ERRNO_OVERRUN); \
1473 assert((JErrno) != JU_ERRNO_CORRUPT); \
1474 \
1475 if (PJError != (PJError_t) NULL) \
1476 { \
1477 JU_ERRNO(PJError) = (JErrno); \
1478 JU_ERRID(PJError) = __LINE__; \
1479 } \
1480 }
1481
1482 // Variation for callers who know already that PJError is non-null; and, it can
1483 // also be Pjpm (both PJError_t and Pjpm_t have je_* fields), so only assert it
1484 // for null, not cast to any specific pointer type:
1485
1486 #define JU_SET_ERRNO_NONNULL(PJError, JErrno) \
1487 { \
1488 assert((JErrno) != JU_ERRNO_OVERRUN); \
1489 assert((JErrno) != JU_ERRNO_CORRUPT); \
1490 assert(PJError); \
1491 \
1492 JU_ERRNO(PJError) = (JErrno); \
1493 JU_ERRID(PJError) = __LINE__; \
1494 }
1495
1496 // Variation to copy error info from a (required) JPM to an (optional)
1497 // PJError_t:
1498 //
1499 // Note: The assertions above about JU_ERRNO_OVERRUN and JU_ERRNO_CORRUPT
1500 // should have already popped, so they are not needed here.
1501
1502 #define JU_COPY_ERRNO(PJError, Pjpm) \
1503 { \
1504 if (PJError) \
1505 { \
1506 JU_ERRNO(PJError) = (uint8_t)JU_ERRNO(Pjpm); \
1507 JU_ERRID(PJError) = JU_ERRID(Pjpm); \
1508 } \
1509 }
1510
1511 // For JErrno parameter to previous macros upon return from Judy*Alloc*():
1512 //
1513 // The memory allocator returns an address of 0 for out of memory,
1514 // 1..sizeof(Word_t)-1 for corruption (an invalid pointer), otherwise a valid
1515 // pointer.
1516
1517 #define JU_ALLOC_ERRNO(ADDR) \
1518 (((void *) (ADDR) != (void *) NULL) ? JU_ERRNO_OVERRUN : JU_ERRNO_NOMEM)
1519
1520 #define JU_CHECKALLOC(Type,Ptr,Retval) \
1521 if ((Ptr) < (Type) sizeof(Word_t)) \
1522 { \
1523 JU_SET_ERRNO(PJError, JU_ALLOC_ERRNO(Ptr)); \
1524 return(Retval); \
1525 }
1526
1527 // Leaf search routines
1528
1529 #ifdef JU_NOINLINE
1530
1531 int j__udySearchLeaf1(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
1532 int j__udySearchLeaf2(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
1533 int j__udySearchLeaf3(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
1534
1535 #ifdef JU_64BIT
1536
1537 int j__udySearchLeaf4(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
1538 int j__udySearchLeaf5(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
1539 int j__udySearchLeaf6(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
1540 int j__udySearchLeaf7(Pjll_t Pjll, Word_t LeafPop1, Word_t Index);
1541
1542 #endif // JU_64BIT
1543
1544 int j__udySearchLeafW(Pjlw_t Pjlw, Word_t LeafPop1, Word_t Index);
1545
1546 #else // complier support for inline
1547
1548 #ifdef JU_WIN
j__udySearchLeaf1(Pjll_t Pjll,Word_t LeafPop1,Word_t Index)1549 static __inline int j__udySearchLeaf1(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1550 #else
1551 static inline int j__udySearchLeaf1(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1552 #endif
1553 { SEARCHLEAFNATIVE(uint8_t, Pjll, LeafPop1, Index); }
1554
1555 #ifdef JU_WIN
j__udySearchLeaf2(Pjll_t Pjll,Word_t LeafPop1,Word_t Index)1556 static __inline int j__udySearchLeaf2(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1557 #else
1558 static inline int j__udySearchLeaf2(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1559 #endif
1560 { SEARCHLEAFNATIVE(uint16_t, Pjll, LeafPop1, Index); }
1561
1562 #ifdef JU_WIN
j__udySearchLeaf3(Pjll_t Pjll,Word_t LeafPop1,Word_t Index)1563 static __inline int j__udySearchLeaf3(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1564 #else
1565 static inline int j__udySearchLeaf3(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1566 #endif
1567 { SEARCHLEAFNONNAT(Pjll, LeafPop1, Index, 3, JU_COPY3_PINDEX_TO_LONG); }
1568
1569 #ifdef JU_64BIT
1570
1571 #ifdef JU_WIN
j__udySearchLeaf4(Pjll_t Pjll,Word_t LeafPop1,Word_t Index)1572 static __inline int j__udySearchLeaf4(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1573 #else
1574 static inline int j__udySearchLeaf4(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1575 #endif
1576 { SEARCHLEAFNATIVE(uint32_t, Pjll, LeafPop1, Index); }
1577
1578 #ifdef JU_WIN
j__udySearchLeaf5(Pjll_t Pjll,Word_t LeafPop1,Word_t Index)1579 static __inline int j__udySearchLeaf5(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1580 #else
1581 static inline int j__udySearchLeaf5(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1582 #endif
1583 { SEARCHLEAFNONNAT(Pjll, LeafPop1, Index, 5, JU_COPY5_PINDEX_TO_LONG); }
1584
1585 #ifdef JU_WIN
j__udySearchLeaf6(Pjll_t Pjll,Word_t LeafPop1,Word_t Index)1586 static __inline int j__udySearchLeaf6(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1587 #else
1588 static inline int j__udySearchLeaf6(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1589 #endif
1590 { SEARCHLEAFNONNAT(Pjll, LeafPop1, Index, 6, JU_COPY6_PINDEX_TO_LONG); }
1591
1592 #ifdef JU_WIN
j__udySearchLeaf7(Pjll_t Pjll,Word_t LeafPop1,Word_t Index)1593 static __inline int j__udySearchLeaf7(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1594 #else
1595 static inline int j__udySearchLeaf7(Pjll_t Pjll, Word_t LeafPop1, Word_t Index)
1596 #endif
1597 { SEARCHLEAFNONNAT(Pjll, LeafPop1, Index, 7, JU_COPY7_PINDEX_TO_LONG); }
1598
1599 #endif // JU_64BIT
1600
1601 #ifdef JU_WIN
j__udySearchLeafW(Pjlw_t Pjlw,Word_t LeafPop1,Word_t Index)1602 static __inline int j__udySearchLeafW(Pjlw_t Pjlw, Word_t LeafPop1, Word_t Index)
1603 #else
1604 static inline int j__udySearchLeafW(Pjlw_t Pjlw, Word_t LeafPop1, Word_t Index)
1605 #endif
1606 { SEARCHLEAFNATIVE(Word_t, Pjlw, LeafPop1, Index); }
1607
1608 #endif // compiler support for inline
1609
1610 #endif // ! _JUDYPRIVATE_INCLUDED
1611