| 1 | #ifndef _JUDYL_INCLUDED |
| 2 | #define _JUDYL_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.41 $ $Source: /judy/src/JudyL/JudyL.h $ |
| 23 | |
| 24 | // **************************************************************************** |
| 25 | // JUDYL -- SMALL/LARGE AND/OR CLUSTERED/SPARSE ARRAYS |
| 26 | // |
| 27 | // -by- |
| 28 | // |
| 29 | // Douglas L. Baskins |
| 30 | // doug@sourcejudy.com |
| 31 | // |
| 32 | // Judy arrays are designed to be used instead of arrays. The performance |
| 33 | // suggests the reason why Judy arrays are thought of as arrays, instead of |
| 34 | // trees. They are remarkably memory efficient at all populations. |
| 35 | // Implemented as a hybrid digital tree (but really a state machine, see |
| 36 | // below), Judy arrays feature fast insert/retrievals, fast near neighbor |
| 37 | // searching, and contain a population tree for extremely fast ordinal related |
| 38 | // retrievals. |
| 39 | // |
| 40 | // CONVENTIONS: |
| 41 | // |
| 42 | // - The comments here refer to 32-bit [64-bit] systems. |
| 43 | // |
| 44 | // - BranchL, LeafL refer to linear branches and leaves (small populations), |
| 45 | // except LeafL does not actually appear as such; rather, Leaf1..3 [Leaf1..7] |
| 46 | // is used to represent leaf Index sizes, and LeafW refers to a Leaf with |
| 47 | // full (Long) word Indexes, which is also a type of linear leaf. Note that |
| 48 | // root-level LeafW (Leaf4 [Leaf8]) leaves are called LEAFW. |
| 49 | // |
| 50 | // - BranchB, LeafB1 refer to bitmap branches and leaves (intermediate |
| 51 | // populations). |
| 52 | // |
| 53 | // - BranchU refers to uncompressed branches. An uncompressed branch has 256 |
| 54 | // JPs, some of which could be null. Note: All leaves are compressed (and |
| 55 | // sorted), or else an expanse is full (FullPopu), so there is no LeafU |
| 56 | // equivalent to BranchU. |
| 57 | // |
| 58 | // - "Popu" is short for "Population". |
| 59 | // - "Pop1" refers to actual population (base 1). |
| 60 | // - "Pop0" refers to Pop1 - 1 (base 0), the way populations are stored in data |
| 61 | // structures. |
| 62 | // |
| 63 | // - Branches and Leaves are both named by the number of bytes in their Pop0 |
| 64 | // field. In the case of Leaves, the same number applies to the Index sizes. |
| 65 | // |
| 66 | // - The representation of many numbers as hex is a relatively safe and |
| 67 | // portable way to get desired bitpatterns as unsigned longs. |
| 68 | // |
| 69 | // - Some preprocessors cant handle single apostrophe characters within |
| 70 | // #ifndef code, so here, delete all instead. |
| 71 | |
| 72 | |
| 73 | #include "JudyPrivate.h" // includes Judy.h in turn. |
| 74 | #include "JudyPrivateBranch.h" // support for branches. |
| 75 | |
| 76 | |
| 77 | // **************************************************************************** |
| 78 | // JUDYL ROOT POINTER (JRP) AND JUDYL POINTER (JP) TYPE FIELDS |
| 79 | // **************************************************************************** |
| 80 | |
| 81 | typedef enum // uint8_t -- but C does not support this type of enum. |
| 82 | { |
| 83 | |
| 84 | // JP NULL TYPES: |
| 85 | // |
| 86 | // There is a series of cJL_JPNULL* Types because each one pre-records a |
| 87 | // different Index Size for when the first Index is inserted in the previously |
| 88 | // null JP. They must start >= 8 (three bits). |
| 89 | // |
| 90 | // Note: These Types must be in sequential order for doing relative |
| 91 | // calculations between them. |
| 92 | |
| 93 | cJL_JPNULL1 = 1, |
| 94 | // Index Size 1[1] byte when 1 Index inserted. |
| 95 | cJL_JPNULL2, // Index Size 2[2] bytes when 1 Index inserted. |
| 96 | cJL_JPNULL3, // Index Size 3[3] bytes when 1 Index inserted. |
| 97 | |
| 98 | #ifndef JU_64BIT |
| 99 | #define cJL_JPNULLMAX cJL_JPNULL3 |
| 100 | #else |
| 101 | cJL_JPNULL4, // Index Size 4[4] bytes when 1 Index inserted. |
| 102 | cJL_JPNULL5, // Index Size 5[5] bytes when 1 Index inserted. |
| 103 | cJL_JPNULL6, // Index Size 6[6] bytes when 1 Index inserted. |
| 104 | cJL_JPNULL7, // Index Size 7[7] bytes when 1 Index inserted. |
| 105 | #define cJL_JPNULLMAX cJL_JPNULL7 |
| 106 | #endif |
| 107 | |
| 108 | |
| 109 | // JP BRANCH TYPES: |
| 110 | // |
| 111 | // Note: There are no state-1 branches; only leaves reside at state 1. |
| 112 | |
| 113 | // Linear branches: |
| 114 | // |
| 115 | // Note: These Types must be in sequential order for doing relative |
| 116 | // calculations between them. |
| 117 | |
| 118 | cJL_JPBRANCH_L2, // 2[2] bytes Pop0, 1[5] bytes Dcd. |
| 119 | cJL_JPBRANCH_L3, // 3[3] bytes Pop0, 0[4] bytes Dcd. |
| 120 | |
| 121 | #ifdef JU_64BIT |
| 122 | cJL_JPBRANCH_L4, // [4] bytes Pop0, [3] bytes Dcd. |
| 123 | cJL_JPBRANCH_L5, // [5] bytes Pop0, [2] bytes Dcd. |
| 124 | cJL_JPBRANCH_L6, // [6] bytes Pop0, [1] byte Dcd. |
| 125 | cJL_JPBRANCH_L7, // [7] bytes Pop0, [0] bytes Dcd. |
| 126 | #endif |
| 127 | |
| 128 | cJL_JPBRANCH_L, // note: DcdPopO field not used. |
| 129 | |
| 130 | // Bitmap branches: |
| 131 | // |
| 132 | // Note: These Types must be in sequential order for doing relative |
| 133 | // calculations between them. |
| 134 | |
| 135 | cJL_JPBRANCH_B2, // 2[2] bytes Pop0, 1[5] bytes Dcd. |
| 136 | cJL_JPBRANCH_B3, // 3[3] bytes Pop0, 0[4] bytes Dcd. |
| 137 | |
| 138 | #ifdef JU_64BIT |
| 139 | cJL_JPBRANCH_B4, // [4] bytes Pop0, [3] bytes Dcd. |
| 140 | cJL_JPBRANCH_B5, // [5] bytes Pop0, [2] bytes Dcd. |
| 141 | cJL_JPBRANCH_B6, // [6] bytes Pop0, [1] byte Dcd. |
| 142 | cJL_JPBRANCH_B7, // [7] bytes Pop0, [0] bytes Dcd. |
| 143 | #endif |
| 144 | |
| 145 | cJL_JPBRANCH_B, // note: DcdPopO field not used. |
| 146 | |
| 147 | // Uncompressed branches: |
| 148 | // |
| 149 | // Note: These Types must be in sequential order for doing relative |
| 150 | // calculations between them. |
| 151 | |
| 152 | cJL_JPBRANCH_U2, // 2[2] bytes Pop0, 1[5] bytes Dcd. |
| 153 | cJL_JPBRANCH_U3, // 3[3] bytes Pop0, 0[4] bytes Dcd. |
| 154 | |
| 155 | #ifdef JU_64BIT |
| 156 | cJL_JPBRANCH_U4, // [4] bytes Pop0, [3] bytes Dcd. |
| 157 | cJL_JPBRANCH_U5, // [5] bytes Pop0, [2] bytes Dcd. |
| 158 | cJL_JPBRANCH_U6, // [6] bytes Pop0, [1] byte Dcd. |
| 159 | cJL_JPBRANCH_U7, // [7] bytes Pop0, [0] bytes Dcd. |
| 160 | #endif |
| 161 | |
| 162 | cJL_JPBRANCH_U, // note: DcdPopO field not used. |
| 163 | |
| 164 | |
| 165 | // JP LEAF TYPES: |
| 166 | |
| 167 | // Linear leaves: |
| 168 | // |
| 169 | // Note: These Types must be in sequential order for doing relative |
| 170 | // calculations between them. |
| 171 | // |
| 172 | // Note: There is no full-word (4-byte [8-byte]) Index leaf under a JP because |
| 173 | // non-root-state leaves only occur under branches that decode at least one |
| 174 | // byte. Full-word, root-state leaves are under a JRP, not a JP. However, in |
| 175 | // the code a "fake" JP can be created temporarily above a root-state leaf. |
| 176 | |
| 177 | cJL_JPLEAF1, // 1[1] byte Pop0, 2 bytes Dcd. |
| 178 | cJL_JPLEAF2, // 2[2] bytes Pop0, 1[5] bytes Dcd. |
| 179 | cJL_JPLEAF3, // 3[3] bytes Pop0, 0[4] bytes Dcd. |
| 180 | |
| 181 | #ifdef JU_64BIT |
| 182 | cJL_JPLEAF4, // [4] bytes Pop0, [3] bytes Dcd. |
| 183 | cJL_JPLEAF5, // [5] bytes Pop0, [2] bytes Dcd. |
| 184 | cJL_JPLEAF6, // [6] bytes Pop0, [1] byte Dcd. |
| 185 | cJL_JPLEAF7, // [7] bytes Pop0, [0] bytes Dcd. |
| 186 | #endif |
| 187 | |
| 188 | // Bitmap leaf; Index Size == 1: |
| 189 | // |
| 190 | // Note: These are currently only supported at state 1. At other states the |
| 191 | // bitmap would grow from 256 to 256^2, 256^3, ... bits, which would not be |
| 192 | // efficient.. |
| 193 | |
| 194 | cJL_JPLEAF_B1, // 1[1] byte Pop0, 2[6] bytes Dcd. |
| 195 | |
| 196 | // Full population; Index Size == 1 virtual leaf: |
| 197 | // |
| 198 | // Note: JudyL has no cJL_JPFULLPOPU1 equivalent to cJ1_JPFULLPOPU1, because |
| 199 | // in the JudyL case this could result in a values-only leaf of up to 256 words |
| 200 | // (value areas) that would be slow to insert/delete. |
| 201 | |
| 202 | |
| 203 | // JP IMMEDIATES; leaves (Indexes) stored inside a JP: |
| 204 | // |
| 205 | // The second numeric suffix is the Pop1 for each type. As the Index Size |
| 206 | // increases, the maximum possible population decreases. |
| 207 | // |
| 208 | // Note: These Types must be in sequential order in each group (Index Size), |
| 209 | // and the groups in correct order too, for doing relative calculations between |
| 210 | // them. For example, since these Types enumerate the Pop1 values (unlike |
| 211 | // other JP Types where there is a Pop0 value in the JP), the maximum Pop1 for |
| 212 | // each Index Size is computable. |
| 213 | // |
| 214 | // All enums equal or above this point are cJL_JPIMMEDs. |
| 215 | |
| 216 | cJL_JPIMMED_1_01, // Index Size = 1, Pop1 = 1. |
| 217 | cJL_JPIMMED_2_01, // Index Size = 2, Pop1 = 1. |
| 218 | cJL_JPIMMED_3_01, // Index Size = 3, Pop1 = 1. |
| 219 | |
| 220 | #ifdef JU_64BIT |
| 221 | cJL_JPIMMED_4_01, // Index Size = 4, Pop1 = 1. |
| 222 | cJL_JPIMMED_5_01, // Index Size = 5, Pop1 = 1. |
| 223 | cJL_JPIMMED_6_01, // Index Size = 6, Pop1 = 1. |
| 224 | cJL_JPIMMED_7_01, // Index Size = 7, Pop1 = 1. |
| 225 | #endif |
| 226 | |
| 227 | cJL_JPIMMED_1_02, // Index Size = 1, Pop1 = 2. |
| 228 | cJL_JPIMMED_1_03, // Index Size = 1, Pop1 = 3. |
| 229 | |
| 230 | #ifdef JU_64BIT |
| 231 | cJL_JPIMMED_1_04, // Index Size = 1, Pop1 = 4. |
| 232 | cJL_JPIMMED_1_05, // Index Size = 1, Pop1 = 5. |
| 233 | cJL_JPIMMED_1_06, // Index Size = 1, Pop1 = 6. |
| 234 | cJL_JPIMMED_1_07, // Index Size = 1, Pop1 = 7. |
| 235 | |
| 236 | cJL_JPIMMED_2_02, // Index Size = 2, Pop1 = 2. |
| 237 | cJL_JPIMMED_2_03, // Index Size = 2, Pop1 = 3. |
| 238 | |
| 239 | cJL_JPIMMED_3_02, // Index Size = 3, Pop1 = 2. |
| 240 | #endif |
| 241 | |
| 242 | // This special Type is merely a sentinel for doing relative calculations. |
| 243 | // This value should not be used in switch statements (to avoid allocating code |
| 244 | // for it), which is also why it appears at the end of the enum list. |
| 245 | |
| 246 | cJL_JPIMMED_CAP |
| 247 | |
| 248 | } jpL_Type_t; |
| 249 | |
| 250 | |
| 251 | // RELATED VALUES: |
| 252 | |
| 253 | // Index Size (state) for leaf JP, and JP type based on Index Size (state): |
| 254 | |
| 255 | #define JL_LEAFINDEXSIZE(jpType) ((jpType) - cJL_JPLEAF1 + 1) |
| 256 | #define JL_LEAFTYPE(IndexSize) ((IndexSize) + cJL_JPLEAF1 - 1) |
| 257 | |
| 258 | |
| 259 | // MAXIMUM POPULATIONS OF LINEAR LEAVES: |
| 260 | |
| 261 | #ifndef JU_64BIT // 32-bit |
| 262 | |
| 263 | #define J_L_MAXB (sizeof(Word_t) * 64) |
| 264 | #define ALLOCSIZES { 3, 5, 7, 11, 15, 23, 32, 47, 64, TERMINATOR } // in words. |
| 265 | #define cJL_LEAF1_MAXWORDS (32) // max Leaf1 size in words. |
| 266 | |
| 267 | // Note: cJL_LEAF1_MAXPOP1 is chosen such that the index portion is less than |
| 268 | // 32 bytes -- the number of bytes the index takes in a bitmap leaf. |
| 269 | |
| 270 | #define cJL_LEAF1_MAXPOP1 \ |
| 271 | ((cJL_LEAF1_MAXWORDS * cJU_BYTESPERWORD)/(1 + cJU_BYTESPERWORD)) |
| 272 | #define cJL_LEAF2_MAXPOP1 (J_L_MAXB / (2 + cJU_BYTESPERWORD)) |
| 273 | #define cJL_LEAF3_MAXPOP1 (J_L_MAXB / (3 + cJU_BYTESPERWORD)) |
| 274 | #define cJL_LEAFW_MAXPOP1 \ |
| 275 | ((J_L_MAXB - cJU_BYTESPERWORD) / (2 * cJU_BYTESPERWORD)) |
| 276 | |
| 277 | #else // 64-bit |
| 278 | |
| 279 | #define J_L_MAXB (sizeof(Word_t) * 64) |
| 280 | #define ALLOCSIZES { 3, 5, 7, 11, 15, 23, 32, 47, 64, TERMINATOR } // in words. |
| 281 | #define cJL_LEAF1_MAXWORDS (15) // max Leaf1 size in words. |
| 282 | |
| 283 | #define cJL_LEAF1_MAXPOP1 \ |
| 284 | ((cJL_LEAF1_MAXWORDS * cJU_BYTESPERWORD)/(1 + cJU_BYTESPERWORD)) |
| 285 | #define cJL_LEAF2_MAXPOP1 (J_L_MAXB / (2 + cJU_BYTESPERWORD)) |
| 286 | #define cJL_LEAF3_MAXPOP1 (J_L_MAXB / (3 + cJU_BYTESPERWORD)) |
| 287 | #define cJL_LEAF4_MAXPOP1 (J_L_MAXB / (4 + cJU_BYTESPERWORD)) |
| 288 | #define cJL_LEAF5_MAXPOP1 (J_L_MAXB / (5 + cJU_BYTESPERWORD)) |
| 289 | #define cJL_LEAF6_MAXPOP1 (J_L_MAXB / (6 + cJU_BYTESPERWORD)) |
| 290 | #define cJL_LEAF7_MAXPOP1 (J_L_MAXB / (7 + cJU_BYTESPERWORD)) |
| 291 | #define cJL_LEAFW_MAXPOP1 \ |
| 292 | ((J_L_MAXB - cJU_BYTESPERWORD) / (2 * cJU_BYTESPERWORD)) |
| 293 | |
| 294 | #endif // 64-bit |
| 295 | |
| 296 | |
| 297 | // MAXIMUM POPULATIONS OF IMMEDIATE JPs: |
| 298 | // |
| 299 | // These specify the maximum Population of immediate JPs with various Index |
| 300 | // Sizes (== sizes of remaining undecoded Index bits). Since the JP Types enum |
| 301 | // already lists all the immediates in order by state and size, calculate these |
| 302 | // values from it to avoid redundancy. |
| 303 | |
| 304 | #define cJL_IMMED1_MAXPOP1 ((cJU_BYTESPERWORD - 1) / 1) // 3 [7]. |
| 305 | #define cJL_IMMED2_MAXPOP1 ((cJU_BYTESPERWORD - 1) / 2) // 1 [3]. |
| 306 | #define cJL_IMMED3_MAXPOP1 ((cJU_BYTESPERWORD - 1) / 3) // 1 [2]. |
| 307 | |
| 308 | #ifdef JU_64BIT |
| 309 | #define cJL_IMMED4_MAXPOP1 ((cJU_BYTESPERWORD - 1) / 4) // [1]. |
| 310 | #define cJL_IMMED5_MAXPOP1 ((cJU_BYTESPERWORD - 1) / 5) // [1]. |
| 311 | #define cJL_IMMED6_MAXPOP1 ((cJU_BYTESPERWORD - 1) / 6) // [1]. |
| 312 | #define cJL_IMMED7_MAXPOP1 ((cJU_BYTESPERWORD - 1) / 7) // [1]. |
| 313 | #endif |
| 314 | |
| 315 | |
| 316 | // **************************************************************************** |
| 317 | // JUDYL LEAF BITMAP (JLLB) SUPPORT |
| 318 | // **************************************************************************** |
| 319 | // |
| 320 | // Assemble bitmap leaves out of smaller units that put bitmap subexpanses |
| 321 | // close to their associated pointers. Why not just use a bitmap followed by a |
| 322 | // series of pointers? (See 4.27.) Turns out this wastes a cache fill on |
| 323 | // systems with smaller cache lines than the assumed value cJU_WORDSPERCL. |
| 324 | |
| 325 | #define JL_JLB_BITMAP(Pjlb, Subexp) ((Pjlb)->jLlb_jLlbs[Subexp].jLlbs_Bitmap) |
| 326 | #define JL_JLB_PVALUE(Pjlb, Subexp) ((Pjlb)->jLlb_jLlbs[Subexp].jLlbs_PValue) |
| 327 | |
| 328 | typedef struct J__UDYL_LEAF_BITMAP_SUBEXPANSE |
| 329 | { |
| 330 | BITMAPL_t jLlbs_Bitmap; |
| 331 | Pjv_t jLlbs_PValue; |
| 332 | |
| 333 | } jLlbs_t; |
| 334 | |
| 335 | typedef struct J__UDYL_LEAF_BITMAP |
| 336 | { |
| 337 | jLlbs_t jLlb_jLlbs[cJU_NUMSUBEXPL]; |
| 338 | |
| 339 | } jLlb_t, * PjLlb_t; |
| 340 | |
| 341 | // Words per bitmap leaf: |
| 342 | |
| 343 | #define cJL_WORDSPERLEAFB1 (sizeof(jLlb_t) / cJU_BYTESPERWORD) |
| 344 | |
| 345 | |
| 346 | // **************************************************************************** |
| 347 | // MEMORY ALLOCATION SUPPORT |
| 348 | // **************************************************************************** |
| 349 | |
| 350 | // ARRAY-GLOBAL INFORMATION: |
| 351 | // |
| 352 | // At the cost of an occasional additional cache fill, this object, which is |
| 353 | // pointed at by a JRP and in turn points to a JP_BRANCH*, carries array-global |
| 354 | // information about a JudyL array that has sufficient population to amortize |
| 355 | // the cost. The jpm_Pop0 field prevents having to add up the total population |
| 356 | // for the array in insert, delete, and count code. The jpm_JP field prevents |
| 357 | // having to build a fake JP for entry to a state machine; however, the |
| 358 | // jp_DcdPopO field in jpm_JP, being one byte too small, is not used. |
| 359 | // |
| 360 | // Note: Struct fields are ordered to keep "hot" data in the first 8 words |
| 361 | // (see left-margin comments) for machines with 8-word cache lines, and to keep |
| 362 | // sub-word fields together for efficient packing. |
| 363 | |
| 364 | typedef struct J_UDYL_POPULATION_AND_MEMORY |
| 365 | { |
| 366 | /* 1 */ Word_t jpm_Pop0; // total population-1 in array. |
| 367 | /* 2 */ jp_t jpm_JP; // JP to first branch; see above. |
| 368 | /* 4 */ Word_t jpm_LastUPop0; // last jpm_Pop0 when convert to BranchU |
| 369 | /* 7 */ Pjv_t jpm_PValue; // pointer to value to return. |
| 370 | // Note: Field names match PJError_t for convenience in macros: |
| 371 | /* 8 */ char je_Errno; // one of the enums in Judy.h. |
| 372 | /* 8/9 */ int je_ErrID; // often an internal source line number. |
| 373 | /* 9/10 */ Word_t jpm_TotalMemWords; // words allocated in array. |
| 374 | } jLpm_t, *PjLpm_t; |
| 375 | |
| 376 | |
| 377 | // TABLES FOR DETERMINING IF LEAVES HAVE ROOM TO GROW: |
| 378 | // |
| 379 | // These tables indicate if a given memory chunk can support growth of a given |
| 380 | // object into wasted (rounded-up) memory in the chunk. Note: This violates |
| 381 | // the hiddenness of the JudyMalloc code. |
| 382 | |
| 383 | extern const uint8_t j__L_Leaf1PopToWords[cJL_LEAF1_MAXPOP1 + 1]; |
| 384 | extern const uint8_t j__L_Leaf2PopToWords[cJL_LEAF2_MAXPOP1 + 1]; |
| 385 | extern const uint8_t j__L_Leaf3PopToWords[cJL_LEAF3_MAXPOP1 + 1]; |
| 386 | #ifdef JU_64BIT |
| 387 | extern const uint8_t j__L_Leaf4PopToWords[cJL_LEAF4_MAXPOP1 + 1]; |
| 388 | extern const uint8_t j__L_Leaf5PopToWords[cJL_LEAF5_MAXPOP1 + 1]; |
| 389 | extern const uint8_t j__L_Leaf6PopToWords[cJL_LEAF6_MAXPOP1 + 1]; |
| 390 | extern const uint8_t j__L_Leaf7PopToWords[cJL_LEAF7_MAXPOP1 + 1]; |
| 391 | #endif |
| 392 | extern const uint8_t j__L_LeafWPopToWords[cJL_LEAFW_MAXPOP1 + 1]; |
| 393 | extern const uint8_t j__L_LeafVPopToWords[]; |
| 394 | |
| 395 | // These tables indicate where value areas start: |
| 396 | |
| 397 | extern const uint8_t j__L_Leaf1Offset [cJL_LEAF1_MAXPOP1 + 1]; |
| 398 | extern const uint8_t j__L_Leaf2Offset [cJL_LEAF2_MAXPOP1 + 1]; |
| 399 | extern const uint8_t j__L_Leaf3Offset [cJL_LEAF3_MAXPOP1 + 1]; |
| 400 | #ifdef JU_64BIT |
| 401 | extern const uint8_t j__L_Leaf4Offset [cJL_LEAF4_MAXPOP1 + 1]; |
| 402 | extern const uint8_t j__L_Leaf5Offset [cJL_LEAF5_MAXPOP1 + 1]; |
| 403 | extern const uint8_t j__L_Leaf6Offset [cJL_LEAF6_MAXPOP1 + 1]; |
| 404 | extern const uint8_t j__L_Leaf7Offset [cJL_LEAF7_MAXPOP1 + 1]; |
| 405 | #endif |
| 406 | extern const uint8_t j__L_LeafWOffset [cJL_LEAFW_MAXPOP1 + 1]; |
| 407 | |
| 408 | // Also define macros to hide the details in the code using these tables. |
| 409 | |
| 410 | #define JL_LEAF1GROWINPLACE(Pop1) \ |
| 411 | J__U_GROWCK(Pop1, cJL_LEAF1_MAXPOP1, j__L_Leaf1PopToWords) |
| 412 | #define JL_LEAF2GROWINPLACE(Pop1) \ |
| 413 | J__U_GROWCK(Pop1, cJL_LEAF2_MAXPOP1, j__L_Leaf2PopToWords) |
| 414 | #define JL_LEAF3GROWINPLACE(Pop1) \ |
| 415 | J__U_GROWCK(Pop1, cJL_LEAF3_MAXPOP1, j__L_Leaf3PopToWords) |
| 416 | #ifdef JU_64BIT |
| 417 | #define JL_LEAF4GROWINPLACE(Pop1) \ |
| 418 | J__U_GROWCK(Pop1, cJL_LEAF4_MAXPOP1, j__L_Leaf4PopToWords) |
| 419 | #define JL_LEAF5GROWINPLACE(Pop1) \ |
| 420 | J__U_GROWCK(Pop1, cJL_LEAF5_MAXPOP1, j__L_Leaf5PopToWords) |
| 421 | #define JL_LEAF6GROWINPLACE(Pop1) \ |
| 422 | J__U_GROWCK(Pop1, cJL_LEAF6_MAXPOP1, j__L_Leaf6PopToWords) |
| 423 | #define JL_LEAF7GROWINPLACE(Pop1) \ |
| 424 | J__U_GROWCK(Pop1, cJL_LEAF7_MAXPOP1, j__L_Leaf7PopToWords) |
| 425 | #endif |
| 426 | #define JL_LEAFWGROWINPLACE(Pop1) \ |
| 427 | J__U_GROWCK(Pop1, cJL_LEAFW_MAXPOP1, j__L_LeafWPopToWords) |
| 428 | #define JL_LEAFVGROWINPLACE(Pop1) \ |
| 429 | J__U_GROWCK(Pop1, cJU_BITSPERSUBEXPL, j__L_LeafVPopToWords) |
| 430 | |
| 431 | #define JL_LEAF1VALUEAREA(Pjv,Pop1) (((PWord_t)(Pjv)) + j__L_Leaf1Offset[Pop1]) |
| 432 | #define JL_LEAF2VALUEAREA(Pjv,Pop1) (((PWord_t)(Pjv)) + j__L_Leaf2Offset[Pop1]) |
| 433 | #define JL_LEAF3VALUEAREA(Pjv,Pop1) (((PWord_t)(Pjv)) + j__L_Leaf3Offset[Pop1]) |
| 434 | #ifdef JU_64BIT |
| 435 | #define JL_LEAF4VALUEAREA(Pjv,Pop1) (((PWord_t)(Pjv)) + j__L_Leaf4Offset[Pop1]) |
| 436 | #define JL_LEAF5VALUEAREA(Pjv,Pop1) (((PWord_t)(Pjv)) + j__L_Leaf5Offset[Pop1]) |
| 437 | #define JL_LEAF6VALUEAREA(Pjv,Pop1) (((PWord_t)(Pjv)) + j__L_Leaf6Offset[Pop1]) |
| 438 | #define JL_LEAF7VALUEAREA(Pjv,Pop1) (((PWord_t)(Pjv)) + j__L_Leaf7Offset[Pop1]) |
| 439 | #endif |
| 440 | #define JL_LEAFWVALUEAREA(Pjv,Pop1) (((PWord_t)(Pjv)) + j__L_LeafWOffset[Pop1]) |
| 441 | |
| 442 | #define JL_LEAF1POPTOWORDS(Pop1) (j__L_Leaf1PopToWords[Pop1]) |
| 443 | #define JL_LEAF2POPTOWORDS(Pop1) (j__L_Leaf2PopToWords[Pop1]) |
| 444 | #define JL_LEAF3POPTOWORDS(Pop1) (j__L_Leaf3PopToWords[Pop1]) |
| 445 | #ifdef JU_64BIT |
| 446 | #define JL_LEAF4POPTOWORDS(Pop1) (j__L_Leaf4PopToWords[Pop1]) |
| 447 | #define JL_LEAF5POPTOWORDS(Pop1) (j__L_Leaf5PopToWords[Pop1]) |
| 448 | #define JL_LEAF6POPTOWORDS(Pop1) (j__L_Leaf6PopToWords[Pop1]) |
| 449 | #define JL_LEAF7POPTOWORDS(Pop1) (j__L_Leaf7PopToWords[Pop1]) |
| 450 | #endif |
| 451 | #define JL_LEAFWPOPTOWORDS(Pop1) (j__L_LeafWPopToWords[Pop1]) |
| 452 | #define JL_LEAFVPOPTOWORDS(Pop1) (j__L_LeafVPopToWords[Pop1]) |
| 453 | |
| 454 | |
| 455 | // FUNCTIONS TO ALLOCATE OBJECTS: |
| 456 | |
| 457 | PjLpm_t j__udyLAllocJLPM(void); // constant size. |
| 458 | |
| 459 | Pjbl_t j__udyLAllocJBL( PjLpm_t); // constant size. |
| 460 | Pjbb_t j__udyLAllocJBB( PjLpm_t); // constant size. |
| 461 | Pjp_t j__udyLAllocJBBJP(Word_t, PjLpm_t); |
| 462 | Pjbu_t j__udyLAllocJBU( PjLpm_t); // constant size. |
| 463 | |
| 464 | Pjll_t j__udyLAllocJLL1( Word_t, PjLpm_t); |
| 465 | Pjll_t j__udyLAllocJLL2( Word_t, PjLpm_t); |
| 466 | Pjll_t j__udyLAllocJLL3( Word_t, PjLpm_t); |
| 467 | |
| 468 | #ifdef JU_64BIT |
| 469 | Pjll_t j__udyLAllocJLL4( Word_t, PjLpm_t); |
| 470 | Pjll_t j__udyLAllocJLL5( Word_t, PjLpm_t); |
| 471 | Pjll_t j__udyLAllocJLL6( Word_t, PjLpm_t); |
| 472 | Pjll_t j__udyLAllocJLL7( Word_t, PjLpm_t); |
| 473 | #endif |
| 474 | |
| 475 | Pjlw_t j__udyLAllocJLW( Word_t ); // no PjLpm_t needed. |
| 476 | PjLlb_t j__udyLAllocJLB1( PjLpm_t); // constant size. |
| 477 | Pjv_t j__udyLAllocJV( Word_t, PjLpm_t); |
| 478 | |
| 479 | |
| 480 | // FUNCTIONS TO FREE OBJECTS: |
| 481 | |
| 482 | void j__udyLFreeJLPM( PjLpm_t, PjLpm_t); // constant size. |
| 483 | |
| 484 | void j__udyLFreeJBL( Pjbl_t, PjLpm_t); // constant size. |
| 485 | void j__udyLFreeJBB( Pjbb_t, PjLpm_t); // constant size. |
| 486 | void j__udyLFreeJBBJP(Pjp_t, Word_t, PjLpm_t); |
| 487 | void j__udyLFreeJBU( Pjbu_t, PjLpm_t); // constant size. |
| 488 | |
| 489 | void j__udyLFreeJLL1( Pjll_t, Word_t, PjLpm_t); |
| 490 | void j__udyLFreeJLL2( Pjll_t, Word_t, PjLpm_t); |
| 491 | void j__udyLFreeJLL3( Pjll_t, Word_t, PjLpm_t); |
| 492 | |
| 493 | #ifdef JU_64BIT |
| 494 | void j__udyLFreeJLL4( Pjll_t, Word_t, PjLpm_t); |
| 495 | void j__udyLFreeJLL5( Pjll_t, Word_t, PjLpm_t); |
| 496 | void j__udyLFreeJLL6( Pjll_t, Word_t, PjLpm_t); |
| 497 | void j__udyLFreeJLL7( Pjll_t, Word_t, PjLpm_t); |
| 498 | #endif |
| 499 | |
| 500 | void j__udyLFreeJLW( Pjlw_t, Word_t, PjLpm_t); |
| 501 | void j__udyLFreeJLB1( PjLlb_t, PjLpm_t); // constant size. |
| 502 | void j__udyLFreeJV( Pjv_t, Word_t, PjLpm_t); |
| 503 | void j__udyLFreeSM( Pjp_t, PjLpm_t); // everything below Pjp. |
| 504 | |
| 505 | #endif // ! _JUDYL_INCLUDED |