← Back to branch summary

~ubuntu-branches/ubuntu/trusty/judy/trusty

« back to all changes in this revision

Viewing changes to src/JudyCommon/JudyFreeArray.c

  • Committer: Bazaar Package Importer
  • Author(s): Troy Heber
  • Date: 2005-03-22 06:55:53 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20050322065553-syjpkd48r4re18dn
Tags: 1.0.1-5

* Moving LGPL link in copyright back to LGPL-2.1
* Cleanup of debian/rules: removed explicit refs to 32-bit archs, removed
  unnecessary nostrip, using --man dir to install man pages, moving from
  dh_movefiles to dh_install.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/JudyCommon/JudyFreeArray.c
21
21
// Compile with one of -DJUDY1 or -DJUDYL.
22
22
// Return the number of bytes freed from the array.
23
23
 
24
 
#if (! (JUDY1 || JUDYL))
25
 
    Error:  One of -DJUDY1 or -DJUDYL must be specified.
 
24
#if (! (defined(JUDY1) || defined(JUDYL)))
 
25
#error:  One of -DJUDY1 or -DJUDYL must be specified.
26
26
#endif
27
27
 
28
28
#ifdef JUDY1
42
42
//
43
43
// See the Judy*(3C) manual entry for details.
44
44
//
45
 
// This code is written recursively, at least at first, because that's much
46
 
// simpler.  Hope it's fast enough.
 
45
// This code is written recursively, at least at first, because thats much
 
46
// simpler.  Hope its fast enough.
47
47
 
48
48
#ifdef JUDY1
49
 
FUNCTION Word_t Judy1FreeArray(
 
49
FUNCTION Word_t Judy1FreeArray
50
50
#else
51
 
FUNCTION Word_t JudyLFreeArray(
 
51
FUNCTION Word_t JudyLFreeArray
52
52
#endif
 
53
        (
53
54
        PPvoid_t  PPArray,      // array to free.
54
 
        PJError_t PJError)      // optional, for returning error info.
 
55
        PJError_t PJError       // optional, for returning error info.
 
56
        )
55
57
{
56
58
        jpm_t     jpm;          // local to accumulate free statistics.
57
 
        Word_t    JAPtype;      // JAP type part of *PPArray.
58
 
 
59
59
 
60
60
// CHECK FOR NULL POINTER (error by caller):
61
61
 
67
67
 
68
68
        DBGCODE(JudyCheckPop(*PPArray);)
69
69
 
70
 
 
71
 
// PROCESS TOP LEVEL "JAP" BRANCHES AND LEAVES:
72
 
//
73
70
// Zero jpm.jpm_Pop0 (meaning the array will be empty in a moment) for accurate
74
71
// logging in TRACEMI2.
75
72
 
76
73
        jpm.jpm_Pop0          = 0;              // see above.
77
74
        jpm.jpm_TotalMemWords = 0;              // initialize memory freed.
78
75
 
79
 
// Get pointer and type from array pointer:
80
 
 
81
 
        JAPtype = JAPTYPE(*PPArray);
82
 
 
83
 
        switch (JAPtype)
84
 
        {
85
 
 
86
 
// Empty array:
87
 
//
88
 
// Note:  It is an error to have a JAPtype for a JAPNULL with the rest of the
89
 
// pointer not being null.
90
 
 
91
 
        case cJU_JAPNULL:
92
 
        {
93
 
            if (P_JLW(*PPArray) == (Pjlw_t) NULL) return(0);
94
 
            break;  // invalid JAP, although possibly a valid non-Judy pointer.
 
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.
95
89
        }
 
90
        else
96
91
 
97
92
// Rootstate leaves:  just free the leaf:
98
93
 
99
94
// Common code for returning the amount of memory freed.
100
95
//
101
 
// Note:  In a an ordinary JAPLEAF, pop0 = *PPArray[0].
 
96
// Note:  In a an ordinary LEAFW, pop0 = *PPArray[0].
102
97
//
103
98
// Accumulate (negative) words freed, while freeing objects.
104
99
// Return the positive bytes freed.
105
100
 
106
 
        case cJU_JAPLEAF:
107
 
        {
108
 
            Pjlw_t Pjlw = P_JLW(*PPArray);      // first word of leaf.
109
 
 
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.
113
 
        }
114
 
 
115
 
#if (LOW_POP && JUDYL)
116
 
        case cJL_JAPLEAF_POPU1:
117
 
        {
118
 
            Pjlw_t Pjlw= P_JLW(*PPArray);       // first word of leaf.
119
 
 
120
 
            __JudyFreeJLW(Pjlw, 1, &jpm);
121
 
            *PPArray = (Pvoid_t) NULL;          // make an empty array.
122
 
            return (-(jpm.jpm_TotalMemWords * cJU_BYTESPERWORD));  // see above.
123
 
        }
124
 
        case cJL_JAPLEAF_POPU2:
125
 
        {
126
 
            Pjlw_t Pjlw = P_JLW(*PPArray);      // first word of leaf.
127
 
 
128
 
            __JudyFreeJLW(Pjlw, 2, &jpm);
129
 
            *PPArray = (Pvoid_t) NULL;          // make an empty array.
130
 
            return (-(jpm.jpm_TotalMemWords * cJU_BYTESPERWORD));  // see above.
131
 
        }
132
 
#endif
133
 
 
134
 
        case cJU_JAPBRANCH:
135
101
        {
136
102
            Pjpm_t Pjpm     = P_JPM(*PPArray);
137
103
            Word_t TotalMem = Pjpm->jpm_TotalMemWords;
138
104
 
139
 
            __JudyFreeSM(&(Pjpm->jpm_JP), &jpm);  // recurse through tree.
140
 
            __JudyFreeJPM(Pjpm, &jpm);
 
105
            j__udyFreeSM(&(Pjpm->jpm_JP), &jpm);  // recurse through tree.
 
106
            j__udyFreeJPM(Pjpm, &jpm);
141
107
 
142
108
// Verify the array was not corrupt.  This means that amount of memory freed
143
109
// (which is negative) is equal to the initial amount:
152
118
            return (TotalMem * cJU_BYTESPERWORD);
153
119
        }
154
120
 
155
 
// No match above implies invalid root pointer (JAP):
156
 
 
157
 
        default: break;
158
 
 
159
 
        } // switch (JAPtype)
160
 
 
161
 
        JUDY1CODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDY1);)
162
 
        JUDYLCODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDYL);)
163
 
        return(JERR);
164
 
 
165
121
} // Judy1FreeArray() / JudyLFreeArray()
166
122
 
167
123
 
173
129
// the total words freed (as a negative value).  "SM" = State Machine.
174
130
//
175
131
// 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
 
132
// if the code hasnt already core dumped, its better to remain silent, even
177
133
// if some memory has not been freed, than to bother the caller about the
178
134
// corruption.  TBD:  Is this true?  If not, must list all legitimate JPNULL
179
135
// and JPIMMED above first, and revert to returning bool_t (see 4.34).
180
136
 
181
 
FUNCTION void __JudyFreeSM(
 
137
FUNCTION void j__udyFreeSM(
182
138
        Pjp_t   Pjp,            // top of Judy (top-state).
183
139
        Pjpm_t  Pjpm)           // to return words freed.
184
140
{
185
141
        Word_t  Pop1;
186
142
 
187
 
        switch (Pjp->jp_Type)
 
143
        switch (JU_JPTYPE(Pjp))
188
144
        {
189
145
 
190
146
#ifdef JUDY1
197
153
 
198
154
// JUDY BRANCH -- free the sub-tree depth first:
199
155
 
200
 
// LINEAR BRANCH -- visit each JP in the JBL's list, then free the JBL:
 
156
// LINEAR BRANCH -- visit each JP in the JBLs list, then free the JBL:
201
157
//
202
158
// Note:  There are no null JPs in a JBL.
203
159
 
215
171
            Word_t offset;
216
172
 
217
173
            for (offset = 0; offset < Pjbl->jbl_NumJPs; ++offset)
218
 
                __JudyFreeSM((Pjbl->jbl_jp) + offset, Pjpm);
 
174
                j__udyFreeSM((Pjbl->jbl_jp) + offset, Pjpm);
219
175
 
220
 
            __JudyFreeJBL((Pjbl_t) (Pjp->jp_Addr), Pjpm);
 
176
            j__udyFreeJBL((Pjbl_t) (Pjp->jp_Addr), Pjpm);
221
177
            break;
222
178
        }
223
179
 
244
200
 
245
201
            for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
246
202
            {
247
 
                jpcount = __JudyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp));
 
203
                jpcount = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp));
248
204
 
249
205
                if (jpcount)
250
206
                {
251
207
                    for (offset = 0; offset < jpcount; ++offset)
252
208
                    {
253
 
                       __JudyFreeSM(P_JP(JU_JBB_PJP(Pjbb, subexp)) + offset,
 
209
                       j__udyFreeSM(P_JP(JU_JBB_PJP(Pjbb, subexp)) + offset,
254
210
                                    Pjpm);
255
211
                    }
256
 
                    __JudyFreeJBBJP(JU_JBB_PJP(Pjbb, subexp), jpcount, Pjpm);
 
212
                    j__udyFreeJBBJP(JU_JBB_PJP(Pjbb, subexp), jpcount, Pjpm);
257
213
                }
258
214
            }
259
 
            __JudyFreeJBB((Pjbb_t) (Pjp->jp_Addr), Pjpm);
 
215
            j__udyFreeJBB((Pjbb_t) (Pjp->jp_Addr), Pjpm);
260
216
 
261
217
            break;
262
218
        }
281
237
            Pjbu_t Pjbu = P_JBU(Pjp->jp_Addr);
282
238
 
283
239
            for (offset = 0; offset < cJU_BRANCHUNUMJPS; ++offset)
284
 
                __JudyFreeSM((Pjbu->jbu_jp) + offset, Pjpm);
 
240
                j__udyFreeSM((Pjbu->jbu_jp) + offset, Pjpm);
285
241
 
286
 
            __JudyFreeJBU((Pjbu_t) (Pjp->jp_Addr), Pjpm);
 
242
            j__udyFreeJBU((Pjbu_t) (Pjp->jp_Addr), Pjpm);
287
243
            break;
288
244
        }
289
245
 
295
251
//
296
252
// Note:  cJU_JPLEAF1 is a special case, see discussion in ../Judy1/Judy1.h
297
253
 
298
 
#if (JUDYL || (! JU_64BIT ))
 
254
#if (defined(JUDYL) || (! defined(JU_64BIT)))
299
255
        case cJU_JPLEAF1:
300
 
            Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
301
 
            __JudyFreeJLL1((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
 
256
            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
 
257
            j__udyFreeJLL1((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
302
258
            break;
303
259
#endif
304
260
 
305
261
        case cJU_JPLEAF2:
306
 
            Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
307
 
            __JudyFreeJLL2((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
 
262
            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
 
263
            j__udyFreeJLL2((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
308
264
            break;
309
265
 
310
266
        case cJU_JPLEAF3:
311
 
            Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
312
 
            __JudyFreeJLL3((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
 
267
            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
 
268
            j__udyFreeJLL3((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
313
269
            break;
314
270
 
315
271
#ifdef JU_64BIT
316
272
        case cJU_JPLEAF4:
317
 
            Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
318
 
            __JudyFreeJLL4((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
 
273
            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
 
274
            j__udyFreeJLL4((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
319
275
            break;
320
276
 
321
277
        case cJU_JPLEAF5:
322
 
            Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
323
 
            __JudyFreeJLL5((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
 
278
            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
 
279
            j__udyFreeJLL5((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
324
280
            break;
325
281
 
326
282
        case cJU_JPLEAF6:
327
 
            Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
328
 
            __JudyFreeJLL6((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
 
283
            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
 
284
            j__udyFreeJLL6((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
329
285
            break;
330
286
 
331
287
        case cJU_JPLEAF7:
332
 
            Pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;
333
 
            __JudyFreeJLL7((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
 
288
            Pop1 = JU_JPLEAF_POP0(Pjp) + 1;
 
289
            j__udyFreeJLL7((Pjll_t) (Pjp->jp_Addr), Pop1, Pjpm);
334
290
            break;
335
291
#endif // JU_64BIT
336
292
 
348
304
 
349
305
            for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp)
350
306
            {
351
 
                jpcount = __JudyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp));
 
307
                jpcount = j__udyCountBitsL(JU_JLB_BITMAP(Pjlb, subexp));
352
308
 
353
309
                if (jpcount)
354
 
                    __JudyLFreeJV(JL_JLB_PVALUE(Pjlb, subexp), jpcount, Pjpm);
 
310
                    j__udyLFreeJV(JL_JLB_PVALUE(Pjlb, subexp), jpcount, Pjpm);
355
311
            }
356
312
#endif // JUDYL
357
313
 
358
 
            __JudyFreeJLB1((Pjlb_t) (Pjp->jp_Addr), Pjpm);
 
314
            j__udyFreeJLB1((Pjlb_t) (Pjp->jp_Addr), Pjpm);
359
315
            break;
360
316
 
361
317
        } // case cJU_JPLEAF_B1
375
331
        case cJU_JPIMMED_1_06:
376
332
        case cJU_JPIMMED_1_07:
377
333
#endif
378
 
            Pop1 = Pjp->jp_Type - cJU_JPIMMED_1_02 + 2;
379
 
            __JudyLFreeJV((Pjv_t) (Pjp->jp_Addr), Pop1, Pjpm);
 
334
            Pop1 = JU_JPTYPE(Pjp) - cJU_JPIMMED_1_02 + 2;
 
335
            j__udyLFreeJV((Pjv_t) (Pjp->jp_Addr), Pop1, Pjpm);
380
336
            break;
381
337
 
382
338
#ifdef JU_64BIT
383
339
        case cJU_JPIMMED_2_02:
384
340
        case cJU_JPIMMED_2_03:
385
341
 
386
 
            Pop1 = Pjp->jp_Type - cJU_JPIMMED_2_02 + 2;
387
 
            __JudyLFreeJV((Pjv_t) (Pjp->jp_Addr), Pop1, Pjpm);
 
342
            Pop1 = JU_JPTYPE(Pjp) - cJU_JPIMMED_2_02 + 2;
 
343
            j__udyLFreeJV((Pjv_t) (Pjp->jp_Addr), Pop1, Pjpm);
388
344
            break;
389
345
 
390
346
        case cJU_JPIMMED_3_02:
391
 
            __JudyLFreeJV((Pjv_t) (Pjp->jp_Addr), 2, Pjpm);
 
347
            j__udyLFreeJV((Pjv_t) (Pjp->jp_Addr), 2, Pjpm);
392
348
            break;
393
349
 
394
350
#endif // JU_64BIT
402
358
 
403
359
        default: break;
404
360
 
405
 
        } // switch (Pjp -> jp_Type)
 
361
        } // switch (JU_JPTYPE(Pjp))
406
362
 
407
 
} // __JudyFreeSM()
 
363
} // j__udyFreeSM()