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