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 // Branch creation functions for Judy1 and JudyL.
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
34 // ****************************************************************************
35 // J U D Y C R E A T E B R A N C H L
36 //
37 // Build a BranchL from an array of JPs and associated 1 byte digits
38 // (expanses). Return with Pjp pointing to the BranchL. Caller must
39 // deallocate passed arrays, if necessary.
40 //
41 // We have no idea what kind of BranchL it is, so caller must set the jp_Type.
42 //
43 // Return -1 if error (details in Pjpm), otherwise return 1.
44
j__udyCreateBranchL(Pjp_t Pjp,Pjp_t PJPs,uint8_t Exp[],Word_t ExpCnt,Pvoid_t Pjpm)45 FUNCTION int j__udyCreateBranchL(
46 Pjp_t Pjp, // Build JPs from this place
47 Pjp_t PJPs, // Array of JPs to put into Bitmap branch
48 uint8_t Exp[], // Array of expanses to put into bitmap
49 Word_t ExpCnt, // Number of above JPs and Expanses
50 Pvoid_t Pjpm)
51 {
52 Pjbl_t PjblRaw; // pointer to linear branch.
53 Pjbl_t Pjbl;
54
55 assert(ExpCnt <= cJU_BRANCHLMAXJPS);
56
57 PjblRaw = j__udyAllocJBL(Pjpm);
58 if (PjblRaw == (Pjbl_t) NULL) return(-1);
59 Pjbl = P_JBL(PjblRaw);
60
61 // Build a Linear Branch
62 Pjbl->jbl_NumJPs = ExpCnt;
63
64 // Copy from the Linear branch from splayed leaves
65 JU_COPYMEM(Pjbl->jbl_Expanse, Exp, ExpCnt);
66 JU_COPYMEM(Pjbl->jbl_jp, PJPs, ExpCnt);
67
68 // Pass back new pointer to the Linear branch in JP
69 Pjp->jp_Addr = (Word_t) PjblRaw;
70
71 return(1);
72
73 } // j__udyCreateBranchL()
74
75
76 // ****************************************************************************
77 // J U D Y C R E A T E B R A N C H B
78 //
79 // Build a BranchB from an array of JPs and associated 1 byte digits
80 // (expanses). Return with Pjp pointing to the BranchB. Caller must
81 // deallocate passed arrays, if necessary.
82 //
83 // We have no idea what kind of BranchB it is, so caller must set the jp_Type.
84 //
85 // Return -1 if error (details in Pjpm), otherwise return 1.
86
j__udyCreateBranchB(Pjp_t Pjp,Pjp_t PJPs,uint8_t Exp[],Word_t ExpCnt,Pvoid_t Pjpm)87 FUNCTION int j__udyCreateBranchB(
88 Pjp_t Pjp, // Build JPs from this place
89 Pjp_t PJPs, // Array of JPs to put into Bitmap branch
90 uint8_t Exp[], // Array of expanses to put into bitmap
91 Word_t ExpCnt, // Number of above JPs and Expanses
92 Pvoid_t Pjpm)
93 {
94 Pjbb_t PjbbRaw; // pointer to bitmap branch.
95 Pjbb_t Pjbb;
96 Word_t ii, jj; // Temps
97 uint8_t CurrSubExp; // Current sub expanse for BM
98
99 // This assertion says the number of populated subexpanses is not too large.
100 // This function is only called when a BranchL overflows to a BranchB or when a
101 // cascade occurs, meaning a leaf overflows. Either way ExpCnt cant be very
102 // large, in fact a lot smaller than cJU_BRANCHBMAXJPS. (Otherwise a BranchU
103 // would be used.) Popping this assertion means something (unspecified) has
104 // gone very wrong, or else Judys design criteria have changed, although in
105 // fact there should be no HARM in creating a BranchB with higher actual
106 // fanout.
107
108 assert(ExpCnt <= cJU_BRANCHBMAXJPS);
109
110 // Get memory for a Bitmap branch
111 PjbbRaw = j__udyAllocJBB(Pjpm);
112 if (PjbbRaw == (Pjbb_t) NULL) return(-1);
113 Pjbb = P_JBB(PjbbRaw);
114
115 // Get 1st "sub" expanse (0..7) of bitmap branch
116 CurrSubExp = Exp[0] / cJU_BITSPERSUBEXPB;
117
118 // Index thru all 1 byte sized expanses:
119
120 for (jj = ii = 0; ii <= ExpCnt; ii++)
121 {
122 Word_t SubExp; // Cannot be a uint8_t
123
124 // Make sure we cover the last one
125 if (ii == ExpCnt)
126 {
127 SubExp = cJU_ALLONES; // Force last one
128 }
129 else
130 {
131 // Calculate the "sub" expanse of the byte expanse
132 SubExp = Exp[ii] / cJU_BITSPERSUBEXPB; // Bits 5..7.
133
134 // Set the bit that represents the expanse in Exp[]
135 JU_JBB_BITMAP(Pjbb, SubExp) |= JU_BITPOSMASKB(Exp[ii]);
136 }
137 // Check if a new "sub" expanse range needed
138 if (SubExp != CurrSubExp)
139 {
140 // Get number of JPs in this sub expanse
141 Word_t NumJP = ii - jj;
142 Pjp_t PjpRaw;
143 Pjp_t Pjp;
144
145 PjpRaw = j__udyAllocJBBJP(NumJP, Pjpm);
146 Pjp = P_JP(PjpRaw);
147
148 if (PjpRaw == (Pjp_t) NULL) // out of memory.
149 {
150
151 // Free any previous allocations:
152
153 while(CurrSubExp--)
154 {
155 NumJP = j__udyCountBitsB(JU_JBB_BITMAP(Pjbb,
156 CurrSubExp));
157 if (NumJP)
158 {
159 j__udyFreeJBBJP(JU_JBB_PJP(Pjbb,
160 CurrSubExp), NumJP, Pjpm);
161 }
162 }
163 j__udyFreeJBB(PjbbRaw, Pjpm);
164 return(-1);
165 }
166
167 // Place the array of JPs in bitmap branch:
168
169 JU_JBB_PJP(Pjbb, CurrSubExp) = PjpRaw;
170
171 // Copy the JPs to new leaf:
172
173 JU_COPYMEM(Pjp, PJPs + jj, NumJP);
174
175 // On to the next bitmap branch "sub" expanse:
176
177 jj = ii;
178 CurrSubExp = SubExp;
179 }
180 } // for each 1-byte expanse
181
182 // Pass back some of the JP to the new Bitmap branch:
183
184 Pjp->jp_Addr = (Word_t) PjbbRaw;
185
186 return(1);
187
188 } // j__udyCreateBranchB()
189
190
191 // ****************************************************************************
192 // J U D Y C R E A T E B R A N C H U
193 //
194 // Build a BranchU from a BranchB. Return with Pjp pointing to the BranchU.
195 // Free the BranchB and its JP subarrays.
196 //
197 // Return -1 if error (details in Pjpm), otherwise return 1.
198
j__udyCreateBranchU(Pjp_t Pjp,Pvoid_t Pjpm)199 FUNCTION int j__udyCreateBranchU(
200 Pjp_t Pjp,
201 Pvoid_t Pjpm)
202 {
203 jp_t JPNull;
204 Pjbu_t PjbuRaw;
205 Pjbu_t Pjbu;
206 Pjbb_t PjbbRaw;
207 Pjbb_t Pjbb;
208 Word_t ii, jj;
209 BITMAPB_t BitMap;
210 Pjp_t PDstJP;
211 #ifdef JU_STAGED_EXP
212 jbu_t BranchU; // Staged uncompressed branch
213 #else
214
215 // Allocate memory for a BranchU:
216
217 PjbuRaw = j__udyAllocJBU(Pjpm);
218 if (PjbuRaw == (Pjbu_t) NULL) return(-1);
219 Pjbu = P_JBU(PjbuRaw);
220 #endif
221 JU_JPSETADT(&JPNull, 0, 0, JU_JPTYPE(Pjp) - cJU_JPBRANCH_B2 + cJU_JPNULL1);
222
223 // Get the pointer to the BranchB:
224
225 PjbbRaw = (Pjbb_t) (Pjp->jp_Addr);
226 Pjbb = P_JBB(PjbbRaw);
227
228 // Set the pointer to the Uncompressed branch
229 #ifdef JU_STAGED_EXP
230 PDstJP = BranchU.jbu_jp;
231 #else
232 PDstJP = Pjbu->jbu_jp;
233 #endif
234 for (ii = 0; ii < cJU_NUMSUBEXPB; ii++)
235 {
236 Pjp_t PjpA;
237 Pjp_t PjpB;
238
239 PjpB = PjpA = P_JP(JU_JBB_PJP(Pjbb, ii));
240
241 // Get the bitmap for this subexpanse
242 BitMap = JU_JBB_BITMAP(Pjbb, ii);
243
244 // NULL empty subexpanses
245 if (BitMap == 0)
246 {
247 // But, fill with NULLs
248 for (jj = 0; jj < cJU_BITSPERSUBEXPB; jj++)
249 {
250 PDstJP[jj] = JPNull;
251 }
252 PDstJP += cJU_BITSPERSUBEXPB;
253 continue;
254 }
255 // Check if Uncompressed subexpanse
256 if (BitMap == cJU_FULLBITMAPB)
257 {
258 // Copy subexpanse to the Uncompressed branch intact
259 JU_COPYMEM(PDstJP, PjpA, cJU_BITSPERSUBEXPB);
260
261 // Bump to next subexpanse
262 PDstJP += cJU_BITSPERSUBEXPB;
263
264 // Set length of subexpanse
265 jj = cJU_BITSPERSUBEXPB;
266 }
267 else
268 {
269 for (jj = 0; jj < cJU_BITSPERSUBEXPB; jj++)
270 {
271 // Copy JP or NULLJP depending on bit
272 if (BitMap & 1) { *PDstJP = *PjpA++; }
273 else { *PDstJP = JPNull; }
274
275 PDstJP++; // advance to next JP
276 BitMap >>= 1;
277 }
278 jj = PjpA - PjpB;
279 }
280
281 // Free the subexpanse:
282
283 j__udyFreeJBBJP(JU_JBB_PJP(Pjbb, ii), jj, Pjpm);
284
285 } // for each JP in BranchU
286
287 #ifdef JU_STAGED_EXP
288
289 // Allocate memory for a BranchU:
290
291 PjbuRaw = j__udyAllocJBU(Pjpm);
292 if (PjbuRaw == (Pjbu_t) NULL) return(-1);
293 Pjbu = P_JBU(PjbuRaw);
294
295 // Copy staged branch to newly allocated branch:
296 //
297 // TBD: I think this code is broken.
298
299 *Pjbu = BranchU;
300
301 #endif // JU_STAGED_EXP
302
303 // Finally free the BranchB and put the BranchU in its place:
304
305 j__udyFreeJBB(PjbbRaw, Pjpm);
306
307 Pjp->jp_Addr = (Word_t) PjbuRaw;
308 Pjp->jp_Type += cJU_JPBRANCH_U - cJU_JPBRANCH_B;
309
310 return(1);
311
312 } // j__udyCreateBranchU()
313