~ubuntu-branches/ubuntu/lucid/judy/lucid : revision 1

1

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.68 $ $Source: /judy/src/JudyCommon/JudyDel.c $

19

//

20

// Judy1Unset() and JudyLDel() functions for Judy1 and JudyL.

21

// Compile with one of -DJUDY1 or -DJUDYL.

22

//

23

// About HYSTERESIS: In the Judy code, hysteresis means leaving around a

24

// nominally suboptimal (not maximally compressed) data structure after a

25

// deletion. As a result, the shape of the tree for two identical index sets

26

// can differ depending on the insert/delete path taken to arrive at the index

27

// sets. The purpose is to minimize worst-case behavior (thrashing) that could

28

// result from a series of intermixed insertions and deletions. It also makes

29

// for MUCH simpler code, because instead of performing, "delete and then

30

// compress," it can say, "compress and then delete," where due to hysteresis,

31

// compression is not even attempted until the object IS compressible.

32

//

33

// In some cases the code has no choice and it must "ungrow" a data structure

34

// across a "phase transition" boundary without hysteresis. In other cases the

35

// amount (such as "hysteresis = 1") is indicated by the number of JP deletions

36

// (in branches) or index deletions (in leaves) that can occur in succession

37

// before compressing the data structure. (It appears that hysteresis <= 1 in

38

// all cases.)

39

//

40

// In general no hysteresis occurs when the data structure type remains the

41

// same but the allocated memory chunk for the node must shrink, because the

42

// relationship is hardwired and there's no way to know how much memory is

43

// allocated to a given data structure. Hysteresis = 0 in all these cases.

44

//

45

// TBD: Could this code be faster if memory chunk hysteresis were supported

46

// somehow along with data structure type hysteresis?

47

//

48

// TBD: Should some of the assertions here be converted to product code that

49

// returns JU_ERRNO_CORRUPT?

50

//

51

// TBD: Doug's code had an odd mix of function-wide and limited-scope

52

// variables. Should some of the function-wide variables appear only in

53

// limited scopes, or more likely, vice-versa?

54

55

#if (! (JUDY1 || JUDYL))

56

Error: One of -DJUDY1 or -DJUDYL must be specified.

57

#endif

58

59

#ifdef JUDY1

60

#include "Judy1.h"

61

#else

62

#include "JudyL.h"

63

#endif

64

65

#include "JudyPrivate1L.h"

66

67

DBGCODE(extern void JudyCheckPop(Pvoid_t PArray);)

68

DBGCODE(extern void JudyCheckSorted(Pjll_t Pjll, Word_t Pop1, long IndexSize);)

69

70

#ifdef TRACEJP

71

#include "JudyPrintJP.c"

72

#endif

73

74

// These are defined to generic values in JudyCommon/JudyPrivateTypes.h:

75

//

76

// TBD: These should be exported from a header file, but perhaps not, as they

77

// are only used here, and exported from JudyDecascade.c, which is a separate

78

// file for profiling reasons (to prevent inlining), but which potentially

79

// could be merged with this file, either in SoftCM or at compile-time:

80

81

#ifdef JUDY1

82

83

extern int __Judy1BranchBToBranchL(Pjp_t Pjp, Pvoid_t Pjpm);

84

#ifndef JU_64BIT

85

extern int __Judy1LeafB1ToLeaf1(Pjp_t, Pvoid_t);

86

#endif

87

extern Word_t __Judy1Leaf1ToLeaf2(uint16_t *, Pjp_t, Word_t, Pvoid_t);

88

extern Word_t __Judy1Leaf2ToLeaf3(uint8_t *, Pjp_t, Word_t, Pvoid_t);

89

#ifndef JU_64BIT

90

extern Word_t __Judy1Leaf3ToLeafW(Pjlw_t, Pjp_t, Word_t, Pvoid_t);

91

#else

92

extern Word_t __Judy1Leaf3ToLeaf4(uint32_t *, Pjp_t, Word_t, Pvoid_t);

93

extern Word_t __Judy1Leaf4ToLeaf5(uint8_t *, Pjp_t, Word_t, Pvoid_t);

94

extern Word_t __Judy1Leaf5ToLeaf6(uint8_t *, Pjp_t, Word_t, Pvoid_t);

95

extern Word_t __Judy1Leaf6ToLeaf7(uint8_t *, Pjp_t, Word_t, Pvoid_t);

96

extern Word_t __Judy1Leaf7ToLeafW(Pjlw_t, Pjp_t, Word_t, Pvoid_t);

97

#endif

98

99

#else // JUDYL

100

101

extern int __JudyLBranchBToBranchL(Pjp_t Pjp, Pvoid_t Pjpm);

102

extern int __JudyLLeafB1ToLeaf1(Pjp_t, Pvoid_t);

103

extern Word_t __JudyLLeaf1ToLeaf2(uint16_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);

104

extern Word_t __JudyLLeaf2ToLeaf3(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);

105

#ifndef JU_64BIT

106

extern Word_t __JudyLLeaf3ToLeafW(Pjlw_t, Pjv_t, Pjp_t, Word_t, Pvoid_t);

107

#else

108

extern Word_t __JudyLLeaf3ToLeaf4(uint32_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);

109

extern Word_t __JudyLLeaf4ToLeaf5(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);

110

extern Word_t __JudyLLeaf5ToLeaf6(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);

111

extern Word_t __JudyLLeaf6ToLeaf7(uint8_t *, Pjv_t, Pjp_t, Word_t, Pvoid_t);

112

extern Word_t __JudyLLeaf7ToLeafW(Pjlw_t, Pjv_t, Pjp_t, Word_t, Pvoid_t);

113

#endif

114

115

#endif // JUDYL

116

117

// For convenience in the calling code; "M1" means "minus one":

118

119

#ifndef JU_64BIT

120

#define __JudyLeafM1ToLeafW __JudyLeaf3ToLeafW

121

#else

122

#define __JudyLeafM1ToLeafW __JudyLeaf7ToLeafW

123

#endif

124

125

126

// ****************************************************************************

127

// __ J U D Y D E L W A L K

128

//

129

// Given a pointer to a JP, an Index known to be valid, the number of bytes

130

// left to decode (== level in the tree), and a pointer to a global JPM, walk a

131

// Judy (sub)tree to do an unset/delete of that index, and possibly modify the

132

// JPM. This function is only called internally, and recursively. Unlike

133

// Judy1Test() and JudyLGet(), the extra time required for recursion should be

134

// negligible compared with the total.

135

//

136

// Return values:

137

//

138

// -1 error; details in JPM

139

//

140

// 0 Index already deleted (should never happen, Index is known to be valid)

141

//

142

// 1 previously valid Index deleted

143

//

144

// 2 same as 1, but in addition the JP now points to a BranchL containing a

145

// single JP, which should be compressed into the parent branch (if there

146

// is one, which is not the case for a top-level branch under a JPM)

147

148

DBGCODE(uint8_t parentJPtype;) // parent branch JP type.

149

150

FUNCTION static int __JudyDelWalk(

151

Pjp_t Pjp, // current JP under which to delete.

152

Word_t Index, // to delete.

153

Word_t ParentLevel, // of parent branch.

154

Pjpm_t Pjpm) // for returning info to top level.

155

{

156

Word_t pop1; // of a leaf.

157

Word_t level; // of a leaf.

158

uint8_t digit; // from Index, in current branch.

159

Pjll_t PjllnewRaw; // address of newly allocated leaf.

160

Pjll_t Pjllnew;

161

int offset; // within a branch.

162

int retcode; // return code: -1, 0, 1, 2.

163

JUDYLCODE(Pjv_t PjvRaw;) // value area.

164

JUDYLCODE(Pjv_t Pjv;)

165

166

DBGCODE(level = 0;)

167

168

ContinueDelWalk: // for modifying state without recursing.

169

170

#ifdef TRACEJP

171

JudyPrintJP(Pjp, "d", __LINE__);

172

#endif

173

174

switch (Pjp->jp_Type) // entry: Pjp, Index.

175

{

176

177

178

// ****************************************************************************

179

// LINEAR BRANCH:

180

//

181

// MACROS FOR COMMON CODE:

182

//

183

// Check for population too high to compress a branch to a leaf, meaning just

184

// descend through the branch, with a purposeful off-by-one error that

185

// constitutes hysteresis = 1. In other words, do not compress until the

186

// branch's CURRENT population fits in the leaf, even BEFORE deleting one

187

// index.

188

//

189

// Next is a label for branch-type-specific common code. Variables pop1,

190

// level, digit, and Index are in the context.

191

192

#define JU_BRANCH_KEEP(cLevel,MaxPop1,Next) \

193

if (pop1 > (MaxPop1)) /* hysteresis = 1 */ \

194

{ \

195

assert((cLevel) >= 2); \

196

level = (cLevel); \

197

digit = JU_DIGITATSTATE(Index, cLevel); \

198

goto Next; \

199

}

200

201

// Support for generic calling of JudyLeaf*ToLeaf*() functions:

202

//

203

// Note: Cannot use JUDYLCODE() because this contains a comma.

204

205

#ifdef JUDY1

206

#define JU_PVALUEPASS // null.

207

#else

208

#define JU_PVALUEPASS Pjv,

209

#endif

210

211

// During compression to a leaf, check if a JP contains nothing but a

212

// cJU_JPIMMED_*_01, in which case shortcut calling __JudyLeaf*ToLeaf*():

213

//

214

// Copy the index bytes from the jp_DcdPop0 field (with possible truncation),

215

// and continue the branch-JP-walk loop. Variables Pjp and Pleaf are in the

216

// context.

217

218

#define JU_BRANCH_COPY_IMMED_EVEN(cLevel,Pjp,ignore) \

219

if (((Pjp)->jp_Type) == cJU_JPIMMED_1_01 + (cLevel) - 2)\

220

{ \

221

*Pleaf++ = (Pjp)->jp_DcdPop0; \

222

JUDYLCODE(*Pjv++ = (Pjp)->jp_Addr;) \

223

continue; /* for-loop */ \

224

}

225

226

#define JU_BRANCH_COPY_IMMED_ODD(cLevel,Pjp,CopyIndex) \

227

if (((Pjp)->jp_Type) == cJU_JPIMMED_1_01 + (cLevel) - 2)\

228

{ \

229

CopyIndex(Pleaf, (Word_t) ((Pjp)->jp_DcdPop0)); \

230

Pleaf += (cLevel); /* index size = level */ \

231

JUDYLCODE(*Pjv++ = (Pjp)->jp_Addr;) \

232

continue; /* for-loop */ \

233

}

234

235

// Compress a BranchL into a leaf one index size larger:

236

//

237

// Allocate a new leaf, walk the JPs in the old BranchL and pack their contents

238

// into the new leaf (of type NewJPType), free the old BranchL, and finally

239

// restart the switch to delete Index from the new leaf. (Note that all

240

// BranchL's are the same size.) Variables Pjp, Pjpm, Pleaf, digit, and pop1

241

// are in the context.

242

243

#define JU_BRANCHL_COMPRESS(cLevel,LeafType,MaxPop1,NewJPType, \

244

LeafToLeaf,Alloc,ValueArea, \

245

CopyImmed,CopyIndex) \

246

{ \

247

LeafType Pleaf; \

248

Pjbl_t PjblRaw; \

249

Pjbl_t Pjbl; \

250

Word_t numJPs; \

251

\

252

if ((PjllnewRaw = Alloc(MaxPop1, Pjpm)) == 0) return(-1); \

253

Pjllnew = P_JLL(PjllnewRaw); \

254

Pleaf = (LeafType) Pjllnew; \

255

JUDYLCODE(Pjv = ValueArea(Pleaf, MaxPop1);) \

256

\

257

PjblRaw = (Pjbl_t) (Pjp->jp_Addr); \

258

Pjbl = P_JBL(PjblRaw); \

259

numJPs = Pjbl->jbl_NumJPs; \

260

\

261

for (offset = 0; offset < numJPs; ++offset) \

262

{ \

263

CopyImmed(cLevel, (Pjbl->jbl_jp) + offset, CopyIndex); \

264

\

265

pop1 = LeafToLeaf(Pleaf, JU_PVALUEPASS \

266

(Pjbl->jbl_jp) + offset, \

267

JU_DIGITTOSTATE(Pjbl->jbl_Expanse[offset], \

268

cLevel), (Pvoid_t) Pjpm); \

269

Pleaf = (LeafType) (((Word_t) Pleaf) + ((cLevel) * pop1)); \

270

JUDYLCODE(Pjv += pop1;) \

271

} \

272

assert(((((Word_t) Pleaf) - ((Word_t) Pjllnew)) / (cLevel)) == (MaxPop1)); \

273

JUDYLCODE(assert((Pjv - ValueArea(Pjllnew, MaxPop1)) == (MaxPop1));) \

274

DBGCODE(JudyCheckSorted(Pjllnew, MaxPop1, cLevel);) \

275

\

276

__JudyFreeJBL(PjblRaw, Pjpm); \

277

\

278

(Pjp->jp_Type) = (NewJPType); \

279

(Pjp->jp_Addr) = (Word_t) PjllnewRaw; \

280

goto ContinueDelWalk; /* delete from new leaf */ \

281

}

282

283

// Overall common code for initial BranchL deletion handling:

284

//

285

// Assert that Index is in the branch, then see if the BranchL should be kept

286

// or else compressed to a leaf. Variables Index, Pjp, and pop1 are in the

287

// context.

288

289

#define JU_BRANCHL(cLevel,MaxPop1,LeafType,NewJPType, \

290

LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \

291

\

292

assert(! JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, cLevel)); \

293

assert(ParentLevel > (cLevel)); \

294

\

295

pop1 = JU_JPBRANCH_POP0(Pjp->jp_DcdPop0, cLevel) + 1; \

296

JU_BRANCH_KEEP(cLevel, MaxPop1, BranchLKeep); \

297

assert(pop1 == (MaxPop1)); \

298

\

299

JU_BRANCHL_COMPRESS(cLevel, LeafType, MaxPop1, NewJPType, \

300

LeafToLeaf, Alloc, ValueArea, CopyImmed, CopyIndex)

301

302

303

// END OF MACROS, START OF CASES:

304

305

case cJU_JPBRANCH_L2:

306

307

JU_BRANCHL(2, cJU_LEAF2_MAXPOP1, uint16_t *, cJU_JPLEAF2,

308

__JudyLeaf1ToLeaf2, __JudyAllocJLL2, JL_LEAF2VALUEAREA,

309

JU_BRANCH_COPY_IMMED_EVEN, ignore);

310

311

case cJU_JPBRANCH_L3:

312

313

JU_BRANCHL(3, cJU_LEAF3_MAXPOP1, uint8_t *, cJU_JPLEAF3,

314

__JudyLeaf2ToLeaf3, __JudyAllocJLL3, JL_LEAF3VALUEAREA,

315

JU_BRANCH_COPY_IMMED_ODD, JU_COPY3_LONG_TO_PINDEX);

316

317

#ifdef JU_64BIT

318

case cJU_JPBRANCH_L4:

319

320

JU_BRANCHL(4, cJU_LEAF4_MAXPOP1, uint32_t *, cJU_JPLEAF4,

321

__JudyLeaf3ToLeaf4, __JudyAllocJLL4, JL_LEAF4VALUEAREA,

322

JU_BRANCH_COPY_IMMED_EVEN, ignore);

323

324

case cJU_JPBRANCH_L5:

325

326

JU_BRANCHL(5, cJU_LEAF5_MAXPOP1, uint8_t *, cJU_JPLEAF5,

327

__JudyLeaf4ToLeaf5, __JudyAllocJLL5, JL_LEAF5VALUEAREA,

328

JU_BRANCH_COPY_IMMED_ODD, JU_COPY5_LONG_TO_PINDEX);

329

330

case cJU_JPBRANCH_L6:

331

332

JU_BRANCHL(6, cJU_LEAF6_MAXPOP1, uint8_t *, cJU_JPLEAF6,

333

__JudyLeaf5ToLeaf6, __JudyAllocJLL6, JL_LEAF6VALUEAREA,

334

JU_BRANCH_COPY_IMMED_ODD, JU_COPY6_LONG_TO_PINDEX);

335

336

case cJU_JPBRANCH_L7:

337

338

JU_BRANCHL(7, cJU_LEAF7_MAXPOP1, uint8_t *, cJU_JPLEAF7,

339

__JudyLeaf6ToLeaf7, __JudyAllocJLL7, JL_LEAF7VALUEAREA,

340

JU_BRANCH_COPY_IMMED_ODD, JU_COPY7_LONG_TO_PINDEX);

341

#endif // JU_64BIT

342

343

// A top-level BranchL is different and cannot use JU_BRANCHL(): Don't try to

344

// compress to a (JAP) leaf yet, but leave this for a later deletion

345

// (hysteresis > 0); and the next JP type depends on the system word size; so

346

// don't use JU_BRANCH_KEEP():

347

348

case cJU_JPBRANCH_L:

349

{

350

Pjbl_t Pjbl;

351

Word_t numJPs;

352

353

level = cJU_ROOTSTATE;

354

digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);

355

356

// fall through:

357

358

359

// COMMON CODE FOR KEEPING AND DESCENDING THROUGH A BRANCHL:

360

//

361

// Come here with level and digit set.

362

363

BranchLKeep:

364

Pjbl = P_JBL(Pjp->jp_Addr);

365

numJPs = Pjbl->jbl_NumJPs;

366

assert(numJPs > 0);

367

DBGCODE(parentJPtype = Pjp->jp_Type;)

368

369

// Search for a match to the digit (valid Index => must find digit):

370

371

for (offset = 0; (Pjbl->jbl_Expanse[offset]) != digit; ++offset)

372

assert(offset < numJPs - 1);

373

374

Pjp = (Pjbl->jbl_jp) + offset;

375

376

// If not at a (deletable) JPIMMED_*_01, continue the walk (to descend through

377

// the BranchL):

378

379

assert(level >= 2);

380

if ((Pjp->jp_Type) != cJU_JPIMMED_1_01 + level - 2) break;

381

382

// At JPIMMED_*_01: Ensure the index is in the right expanse, then delete the

383

// Immed from the BranchL:

384

//

385

// Note: A BranchL has a fixed size and format regardless of numJPs.

386

387

assert((Pjp->jp_DcdPop0) == JU_TRIMTODCDSIZE(Index));

388

389

JU_DELETEINPLACE(Pjbl->jbl_Expanse, numJPs, offset, ignore);

390

JU_DELETEINPLACE(Pjbl->jbl_jp, numJPs, offset, ignore);

391

392

DBGCODE(JudyCheckSorted((Pjll_t) (Pjbl->jbl_Expanse),

393

numJPs - 1, 1);)

394

395

// If only one index left in the BranchL, indicate this to the caller:

396

397

return ((--(Pjbl->jbl_NumJPs) <= 1) ? 2 : 1);

398

399

} // case cJU_JPBRANCH_L.

400

401

402

// ****************************************************************************

403

// BITMAP BRANCH:

404

//

405

// MACROS FOR COMMON CODE:

406

//

407

// Note the reuse of common macros here, defined earlier: JU_BRANCH_KEEP(),

408

// JU_PVALUE*.

409

//

410

// Compress a BranchB into a leaf one index size larger:

411

//

412

// Allocate a new leaf, walk the JPs in the old BranchB (one bitmap subexpanse

413

// at a time) and pack their contents into the new leaf (of type NewJPType),

414

// free the old BranchB, and finally restart the switch to delete Index from

415

// the new leaf. Variables Pjp, Pjpm, Pleaf, digit, and pop1 are in the

416

// context.

417

//

418

// Note: It's no accident that the interface to JU_BRANCHB_COMPRESS() is

419

// identical to JU_BRANCHL_COMPRESS(). Only the details differ in how to

420

// traverse the branch's JPs.

421

422

#define JU_BRANCHB_COMPRESS(cLevel,LeafType,MaxPop1,NewJPType, \

423

LeafToLeaf,Alloc,ValueArea, \

424

CopyImmed,CopyIndex) \

425

{ \

426

LeafType Pleaf; \

427

Pjbb_t PjbbRaw; /* BranchB to compress */ \

428

Pjbb_t Pjbb; \

429

Word_t subexp; /* current subexpanse number */ \

430

BITMAPB_t bitmap; /* portion for this subexpanse */ \

431

Pjp_t Pjp2Raw; /* one subexpanse's subarray */ \

432

Pjp_t Pjp2; \

433

\

434

if ((PjllnewRaw = Alloc(MaxPop1, Pjpm)) == 0) return(-1); \

435

Pjllnew = P_JLL(PjllnewRaw); \

436

Pleaf = (LeafType) Pjllnew; \

437

JUDYLCODE(Pjv = ValueArea(Pleaf, MaxPop1);) \

438

\

439

PjbbRaw = (Pjbb_t) (Pjp->jp_Addr); \

440

Pjbb = P_JBB(PjbbRaw); \

441

\

442

for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp) \

443

{ \

444

if ((bitmap = JU_JBB_BITMAP(Pjbb, subexp)) == 0) \

445

continue; /* empty subexpanse */ \

446

\

447

digit = subexp * cJU_BITSPERSUBEXPB; \

448

Pjp2Raw = JU_JBB_PJP(Pjbb, subexp); \

449

Pjp2 = P_JP(Pjp2Raw); \

450

assert(Pjp2 != (Pjp_t) NULL); \

451

\

452

for (offset = 0; bitmap != 0; bitmap >>= 1, ++digit) \

453

{ \

454

if (! (bitmap & 1)) \

455

continue; /* empty sub-subexpanse */ \

456

\

457

++offset; /* before any continue */ \

458

\

459

CopyImmed(cLevel, Pjp2 + offset - 1, CopyIndex); \

460

\

461

pop1 = LeafToLeaf(Pleaf, JU_PVALUEPASS \

462

Pjp2 + offset - 1, \

463

JU_DIGITTOSTATE(digit, cLevel), \

464

(Pvoid_t) Pjpm); \

465

Pleaf = (LeafType) (((Word_t) Pleaf) + ((cLevel) * pop1)); \

466

JUDYLCODE(Pjv += pop1;) \

467

} \

468

__JudyFreeJBBJP(Pjp2Raw, /* pop1 = */ offset, Pjpm); \

469

} \

470

assert(((((Word_t) Pleaf) - ((Word_t) Pjllnew)) / (cLevel)) == (MaxPop1)); \

471

JUDYLCODE(assert((Pjv - ValueArea(Pjllnew, MaxPop1)) == (MaxPop1));) \

472

DBGCODE(JudyCheckSorted(Pjllnew, MaxPop1, cLevel);) \

473

\

474

__JudyFreeJBB(PjbbRaw, Pjpm); \

475

\

476

(Pjp->jp_Type) = (NewJPType); \

477

(Pjp->jp_Addr) = (Word_t) PjllnewRaw; \

478

goto ContinueDelWalk; /* delete from new leaf */ \

479

}

480

481

// Overall common code for initial BranchB deletion handling:

482

//

483

// Assert that Index is in the branch, then see if the BranchB should be kept

484

// or else compressed to a leaf. Variables Index, Pjp, and pop1 are in the

485

// context.

486

487

#define JU_BRANCHB(cLevel,MaxPop1,LeafType,NewJPType, \

488

LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \

489

\

490

assert(! JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, cLevel)); \

491

assert(ParentLevel > (cLevel)); \

492

\

493

pop1 = JU_JPBRANCH_POP0(Pjp->jp_DcdPop0, cLevel) + 1; \

494

JU_BRANCH_KEEP(cLevel, MaxPop1, BranchBKeep); \

495

assert(pop1 == (MaxPop1)); \

496

\

497

JU_BRANCHB_COMPRESS(cLevel, LeafType, MaxPop1, NewJPType, \

498

LeafToLeaf, Alloc, ValueArea, CopyImmed, CopyIndex)

499

500

501

// END OF MACROS, START OF CASES:

502

//

503

// Note: It's no accident that the macro calls for these cases is nearly

504

// identical to the code for BranchL's.

505

506

case cJU_JPBRANCH_B2:

507

508

JU_BRANCHB(2, cJU_LEAF2_MAXPOP1, uint16_t *, cJU_JPLEAF2,

509

__JudyLeaf1ToLeaf2, __JudyAllocJLL2, JL_LEAF2VALUEAREA,

510

JU_BRANCH_COPY_IMMED_EVEN, ignore);

511

512

case cJU_JPBRANCH_B3:

513

514

JU_BRANCHB(3, cJU_LEAF3_MAXPOP1, uint8_t *, cJU_JPLEAF3,

515

__JudyLeaf2ToLeaf3, __JudyAllocJLL3, JL_LEAF3VALUEAREA,

516

JU_BRANCH_COPY_IMMED_ODD, JU_COPY3_LONG_TO_PINDEX);

517

518

#ifdef JU_64BIT

519

case cJU_JPBRANCH_B4:

520

521

JU_BRANCHB(4, cJU_LEAF4_MAXPOP1, uint32_t *, cJU_JPLEAF4,

522

__JudyLeaf3ToLeaf4, __JudyAllocJLL4, JL_LEAF4VALUEAREA,

523

JU_BRANCH_COPY_IMMED_EVEN, ignore);

524

525

case cJU_JPBRANCH_B5:

526

527

JU_BRANCHB(5, cJU_LEAF5_MAXPOP1, uint8_t *, cJU_JPLEAF5,

528

__JudyLeaf4ToLeaf5, __JudyAllocJLL5, JL_LEAF5VALUEAREA,

529

JU_BRANCH_COPY_IMMED_ODD, JU_COPY5_LONG_TO_PINDEX);

530

531

case cJU_JPBRANCH_B6:

532

533

JU_BRANCHB(6, cJU_LEAF6_MAXPOP1, uint8_t *, cJU_JPLEAF6,

534

__JudyLeaf5ToLeaf6, __JudyAllocJLL6, JL_LEAF6VALUEAREA,

535

JU_BRANCH_COPY_IMMED_ODD, JU_COPY6_LONG_TO_PINDEX);

536

537

case cJU_JPBRANCH_B7:

538

539

JU_BRANCHB(7, cJU_LEAF7_MAXPOP1, uint8_t *, cJU_JPLEAF7,

540

__JudyLeaf6ToLeaf7, __JudyAllocJLL7, JL_LEAF7VALUEAREA,

541

JU_BRANCH_COPY_IMMED_ODD, JU_COPY7_LONG_TO_PINDEX);

542

#endif // JU_64BIT

543

544

// A top-level BranchB is different and cannot use JU_BRANCHB(): Don't try to

545

// compress to a (JAP) leaf yet, but leave this for a later deletion

546

// (hysteresis > 0); and the next JP type depends on the system word size; so

547

// don't use JU_BRANCH_KEEP():

548

549

case cJU_JPBRANCH_B:

550

{

551

Pjbb_t Pjbb; // BranchB to modify.

552

Word_t subexp; // current subexpanse number.

553

Word_t subexp2; // in second-level loop.

554

BITMAPB_t bitmap; // portion for this subexpanse.

555

BITMAPB_t bitmask; // with digit's bit set.

556

Pjp_t Pjp2Raw; // one subexpanse's subarray.

557

Pjp_t Pjp2;

558

Word_t numJPs; // in one subexpanse.

559

560

level = cJU_ROOTSTATE;

561

digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);

562

563

// fall through:

564

565

566

// COMMON CODE FOR KEEPING AND DESCENDING THROUGH A BRANCHB:

567

//

568

// Come here with level and digit set.

569

570

BranchBKeep:

571

Pjbb = P_JBB(Pjp->jp_Addr);

572

subexp = digit / cJU_BITSPERSUBEXPB;

573

bitmap = JU_JBB_BITMAP(Pjbb, subexp);

574

bitmask = JU_BITPOSMASKB(digit);

575

assert(bitmap & bitmask); // Index valid => digit's bit is set.

576

DBGCODE(parentJPtype = Pjp->jp_Type;)

577

578

// Compute digit's offset into the bitmap, with a fast method if all bits are

579

// set:

580

581

offset = ((bitmap == (cJU_FULLBITMAPB)) ?

582

digit % cJU_BITSPERSUBEXPB :

583

__JudyCountBitsB(bitmap & JU_MASKLOWEREXC(bitmask)));

584

585

Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);

586

Pjp2 = P_JP(Pjp2Raw);

587

assert(Pjp2 != (Pjp_t) NULL); // valid subexpanse pointer.

588

589

// If not at a (deletable) JPIMMED_*_01, continue the walk (to descend through

590

// the BranchB):

591

592

if (((Pjp2 + offset)->jp_Type) != cJU_JPIMMED_1_01 + level - 2)

593

{

594

Pjp = Pjp2 + offset;

595

break;

596

}

597

598

// At JPIMMED_*_01: Ensure the index is in the right expanse, then delete the

599

// Immed from the BranchB:

600

601

assert(((Pjp2 + offset)->jp_DcdPop0)

602

== JU_TRIMTODCDSIZE(Index));

603

604

// If only one index is left in the subexpanse, free the JP array:

605

606

if ((numJPs = __JudyCountBitsB(bitmap)) == 1)

607

{

608

__JudyFreeJBBJP(Pjp2Raw, /* pop1 = */ 1, Pjpm);

609

JU_JBB_PJP(Pjbb, subexp) = (Pjp_t) NULL;

610

}

611

612

// Shrink JP array in-place:

613

614

else if (JU_BRANCHBJPGROWINPLACE(numJPs - 1))

615

{

616

assert(numJPs > 0);

617

JU_DELETEINPLACE(Pjp2, numJPs, offset, ignore);

618

}

619

620

// JP array would end up too large; compress it to a smaller one:

621

622

else

623

{

624

Pjp_t PjpnewRaw;

625

Pjp_t Pjpnew;

626

627

if ((PjpnewRaw = __JudyAllocJBBJP(numJPs - 1, Pjpm))

628

== (Pjp_t) NULL) return(-1);

629

Pjpnew = P_JP(PjpnewRaw);

630

631

JU_DELETECOPY(Pjpnew, Pjp2, numJPs, offset, ignore);

632

__JudyFreeJBBJP(Pjp2Raw, numJPs, Pjpm); // old.

633

634

JU_JBB_PJP(Pjbb, subexp) = PjpnewRaw;

635

}

636

637

// Clear digit's bit in the bitmap:

638

639

JU_JBB_BITMAP(Pjbb, subexp) ^= bitmask;

640

641

// If the current subexpanse alone is still too large for a BranchL (with

642

// hysteresis = 1), the delete is all done:

643

644

if (numJPs > cJU_BRANCHLMAXJPS) return(1);

645

646

// Consider shrinking the current BranchB to a BranchL:

647

//

648

// Check the numbers of JPs in other subexpanses in the BranchL. Upon reaching

649

// the critical number of numJPs (which could be right at the start; again,

650

// with hysteresis = 1), it's faster to just watch for any non-empty subexpanse

651

// than to count bits in each subexpanse. Upon finding too many JPs, give up

652

// on shrinking the BranchB.

653

654

for (subexp2 = 0; subexp2 < cJU_NUMSUBEXPB; ++subexp2)

655

{

656

if (subexp2 == subexp) continue; // skip current subexpanse.

657

658

if ((numJPs == cJU_BRANCHLMAXJPS) ?

659

JU_JBB_BITMAP(Pjbb, subexp2) :

660

((numJPs += __JudyCountBitsB(JU_JBB_BITMAP(Pjbb, subexp2)))

661

> cJU_BRANCHLMAXJPS))

662

{

663

return(1); // too many JPs, cannot shrink.

664

}

665

}

666

667

// Shrink current BranchB to a BranchL:

668

//

669

// Note: In this rare case, ignore the return value, do not pass it to the

670

// caller, because the deletion is already successfully completed and the

671

// caller(s) must decrement population counts. The only errors expected from

672

// this call are JU_ERRNO_NOMEM and JU_ERRNO_OVERRUN, neither of which is worth

673

// forwarding from this point. See also 4.1, 4.8, and 4.15 of this file.

674

675

(void) __JudyBranchBToBranchL(Pjp, Pjpm);

676

return(1);

677

678

} // case.

679

680

681

// ****************************************************************************

682

// UNCOMPRESSED BRANCH:

683

//

684

// MACROS FOR COMMON CODE:

685

//

686

// Note the reuse of common macros here, defined earlier: JU_PVALUE*.

687

//

688

// Compress a BranchU into a leaf one index size larger:

689

//

690

// Allocate a new leaf, walk the JPs in the old BranchU and pack their contents

691

// into the new leaf (of type NewJPType), free the old BranchU, and finally

692

// restart the switch to delete Index from the new leaf. Variables Pjp, Pjpm,

693

// digit, and pop1 are in the context.

694

//

695

// Note: It's no accident that the interface to JU_BRANCHU_COMPRESS() is

696

// nearly identical to JU_BRANCHL_COMPRESS(); just NullJPType is added. The

697

// details differ in how to traverse the branch's JPs --

698

//

699

// -- and also, what to do upon encountering a cJU_JPIMMED_*_01 JP. In

700

// BranchL's and BranchB's the JP must be deleted, but in a BranchU it's merely

701

// converted to a null JP, and this is done by other switch cases, so the "keep

702

// branch" situation is simpler here and JU_BRANCH_KEEP() is not used. Also,

703

// there's no code to convert a BranchU to a BranchB since counting the JPs in

704

// a BranchU is (at least presently) expensive, and besides, keeping around a

705

// BranchU is form of hysteresis.

706

707

#define JU_BRANCHU_COMPRESS(cLevel,LeafType,MaxPop1,NullJPType,NewJPType, \

708

LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \

709

{ \

710

LeafType Pleaf; \

711

Pjbu_t PjbuRaw = (Pjbu_t) (Pjp->jp_Addr); \

712

Pjp_t Pjp2 = JU_JBU_PJP0(Pjp); \

713

Word_t ldigit; /* larger than uint8_t */ \

714

\

715

if ((PjllnewRaw = Alloc(MaxPop1, Pjpm)) == 0) return(-1); \

716

Pjllnew = P_JLL(PjllnewRaw); \

717

Pleaf = (LeafType) Pjllnew; \

718

JUDYLCODE(Pjv = ValueArea(Pleaf, MaxPop1);) \

719

\

720

for (ldigit = 0; ldigit < cJU_BRANCHUNUMJPS; ++ldigit, ++Pjp2) \

721

{ \

722

/* fast-process common types: */ \

723

if ((Pjp2->jp_Type) == (NullJPType)) continue; \

724

CopyImmed(cLevel, Pjp2, CopyIndex); \

725

\

726

pop1 = LeafToLeaf(Pleaf, JU_PVALUEPASS Pjp2, \

727

JU_DIGITTOSTATE(ldigit, cLevel), \

728

(Pvoid_t) Pjpm); \

729

Pleaf = (LeafType) (((Word_t) Pleaf) + ((cLevel) * pop1)); \

730

JUDYLCODE(Pjv += pop1;) \

731

} \

732

assert(((((Word_t) Pleaf) - ((Word_t) Pjllnew)) / (cLevel)) == (MaxPop1)); \

733

JUDYLCODE(assert((Pjv - ValueArea(Pjllnew, MaxPop1)) == (MaxPop1));) \

734

DBGCODE(JudyCheckSorted(Pjllnew, MaxPop1, cLevel);) \

735

\

736

__JudyFreeJBU(PjbuRaw, Pjpm); \

737

\

738

(Pjp->jp_Type) = (NewJPType); \

739

(Pjp->jp_Addr) = (Word_t) PjllnewRaw; \

740

goto ContinueDelWalk; /* delete from new leaf */ \

741

}

742

743

// Overall common code for initial BranchU deletion handling:

744

//

745

// Assert that Index is in the branch, then see if a BranchU should be kept or

746

// else compressed to a leaf. Variables level, Index, Pjp, and pop1 are in the

747

// context.

748

//

749

// Note: BranchU handling differs from BranchL and BranchB as described above.

750

751

#define JU_BRANCHU(cLevel,MaxPop1,LeafType,NullJPType,NewJPType, \

752

LeafToLeaf,Alloc,ValueArea,CopyImmed,CopyIndex) \

753

\

754

assert(! JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, cLevel)); \

755

assert(ParentLevel > (cLevel)); \

756

DBGCODE(parentJPtype = Pjp->jp_Type;) \

757

\

758

pop1 = JU_JPBRANCH_POP0(Pjp->jp_DcdPop0, cLevel) + 1; \

759

\

760

if (pop1 > (MaxPop1)) /* hysteresis = 1 */ \

761

{ \

762

level = (cLevel); \

763

Pjp = P_JP(Pjp->jp_Addr) + JU_DIGITATSTATE(Index, cLevel);\

764

break; /* descend to next level */ \

765

} \

766

assert(pop1 == (MaxPop1)); \

767

\

768

JU_BRANCHU_COMPRESS(cLevel, LeafType, MaxPop1, NullJPType, NewJPType, \

769

LeafToLeaf, Alloc, ValueArea, CopyImmed, CopyIndex)

770

771

772

// END OF MACROS, START OF CASES:

773

//

774

// Note: It's no accident that the macro calls for these cases is nearly

775

// identical to the code for BranchL's, with the addition of cJU_JPNULL*

776

// parameters only needed for BranchU's.

777

778

case cJU_JPBRANCH_U2:

779

780

JU_BRANCHU(2, cJU_LEAF2_MAXPOP1, uint16_t *,

781

cJU_JPNULL1, cJU_JPLEAF2,

782

__JudyLeaf1ToLeaf2, __JudyAllocJLL2, JL_LEAF2VALUEAREA,

783

JU_BRANCH_COPY_IMMED_EVEN, ignore);

784

785

case cJU_JPBRANCH_U3:

786

787

JU_BRANCHU(3, cJU_LEAF3_MAXPOP1, uint8_t *,

788

cJU_JPNULL2, cJU_JPLEAF3,

789

__JudyLeaf2ToLeaf3, __JudyAllocJLL3, JL_LEAF3VALUEAREA,

790

JU_BRANCH_COPY_IMMED_ODD, JU_COPY3_LONG_TO_PINDEX);

791

792

#ifdef JU_64BIT

793

case cJU_JPBRANCH_U4:

794

795

JU_BRANCHU(4, cJU_LEAF4_MAXPOP1, uint32_t *,

796

cJU_JPNULL3, cJU_JPLEAF4,

797

__JudyLeaf3ToLeaf4, __JudyAllocJLL4, JL_LEAF4VALUEAREA,

798

JU_BRANCH_COPY_IMMED_EVEN, ignore);

799

800

case cJU_JPBRANCH_U5:

801

802

JU_BRANCHU(5, cJU_LEAF5_MAXPOP1, uint8_t *,

803

cJU_JPNULL4, cJU_JPLEAF5,

804

__JudyLeaf4ToLeaf5, __JudyAllocJLL5, JL_LEAF5VALUEAREA,

805

JU_BRANCH_COPY_IMMED_ODD, JU_COPY5_LONG_TO_PINDEX);

806

807

case cJU_JPBRANCH_U6:

808

809

JU_BRANCHU(6, cJU_LEAF6_MAXPOP1, uint8_t *,

810

cJU_JPNULL5, cJU_JPLEAF6,

811

__JudyLeaf5ToLeaf6, __JudyAllocJLL6, JL_LEAF6VALUEAREA,

812

JU_BRANCH_COPY_IMMED_ODD, JU_COPY6_LONG_TO_PINDEX);

813

814

case cJU_JPBRANCH_U7:

815

816

JU_BRANCHU(7, cJU_LEAF7_MAXPOP1, uint8_t *,

817

cJU_JPNULL6, cJU_JPLEAF7,

818

__JudyLeaf6ToLeaf7, __JudyAllocJLL7, JL_LEAF7VALUEAREA,

819

JU_BRANCH_COPY_IMMED_ODD, JU_COPY7_LONG_TO_PINDEX);

820

#endif // JU_64BIT

821

822

// A top-level BranchU is different and cannot use JU_BRANCHU(): Don't try to

823

// compress to a (JAP) leaf yet, but leave this for a later deletion

824

// (hysteresis > 0); just descend through the BranchU:

825

826

case cJU_JPBRANCH_U:

827

828

DBGCODE(parentJPtype = Pjp->jp_Type;)

829

830

level = cJU_ROOTSTATE;

831

Pjp = P_JP(Pjp->jp_Addr) + JU_DIGITATSTATE(Index, cJU_ROOTSTATE);

832

break;

833

834

835

// ****************************************************************************

836

// LINEAR LEAF:

837

//

838

// State transitions while deleting an Index, the inverse of the similar table

839

// that appears in JudyIns.c:

840

//

841

// Note: In JudyIns.c this table is not needed and does not appear until the

842

// Immed handling code; because once a Leaf is reached upon growing the tree,

843

// the situation remains simpler, but for deleting indexes, the complexity

844

// arises when leaves must compress to Immeds.

845

//

846

// Note: There are other transitions possible too, not shown here, such as to

847

// a leaf one level higher.

848

//

849

// (Yes, this is very terse... Study it and it will make sense.)

850

// (Note, parts of this diagram are repeated below for quick reference.)

851

//

852

// reformat JP here for Judy1 only, from word-1 to word-2

853

// |

854

// JUDY1 && JU_64BIT JUDY1 || JU_64BIT |

855

// V

856

// (*) Leaf1 [[ => 1_15..08 ] => 1_07 => ... => 1_04 ] => 1_03 => 1_02 => 1_01

857

// Leaf2 [[ => 2_07..04 ] => 2_03 => 2_02 ] => 2_01

858

// Leaf3 [[ => 3_05..03 ] => 3_02 ] => 3_01

859

// JU_64BIT only:

860

// Leaf4 [[ => 4_03..02 ]] => 4_01

861

// Leaf5 [[ => 5_03..02 ]] => 5_01

862

// Leaf6 [[ => 6_02 ]] => 6_01

863

// Leaf7 [[ => 7_02 ]] => 7_01

864

//

865

// (*) For Judy1 & 64-bit, go directly from a LeafB1 to cJU_JPIMMED_1_15; skip

866

// Leaf1, as described in Judy1.h regarding cJ1_JPLEAF1.

867

//

868

// MACROS FOR COMMON CODE:

869

//

870

// (De)compress a LeafX into a LeafY one index size (cIS) larger (X+1 = Y):

871

//

872

// This is only possible when the current leaf is under a narrow pointer

873

// ((ParentLevel - 1) > cIS) and its population fits in a higher-level leaf.

874

// Variables ParentLevel, pop1, PjllnewRaw, Pjllnew, Pjpm, and Index are in the

875

// context.

876

//

877

// Note: Doing an "uplevel" doesn't occur until the old leaf can be compressed

878

// up one level BEFORE deleting an index; that is, hysteresis = 1.

879

//

880

// Note: LeafType, MaxPop1, NewJPType, and Alloc refer to the up-level leaf,

881

// not the current leaf.

882

//

883

// Note: 010327: Fixed bug where the jp_DcdPop0 next-uplevel digit (byte)

884

// above the current Pop0 value was not being cleared. When upleveling, one

885

// digit in jp_DcdPop0 "moves" from being part of the Dcd subfield to the Pop0

886

// subfield, but since a leaf maxpop1 is known to be <= 1 byte in size, the new

887

// Pop0 byte should always be zero. This is easy to overlook because

888

// JU_JPLEAF_POP0() "knows" to only use the LSB of Pop0 (for efficiency) and

889

// ignore the other bytes... Until someone uses cJU_POP0MASK() instead of

890

// JU_JPLEAF_POP0(), such as in JudyInsertBranch.c.

891

//

892

// TBD: Should JudyInsertBranch.c use JU_JPLEAF_POP0() rather than

893

// cJU_POP0MASK(), for efficiency? Does it know for sure it's a narrow pointer

894

// under the leaf? Not necessarily.

895

896

#define JU_LEAF_UPLEVEL(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \

897

Alloc,ValueArea) \

898

\

899

assert(((ParentLevel - 1) == (cIS)) || (pop1 >= (MaxPop1))); \

900

\

901

if (((ParentLevel - 1) > (cIS)) /* under narrow pointer */ \

902

&& (pop1 == (MaxPop1))) /* hysteresis = 1 */ \

903

{ \

904

if ((PjllnewRaw = Alloc(MaxPop1, Pjpm)) == 0) return(-1); \

905

Pjllnew = P_JLL(PjllnewRaw); \

906

JUDYLCODE(Pjv = ValueArea((LeafType) Pjllnew, MaxPop1);) \

907

\

908

(void) LeafToLeaf((LeafType) Pjllnew, JU_PVALUEPASS Pjp, \

909

Index & cJU_DCDMASK(cIS), /* TBD, Doug says */ \

910

(Pvoid_t) Pjpm); \

911

DBGCODE(JudyCheckSorted(Pjllnew, MaxPop1, cIS + 1);) \

912

\

913

(Pjp->jp_Addr) = (Word_t) PjllnewRaw; \

914

(Pjp->jp_DcdPop0) &= ~cJU_MASKATSTATE((cIS) + 1); /* see above */ \

915

(Pjp->jp_Type) = (NewJPType); \

916

goto ContinueDelWalk; /* delete from new leaf */ \

917

}

918

919

// For Leaf3, only support JU_LEAF_UPLEVEL on a 64-bit system, and for Leaf7,

920

// there is no JU_LEAF_UPLEVEL:

921

//

922

// Note: There's no way here to go from Leaf3 [Leaf7] to JAPLEAF on a 32-bit

923

// [64-bit] system. That's handled in the main code, because it's different in

924

// that a JPM is involved.

925

926

#ifndef JU_64BIT // 32-bit.

927

#define JU_LEAF_UPLEVEL64(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \

928

Alloc,ValueArea) // null.

929

#else

930

#define JU_LEAF_UPLEVEL64(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \

931

Alloc,ValueArea) \

932

JU_LEAF_UPLEVEL (cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \

933

Alloc,ValueArea)

934

#define JU_LEAF_UPLEVEL_NONE(cIS,LeafType,MaxPop1,NewJPType,LeafToLeaf, \

935

Alloc,ValueArea) // null.

936

#endif

937

938

// Compress a Leaf* with pop1 = 2, or a JPIMMED_*_02, into a JPIMMED_*_01:

939

//

940

// Copy whichever Index is NOT being deleted (and assert that the other one is

941

// found; Index must be valid). This requires special handling of the Index

942

// bytes (and value area). Variables Pjp, Index, offset, and Pleaf are in the

943

// context, offset is modified to the undeleted Index, and Pjp is modified

944

// including jp_Addr.

945

946

#define JU_TOIMMED_01_EVEN(cIS,ignore1,ignore2) \

947

offset = (Pleaf[0] == JU_LEASTBYTES(Index, cIS)); /* undeleted Ind */ \

948

assert(Pleaf[offset ? 0 : 1] == JU_LEASTBYTES(Index, cIS)); \

949

(Pjp->jp_DcdPop0) = (Index & cJU_DCDMASK(cIS)) | Pleaf[offset]; \

950

JUDYLCODE((Pjp->jp_Addr) = Pjv[offset];)

951

952

#define JU_TOIMMED_01_ODD(cIS,SearchLeaf,CopyPIndex) \

953

{ \

954

Word_t tempindex; \

955

\

956

offset = SearchLeaf(Pleaf, 2, Index); \

957

assert(offset >= 0); /* Index must be valid */ \

958

CopyPIndex(tempindex, & (Pleaf[offset ? 0 : cIS])); \

959

(Pjp->jp_DcdPop0) = tempindex | (Index & cJU_DCDMASK(cIS)); \

960

JUDYLCODE((Pjp->jp_Addr) = Pjv[offset ? 0 : 1];) \

961

}

962

963

// Compress a Leaf* into a JPIMMED_*_0[2+]:

964

//

965

// This occurs as soon as it's possible, with hysteresis = 0. Variables pop1,

966

// Pleaf, offset, and Pjpm are in the context.

967

//

968

// TBD: Explain why hysteresis = 0 here, rather than > 0. Probably because

969

// the insert code assumes if the population is small enough, an Immed is used,

970

// not a leaf.

971

//

972

// The differences between Judy1 and JudyL with respect to value area handling

973

// are just too large for completely common code between them... Oh well, some

974

// big ifdefs follow.

975

976

#ifdef JUDY1

977

978

#define JU_LEAF_TOIMMED(cIS,LeafType,MaxPop1,BaseJPType,ignore1,\

979

ignore2,ignore3,ignore4, \

980

DeleteCopy,FreeLeaf) \

981

\

982

assert(pop1 > (MaxPop1)); \

983

\

984

if ((pop1 - 1) == (MaxPop1)) /* hysteresis = 0 */ \

985

{ \

986

Pjll_t PjllRaw = (Pjll_t) (Pjp->jp_Addr); \

987

DeleteCopy((LeafType) (Pjp->jp_1Index), Pleaf, pop1, offset, cIS); \

988

DBGCODE(JudyCheckSorted((Pjll_t) (Pjp->jp_1Index), pop1-1, cIS);) \

989

(Pjp->jp_Type) = (BaseJPType) - 1 + (MaxPop1) - 1; \

990

FreeLeaf(PjllRaw, pop1, Pjpm); \

991

return(1); \

992

}

993

994

#else // JUDYL

995

996

// Pjv is also in the context.

997

998

#define JU_LEAF_TOIMMED(cIS,LeafType,MaxPop1,BaseJPType,ignore1,\

999

ignore2,ignore3,ignore4, \

1000

DeleteCopy,FreeLeaf) \

1001

\

1002

assert(pop1 > (MaxPop1)); \

1003

\

1004

if ((pop1 - 1) == (MaxPop1)) /* hysteresis = 0 */ \

1005

{ \

1006

Pjll_t PjllRaw = (Pjll_t) (Pjp->jp_Addr); \

1007

Pjv_t PjvnewRaw; \

1008

Pjv_t Pjvnew; \

1009

\

1010

if ((PjvnewRaw = __JudyLAllocJV(pop1 - 1, Pjpm)) \

1011

== (Pjv_t) NULL) return(-1); \

1012

JUDYLCODE(Pjvnew = P_JV(PjvnewRaw);) \

1013

\

1014

DeleteCopy((LeafType) (Pjp->jp_LIndex), Pleaf, pop1, offset, cIS); \

1015

JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, cIS); \

1016

DBGCODE(JudyCheckSorted((Pjll_t) (Pjp->jp_LIndex), pop1-1, cIS);) \

1017

FreeLeaf(PjllRaw, pop1, Pjpm); \

1018

(Pjp->jp_Addr) = (Word_t) PjvnewRaw; \

1019

(Pjp->jp_Type) = (BaseJPType) - 2 + (MaxPop1); \

1020

return(1); \

1021

}

1022

1023

// A complicating factor for JudyL & 32-bit is that Leaf2..3, and for JudyL &

1024

// 64-bit Leaf 4..7, go directly to an Immed*_01, where the value is stored in

1025

// jp_Addr and not in a separate LeafV. For efficiency, use the following

1026

// macro in cases where it can apply; it is rigged to do the right thing.

1027

// Unfortunately, this requires the calling code to "know" the transition table

1028

// and call the right macro.

1029

//

1030

// This variant compresses a Leaf* with pop1 = 2 into a JPIMMED_*_01:

1031

1032

#define JU_LEAF_TOIMMED_01(cIS,LeafType,MaxPop1,ignore,Immed01JPType, \

1033

ToImmed,SearchLeaf,CopyPIndex, \

1034

DeleteCopy,FreeLeaf) \

1035

\

1036

assert(pop1 > (MaxPop1)); \

1037

\

1038

if ((pop1 - 1) == (MaxPop1)) /* hysteresis = 0 */ \

1039

{ \

1040

Pjll_t PjllRaw = (Pjll_t) (Pjp->jp_Addr); \

1041

ToImmed(cIS, SearchLeaf, CopyPIndex); \

1042

FreeLeaf(PjllRaw, pop1, Pjpm); \

1043

(Pjp->jp_Type) = (Immed01JPType); \

1044

return(1); \

1045

}

1046

#endif // JUDYL

1047

1048

// See comments above about these:

1049

//

1050

// Note: Here "23" means index size 2 or 3, and "47" means 4..7.

1051

1052

#if (JUDY1 || JU_64BIT)

1053

#define JU_LEAF_TOIMMED_23(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \

1054

ToImmed,SearchLeaf,CopyPIndex, \

1055

DeleteCopy,FreeLeaf) \

1056

JU_LEAF_TOIMMED( cIS,LeafType,MaxPop1,BaseJPType,ignore1, \

1057

ignore2,ignore3,ignore4, \

1058

DeleteCopy,FreeLeaf)

1059

#else // JUDYL && 32-bit

1060

#define JU_LEAF_TOIMMED_23(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \

1061

ToImmed,SearchLeaf,CopyPIndex, \

1062

DeleteCopy,FreeLeaf) \

1063

JU_LEAF_TOIMMED_01(cIS,LeafType,MaxPop1,ignore,Immed01JPType, \

1064

ToImmed,SearchLeaf,CopyPIndex, \

1065

DeleteCopy,FreeLeaf)

1066

#endif

1067

1068

#ifdef JU_64BIT

1069

#ifdef JUDY1

1070

#define JU_LEAF_TOIMMED_47(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \

1071

ToImmed,SearchLeaf,CopyPIndex, \

1072

DeleteCopy,FreeLeaf) \

1073

JU_LEAF_TOIMMED( cIS,LeafType,MaxPop1,BaseJPType,ignore1, \

1074

ignore2,ignore3,ignore4, \

1075

DeleteCopy,FreeLeaf)

1076

#else // JUDYL && 64-bit

1077

#define JU_LEAF_TOIMMED_47(cIS,LeafType,MaxPop1,BaseJPType,Immed01JPType, \

1078

ToImmed,SearchLeaf,CopyPIndex, \

1079

DeleteCopy,FreeLeaf) \

1080

JU_LEAF_TOIMMED_01(cIS,LeafType,MaxPop1,ignore,Immed01JPType, \

1081

ToImmed,SearchLeaf,CopyPIndex, \

1082

DeleteCopy,FreeLeaf)

1083

#endif // JUDYL

1084

#endif // JU_64BIT

1085

1086

// Compress a Leaf* in place:

1087

//

1088

// Here hysteresis = 0 (no memory is wasted). Variables pop1, Pleaf, and

1089

// offset, and for JudyL, Pjv, are in the context.

1090

1091

#ifdef JUDY1

1092

#define JU_LEAF_INPLACE(cIS,GrowInPlace,DeleteInPlace) \

1093

if (GrowInPlace(pop1 - 1)) /* hysteresis = 0 */ \

1094

{ \

1095

DeleteInPlace(Pleaf, pop1, offset, cIS); \

1096

DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \

1097

return(1); \

1098

}

1099

#else

1100

#define JU_LEAF_INPLACE(cIS,GrowInPlace,DeleteInPlace) \

1101

if (GrowInPlace(pop1 - 1)) /* hysteresis = 0 */ \

1102

{ \

1103

DeleteInPlace(Pleaf, pop1, offset, cIS); \

1104

/**/ JU_DELETEINPLACE(Pjv, pop1, offset, ignore); \

1105

DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \

1106

return(1); \

1107

}

1108

#endif

1109

1110

// Compress a Leaf* into a smaller memory object of the same JP type:

1111

//

1112

// Variables PjllnewRaw, Pjllnew, Pleafpop1, Pjpm, PleafRaw, Pleaf, and offset

1113

// are in the context.

1114

1115

#ifdef JUDY1

1116

1117

#define JU_LEAF_SHRINK(cIS,LeafType,DeleteCopy,Alloc,FreeLeaf,ValueArea) \

1118

if ((PjllnewRaw = Alloc(pop1 - 1, Pjpm)) == 0) return(-1); \

1119

Pjllnew = P_JLL(PjllnewRaw); \

1120

DeleteCopy((LeafType) Pjllnew, Pleaf, pop1, offset, cIS); \

1121

DBGCODE(JudyCheckSorted(Pjllnew, pop1 - 1, cIS);) \

1122

FreeLeaf(PleafRaw, pop1, Pjpm); \

1123

Pjp->jp_Addr = (Word_t) PjllnewRaw; \

1124

return(1)

1125

1126

#else // JUDYL

1127

1128

#define JU_LEAF_SHRINK(cIS,LeafType,DeleteCopy,Alloc,FreeLeaf,ValueArea) \

1129

{ \

1130

/**/ Pjv_t Pjvnew; \

1131

\

1132

if ((PjllnewRaw = Alloc(pop1 - 1, Pjpm)) == 0) return(-1); \

1133

Pjllnew = P_JLL(PjllnewRaw); \

1134

/**/ Pjvnew = ValueArea(Pjllnew, pop1 - 1); \

1135

DeleteCopy((LeafType) Pjllnew, Pleaf, pop1, offset, cIS); \

1136

/**/ JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, cIS); \

1137

DBGCODE(JudyCheckSorted(Pjllnew, pop1 - 1, cIS);) \

1138

FreeLeaf(PleafRaw, pop1, Pjpm); \

1139

Pjp->jp_Addr = (Word_t) PjllnewRaw; \

1140

return(1); \

1141

}

1142

#endif // JUDYL

1143

1144

// Overall common code for Leaf* deletion handling:

1145

//

1146

// See if the leaf can be:

1147

// - (de)compressed to one a level higher (JU_LEAF_UPLEVEL()), or if not,

1148

// - compressed to an Immediate JP (JU_LEAF_TOIMMED()), or if not,

1149

// - shrunk in place (JU_LEAF_INPLACE()), or if none of those, then

1150

// - shrink the leaf to a smaller chunk of memory (JU_LEAF_SHRINK()).

1151

//

1152

// Variables Pjp, pop1, Index, and offset are in the context.

1153

// The *Up parameters refer to a leaf one level up, if there is any.

1154

1155

#define JU_LEAF(cIS, \

1156

UpLevel, \

1157

LeafTypeUp,MaxPop1Up,LeafJPTypeUp,LeafToLeaf, \

1158

AllocUp,ValueAreaUp, \

1159

LeafToImmed,ToImmed,CopyPIndex, \

1160

LeafType,ImmedMaxPop1,ImmedBaseJPType,Immed01JPType, \

1161

SearchLeaf,GrowInPlace,DeleteInPlace,DeleteCopy, \

1162

Alloc,FreeLeaf,ValueArea) \

1163

{ \

1164

Pjll_t PleafRaw; \

1165

LeafType Pleaf; \

1166

\

1167

assert(! JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, cIS)); \

1168

assert(ParentLevel > (cIS)); \

1169

\

1170

PleafRaw = (Pjll_t) (Pjp->jp_Addr); \

1171

Pleaf = (LeafType) P_JLL(PleafRaw); \

1172

pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1; \

1173

\

1174

UpLevel(cIS, LeafTypeUp, MaxPop1Up, LeafJPTypeUp, \

1175

LeafToLeaf, AllocUp, ValueAreaUp); \

1176

\

1177

offset = SearchLeaf(Pleaf, pop1, Index); \

1178

assert(offset >= 0); /* Index must be valid */ \

1179

JUDYLCODE(Pjv = ValueArea(Pleaf, pop1);) \

1180

\

1181

LeafToImmed(cIS, LeafType, ImmedMaxPop1, \

1182

ImmedBaseJPType, Immed01JPType, \

1183

ToImmed, SearchLeaf, CopyPIndex, \

1184

DeleteCopy, FreeLeaf); \

1185

\

1186

JU_LEAF_INPLACE(cIS, GrowInPlace, DeleteInPlace); \

1187

\

1188

JU_LEAF_SHRINK(cIS, LeafType, DeleteCopy, Alloc, FreeLeaf, \

1189

ValueArea); \

1190

}

1191

1192

// END OF MACROS, START OF CASES:

1193

//

1194

// (*) Leaf1 [[ => 1_15..08 ] => 1_07 => ... => 1_04 ] => 1_03 => 1_02 => 1_01

1195

1196

#if (JUDYL || (! JU_64BIT))

1197

case cJU_JPLEAF1:

1198

1199

JU_LEAF(1,

1200

JU_LEAF_UPLEVEL, uint16_t *, cJU_LEAF2_MAXPOP1, cJU_JPLEAF2,

1201

__JudyLeaf1ToLeaf2, __JudyAllocJLL2, JL_LEAF2VALUEAREA,

1202

JU_LEAF_TOIMMED, ignore, ignore,

1203

uint8_t *, cJU_IMMED1_MAXPOP1,

1204

cJU_JPIMMED_1_02, cJU_JPIMMED_1_01, __JudySearchLeaf1,

1205

JU_LEAF1GROWINPLACE, JU_DELETEINPLACE, JU_DELETECOPY,

1206

__JudyAllocJLL1, __JudyFreeJLL1, JL_LEAF1VALUEAREA);

1207

#endif

1208

1209

// A complicating factor is that for JudyL & 32-bit, a Leaf2 must go directly

1210

// to an Immed 2_01 and a Leaf3 must go directly to an Immed 3_01:

1211

//

1212

// Leaf2 [[ => 2_07..04 ] => 2_03 => 2_02 ] => 2_01

1213

// Leaf3 [[ => 3_05..03 ] => 3_02 ] => 3_01

1214

//

1215

// Hence use JU_LEAF_TOIMMED_23 instead of JU_LEAF_TOIMMED in the cases below,

1216

// and also the parameters ToImmed and, for odd index sizes, CopyPIndex, are

1217

// required.

1218

1219

case cJU_JPLEAF2:

1220

1221

JU_LEAF(2,

1222

JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF3_MAXPOP1, cJU_JPLEAF3,

1223

__JudyLeaf2ToLeaf3, __JudyAllocJLL3, JL_LEAF3VALUEAREA,

1224

JU_LEAF_TOIMMED_23, JU_TOIMMED_01_EVEN, ignore,

1225

uint16_t *, cJU_IMMED2_MAXPOP1,

1226

cJU_JPIMMED_2_02, cJU_JPIMMED_2_01, __JudySearchLeaf2,

1227

JU_LEAF2GROWINPLACE, JU_DELETEINPLACE, JU_DELETECOPY,

1228

__JudyAllocJLL2, __JudyFreeJLL2, JL_LEAF2VALUEAREA);

1229

1230

// On 32-bit there is no transition to "uplevel" for a Leaf3, so use

1231

// JU_LEAF_UPLEVEL64 instead of JU_LEAF_UPLEVEL:

1232

1233

case cJU_JPLEAF3:

1234

1235

JU_LEAF(3,

1236

JU_LEAF_UPLEVEL64, uint32_t *, cJU_LEAF4_MAXPOP1,

1237

cJU_JPLEAF4,

1238

__JudyLeaf3ToLeaf4, __JudyAllocJLL4, JL_LEAF4VALUEAREA,

1239

JU_LEAF_TOIMMED_23,

1240

JU_TOIMMED_01_ODD, JU_COPY3_PINDEX_TO_LONG,

1241

uint8_t *, cJU_IMMED3_MAXPOP1,

1242

cJU_JPIMMED_3_02, cJU_JPIMMED_3_01, __JudySearchLeaf3,

1243

JU_LEAF3GROWINPLACE, JU_DELETEINPLACE_ODD,

1244

JU_DELETECOPY_ODD,

1245

__JudyAllocJLL3, __JudyFreeJLL3, JL_LEAF3VALUEAREA);

1246

1247

#ifdef JU_64BIT

1248

1249

// A complicating factor is that for JudyL & 64-bit, a Leaf[4-7] must go

1250

// directly to an Immed [4-7]_01:

1251

//

1252

// Leaf4 [[ => 4_03..02 ]] => 4_01

1253

// Leaf5 [[ => 5_03..02 ]] => 5_01

1254

// Leaf6 [[ => 6_02 ]] => 6_01

1255

// Leaf7 [[ => 7_02 ]] => 7_01

1256

//

1257

// Hence use JU_LEAF_TOIMMED_47 instead of JU_LEAF_TOIMMED in the cases below.

1258

1259

case cJU_JPLEAF4:

1260

1261

JU_LEAF(4,

1262

JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF5_MAXPOP1, cJU_JPLEAF5,

1263

__JudyLeaf4ToLeaf5, __JudyAllocJLL5, JL_LEAF5VALUEAREA,

1264

JU_LEAF_TOIMMED_47, JU_TOIMMED_01_EVEN, ignore,

1265

uint32_t *, cJU_IMMED4_MAXPOP1,

1266

cJ1_JPIMMED_4_02, cJU_JPIMMED_4_01, __JudySearchLeaf4,

1267

JU_LEAF4GROWINPLACE, JU_DELETEINPLACE, JU_DELETECOPY,

1268

__JudyAllocJLL4, __JudyFreeJLL4, JL_LEAF4VALUEAREA);

1269

1270

case cJU_JPLEAF5:

1271

1272

JU_LEAF(5,

1273

JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF6_MAXPOP1, cJU_JPLEAF6,

1274

__JudyLeaf5ToLeaf6, __JudyAllocJLL6, JL_LEAF6VALUEAREA,

1275

JU_LEAF_TOIMMED_47,

1276

JU_TOIMMED_01_ODD, JU_COPY5_PINDEX_TO_LONG,

1277

uint8_t *, cJU_IMMED5_MAXPOP1,

1278

cJ1_JPIMMED_5_02, cJU_JPIMMED_5_01, __JudySearchLeaf5,

1279

JU_LEAF5GROWINPLACE, JU_DELETEINPLACE_ODD,

1280

JU_DELETECOPY_ODD,

1281

__JudyAllocJLL5, __JudyFreeJLL5, JL_LEAF5VALUEAREA);

1282

1283

case cJU_JPLEAF6:

1284

1285

JU_LEAF(6,

1286

JU_LEAF_UPLEVEL, uint8_t *, cJU_LEAF7_MAXPOP1, cJU_JPLEAF7,

1287

__JudyLeaf6ToLeaf7, __JudyAllocJLL7, JL_LEAF7VALUEAREA,

1288

JU_LEAF_TOIMMED_47,

1289

JU_TOIMMED_01_ODD, JU_COPY6_PINDEX_TO_LONG,

1290

uint8_t *, cJU_IMMED6_MAXPOP1,

1291

cJ1_JPIMMED_6_02, cJU_JPIMMED_6_01, __JudySearchLeaf6,

1292

JU_LEAF6GROWINPLACE, JU_DELETEINPLACE_ODD,

1293

JU_DELETECOPY_ODD,

1294

__JudyAllocJLL6, __JudyFreeJLL6, JL_LEAF6VALUEAREA);

1295

1296

// There is no transition to "uplevel" for a Leaf7, so use JU_LEAF_UPLEVEL_NONE

1297

// instead of JU_LEAF_UPLEVEL, and ignore all of the parameters to that macro:

1298

1299

case cJU_JPLEAF7:

1300

1301

JU_LEAF(7,

1302

JU_LEAF_UPLEVEL_NONE, ignore1, ignore2, ignore3, ignore4,

1303

ignore5, ignore6,

1304

JU_LEAF_TOIMMED_47,

1305

JU_TOIMMED_01_ODD, JU_COPY7_PINDEX_TO_LONG,

1306

uint8_t *, cJU_IMMED7_MAXPOP1,

1307

cJ1_JPIMMED_7_02, cJU_JPIMMED_7_01, __JudySearchLeaf7,

1308

JU_LEAF7GROWINPLACE, JU_DELETEINPLACE_ODD,

1309

JU_DELETECOPY_ODD,

1310

__JudyAllocJLL7, __JudyFreeJLL7, JL_LEAF7VALUEAREA);

1311

#endif // JU_64BIT

1312

1313

1314

// ****************************************************************************

1315

// BITMAP LEAF:

1316

1317

case cJU_JPLEAF_B1:

1318

{

1319

#ifdef JUDYL

1320

Pjv_t PjvnewRaw; // new value area.

1321

Pjv_t Pjvnew;

1322

Word_t subexp; // 1 of 8 subexpanses in bitmap.

1323

Pjlb_t Pjlb; // pointer to bitmap part of the leaf.

1324

BITMAPL_t bitmap; // for one subexpanse.

1325

BITMAPL_t bitmask; // bit set for Index's digit.

1326

#endif

1327

assert(! JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 1));

1328

assert(ParentLevel > 1);

1329

// valid Index:

1330

assert(JU_BITMAPTESTL(P_JLB(Pjp->jp_Addr), Index));

1331

1332

pop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1;

1333

1334

// Like a Leaf1, see if it's under a narrow pointer and can become a Leaf2

1335

// (hysteresis = 1):

1336

1337

JU_LEAF_UPLEVEL(1, uint16_t *, cJU_LEAF2_MAXPOP1, cJU_JPLEAF2,

1338

__JudyLeaf1ToLeaf2, __JudyAllocJLL2,

1339

JL_LEAF2VALUEAREA);

1340

1341

#if (JUDY1 && JU_64BIT)

1342

1343

// Handle the unusual special case, on Judy1 64-bit only, where a LeafB1 goes

1344

// directly to a JPIMMED_1_15; as described in comments in Judy1.h and

1345

// JudyIns.c. Copy 1-byte indexes from old LeafB1 to the Immed:

1346

1347

if ((pop1 - 1) == cJU_IMMED1_MAXPOP1) // hysteresis = 0.

1348

{

1349

Pjlb_t PjlbRaw; // bitmap in old leaf.

1350

Pjlb_t Pjlb;

1351

uint8_t * Pleafnew; // JPIMMED as a pointer.

1352

Word_t ldigit; // larger than uint8_t.

1353

1354

PjlbRaw = (Pjlb_t) (Pjp->jp_Addr);

1355

Pjlb = P_JLB(PjlbRaw);

1356

Pleafnew = Pjp->jp_1Index;

1357

1358

JU_BITMAPCLEARL(Pjlb, Index); // unset Index's bit.

1359

1360

// TBD: This is very slow, there must be a better way:

1361

1362

for (ldigit = 0; ldigit < cJU_BRANCHUNUMJPS; ++ldigit)

1363

{

1364

if (JU_BITMAPTESTL(Pjlb, ldigit))

1365

{

1366

*Pleafnew++ = ldigit;

1367

assert(Pleafnew - (Pjp->jp_1Index)

1368

<= cJU_IMMED1_MAXPOP1);

1369

}

1370

}

1371

1372

DBGCODE(JudyCheckSorted((Pjll_t) (Pjp->jp_1Index),

1373

cJU_IMMED1_MAXPOP1, 1);)

1374

__JudyFreeJLB1(PjlbRaw, Pjpm);

1375

1376

Pjp->jp_Type = cJ1_JPIMMED_1_15;

1377

return(1);

1378

}

1379

1380

#else // (JUDYL || (! JU_64BIT))

1381

1382

// Compress LeafB1 to a Leaf1:

1383

//

1384

// Note: 4.37 of this file contained alternate code for Judy1 only that simply

1385

// cleared the bit and allowed the LeafB1 to go below cJU_LEAF1_MAXPOP1. This

1386

// was the ONLY case where a malloc failure was not fatal; however, it violated

1387

// the critical assumption that the tree is always kept in least-compressed

1388

// form.

1389

1390

if (pop1 == cJU_LEAF1_MAXPOP1) // hysteresis = 1.

1391

{

1392

if (__JudyLeafB1ToLeaf1(Pjp, Pjpm) == -1) return(-1);

1393

goto ContinueDelWalk; // delete Index in new Leaf1.

1394

}

1395

#endif // (JUDYL || (! JU_64BIT))

1396

1397

#ifdef JUDY1

1398

// unset Index's bit:

1399

1400

JU_BITMAPCLEARL(P_JLB(Pjp->jp_Addr), Index);

1401

#else // JUDYL

1402

1403

// This is very different from Judy1 because of the need to manage the value

1404

// area:

1405

//

1406

// Get last byte to decode from Index, and pointer to bitmap leaf:

1407

1408

digit = JU_DIGITATSTATE(Index, 1);

1409

Pjlb = P_JLB(Pjp->jp_Addr);

1410

1411

// Prepare additional values:

1412

1413

subexp = digit / cJU_BITSPERSUBEXPL; // which subexpanse.

1414

bitmap = JU_JLB_BITMAP(Pjlb, subexp); // subexp's 32-bit map.

1415

PjvRaw = JL_JLB_PVALUE(Pjlb, subexp); // corresponding values.

1416

Pjv = P_JV(PjvRaw);

1417

bitmask = JU_BITPOSMASKL(digit); // mask for Index.

1418

1419

assert(bitmap & bitmask); // Index must be valid.

1420

1421

if (bitmap == cJU_FULLBITMAPL) // full bitmap, take shortcut:

1422

{

1423

pop1 = cJU_BITSPERSUBEXPL;

1424

offset = digit % cJU_BITSPERSUBEXPL;

1425

}

1426

else // compute subexpanse pop1 and value area offset:

1427

{

1428

pop1 = __JudyCountBitsL(bitmap);

1429

offset = __JudyCountBitsL(bitmap & (bitmask - 1));

1430

}

1431

1432

// Handle solitary Index remaining in subexpanse:

1433

1434

if (pop1 == 1)

1435

{

1436

__JudyLFreeJV(PjvRaw, 1, Pjpm);

1437

1438

JL_JLB_PVALUE(Pjlb, subexp) = (Pjv_t) NULL;

1439

JU_JLB_BITMAP(Pjlb, subexp) = 0;

1440

1441

return(1);

1442

}

1443

1444

// Shrink value area in place or move to a smaller value area:

1445

1446

if (JL_LEAFVGROWINPLACE(pop1 - 1)) // hysteresis = 0.

1447

{

1448

JU_DELETEINPLACE(Pjv, pop1, offset, ignore);

1449

}

1450

else

1451

{

1452

if ((PjvnewRaw = __JudyLAllocJV(pop1 - 1, Pjpm))

1453

== (Pjv_t) NULL) return(-1);

1454

Pjvnew = P_JV(PjvnewRaw);

1455

1456

JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, ignore);

1457

__JudyLFreeJV(PjvRaw, pop1, Pjpm);

1458

JL_JLB_PVALUE(Pjlb, subexp) = (Pjv_t) PjvnewRaw;

1459

}

1460

1461

JU_JLB_BITMAP(Pjlb, subexp) ^= bitmask; // clear Index's bit.

1462

1463

#endif // JUDYL

1464

1465

return(1);

1466

1467

} // case.

1468

1469

1470

#ifdef JUDY1

1471

1472

// ****************************************************************************

1473

// FULL POPULATION LEAF:

1474

//

1475

// Convert to a LeafB1 and delete the index. Hysteresis = 0; none is possible.

1476

//

1477

// Note: Earlier the second assertion below said, "== 2", but in fact the

1478

// parent could be at a higher level if a fullpop is under a narrow pointer.

1479

1480

case cJ1_JPFULLPOPU1:

1481

{

1482

Pjlb_t PjlbRaw;

1483

Pjlb_t Pjlb;

1484

Word_t subexp;

1485

1486

assert(! JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, 2));

1487

assert(ParentLevel > 1); // see above.

1488

1489

if ((PjlbRaw = __JudyAllocJLB1(Pjpm)) == (Pjlb_t) NULL)

1490

return(-1);

1491

Pjlb = P_JLB(PjlbRaw);

1492

1493

// Fully populate the leaf, then unset Index's bit:

1494

1495

for (subexp = 0; subexp < cJU_NUMSUBEXPL; ++subexp)

1496

JU_JLB_BITMAP(Pjlb, subexp) = cJU_FULLBITMAPL;

1497

1498

JU_BITMAPCLEARL(Pjlb, Index);

1499

1500

(Pjp->jp_Addr) = (Word_t) PjlbRaw;

1501

(Pjp->jp_Type) = cJU_JPLEAF_B1;

1502

1503

return(1);

1504

}

1505

#endif // JUDY1

1506

1507

1508

// ****************************************************************************

1509

// IMMEDIATE JP:

1510

//

1511

// If there's just the one Index in the Immed, convert the JP to a JPNULL*

1512

// (should only happen in a BranchU); otherwise delete the Index from the

1513

// Immed. See the state transitions table elsewhere in this file for a summary

1514

// of which Immed types must be handled. Hysteresis = 0; none is possible with

1515

// Immeds.

1516

//

1517

// MACROS FOR COMMON CODE:

1518

//

1519

// Single Index remains in cJU_JPIMMED_*_01; convert JP to null:

1520

//

1521

// Variables Pjp and parentJPtype are in the context.

1522

//

1523

// Note: cJU_JPIMMED_*_01 should only be encountered in BranchU's, not in

1524

// BranchL's or BranchB's (where it's improper to merely modify the JP to be a

1525

// null JP); that is, BranchL and BranchB code should have already handled

1526

// any cJU_JPIMMED_*_01 by different means.

1527

1528

#define JU_IMMED_01(NewJPType,ParentJPType) \

1529

\

1530

assert(parentJPtype == (ParentJPType)); \

1531

assert((Pjp->jp_DcdPop0) == JU_TRIMTODCDSIZE(Index)); \

1532

\

1533

(Pjp->jp_Type) = (NewJPType); \

1534

(Pjp->jp_DcdPop0) = 0; \

1535

(Pjp->jp_Addr) = 0; \

1536

return(1)

1537

1538

// Convert cJ*_JPIMMED_*_02 to cJU_JPIMMED_*_01:

1539

//

1540

// Move the undeleted Index, whichever does not match the least bytes of Index,

1541

// from undecoded-bytes-only (in jp_1Index or jp_LIndex as appropriate) to

1542

// jp_DcdPop0 (full-field). Pjp, Index, and offset are in the context.

1543

1544

#define JU_IMMED_02(cIS,LeafType,NewJPType) \

1545

{ \

1546

LeafType Pleaf; \

1547

\

1548

assert((ParentLevel - 1) == (cIS)); \

1549

JUDY1CODE(Pleaf = (LeafType) (Pjp->jp_1Index);) \

1550

JUDYLCODE(Pleaf = (LeafType) (Pjp->jp_LIndex);) \

1551

JUDYLCODE(PjvRaw = (Pjv_t) (Pjp->jp_Addr);) \

1552

JUDYLCODE(Pjv = P_JV(PjvRaw);) \

1553

JU_TOIMMED_01_EVEN(cIS, ignore, ignore); \

1554

JUDYLCODE(__JudyLFreeJV(PjvRaw, 2, Pjpm);) \

1555

(Pjp->jp_Type) = (NewJPType); \

1556

return(1); \

1557

}

1558

1559

#if (JUDY1 || JU_64BIT)

1560

1561

// Variation for "odd" cJ*_JPIMMED_*_02 JP types, which are very different from

1562

// "even" types because they use leaf search code and odd-copy macros:

1563

//

1564

// Note: JudyL 32-bit has no "odd" JPIMMED_*_02 types.

1565

1566

#define JU_IMMED_02_ODD(cIS,NewJPType,SearchLeaf,CopyPIndex) \

1567

{ \

1568

uint8_t * Pleaf; \

1569

\

1570

assert((ParentLevel - 1) == (cIS)); \

1571

JUDY1CODE(Pleaf = (uint8_t *) (Pjp->jp_1Index);) \

1572

JUDYLCODE(Pleaf = (uint8_t *) (Pjp->jp_LIndex);) \

1573

JUDYLCODE(PjvRaw = (Pjv_t) (Pjp->jp_Addr);) \

1574

JUDYLCODE(Pjv = P_JV(PjvRaw);) \

1575

JU_TOIMMED_01_ODD(cIS, SearchLeaf, CopyPIndex); \

1576

JUDYLCODE(__JudyLFreeJV(PjvRaw, 2, Pjpm);) \

1577

(Pjp->jp_Type) = (NewJPType); \

1578

return(1); \

1579

}

1580

#endif // (JUDY1 || JU_64BIT)

1581

1582

// Core code for deleting one Index (and for JudyL, its value area) from a

1583

// larger Immed:

1584

//

1585

// Variables Pleaf, pop1, and offset are in the context.

1586

1587

#ifdef JUDY1

1588

#define JU_IMMED_DEL(cIS,DeleteInPlace) \

1589

DeleteInPlace(Pleaf, pop1, offset, cIS); \

1590

DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);)

1591

1592

#else // JUDYL

1593

1594

// For JudyL the value area might need to be shrunk:

1595

1596

#define JU_IMMED_DEL(cIS,DeleteInPlace) \

1597

\

1598

if (JL_LEAFVGROWINPLACE(pop1 - 1)) /* hysteresis = 0 */ \

1599

{ \

1600

DeleteInPlace( Pleaf, pop1, offset, cIS); \

1601

JU_DELETEINPLACE(Pjv, pop1, offset, ignore); \

1602

DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \

1603

} \

1604

else \

1605

{ \

1606

Pjv_t PjvnewRaw; \

1607

Pjv_t Pjvnew; \

1608

\

1609

if ((PjvnewRaw = __JudyLAllocJV(pop1 - 1, Pjpm)) \

1610

== (Pjv_t) NULL) return(-1); \

1611

Pjvnew = P_JV(PjvnewRaw); \

1612

\

1613

DeleteInPlace(Pleaf, pop1, offset, cIS); \

1614

JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, ignore); \

1615

DBGCODE(JudyCheckSorted(Pleaf, pop1 - 1, cIS);) \

1616

__JudyLFreeJV(PjvRaw, pop1, Pjpm); \

1617

\

1618

(Pjp->jp_Addr) = (Word_t) PjvnewRaw; \

1619

}

1620

#endif // JUDYL

1621

1622

// Delete one Index from a larger Immed where no restructuring is required:

1623

//

1624

// Variables pop1, Pjp, offset, and Index are in the context.

1625

1626

#define JU_IMMED(cIS,LeafType,BaseJPType,SearchLeaf,DeleteInPlace) \

1627

{ \

1628

LeafType Pleaf; \

1629

\

1630

assert((ParentLevel - 1) == (cIS)); \

1631

JUDY1CODE(Pleaf = (LeafType) (Pjp->jp_1Index);) \

1632

JUDYLCODE(Pleaf = (LeafType) (Pjp->jp_LIndex);) \

1633

JUDYLCODE(PjvRaw = (Pjv_t) (Pjp->jp_Addr);) \

1634

JUDYLCODE(Pjv = P_JV(PjvRaw);) \

1635

pop1 = (Pjp->jp_Type) - (BaseJPType) + 2; \

1636

offset = SearchLeaf(Pleaf, pop1, Index); \

1637

assert(offset >= 0); /* Index must be valid */ \

1638

\

1639

JU_IMMED_DEL(cIS, DeleteInPlace); \

1640

--(Pjp->jp_Type); \

1641

return(1); \

1642

}

1643

1644

1645

// END OF MACROS, START OF CASES:

1646

1647

// Single Index remains in Immed; convert JP to null:

1648

1649

case cJU_JPIMMED_1_01: JU_IMMED_01(cJU_JPNULL1, cJU_JPBRANCH_U2);

1650

case cJU_JPIMMED_2_01: JU_IMMED_01(cJU_JPNULL2, cJU_JPBRANCH_U3);

1651

#ifndef JU_64BIT

1652

case cJU_JPIMMED_3_01: JU_IMMED_01(cJU_JPNULL3, cJU_JPBRANCH_U);

1653

#else

1654

case cJU_JPIMMED_3_01: JU_IMMED_01(cJU_JPNULL3, cJU_JPBRANCH_U4);

1655

case cJU_JPIMMED_4_01: JU_IMMED_01(cJU_JPNULL4, cJU_JPBRANCH_U5);

1656

case cJU_JPIMMED_5_01: JU_IMMED_01(cJU_JPNULL5, cJU_JPBRANCH_U6);

1657

case cJU_JPIMMED_6_01: JU_IMMED_01(cJU_JPNULL6, cJU_JPBRANCH_U7);

1658

case cJU_JPIMMED_7_01: JU_IMMED_01(cJU_JPNULL7, cJU_JPBRANCH_U);

1659

#endif

1660

1661

// Multiple Indexes remain in the Immed JP; delete the specified Index:

1662

1663

case cJU_JPIMMED_1_02:

1664

1665

JU_IMMED_02(1, uint8_t *, cJU_JPIMMED_1_01);

1666

1667

case cJU_JPIMMED_1_03:

1668

#if (JUDY1 || JU_64BIT)

1669

case cJU_JPIMMED_1_04:

1670

case cJU_JPIMMED_1_05:

1671

case cJU_JPIMMED_1_06:

1672

case cJU_JPIMMED_1_07:

1673

#endif

1674

#if (JUDY1 && JU_64BIT)

1675

case cJ1_JPIMMED_1_08:

1676

case cJ1_JPIMMED_1_09:

1677

case cJ1_JPIMMED_1_10:

1678

case cJ1_JPIMMED_1_11:

1679

case cJ1_JPIMMED_1_12:

1680

case cJ1_JPIMMED_1_13:

1681

case cJ1_JPIMMED_1_14:

1682

case cJ1_JPIMMED_1_15:

1683

#endif

1684

JU_IMMED(1, uint8_t *, cJU_JPIMMED_1_02,

1685

__JudySearchLeaf1, JU_DELETEINPLACE);

1686

1687

#if (JUDY1 || JU_64BIT)

1688

case cJU_JPIMMED_2_02:

1689

1690

JU_IMMED_02(2, uint16_t *, cJU_JPIMMED_2_01);

1691

1692

case cJU_JPIMMED_2_03:

1693

#endif

1694

#if (JUDY1 && JU_64BIT)

1695

case cJ1_JPIMMED_2_04:

1696

case cJ1_JPIMMED_2_05:

1697

case cJ1_JPIMMED_2_06:

1698

case cJ1_JPIMMED_2_07:

1699

#endif

1700

#if (JUDY1 || JU_64BIT)

1701

JU_IMMED(2, uint16_t *, cJU_JPIMMED_2_02,

1702

__JudySearchLeaf2, JU_DELETEINPLACE);

1703

1704

case cJU_JPIMMED_3_02:

1705

1706

JU_IMMED_02_ODD(3, cJU_JPIMMED_3_01,

1707

__JudySearchLeaf3, JU_COPY3_PINDEX_TO_LONG);

1708

1709

#endif

1710

1711

#if (JUDY1 && JU_64BIT)

1712

case cJ1_JPIMMED_3_03:

1713

case cJ1_JPIMMED_3_04:

1714

case cJ1_JPIMMED_3_05:

1715

1716

JU_IMMED(3, uint8_t *, cJU_JPIMMED_3_02,

1717

__JudySearchLeaf3, JU_DELETEINPLACE_ODD);

1718

1719

case cJ1_JPIMMED_4_02:

1720

1721

JU_IMMED_02(4, uint32_t *, cJU_JPIMMED_4_01);

1722

1723

case cJ1_JPIMMED_4_03:

1724

1725

JU_IMMED(4, uint32_t *, cJ1_JPIMMED_4_02,

1726

__JudySearchLeaf4, JU_DELETEINPLACE);

1727

1728

case cJ1_JPIMMED_5_02:

1729

1730

JU_IMMED_02_ODD(5, cJU_JPIMMED_5_01,

1731

__JudySearchLeaf5, JU_COPY5_PINDEX_TO_LONG);

1732

1733

case cJ1_JPIMMED_5_03:

1734

1735

JU_IMMED(5, uint8_t *, cJ1_JPIMMED_5_02,

1736

__JudySearchLeaf5, JU_DELETEINPLACE_ODD);

1737

1738

case cJ1_JPIMMED_6_02:

1739

1740

JU_IMMED_02_ODD(6, cJU_JPIMMED_6_01,

1741

__JudySearchLeaf6, JU_COPY6_PINDEX_TO_LONG);

1742

1743

case cJ1_JPIMMED_7_02:

1744

1745

JU_IMMED_02_ODD(7, cJU_JPIMMED_7_01,

1746

__JudySearchLeaf7, JU_COPY7_PINDEX_TO_LONG);

1747

1748

#endif // (JUDY1 && JU_64BIT)

1749

1750

1751

// ****************************************************************************

1752

// INVALID JP TYPE:

1753

1754

default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT); return(-1);

1755

1756

} // switch

1757

1758

1759

// PROCESS JP -- RECURSIVELY:

1760

//

1761

// For non-Immed JP types, if successful, post-decrement the population count

1762

// at this level, or collapse a BranchL if necessary by copying the remaining

1763

// JP in the BranchL to the parent (hysteresis = 0), which implicitly creates a

1764

// narrow pointer if there was not already one in the hierarchy.

1765

1766

assert(level);

1767

retcode = __JudyDelWalk(Pjp, Index, level, Pjpm);

1768

assert(retcode != 0); // should never happen.

1769

1770

if ((Pjp->jp_Type) < cJU_JPIMMED_1_01) // not an Immed.

1771

{

1772

switch (retcode)

1773

{

1774

case 1: --(Pjp->jp_DcdPop0); break; // decrement count.

1775

1776

case 2: // collapse BranchL to single JP; see above:

1777

{

1778

Pjbl_t PjblRaw = (Pjbl_t) (Pjp->jp_Addr);

1779

Pjbl_t Pjbl = P_JBL(PjblRaw);

1780

1781

*Pjp = Pjbl->jbl_jp[0];

1782

__JudyFreeJBL(PjblRaw, Pjpm);

1783

retcode = 1;

1784

}

1785

}

1786

}

1787

1788

return(retcode);

1789

1790

} // __JudyDelWalk()

1791

1792

1793

// ****************************************************************************

1794

// J U D Y 1 U N S E T

1795

// J U D Y L D E L

1796

//

1797

// Main entry point. See the manual entry for details.

1798

1799

#ifdef JUDY1

1800

FUNCTION int Judy1Unset (

1801

#else

1802

FUNCTION int JudyLDel (

1803

#endif

1804

PPvoid_t PPArray, // in which to delete.

1805

Word_t Index, // to delete.

1806

PJError_t PJError) // optional, for returning error info.

1807

{

1808

Word_t pop1; // population of leaf.

1809

int offset; // at which to delete Index.

1810

JUDY1CODE(int retcode;) // return code from Judy1Test().

1811

JUDYLCODE(PPvoid_t PPvalue;) // pointer from JudyLGet().

1812

1813

1814

// CHECK FOR NULL ARRAY POINTER (error by caller):

1815

1816

if (PPArray == (PPvoid_t) NULL)

1817

{

1818

JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY);

1819

return(JERRI);

1820

}

1821

1822

1823

// CHECK IF INDEX IS INVALID:

1824

//

1825

// If so, there's nothing to do. This saves a lot of time. Pass through

1826

// PJError, if any, from the "get" function.

1827

1828

#ifdef JUDY1

1829

if ((retcode = Judy1Test(*PPArray, Index, PJError)) == JERRI)

1830

return (JERRI);

1831

1832

if (retcode == 0) return(0);

1833

#else

1834

if ((PPvalue = JudyLGet(*PPArray, Index, PJError)) == PPJERR)

1835

return (JERRI);

1836

1837

if (PPvalue == (PPvoid_t) NULL) return(0);

1838

#endif

1839

1840

1841

// ****************************************************************************

1842

// PROCESS TOP LEVEL (JAP) BRANCHES AND LEAVES:

1843

1844

ContinueDel: // for modifying state without recursing.

1845

1846

switch (JAPTYPE(*PPArray))

1847

{

1848

1849

#if (LOW_POP && JUDYL)

1850

1851

// ****************************************************************************

1852

// JAPLEAF_POPU1:

1853

//

1854

// Check if Index is in the array (should always be). If so, free the leaf and

1855

// modify the root pointer. Hysteresis = 0; none is possible.

1856

1857

case cJL_JAPLEAF_POPU1:

1858

{

1859

Pjlw_t Pjlw = P_JLW(*PPArray); // first word of leaf.

1860

assert(Pjlw[0] == Index);

1861

1862

__JudyFreeJLW(Pjlw, /* pop1 = */ 1, (Pjpm_t) NULL);

1863

1864

*PPArray = (Pvoid_t) NULL; // mark Judy array (JAP) as empty.

1865

DBGCODE(JudyCheckPop(*PPArray);)

1866

return(1);

1867

}

1868

1869

1870

// ****************************************************************************

1871

// JAPLEAF_POPU2:

1872

//

1873

// TBD: It is still debatable whether it is faster to have POPU2 types. It

1874

// needs to be measured. This is a lot of fuss for a 2-element array. -- Doug

1875

1876

case cJL_JAPLEAF_POPU2:

1877

{

1878

1879

// Save the non-deleted Index (whichever it is) and convert the leaf to a

1880

// CJL_JAPLEAF_POPU1 (which is smaller). Hysteresis = 0; none is possible.

1881

//

1882

// TBD: Once again, this would be much cleaner using a data structure.

1883

1884

Pjlw_t Pjlw = P_JLW(*PPArray); // first word of leaf.

1885

Pjlw_t Pjlwnew = __JudyAllocJLW(2 - 1);

1886

JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI);

1887

1888

offset = (Index == Pjlw[0]); // 0 or 1 == undeleted Index.

1889

Pjlwnew[0] = Pjlw[0 + offset]; // undeleted Index.

1890

Pjlwnew[1] = Pjlw[2 + offset]; // its value area.

1891

1892

__JudyFreeJLW(Pjlw, /* pop1 = */ 2, (Pjpm_t) NULL);

1893

1894

*PPArray = (Pvoid_t) ((Word_t) Pjlwnew | cJL_JAPLEAF_POPU1);

1895

DBGCODE(JudyCheckPop(*PPArray);)

1896

return(1);

1897

1898

} // case cJL_JAPLEAF_POPU2.

1899

1900

#endif // (LOW_POP && JUDYL)

1901

1902

1903

// ****************************************************************************

1904

// JAP LEAF, OTHER SIZE:

1905

//

1906

// Shrink or convert the leaf as necessary. Hysteresis = 0; none is possible.

1907

1908

case cJU_JAPLEAF:

1909

{

1910

JUDYLCODE(Pjv_t Pjv;) // current value area.

1911

JUDYLCODE(Pjv_t Pjvnew;) // value area in new leaf.

1912

Pjlw_t Pjlw = P_JLW(*PPArray); // first word of leaf.

1913

Pjlw_t Pjlwnew; // replacement leaf.

1914

pop1 = Pjlw[0] + 1; // first word of leaf is pop0.

1915

1916

// Delete single (last) Index from array:

1917

1918

if (pop1 == 1)

1919

{

1920

__JudyFreeJLW(Pjlw, /* pop1 = */ 1, (Pjpm_t) NULL);

1921

*PPArray = (Pvoid_t) NULL;

1922

return(1);

1923

}

1924

1925

// Locate Index in compressible leaf:

1926

1927

offset = __JudySearchLeafW(Pjlw + 1, pop1, Index);

1928

assert(offset >= 0); // Index must be valid.

1929

1930

JUDYLCODE(Pjv = JL_LEAFWVALUEAREA(Pjlw, pop1);)

1931

1932

// Delete Index in-place:

1933

//

1934

// Note: "Grow in place from pop1 - 1" is the logical inverse of, "shrink in

1935

// place from pop1." Also, Pjlw points to the count word, so skip that for

1936

// doing the deletion.

1937

1938

if (JU_LEAFWGROWINPLACE(pop1 - 1))

1939

{

1940

JU_DELETEINPLACE(Pjlw + 1, pop1, offset, ignore);

1941

#ifdef JUDYL // also delete from value area:

1942

JU_DELETEINPLACE(Pjv, pop1, offset, ignore);

1943

#endif

1944

DBGCODE(JudyCheckSorted((Pjll_t) (Pjlw + 1), pop1 - 1,

1945

cJU_ROOTSTATE);)

1946

--(Pjlw[0]); // decrement population.

1947

DBGCODE(JudyCheckPop(*PPArray);)

1948

return(1);

1949

}

1950

1951

// Allocate new leaf for use in either case below:

1952

1953

Pjlwnew = __JudyAllocJLW(pop1 - 1);

1954

JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI);

1955

1956

#if (LOW_POP && JUDYL)

1957

// Shrink leaf to a cJL_JAPLEAF_POPU2:

1958

//

1959

// Note: The "3" below is equal to pop1, but faster because it's a constant.

1960

1961

if ((pop1 - 1) == 2)

1962

{

1963

JU_DELETECOPY(Pjlwnew + 0, Pjlw + 1, 3, offset, ignore);

1964

JU_DELETECOPY(Pjlwnew + 2, Pjv, 3, offset, ignore);

1965

DBGCODE(JudyCheckSorted(Pjlwnew, 2, cJU_ROOTSTATE);)

1966

1967

__JudyFreeJLW(Pjlw, pop1, (Pjpm_t) NULL);

1968

1969

*PPArray = (Pvoid_t) ((Word_t) Pjlwnew | cJL_JAPLEAF_POPU2);

1970

DBGCODE(JudyCheckPop(*PPArray);)

1971

return(1);

1972

}

1973

#endif // (LOW_POP && JUDYL)

1974

1975

// Shrink to smaller JAPLEAF:

1976

//

1977

// Note: Skip the first word = pop0 in each leaf.

1978

1979

Pjlwnew[0] = (pop1 - 1) - 1;

1980

JU_DELETECOPY(Pjlwnew + 1, Pjlw + 1, pop1, offset, ignore);

1981

1982

#ifdef JUDYL // also delete from value area:

1983

Pjvnew = JL_LEAFWVALUEAREA(Pjlwnew, pop1 - 1);

1984

JU_DELETECOPY(Pjvnew, Pjv, pop1, offset, ignore);

1985

#endif

1986

DBGCODE(JudyCheckSorted(Pjlwnew + 1, pop1 - 1, cJU_ROOTSTATE);)

1987

1988

__JudyFreeJLW(Pjlw, pop1, (Pjpm_t) NULL);

1989

1990

*PPArray = (Pvoid_t) ((Word_t) Pjlwnew | cJU_JAPLEAF);

1991

DBGCODE(JudyCheckPop(*PPArray);)

1992

return(1);

1993

1994

} // case cJU_JAPLEAF.

1995

1996

1997

// ****************************************************************************

1998

// JAP BRANCH:

1999

//

2000

// Traverse through the JPM to do the deletion unless the population is small

2001

// enough to convert immediately to a JAPLEAF.

2002

2003

case cJU_JAPBRANCH:

2004

{

2005

Pjpm_t Pjpm;

2006

Pjp_t Pjp; // top-level JP to process.

2007

Word_t digit; // in a branch.

2008

JUDYLCODE(Pjv_t Pjv;) // to value area.

2009

Pjlw_t Pjlwnew; // replacement leaf.

2010

DBGCODE(Pjlw_t Pjlwnew_orig;)

2011

2012

Pjpm = P_JPM(*PPArray); // top object in array (tree).

2013

Pjp = &(Pjpm->jpm_JP); // next object (first branch or leaf).

2014

2015

assert(((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_L)

2016

|| ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_B)

2017

|| ((Pjpm->jpm_JP.jp_Type) == cJU_JPBRANCH_U));

2018

2019

2020

// CANNOT COMPRESS TO A JAPLEAF => WALK THE TREE (THE NORMAL CASE):

2021

//

2022

// Hysteresis = 1, that is, do not compress to a leaf the first time it could

2023

// actually be done.

2024

//

2025

// Note: Recursive code in __JudyDelWalk() knows how to collapse a lower-level

2026

// BranchL containing a single JP into the parent JP as a narrow pointer, but

2027

// the code here can't do that for a top-level BranchL. The result can be

2028

// PArray -> JPM -> JAPBranchL containing a single JP. This situation is

2029

// unavoidable because a JPM cannot contain a narrow pointer; the BranchL is

2030

// required in order to hold the top digit decoded, and it does not collapse to

2031

// a JAPLEAF until the population is low enough.

2032

//

2033

// TBD: Should we add a topdigit field to JPMs so they can hold narrow

2034

// pointers?

2035

2036

if ((Pjpm->jpm_Pop0 + 1) > cJU_JAPLEAF_MAXPOP1) // see above.

2037

{

2038

if (__JudyDelWalk(Pjp, Index, cJU_ROOTSTATE, Pjpm) == -1)

2039

{

2040

JU_COPY_ERRNO(PJError, Pjpm);

2041

return(JERRI);

2042

}

2043

2044

--(Pjpm->jpm_Pop0); // success; decrement total population.

2045

DBGCODE(JudyCheckPop(*PPArray);)

2046

return(1);

2047

}

2048

2049

2050

// COMPRESS A BRANCH[LBU] TO A JAPLEAF:

2051

//

2052

// Then start over to delete the Index from the new leaf. In other words,

2053

// "compress and then delete."

2054

2055

assert((Pjpm->jpm_Pop0) + 1 == cJU_JAPLEAF_MAXPOP1);

2056

2057

Pjlwnew = __JudyAllocJLW(cJU_JAPLEAF_MAXPOP1);

2058

JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI);

2059

2060

// Plug leaf into root pointer and set population count:

2061

2062

*PPArray = (Pvoid_t) ((Word_t) Pjlwnew | cJU_JAPLEAF);

2063

#ifdef JUDYL // prepare value area:

2064

Pjv = JL_LEAFWVALUEAREA(Pjlwnew, cJU_JAPLEAF_MAXPOP1);

2065

#endif

2066

*Pjlwnew++ = cJU_JAPLEAF_MAXPOP1 - 1; // set pop0.

2067

DBGCODE(Pjlwnew_orig = Pjlwnew;)

2068

2069

switch (Pjp->jp_Type)

2070

{

2071

2072

2073

// JPBRANCH_L: Copy each JP's indexes to the new JAPLEAF and free the old

2074

// branch:

2075

2076

case cJU_JPBRANCH_L:

2077

{

2078

Pjbl_t PjblRaw = (Pjbl_t) (Pjp->jp_Addr);

2079

Pjbl_t Pjbl = P_JBL(PjblRaw);

2080

2081

for (offset = 0; offset < Pjbl->jbl_NumJPs; ++offset)

2082

{

2083

pop1 = __JudyLeafM1ToLeafW(Pjlwnew, JU_PVALUEPASS

2084

(Pjbl->jbl_jp) + offset,

2085

JU_DIGITTOSTATE(Pjbl->jbl_Expanse[offset],

2086

cJU_BYTESPERWORD),

2087

(Pvoid_t) Pjpm);

2088

Pjlwnew += pop1; // advance through indexes.

2089

JUDYLCODE(Pjv += pop1;) // advance through values.

2090

}

2091

__JudyFreeJBL(PjblRaw, Pjpm);

2092

2093

assert(Pjlwnew == Pjlwnew_orig + cJU_JAPLEAF_MAXPOP1);

2094

break; // delete Index from new JAPLEAF.

2095

}

2096

2097

2098

// JPBRANCH_B: Copy each JP's indexes to the new JAPLEAF and free the old

2099

// branch, including each JP subarray:

2100

2101

case cJU_JPBRANCH_B:

2102

{

2103

Pjbb_t PjbbRaw = (Pjbb_t) (Pjp->jp_Addr);

2104

Pjbb_t Pjbb = P_JBB(PjbbRaw);

2105

Word_t subexp; // current subexpanse number.

2106

BITMAPB_t bitmap; // portion for this subexpanse.

2107

Pjp_t Pjp2Raw; // one subexpanse's subarray.

2108

Pjp_t Pjp2;

2109

2110

for (subexp = 0; subexp < cJU_NUMSUBEXPB; ++subexp)

2111

{

2112

if ((bitmap = JU_JBB_BITMAP(Pjbb, subexp)) == 0)

2113

continue; // skip empty subexpanse.

2114

2115

digit = subexp * cJU_BITSPERSUBEXPB;

2116

Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);

2117

Pjp2 = P_JP(Pjp2Raw);

2118

assert(Pjp2 != (Pjp_t) NULL);

2119

2120

// Walk through bits for all possible sub-subexpanses (digits); increment

2121

// offset for each populated subexpanse; until no more set bits:

2122

2123

for (offset = 0; bitmap != 0; bitmap >>= 1, ++digit)

2124

{

2125

if (! (bitmap & 1)) // skip empty sub-subexpanse.

2126

continue;

2127

2128

pop1 = __JudyLeafM1ToLeafW(Pjlwnew, JU_PVALUEPASS

2129

Pjp2 + offset,

2130

JU_DIGITTOSTATE(digit, cJU_BYTESPERWORD),

2131

(Pvoid_t) Pjpm);

2132

Pjlwnew += pop1; // advance through indexes.

2133

JUDYLCODE(Pjv += pop1;) // advance through values.

2134

++offset;

2135

}

2136

__JudyFreeJBBJP(Pjp2Raw, /* pop1 = */ offset, Pjpm);

2137

}

2138

__JudyFreeJBB(PjbbRaw, Pjpm);

2139

2140

assert(Pjlwnew == Pjlwnew_orig + cJU_JAPLEAF_MAXPOP1);

2141

break; // delete Index from new JAPLEAF.

2142

2143

} // case cJU_JPBRANCH_B.

2144

2145

2146

// JPBRANCH_U: Copy each JP's indexes to the new JAPLEAF and free the old

2147

// branch:

2148

2149

case cJU_JPBRANCH_U:

2150

{

2151

Pjbu_t PjbuRaw = (Pjbu_t) (Pjp->jp_Addr);

2152

Pjbu_t Pjbu = P_JBU(PjbuRaw);

2153

Word_t ldigit; // larger than uint8_t.

2154

2155

for (Pjp = Pjbu->jbu_jp, ldigit = 0;

2156

ldigit < cJU_BRANCHUNUMJPS;

2157

++Pjp, ++ldigit)

2158

{

2159

2160

// Shortcuts, to save a little time for possibly big branches:

2161

2162

if ((Pjp->jp_Type) == cJU_JPNULLMAX) // skip null JP.

2163

continue;

2164

2165

// TBD: Should the following shortcut also be used in BranchL and BranchB

2166

// code?

2167

2168

#ifndef JU_64BIT

2169

if ((Pjp->jp_Type) == cJU_JPIMMED_3_01)

2170

#else

2171

if ((Pjp->jp_Type) == cJU_JPIMMED_7_01)

2172

#endif

2173

{ // single Immed:

2174

*Pjlwnew++ = JU_DIGITTOSTATE(ldigit, cJU_BYTESPERWORD)

2175

| (Pjp->jp_DcdPop0); // rebuild Index.

2176

#ifdef JUDYL

2177

*Pjv++ = Pjp->jp_Addr; // copy value area.

2178

#endif

2179

continue;

2180

}

2181

2182

pop1 = __JudyLeafM1ToLeafW(Pjlwnew, JU_PVALUEPASS

2183

Pjp, JU_DIGITTOSTATE(ldigit, cJU_BYTESPERWORD),

2184

(Pvoid_t) Pjpm);

2185

Pjlwnew += pop1; // advance through indexes.

2186

JUDYLCODE(Pjv += pop1;) // advance through values.

2187

}

2188

__JudyFreeJBU(PjbuRaw, Pjpm);

2189

2190

assert(Pjlwnew == Pjlwnew_orig + cJU_JAPLEAF_MAXPOP1);

2191

break; // delete Index from new JAPLEAF.

2192

2193

} // case cJU_JPBRANCH_U.

2194

2195

2196

// INVALID JP TYPE UNDER A JAPBRANCH:

2197

2198

default: JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);

2199

return(JERRI);

2200

2201

} // end switch on sub-JP type.

2202

2203

DBGCODE(JudyCheckSorted((Pjll_t) Pjlwnew_orig, cJU_JAPLEAF_MAXPOP1,

2204

cJU_ROOTSTATE);)

2205

2206

2207

// FREE JPM (no longer needed):

2208

2209

__JudyFreeJPM(Pjpm, (Pjpm_t) NULL);

2210

DBGCODE(JudyCheckPop(*PPArray);)

2211

goto ContinueDel; // delete Index from new leaf.

2212

2213

} // end case cJU_JAPBRANCH.

2214

2215

2216

// INVALID ROOT (JAP) POINTER:

2217

2218

default:

2219

JUDY1CODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDY1);)

2220

JUDYLCODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDYL);)

2221

return(JERRI);

2222

2223

} // switch on JP type.

2224

2225

/*NOTREACHED*/

2226

2227

} // Judy1Unset() / JudyLDel()