| 1 | // Copyright (C) 2000 - 2002 Hewlett-Packard Company |
| 2 | // |
| 3 | // This program is free software; you can redistribute it and/or modify it |
| 4 | // under the term of the GNU Lesser General Public License as published by the |
| 5 | // Free Software Foundation; either version 2 of the License, or (at your |
| 6 | // option) any later version. |
| 7 | // |
| 8 | // This program is distributed in the hope that it will be useful, but WITHOUT |
| 9 | // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 10 | // FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License |
| 11 | // for more details. |
| 12 | // |
| 13 | // You should have received a copy of the GNU Lesser General Public License |
| 14 | // along with this program; if not, write to the Free Software Foundation, |
| 15 | // Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| 16 | // _________________ |
| 17 | |
| 18 | // @(#) $Revision: 4.26 $ $Source: /judy/src/JudyCommon/JudyCreateBranch.c $ |
| 19 | |
| 20 | // Branch creation functions for Judy1 and JudyL. |
| 21 | // Compile with one of -DJUDY1 or -DJUDYL. |
| 22 | |
| 23 | #if (! (defined(JUDY1) || defined(JUDYL))) |
| 24 | #error: One of -DJUDY1 or -DJUDYL must be specified. |
| 25 | #endif |
| 26 | |
| 27 | #ifdef JUDY1 |
| 28 | #include "Judy1.h" |
| 29 | #else |
| 30 | #include "JudyL.h" |
| 31 | #endif |
| 32 | |
| 33 | #include "JudyPrivate1L.h" |
| 34 | |
| 35 | |
| 36 | // **************************************************************************** |
| 37 | // J U D Y C R E A T E B R A N C H L |
| 38 | // |
| 39 | // Build a BranchL from an array of JPs and associated 1 byte digits |
| 40 | // (expanses). Return with Pjp pointing to the BranchL. Caller must |
| 41 | // deallocate passed arrays, if necessary. |
| 42 | // |
| 43 | // We have no idea what kind of BranchL it is, so caller must set the jp_Type. |
| 44 | // |
| 45 | // Return -1 if error (details in Pjpm), otherwise return 1. |
| 46 | |
| 47 | FUNCTION int j__udyCreateBranchL( |
| 48 | Pjp_t Pjp, // Build JPs from this place |
| 49 | Pjp_t PJPs, // Array of JPs to put into Bitmap branch |
| 50 | uint8_t Exp[], // Array of expanses to put into bitmap |
| 51 | Word_t ExpCnt, // Number of above JPs and Expanses |
| 52 | Pvoid_t Pjpm) |
| 53 | { |
| 54 | Pjbl_t PjblRaw; // pointer to linear branch. |
| 55 | Pjbl_t Pjbl; |
| 56 | |
| 57 | assert(ExpCnt <= cJU_BRANCHLMAXJPS); |
| 58 | |
| 59 | PjblRaw = j__udyAllocJBL(Pjpm); |
| 60 | if (PjblRaw == (Pjbl_t) NULL) return(-1); |
| 61 | Pjbl = P_JBL(PjblRaw); |
| 62 | |
| 63 | // Build a Linear Branch |
| 64 | Pjbl->jbl_NumJPs = ExpCnt; |
| 65 | |
| 66 | // Copy from the Linear branch from splayed leaves |
| 67 | JU_COPYMEM(Pjbl->jbl_Expanse, Exp, ExpCnt); |
| 68 | JU_COPYMEM(Pjbl->jbl_jp, PJPs, ExpCnt); |
| 69 | |
| 70 | // Pass back new pointer to the Linear branch in JP |
| 71 | Pjp->jp_Addr = (Word_t) PjblRaw; |
| 72 | |
| 73 | return(1); |
| 74 | |
| 75 | } // j__udyCreateBranchL() |
| 76 | |
| 77 | |
| 78 | // **************************************************************************** |
| 79 | // J U D Y C R E A T E B R A N C H B |
| 80 | // |
| 81 | // Build a BranchB from an array of JPs and associated 1 byte digits |
| 82 | // (expanses). Return with Pjp pointing to the BranchB. Caller must |
| 83 | // deallocate passed arrays, if necessary. |
| 84 | // |
| 85 | // We have no idea what kind of BranchB it is, so caller must set the jp_Type. |
| 86 | // |
| 87 | // Return -1 if error (details in Pjpm), otherwise return 1. |
| 88 | |
| 89 | FUNCTION int j__udyCreateBranchB( |
| 90 | Pjp_t Pjp, // Build JPs from this place |
| 91 | Pjp_t PJPs, // Array of JPs to put into Bitmap branch |
| 92 | uint8_t Exp[], // Array of expanses to put into bitmap |
| 93 | Word_t ExpCnt, // Number of above JPs and Expanses |
| 94 | Pvoid_t Pjpm) |
| 95 | { |
| 96 | Pjbb_t PjbbRaw; // pointer to bitmap branch. |
| 97 | Pjbb_t Pjbb; |
| 98 | Word_t ii, jj; // Temps |
| 99 | uint8_t CurrSubExp; // Current sub expanse for BM |
| 100 | |
| 101 | // This assertion says the number of populated subexpanses is not too large. |
| 102 | // This function is only called when a BranchL overflows to a BranchB or when a |
| 103 | // cascade occurs, meaning a leaf overflows. Either way ExpCnt cant be very |
| 104 | // large, in fact a lot smaller than cJU_BRANCHBMAXJPS. (Otherwise a BranchU |
| 105 | // would be used.) Popping this assertion means something (unspecified) has |
| 106 | // gone very wrong, or else Judys design criteria have changed, although in |
| 107 | // fact there should be no HARM in creating a BranchB with higher actual |
| 108 | // fanout. |
| 109 | |
| 110 | assert(ExpCnt <= cJU_BRANCHBMAXJPS); |
| 111 | |
| 112 | // Get memory for a Bitmap branch |
| 113 | PjbbRaw = j__udyAllocJBB(Pjpm); |
| 114 | if (PjbbRaw == (Pjbb_t) NULL) return(-1); |
| 115 | Pjbb = P_JBB(PjbbRaw); |
| 116 | |
| 117 | // Get 1st "sub" expanse (0..7) of bitmap branch |
| 118 | CurrSubExp = Exp[0] / cJU_BITSPERSUBEXPB; |
| 119 | |
| 120 | // Index thru all 1 byte sized expanses: |
| 121 | |
| 122 | for (jj = ii = 0; ii <= ExpCnt; ii++) |
| 123 | { |
| 124 | Word_t SubExp; // Cannot be a uint8_t |
| 125 | |
| 126 | // Make sure we cover the last one |
| 127 | if (ii == ExpCnt) |
| 128 | { |
| 129 | SubExp = cJU_ALLONES; // Force last one |
| 130 | } |
| 131 | else |
| 132 | { |
| 133 | // Calculate the "sub" expanse of the byte expanse |
| 134 | SubExp = Exp[ii] / cJU_BITSPERSUBEXPB; // Bits 5..7. |
| 135 | |
| 136 | // Set the bit that represents the expanse in Exp[] |
| 137 | JU_JBB_BITMAP(Pjbb, SubExp) |= JU_BITPOSMASKB(Exp[ii]); |
| 138 | } |
| 139 | // Check if a new "sub" expanse range needed |
| 140 | if (SubExp != CurrSubExp) |
| 141 | { |
| 142 | // Get number of JPs in this sub expanse |
| 143 | Word_t NumJP = ii - jj; |
| 144 | Pjp_t PjpRaw; |
| 145 | Pjp_t Pjp; |
| 146 | |
| 147 | PjpRaw = j__udyAllocJBBJP(NumJP, Pjpm); |
| 148 | Pjp = P_JP(PjpRaw); |
| 149 | |
| 150 | if (PjpRaw == (Pjp_t) NULL) // out of memory. |
| 151 | { |
| 152 | |
| 153 | // Free any previous allocations: |
| 154 | |
| 155 | while(CurrSubExp--) |
| 156 | { |
| 157 | NumJP = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, |
| 158 | CurrSubExp)); |
| 159 | if (NumJP) |
| 160 | { |
| 161 | j__udyFreeJBBJP(JU_JBB_PJP(Pjbb, |
| 162 | CurrSubExp), NumJP, Pjpm); |
| 163 | } |
| 164 | } |
| 165 | j__udyFreeJBB(PjbbRaw, Pjpm); |
| 166 | return(-1); |
| 167 | } |
| 168 | |
| 169 | // Place the array of JPs in bitmap branch: |
| 170 | |
| 171 | JU_JBB_PJP(Pjbb, CurrSubExp) = PjpRaw; |
| 172 | |
| 173 | // Copy the JPs to new leaf: |
| 174 | |
| 175 | JU_COPYMEM(Pjp, PJPs + jj, NumJP); |
| 176 | |
| 177 | // On to the next bitmap branch "sub" expanse: |
| 178 | |
| 179 | jj = ii; |
| 180 | CurrSubExp = SubExp; |
| 181 | } |
| 182 | } // for each 1-byte expanse |
| 183 | |
| 184 | // Pass back some of the JP to the new Bitmap branch: |
| 185 | |
| 186 | Pjp->jp_Addr = (Word_t) PjbbRaw; |
| 187 | |
| 188 | return(1); |
| 189 | |
| 190 | } // j__udyCreateBranchB() |
| 191 | |
| 192 | |
| 193 | // **************************************************************************** |
| 194 | // J U D Y C R E A T E B R A N C H U |
| 195 | // |
| 196 | // Build a BranchU from a BranchB. Return with Pjp pointing to the BranchU. |
| 197 | // Free the BranchB and its JP subarrays. |
| 198 | // |
| 199 | // Return -1 if error (details in Pjpm), otherwise return 1. |
| 200 | |
| 201 | FUNCTION int j__udyCreateBranchU( |
| 202 | Pjp_t Pjp, |
| 203 | Pvoid_t Pjpm) |
| 204 | { |
| 205 | jp_t JPNull; |
| 206 | Pjbu_t PjbuRaw; |
| 207 | Pjbu_t Pjbu; |
| 208 | Pjbb_t PjbbRaw; |
| 209 | Pjbb_t Pjbb; |
| 210 | Word_t ii, jj; |
| 211 | BITMAPB_t BitMap; |
| 212 | Pjp_t PDstJP; |
| 213 | #ifdef JU_STAGED_EXP |
| 214 | jbu_t BranchU; // Staged uncompressed branch |
| 215 | #else |
| 216 | |
| 217 | // Allocate memory for a BranchU: |
| 218 | |
| 219 | PjbuRaw = j__udyAllocJBU(Pjpm); |
| 220 | if (PjbuRaw == (Pjbu_t) NULL) return(-1); |
| 221 | Pjbu = P_JBU(PjbuRaw); |
| 222 | #endif |
| 223 | JU_JPSETADT(&JPNull, 0, 0, JU_JPTYPE(Pjp) - cJU_JPBRANCH_B2 + cJU_JPNULL1); |
| 224 | |
| 225 | // Get the pointer to the BranchB: |
| 226 | |
| 227 | PjbbRaw = (Pjbb_t) (Pjp->jp_Addr); |
| 228 | Pjbb = P_JBB(PjbbRaw); |
| 229 | |
| 230 | // Set the pointer to the Uncompressed branch |
| 231 | #ifdef JU_STAGED_EXP |
| 232 | PDstJP = BranchU.jbu_jp; |
| 233 | #else |
| 234 | PDstJP = Pjbu->jbu_jp; |
| 235 | #endif |
| 236 | for (ii = 0; ii < cJU_NUMSUBEXPB; ii++) |
| 237 | { |
| 238 | Pjp_t PjpA; |
| 239 | Pjp_t PjpB; |
| 240 | |
| 241 | PjpB = PjpA = P_JP(JU_JBB_PJP(Pjbb, ii)); |
| 242 | |
| 243 | // Get the bitmap for this subexpanse |
| 244 | BitMap = JU_JBB_BITMAP(Pjbb, ii); |
| 245 | |
| 246 | // NULL empty subexpanses |
| 247 | if (BitMap == 0) |
| 248 | { |
| 249 | // But, fill with NULLs |
| 250 | for (jj = 0; jj < cJU_BITSPERSUBEXPB; jj++) |
| 251 | { |
| 252 | PDstJP[jj] = JPNull; |
| 253 | } |
| 254 | PDstJP += cJU_BITSPERSUBEXPB; |
| 255 | continue; |
| 256 | } |
| 257 | // Check if Uncompressed subexpanse |
| 258 | if (BitMap == cJU_FULLBITMAPB) |
| 259 | { |
| 260 | // Copy subexpanse to the Uncompressed branch intact |
| 261 | JU_COPYMEM(PDstJP, PjpA, cJU_BITSPERSUBEXPB); |
| 262 | |
| 263 | // Bump to next subexpanse |
| 264 | PDstJP += cJU_BITSPERSUBEXPB; |
| 265 | |
| 266 | // Set length of subexpanse |
| 267 | jj = cJU_BITSPERSUBEXPB; |
| 268 | } |
| 269 | else |
| 270 | { |
| 271 | for (jj = 0; jj < cJU_BITSPERSUBEXPB; jj++) |
| 272 | { |
| 273 | // Copy JP or NULLJP depending on bit |
| 274 | if (BitMap & 1) { *PDstJP = *PjpA++; } |
| 275 | else { *PDstJP = JPNull; } |
| 276 | |
| 277 | PDstJP++; // advance to next JP |
| 278 | BitMap >>= 1; |
| 279 | } |
| 280 | jj = PjpA - PjpB; |
| 281 | } |
| 282 | |
| 283 | // Free the subexpanse: |
| 284 | |
| 285 | j__udyFreeJBBJP(JU_JBB_PJP(Pjbb, ii), jj, Pjpm); |
| 286 | |
| 287 | } // for each JP in BranchU |
| 288 | |
| 289 | #ifdef JU_STAGED_EXP |
| 290 | |
| 291 | // Allocate memory for a BranchU: |
| 292 | |
| 293 | PjbuRaw = j__udyAllocJBU(Pjpm); |
| 294 | if (PjbuRaw == (Pjbu_t) NULL) return(-1); |
| 295 | Pjbu = P_JBU(PjbuRaw); |
| 296 | |
| 297 | // Copy staged branch to newly allocated branch: |
| 298 | // |
| 299 | // TBD: I think this code is broken. |
| 300 | |
| 301 | *Pjbu = BranchU; |
| 302 | |
| 303 | #endif // JU_STAGED_EXP |
| 304 | |
| 305 | // Finally free the BranchB and put the BranchU in its place: |
| 306 | |
| 307 | j__udyFreeJBB(PjbbRaw, Pjpm); |
| 308 | |
| 309 | Pjp->jp_Addr = (Word_t) PjbuRaw; |
| 310 | Pjp->jp_Type += cJU_JPBRANCH_U - cJU_JPBRANCH_B; |
| 311 | |
| 312 | return(1); |
| 313 | |
| 314 | } // j__udyCreateBranchU() |