1
// Copyright (C) 2000 - 2002 Hewlett-Packard Company
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.
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
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
18
// @(#) $Revision: 4.51 $ $Source: /judy/src/JudyCommon/JudyFreeArray.c $
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.
24
#if (! (JUDY1 || JUDYL))
25
Error: One of -DJUDY1 or -DJUDYL must be specified.
34
#include "JudyPrivate1L.h"
36
DBGCODE(extern void JudyCheckPop(Pvoid_t PArray);)
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
43
// See the Judy*(3C) manual entry for details.
45
// This code is written recursively, at least at first, because that's much
46
// simpler. Hope it's fast enough.
49
FUNCTION Word_t Judy1FreeArray(
51
FUNCTION Word_t JudyLFreeArray(
53
PPvoid_t PPArray, // array to free.
54
PJError_t PJError) // optional, for returning error info.
56
jpm_t jpm; // local to accumulate free statistics.
57
Word_t JAPtype; // JAP type part of *PPArray.
60
// CHECK FOR NULL POINTER (error by caller):
62
if (PPArray == (PPvoid_t) NULL)
64
JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY);
68
DBGCODE(JudyCheckPop(*PPArray);)
71
// PROCESS TOP LEVEL "JAP" BRANCHES AND LEAVES:
73
// Zero jpm.jpm_Pop0 (meaning the array will be empty in a moment) for accurate
74
// logging in TRACEMI2.
76
jpm.jpm_Pop0 = 0; // see above.
77
jpm.jpm_TotalMemWords = 0; // initialize memory freed.
79
// Get pointer and type from array pointer:
81
JAPtype = JAPTYPE(*PPArray);
88
// Note: It is an error to have a JAPtype for a JAPNULL with the rest of the
89
// pointer not being null.
93
if (P_JLW(*PPArray) == (Pjlw_t) NULL) return(0);
94
break; // invalid JAP, although possibly a valid non-Judy pointer.
97
// Rootstate leaves: just free the leaf:
99
// Common code for returning the amount of memory freed.
101
// Note: In a an ordinary JAPLEAF, pop0 = *PPArray[0].
103
// Accumulate (negative) words freed, while freeing objects.
104
// Return the positive bytes freed.
108
Pjlw_t Pjlw = P_JLW(*PPArray); // first word of leaf.
110
__JudyFreeJLW(Pjlw, Pjlw[0] + 1, &jpm);
111
*PPArray = (Pvoid_t) NULL; // make an empty array.
112
return (-(jpm.jpm_TotalMemWords * cJU_BYTESPERWORD)); // see above.
115
#if (LOW_POP && JUDYL)
116
case cJL_JAPLEAF_POPU1:
118
Pjlw_t Pjlw= P_JLW(*PPArray); // first word of leaf.
120
__JudyFreeJLW(Pjlw, 1, &jpm);
121
*PPArray = (Pvoid_t) NULL; // make an empty array.
122
return (-(jpm.jpm_TotalMemWords * cJU_BYTESPERWORD)); // see above.
124
case cJL_JAPLEAF_POPU2:
126
Pjlw_t Pjlw = P_JLW(*PPArray); // first word of leaf.
128
__JudyFreeJLW(Pjlw, 2, &jpm);
129
*PPArray = (Pvoid_t) NULL; // make an empty array.
130
return (-(jpm.jpm_TotalMemWords * cJU_BYTESPERWORD)); // see above.
136
Pjpm_t Pjpm = P_JPM(*PPArray);
137
Word_t TotalMem = Pjpm->jpm_TotalMemWords;
139
__JudyFreeSM(&(Pjpm->jpm_JP), &jpm); // recurse through tree.
140
__JudyFreeJPM(Pjpm, &jpm);
142
// Verify the array was not corrupt. This means that amount of memory freed
143
// (which is negative) is equal to the initial amount:
145
if (TotalMem + jpm.jpm_TotalMemWords)
147
JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT);
151
*PPArray = (Pvoid_t) NULL; // make an empty array.
152
return (TotalMem * cJU_BYTESPERWORD);
155
// No match above implies invalid root pointer (JAP):
159
} // switch (JAPtype)
161
JUDY1CODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDY1);)
162
JUDYLCODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDYL);)
165
} // Judy1FreeArray() / JudyLFreeArray()
168
// ****************************************************************************
169
// __ J U D Y F R E E S M
171
// Given a pointer to a JP, recursively visit and free (depth first) all nodes
172
// in a Judy array BELOW the JP, but not the JP itself. Accumulate in *Pjpm
173
// the total words freed (as a negative value). "SM" = State Machine.
175
// Note: Corruption is not detected at this level because during a FreeArray,
176
// if the code hasn't already core dumped, it's better to remain silent, even
177
// if some memory has not been freed, than to bother the caller about the
178
// corruption. TBD: Is this true? If not, must list all legitimate JPNULL
179
// and JPIMMED above first, and revert to returning bool_t (see 4.34).
181
FUNCTION void __JudyFreeSM(
182
Pjp_t Pjp, // top of Judy (top-state).
183
Pjpm_t Pjpm) // to return words freed.
187
switch (Pjp->jp_Type)
192
// FULL EXPANSE -- nothing to free for this jp_Type.
194
case cJ1_JPFULLPOPU1:
198
// JUDY BRANCH -- free the sub-tree depth first:
200
// LINEAR BRANCH -- visit each JP in the JBL's list, then free the JBL:
202
// Note: There are no null JPs in a JBL.
205
case cJU_JPBRANCH_L2:
206
case cJU_JPBRANCH_L3:
208
case cJU_JPBRANCH_L4:
209
case cJU_JPBRANCH_L5:
210
case cJU_JPBRANCH_L6:
211
case cJU_JPBRANCH_L7:
214
Pjbl_t Pjbl = P_JBL(Pjp->jp_Addr);
217
for (offset = 0; offset < Pjbl->jbl_NumJPs; ++offset)
218
__JudyFreeSM((Pjbl->jbl_jp) + offset, Pjpm);
220
__JudyFreeJBL((Pjbl_t) (Pjp->jp_Addr), Pjpm);
225
// BITMAP BRANCH -- visit each JP in the JBBs list based on the bitmap, also
227
// Note: There are no null JPs in a JBB.
230
case cJU_JPBRANCH_B2:
231
case cJU_JPBRANCH_B3:
233
case cJU_JPBRANCH_B4:
234
case cJU_JPBRANCH_B5:
235
case cJU_JPBRANCH_B6:
236
case cJU_JPBRANCH_B7:
243
Pjbb_t Pjbb = P_JBB(Pjp->jp_Addr);
245
for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
247
jpcount = __JudyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp));
251
for (offset = 0; offset < jpcount; ++offset)
253
__JudyFreeSM(P_JP(JU_JBB_PJP(Pjbb, subexp)) + offset,
256
__JudyFreeJBBJP(JU_JBB_PJP(Pjbb, subexp), jpcount, Pjpm);
259
__JudyFreeJBB((Pjbb_t) (Pjp->jp_Addr), Pjpm);
265
// UNCOMPRESSED BRANCH -- visit each JP in the JBU array, then free the JBU
268
// Note: Null JPs are handled during recursion at a lower state.
271
case cJU_JPBRANCH_U2:
272
case cJU_JPBRANCH_U3:
274
case cJU_JPBRANCH_U4:
275
case cJU_JPBRANCH_U5:
276
case cJU_JPBRANCH_U6:
277
case cJU_JPBRANCH_U7:
281
Pjbu_t Pjbu = P_JBU(Pjp->jp_Addr);
283
for (offset = 0; offset < cJU_BRANCHUNUMJPS; ++offset)
284
__JudyFreeSM((Pjbu->jbu_jp) + offset, Pjpm);
286
__JudyFreeJBU((Pjbu_t) (Pjp->jp_Addr), Pjpm);
291
// -- Cases below here terminate and do not recurse. --
294
// LINEAR LEAF -- just free the leaf; size is computed from jp_Type:
296
// Note: cJU_JPLEAF1 is a special case, see discussion in ../Judy1/Judy1.h
298
#if (JUDYL || (! JU_64BIT ))
300
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
301
__JudyFreeJLL1((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
306
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
307
__JudyFreeJLL2((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
311
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
312
__JudyFreeJLL3((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
317
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
318
__JudyFreeJLL4((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
322
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
323
__JudyFreeJLL5((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
327
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
328
__JudyFreeJLL6((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
332
Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
333
__JudyFreeJLL7((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
338
// BITMAP LEAF -- free sub-expanse arrays of JPs, then free the JBB.
345
Pjlb_t Pjlb = P_JLB(Pjp->jp_Addr);
347
// Free the value areas in the bitmap leaf:
349
for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp)
351
jpcount = __JudyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp));
354
__JudyLFreeJV(JL_JLB_PVALUE(Pjlb, subexp), jpcount, Pjpm);
358
__JudyFreeJLB1((Pjlb_t) (Pjp->jp_Addr), Pjpm);
361
} // case cJU_JPLEAF_B1
368
// For JUDYL, all non JPIMMED_*_01s have a LeafV which must be freed:
370
case cJU_JPIMMED_1_02:
371
case cJU_JPIMMED_1_03:
373
case cJU_JPIMMED_1_04:
374
case cJU_JPIMMED_1_05:
375
case cJU_JPIMMED_1_06:
376
case cJU_JPIMMED_1_07:
378
Pop1 = Pjp->jp_Type - cJU_JPIMMED_1_02 + 2;
379
__JudyLFreeJV((Pjv_t) (Pjp->jp_Addr), Pop1, Pjpm);
383
case cJU_JPIMMED_2_02:
384
case cJU_JPIMMED_2_03:
386
Pop1 = Pjp->jp_Type - cJU_JPIMMED_2_02 + 2;
387
__JudyLFreeJV((Pjv_t) (Pjp->jp_Addr), Pop1, Pjpm);
390
case cJU_JPIMMED_3_02:
391
__JudyLFreeJV((Pjv_t) (Pjp->jp_Addr), 2, Pjpm);
398
// OTHER JPNULL, JPIMMED, OR UNEXPECTED TYPE -- nothing to free for this type:
400
// Note: Lump together no-op and invalid JP types; see function header
405
} // switch (Pjp -> jp_Type)
added
removed
src/JudyCommon/JudyFreeArray.c
