← Back to branch summary

~ubuntu-branches/ubuntu/precise/judy/precise

« back to all changes in this revision

Viewing changes to src/JudyCommon/JudyMemActive.c

  • Committer: Bazaar Package Importer
  • Author(s): Theodore Y. Ts'o
  • Date: 2004-01-17 00:04:53 UTC
  • Revision ID: james.westby@ubuntu.com-20040117000453-d5sj6uoon2v1g4gf
Tags: upstream-0.0.4
Import upstream version 0.0.4

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/JudyCommon/JudyMemActive.c
 
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.7 $ $Source: /judy/src/JudyCommon/JudyMemActive.c $
 
19
//
 
20
// Return number of bytes of memory used to support a Judy1/L array.
 
21
// Compile with one of -DJUDY1 or -DJUDYL.
 
22
 
 
23
#if (! (JUDY1 || 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
FUNCTION static Word_t __JudyGetMemActive(Pjp_t);
 
36
 
 
37
 
 
38
// ****************************************************************************
 
39
// J U D Y   1   M E M   A C T I V E
 
40
// J U D Y   L   M E M   A C T I V E
 
41
 
 
42
#ifdef JUDY1
 
43
FUNCTION Word_t Judy1MemActive(
 
44
#else
 
45
FUNCTION Word_t JudyLMemActive(
 
46
#endif
 
47
        Pcvoid_t PArray)        // from which to retrieve.
 
48
{
 
49
        uint8_t  JAPtype;       // type of JAP (root pointer).
 
50
 
 
51
        JAPtype = JAPTYPE(PArray);
 
52
 
 
53
        switch (JAPtype)
 
54
        {
 
55
        case cJU_JAPNULL: return(0);
 
56
 
 
57
#if (LOW_POP && JUDYL)
 
58
        case cJL_JAPLEAF_POPU1: return(2 * sizeof(Word_t));
 
59
        case cJL_JAPLEAF_POPU2: return(4 * sizeof(Word_t));
 
60
#endif
 
61
        case cJU_JAPLEAF:
 
62
        {
 
63
            Pjlw_t Pjlw = P_JLW(PArray);        // first word of leaf.
 
64
            Word_t Words = Pjlw[0] + 1;         // population.
 
65
#ifdef JUDY1
 
66
            return((Words + 1) * sizeof(Word_t));
 
67
#else
 
68
            return(((Words * 2) + 1) * sizeof(Word_t));
 
69
#endif
 
70
        }
 
71
        case cJU_JAPBRANCH:
 
72
        {
 
73
            Pjpm_t Pjpm = P_JPM(PArray);
 
74
            return(__JudyGetMemActive(&Pjpm->jpm_JP) + sizeof(jpm_t));
 
75
        }
 
76
 
 
77
        default:
 
78
                break;
 
79
        }
 
80
 
 
81
        return(-1);                             // impossible exit.
 
82
 
 
83
} // JudyMemActive()
 
84
 
 
85
 
 
86
// ****************************************************************************
 
87
// __ J U D Y   G E T   M E M   A C T I V E
 
88
 
 
89
FUNCTION static Word_t __JudyGetMemActive(
 
90
        Pjp_t  Pjp)             // top of subtree.
 
91
{
 
92
        Word_t offset;          // in a branch.
 
93
        Word_t Bytes = 0;       // actual bytes used at this level.
 
94
        Word_t IdxSz;           // bytes per index in leaves
 
95
 
 
96
        switch (Pjp->jp_Type)
 
97
        {
 
98
 
 
99
        case cJU_JPBRANCH_L2:
 
100
        case cJU_JPBRANCH_L3:
 
101
#ifdef JU_64BIT
 
102
        case cJU_JPBRANCH_L4:
 
103
        case cJU_JPBRANCH_L5:
 
104
        case cJU_JPBRANCH_L6:
 
105
        case cJU_JPBRANCH_L7:
 
106
#endif
 
107
        case cJU_JPBRANCH_L:
 
108
        {
 
109
            Pjbl_t Pjbl = P_JBL(Pjp->jp_Addr);
 
110
 
 
111
            for (offset = 0; offset < (Pjbl->jbl_NumJPs); ++offset)
 
112
                Bytes += __JudyGetMemActive((Pjbl->jbl_jp) + offset);
 
113
 
 
114
            return(Bytes + sizeof(jbl_t));
 
115
        }
 
116
 
 
117
        case cJU_JPBRANCH_B2:
 
118
        case cJU_JPBRANCH_B3:
 
119
#ifdef JU_64BIT
 
120
        case cJU_JPBRANCH_B4:
 
121
        case cJU_JPBRANCH_B5:
 
122
        case cJU_JPBRANCH_B6:
 
123
        case cJU_JPBRANCH_B7:
 
124
#endif
 
125
        case cJU_JPBRANCH_B:
 
126
        {
 
127
            Word_t subexp;
 
128
            Word_t jpcount;
 
129
            Pjbb_t Pjbb = P_JBB(Pjp->jp_Addr);
 
130
 
 
131
            for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)
 
132
            {
 
133
                jpcount = __JudyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp));
 
134
                Bytes  += jpcount * sizeof(jp_t);
 
135
 
 
136
                for (offset = 0; offset < jpcount; ++offset)
 
137
                {
 
138
                    Bytes += __JudyGetMemActive(P_JP(JU_JBB_PJP(Pjbb, subexp))
 
139
                           + offset);
 
140
                }
 
141
            }
 
142
 
 
143
            return(Bytes + sizeof(jbb_t));
 
144
        }
 
145
 
 
146
        case cJU_JPBRANCH_U2:
 
147
        case cJU_JPBRANCH_U3:
 
148
#ifdef JU_64BIT
 
149
        case cJU_JPBRANCH_U4:
 
150
        case cJU_JPBRANCH_U5:
 
151
        case cJU_JPBRANCH_U6:
 
152
        case cJU_JPBRANCH_U7:
 
153
#endif
 
154
        case cJU_JPBRANCH_U:
 
155
        {
 
156
            Pjbu_t Pjbu = P_JBU(Pjp->jp_Addr);
 
157
 
 
158
            for (offset = 0; offset < cJU_BRANCHUNUMJPS; ++offset)
 
159
            {
 
160
                if (((Pjbu->jbu_jp[offset].jp_Type) >= cJU_JPNULL1)
 
161
                 && ((Pjbu->jbu_jp[offset].jp_Type) <= cJU_JPNULLMAX))
 
162
                {
 
163
                    continue;           // skip null JP to save time.
 
164
                }
 
165
 
 
166
                Bytes += __JudyGetMemActive(Pjbu->jbu_jp + offset);
 
167
            }
 
168
 
 
169
            return(Bytes + sizeof(jbu_t));
 
170
        }
 
171
 
 
172
 
 
173
// -- Cases below here terminate and do not recurse. --
 
174
 
 
175
#if (JUDYL || (! JU_64BIT ))
 
176
        case cJU_JPLEAF1: IdxSz = 1; goto LeafWords;
 
177
#endif
 
178
        case cJU_JPLEAF2: IdxSz = 2; goto LeafWords;
 
179
        case cJU_JPLEAF3: IdxSz = 3; goto LeafWords;
 
180
#ifdef JU_64BIT
 
181
        case cJU_JPLEAF4: IdxSz = 4; goto LeafWords;
 
182
        case cJU_JPLEAF5: IdxSz = 5; goto LeafWords;
 
183
        case cJU_JPLEAF6: IdxSz = 6; goto LeafWords;
 
184
        case cJU_JPLEAF7: IdxSz = 7; goto LeafWords;
 
185
#endif
 
186
LeafWords:
 
187
 
 
188
#ifdef JUDY1
 
189
            return(IdxSz * (JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1));
 
190
#else
 
191
            return((IdxSz + sizeof(Word_t))
 
192
                 * (JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1));
 
193
#endif
 
194
        case cJU_JPLEAF_B1:
 
195
        {
 
196
#ifdef JUDY1
 
197
            return(sizeof(jlb_t));
 
198
#else
 
199
            Bytes = (JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1) * sizeof(Word_t);
 
200
 
 
201
            return(Bytes + sizeof(jlb_t));
 
202
#endif
 
203
        }
 
204
 
 
205
        JUDY1CODE(case cJ1_JPFULLPOPU1: return(0);)
 
206
 
 
207
#ifdef JUDY1
 
208
#define __JMpy 0
 
209
#else
 
210
#define __JMpy sizeof(Word_t)
 
211
#endif
 
212
 
 
213
        case cJU_JPIMMED_1_01:  return(0);
 
214
        case cJU_JPIMMED_2_01:  return(0);
 
215
        case cJU_JPIMMED_3_01:  return(0);
 
216
#ifdef JU_64BIT
 
217
        case cJU_JPIMMED_4_01:  return(0);
 
218
        case cJU_JPIMMED_5_01:  return(0);
 
219
        case cJU_JPIMMED_6_01:  return(0);
 
220
        case cJU_JPIMMED_7_01:  return(0);
 
221
#endif
 
222
 
 
223
        case cJU_JPIMMED_1_02:  return(__JMpy * 2);
 
224
        case cJU_JPIMMED_1_03:  return(__JMpy * 3);
 
225
#if (JUDY1 || JU_64BIT)
 
226
        case cJU_JPIMMED_1_04:  return(__JMpy * 4);
 
227
        case cJU_JPIMMED_1_05:  return(__JMpy * 5);
 
228
        case cJU_JPIMMED_1_06:  return(__JMpy * 6);
 
229
        case cJU_JPIMMED_1_07:  return(__JMpy * 7);
 
230
#endif
 
231
#if (JUDY1 && JU_64BIT)
 
232
        case cJ1_JPIMMED_1_08:  return(0);
 
233
        case cJ1_JPIMMED_1_09:  return(0);
 
234
        case cJ1_JPIMMED_1_10:  return(0);
 
235
        case cJ1_JPIMMED_1_11:  return(0);
 
236
        case cJ1_JPIMMED_1_12:  return(0);
 
237
        case cJ1_JPIMMED_1_13:  return(0);
 
238
        case cJ1_JPIMMED_1_14:  return(0);
 
239
        case cJ1_JPIMMED_1_15:  return(0);
 
240
#endif
 
241
 
 
242
#if (JUDY1 || JU_64BIT)
 
243
        case cJU_JPIMMED_2_02:  return(__JMpy * 2);
 
244
        case cJU_JPIMMED_2_03:  return(__JMpy * 3);
 
245
#endif
 
246
#if (JUDY1 && JU_64BIT)
 
247
        case cJ1_JPIMMED_2_04:  return(0);
 
248
        case cJ1_JPIMMED_2_05:  return(0);
 
249
        case cJ1_JPIMMED_2_06:  return(0);
 
250
        case cJ1_JPIMMED_2_07:  return(0);
 
251
#endif
 
252
 
 
253
#if (JUDY1 || JU_64BIT)
 
254
        case cJU_JPIMMED_3_02:  return(__JMpy * 2);
 
255
#endif
 
256
#if (JUDY1 && JU_64BIT)
 
257
        case cJ1_JPIMMED_3_03:  return(0);
 
258
        case cJ1_JPIMMED_3_04:  return(0);
 
259
        case cJ1_JPIMMED_3_05:  return(0);
 
260
 
 
261
        case cJ1_JPIMMED_4_02:  return(0);
 
262
        case cJ1_JPIMMED_4_03:  return(0);
 
263
        case cJ1_JPIMMED_5_02:  return(0);
 
264
        case cJ1_JPIMMED_5_03:  return(0);
 
265
        case cJ1_JPIMMED_6_02:  return(0);
 
266
        case cJ1_JPIMMED_7_02:  return(0);
 
267
#endif
 
268
 
 
269
        } // switch (Pjp->jp_Type)
 
270
 
 
271
        return(0);                      // to make some compilers happy.
 
272
 
 
273
} // __JudyGetMemActive()