| 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.51 $ $Source: /judy/src/JudyCommon/JudyFreeArray.c $ |
| 19 | // |
| 20 | // Judy1FreeArray() and JudyLFreeArray() functions for Judy1 and JudyL. |
| 21 | // Compile with one of -DJUDY1 or -DJUDYL. |
| 22 | // Return the number of bytes freed from the array. |
| 23 | |
| 24 | #if (! (defined(JUDY1) || defined(JUDYL))) |
| 25 | #error: One of -DJUDY1 or -DJUDYL must be specified. |
| 26 | #endif |
| 27 | |
| 28 | #ifdef JUDY1 |
| 29 | #include "Judy1.h" |
| 30 | #else |
| 31 | #include "JudyL.h" |
| 32 | #endif |
| 33 | |
| 34 | #include "JudyPrivate1L.h" |
| 35 | |
| 36 | DBGCODE(extern void JudyCheckPop(Pvoid_t PArray);) |
| 37 | |
| 38 | |
| 39 | // **************************************************************************** |
| 40 | // J U D Y 1 F R E E A R R A Y |
| 41 | // J U D Y L F R E E A R R A Y |
| 42 | // |
| 43 | // See the Judy*(3C) manual entry for details. |
| 44 | // |
| 45 | // This code is written recursively, at least at first, because thats much |
| 46 | // simpler. Hope its fast enough. |
| 47 | |
| 48 | #ifdef JUDY1 |
| 49 | FUNCTION Word_t Judy1FreeArray |
| 50 | #else |
| 51 | FUNCTION Word_t JudyLFreeArray |
| 52 | #endif |
| 53 | ( |
| 54 | PPvoid_t PPArray, // array to free. |
| 55 | PJError_t PJError // optional, for returning error info. |
| 56 | ) |
| 57 | { |
| 58 | jpm_t jpm; // local to accumulate free statistics. |
| 59 | |
| 60 | // CHECK FOR NULL POINTER (error by caller): |
| 61 | |
| 62 | if (PPArray == (PPvoid_t) NULL) |
| 63 | { |
| 64 | JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY); |
| 65 | return(JERR); |
| 66 | } |
| 67 | |
| 68 | DBGCODE(JudyCheckPop(*PPArray);) |
| 69 | |
| 70 | // Zero jpm.jpm_Pop0 (meaning the array will be empty in a moment) for accurate |
| 71 | // logging in TRACEMI2. |
| 72 | |
| 73 | jpm.jpm_Pop0 = 0; // see above. |
| 74 | jpm.jpm_TotalMemWords = 0; // initialize memory freed. |
| 75 | |
| 76 | // Empty array: |
| 77 | |
| 78 | if (P_JLW(*PPArray) == (Pjlw_t) NULL) return(0); |
| 79 | |
| 80 | // PROCESS TOP LEVEL "JRP" BRANCHES AND LEAF: |
| 81 | |
| 82 | if (JU_LEAFW_POP0(*PPArray) < cJU_LEAFW_MAXPOP1) // must be a LEAFW |
| 83 | { |
| 84 | Pjlw_t Pjlw = P_JLW(*PPArray); // first word of leaf. |
| 85 | |
| 86 | j__udyFreeJLW(Pjlw, Pjlw[0] + 1, &jpm); |
| 87 | *PPArray = (Pvoid_t) NULL; // make an empty array. |
| 88 | return (-(jpm.jpm_TotalMemWords * cJU_BYTESPERWORD)); // see above. |
| 89 | } |
| 90 | else |
| 91 | |
| 92 | // Rootstate leaves: just free the leaf: |
| 93 | |
| 94 | // Common code for returning the amount of memory freed. |
| 95 | // |
| 96 | // Note: In a an ordinary LEAFW, pop0 = *PPArray[0]. |
| 97 | // |
| 98 | // Accumulate (negative) words freed, while freeing objects. |
| 99 | // Return the positive bytes freed. |
| 100 | |
| 101 | { |
| 102 | Pjpm_t Pjpm = P_JPM(*PPArray); |
| 103 | Word_t TotalMem = Pjpm->jpm_TotalMemWords; |
| 104 | |
| 105 | j__udyFreeSM(&(Pjpm->jpm_JP), &jpm); // recurse through tree. |
| 106 | j__udyFreeJPM(Pjpm, &jpm); |
| 107 | |
| 108 | // Verify the array was not corrupt. This means that amount of memory freed |
| 109 | // (which is negative) is equal to the initial amount: |
| 110 | |
| 111 | if (TotalMem + jpm.jpm_TotalMemWords) |
| 112 | { |
| 113 | JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); |
| 114 | return(JERR); |
| 115 | } |
| 116 | |
| 117 | *PPArray = (Pvoid_t) NULL; // make an empty array. |
| 118 | return (TotalMem * cJU_BYTESPERWORD); |
| 119 | } |
| 120 | |
| 121 | } // Judy1FreeArray() / JudyLFreeArray() |
| 122 | |
| 123 | |
| 124 | // **************************************************************************** |
| 125 | // __ J U D Y F R E E S M |
| 126 | // |
| 127 | // Given a pointer to a JP, recursively visit and free (depth first) all nodes |
| 128 | // in a Judy array BELOW the JP, but not the JP itself. Accumulate in *Pjpm |
| 129 | // the total words freed (as a negative value). "SM" = State Machine. |
| 130 | // |
| 131 | // Note: Corruption is not detected at this level because during a FreeArray, |
| 132 | // if the code hasnt already core dumped, its better to remain silent, even |
| 133 | // if some memory has not been freed, than to bother the caller about the |
| 134 | // corruption. TBD: Is this true? If not, must list all legitimate JPNULL |
| 135 | // and JPIMMED above first, and revert to returning bool_t (see 4.34). |
| 136 | |
| 137 | FUNCTION void j__udyFreeSM( |
| 138 | Pjp_t Pjp, // top of Judy (top-state). |
| 139 | Pjpm_t Pjpm) // to return words freed. |
| 140 | { |
| 141 | Word_t Pop1; |
| 142 | |
| 143 | switch (JU_JPTYPE(Pjp)) |
| 144 | { |
| 145 | |
| 146 | #ifdef JUDY1 |
| 147 | |
| 148 | // FULL EXPANSE -- nothing to free for this jp_Type. |
| 149 | |
| 150 | case cJ1_JPFULLPOPU1: |
| 151 | break; |
| 152 | #endif |
| 153 | |
| 154 | // JUDY BRANCH -- free the sub-tree depth first: |
| 155 | |
| 156 | // LINEAR BRANCH -- visit each JP in the JBLs list, then free the JBL: |
| 157 | // |
| 158 | // Note: There are no null JPs in a JBL. |
| 159 | |
| 160 | case cJU_JPBRANCH_L: |
| 161 | case cJU_JPBRANCH_L2: |
| 162 | case cJU_JPBRANCH_L3: |
| 163 | #ifdef JU_64BIT |
| 164 | case cJU_JPBRANCH_L4: |
| 165 | case cJU_JPBRANCH_L5: |
| 166 | case cJU_JPBRANCH_L6: |
| 167 | case cJU_JPBRANCH_L7: |
| 168 | #endif // JU_64BIT |
| 169 | { |
| 170 | Pjbl_t Pjbl = P_JBL(Pjp->jp_Addr); |
| 171 | Word_t offset; |
| 172 | |
| 173 | for (offset = 0; offset < Pjbl->jbl_NumJPs; ++offset) |
| 174 | j__udyFreeSM((Pjbl->jbl_jp) + offset, Pjpm); |
| 175 | |
| 176 | j__udyFreeJBL((Pjbl_t) (Pjp->jp_Addr), Pjpm); |
| 177 | break; |
| 178 | } |
| 179 | |
| 180 | |
| 181 | // BITMAP BRANCH -- visit each JP in the JBBs list based on the bitmap, also |
| 182 | // |
| 183 | // Note: There are no null JPs in a JBB. |
| 184 | |
| 185 | case cJU_JPBRANCH_B: |
| 186 | case cJU_JPBRANCH_B2: |
| 187 | case cJU_JPBRANCH_B3: |
| 188 | #ifdef JU_64BIT |
| 189 | case cJU_JPBRANCH_B4: |
| 190 | case cJU_JPBRANCH_B5: |
| 191 | case cJU_JPBRANCH_B6: |
| 192 | case cJU_JPBRANCH_B7: |
| 193 | #endif // JU_64BIT |
| 194 | { |
| 195 | Word_t subexp; |
| 196 | Word_t offset; |
| 197 | Word_t jpcount; |
| 198 | |
| 199 | Pjbb_t Pjbb = P_JBB(Pjp->jp_Addr); |
| 200 | |
| 201 | for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp) |
| 202 | { |
| 203 | jpcount = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp)); |
| 204 | |
| 205 | if (jpcount) |
| 206 | { |
| 207 | for (offset = 0; offset < jpcount; ++offset) |
| 208 | { |
| 209 | j__udyFreeSM(P_JP(JU_JBB_PJP(Pjbb, subexp)) + offset, |
| 210 | Pjpm); |
| 211 | } |
| 212 | j__udyFreeJBBJP(JU_JBB_PJP(Pjbb, subexp), jpcount, Pjpm); |
| 213 | } |
| 214 | } |
| 215 | j__udyFreeJBB((Pjbb_t) (Pjp->jp_Addr), Pjpm); |
| 216 | |
| 217 | break; |
| 218 | } |
| 219 | |
| 220 | |
| 221 | // UNCOMPRESSED BRANCH -- visit each JP in the JBU array, then free the JBU |
| 222 | // itself: |
| 223 | // |
| 224 | // Note: Null JPs are handled during recursion at a lower state. |
| 225 | |
| 226 | case cJU_JPBRANCH_U: |
| 227 | case cJU_JPBRANCH_U2: |
| 228 | case cJU_JPBRANCH_U3: |
| 229 | #ifdef JU_64BIT |
| 230 | case cJU_JPBRANCH_U4: |
| 231 | case cJU_JPBRANCH_U5: |
| 232 | case cJU_JPBRANCH_U6: |
| 233 | case cJU_JPBRANCH_U7: |
| 234 | #endif // JU_64BIT |
| 235 | { |
| 236 | Word_t offset; |
| 237 | Pjbu_t Pjbu = P_JBU(Pjp->jp_Addr); |
| 238 | |
| 239 | for (offset = 0; offset < cJU_BRANCHUNUMJPS; ++offset) |
| 240 | j__udyFreeSM((Pjbu->jbu_jp) + offset, Pjpm); |
| 241 | |
| 242 | j__udyFreeJBU((Pjbu_t) (Pjp->jp_Addr), Pjpm); |
| 243 | break; |
| 244 | } |
| 245 | |
| 246 | |
| 247 | // -- Cases below here terminate and do not recurse. -- |
| 248 | |
| 249 | |
| 250 | // LINEAR LEAF -- just free the leaf; size is computed from jp_Type: |
| 251 | // |
| 252 | // Note: cJU_JPLEAF1 is a special case, see discussion in ../Judy1/Judy1.h |
| 253 | |
| 254 | #if (defined(JUDYL) || (! defined(JU_64BIT))) |
| 255 | case cJU_JPLEAF1: |
| 256 | Pop1 = JU_JPLEAF_POP0(Pjp) + 1; |
| 257 | j__udyFreeJLL1((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm); |
| 258 | break; |
| 259 | #endif |
| 260 | |
| 261 | case cJU_JPLEAF2: |
| 262 | Pop1 = JU_JPLEAF_POP0(Pjp) + 1; |
| 263 | j__udyFreeJLL2((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm); |
| 264 | break; |
| 265 | |
| 266 | case cJU_JPLEAF3: |
| 267 | Pop1 = JU_JPLEAF_POP0(Pjp) + 1; |
| 268 | j__udyFreeJLL3((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm); |
| 269 | break; |
| 270 | |
| 271 | #ifdef JU_64BIT |
| 272 | case cJU_JPLEAF4: |
| 273 | Pop1 = JU_JPLEAF_POP0(Pjp) + 1; |
| 274 | j__udyFreeJLL4((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm); |
| 275 | break; |
| 276 | |
| 277 | case cJU_JPLEAF5: |
| 278 | Pop1 = JU_JPLEAF_POP0(Pjp) + 1; |
| 279 | j__udyFreeJLL5((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm); |
| 280 | break; |
| 281 | |
| 282 | case cJU_JPLEAF6: |
| 283 | Pop1 = JU_JPLEAF_POP0(Pjp) + 1; |
| 284 | j__udyFreeJLL6((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm); |
| 285 | break; |
| 286 | |
| 287 | case cJU_JPLEAF7: |
| 288 | Pop1 = JU_JPLEAF_POP0(Pjp) + 1; |
| 289 | j__udyFreeJLL7((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm); |
| 290 | break; |
| 291 | #endif // JU_64BIT |
| 292 | |
| 293 | |
| 294 | // BITMAP LEAF -- free sub-expanse arrays of JPs, then free the JBB. |
| 295 | |
| 296 | case cJU_JPLEAF_B1: |
| 297 | { |
| 298 | #ifdef JUDYL |
| 299 | Word_t subexp; |
| 300 | Word_t jpcount; |
| 301 | Pjlb_t Pjlb = P_JLB(Pjp->jp_Addr); |
| 302 | |
| 303 | // Free the value areas in the bitmap leaf: |
| 304 | |
| 305 | for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp) |
| 306 | { |
| 307 | jpcount = j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp)); |
| 308 | |
| 309 | if (jpcount) |
| 310 | j__udyLFreeJV(JL_JLB_PVALUE(Pjlb, subexp), jpcount, Pjpm); |
| 311 | } |
| 312 | #endif // JUDYL |
| 313 | |
| 314 | j__udyFreeJLB1((Pjlb_t) (Pjp->jp_Addr), Pjpm); |
| 315 | break; |
| 316 | |
| 317 | } // case cJU_JPLEAF_B1 |
| 318 | |
| 319 | #ifdef JUDYL |
| 320 | |
| 321 | |
| 322 | // IMMED*: |
| 323 | // |
| 324 | // For JUDYL, all non JPIMMED_*_01s have a LeafV which must be freed: |
| 325 | |
| 326 | case cJU_JPIMMED_1_02: |
| 327 | case cJU_JPIMMED_1_03: |
| 328 | #ifdef JU_64BIT |
| 329 | case cJU_JPIMMED_1_04: |
| 330 | case cJU_JPIMMED_1_05: |
| 331 | case cJU_JPIMMED_1_06: |
| 332 | case cJU_JPIMMED_1_07: |
| 333 | #endif |
| 334 | Pop1 = JU_JPTYPE(Pjp) - cJU_JPIMMED_1_02 + 2; |
| 335 | j__udyLFreeJV((Pjv_t) (Pjp->jp_Addr), Pop1, Pjpm); |
| 336 | break; |
| 337 | |
| 338 | #ifdef JU_64BIT |
| 339 | case cJU_JPIMMED_2_02: |
| 340 | case cJU_JPIMMED_2_03: |
| 341 | |
| 342 | Pop1 = JU_JPTYPE(Pjp) - cJU_JPIMMED_2_02 + 2; |
| 343 | j__udyLFreeJV((Pjv_t) (Pjp->jp_Addr), Pop1, Pjpm); |
| 344 | break; |
| 345 | |
| 346 | case cJU_JPIMMED_3_02: |
| 347 | j__udyLFreeJV((Pjv_t) (Pjp->jp_Addr), 2, Pjpm); |
| 348 | break; |
| 349 | |
| 350 | #endif // JU_64BIT |
| 351 | #endif // JUDYL |
| 352 | |
| 353 | |
| 354 | // OTHER JPNULL, JPIMMED, OR UNEXPECTED TYPE -- nothing to free for this type: |
| 355 | // |
| 356 | // Note: Lump together no-op and invalid JP types; see function header |
| 357 | // comments. |
| 358 | |
| 359 | default: break; |
| 360 | |
| 361 | } // switch (JU_JPTYPE(Pjp)) |
| 362 | |
| 363 | } // j__udyFreeSM() |