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