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