~ubuntu-branches/ubuntu/precise/judy/precise : 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.116 $ $Source: /judy/src/JudyCommon/JudyIns.c $

19

//

20

// Judy1Set() and JudyLIns() functions for Judy1 and JudyL.

21

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

22

//

23

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

24

// returns JU_ERRNO_CORRUPT?

25

26

#if (! (JUDY1 || JUDYL))

27

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

28

#endif

29

30

#ifdef JUDY1

31

#include "Judy1.h"

32

#else

33

#include "JudyL.h"

34

#endif

35

36

#include "JudyPrivate1L.h"

37

38

// Note: Call JudyCheckPop() even before "already inserted" returns, to catch

39

// population errors; see fix in 4.84:

40

41

DBGCODE(extern void JudyCheckPop(Pvoid_t PArray);)

42

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

43

44

#ifdef TRACEJP

45

#include "JudyPrintJP.c"

46

#endif

47

48

49

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

50

//

51

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

52

// are only used here, and exported from Judy*Decascade, which is a separate

53

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

54

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

55

56

#ifdef JUDY1

57

extern int __Judy1CreateBranchB(Pjp_t, Pjp_t, uint8_t *, Word_t, Pvoid_t);

58

extern int __Judy1CreateBranchU(Pjp_t, Pvoid_t);

59

60

#ifndef JU_64BIT

61

extern int __Judy1Cascade1(Pjp_t, Pvoid_t);

62

#endif

63

extern int __Judy1Cascade2(Pjp_t, Pvoid_t);

64

extern int __Judy1Cascade3(Pjp_t, Pvoid_t);

65

#ifdef JU_64BIT

66

extern int __Judy1Cascade4(Pjp_t, Pvoid_t);

67

extern int __Judy1Cascade5(Pjp_t, Pvoid_t);

68

extern int __Judy1Cascade6(Pjp_t, Pvoid_t);

69

extern int __Judy1Cascade7(Pjp_t, Pvoid_t);

70

#endif

71

extern int __Judy1CascadeL(Pjp_t, Pvoid_t);

72

73

extern int __Judy1InsertBranch(Pjp_t Pjp, Word_t Index, Word_t Btype, Pjpm_t);

74

75

#else // JUDYL

76

77

extern int __JudyLCreateBranchB(Pjp_t, Pjp_t, uint8_t *, Word_t, Pvoid_t);

78

extern int __JudyLCreateBranchU(Pjp_t, Pvoid_t);

79

80

extern int __JudyLCascade1(Pjp_t, Pvoid_t);

81

extern int __JudyLCascade2(Pjp_t, Pvoid_t);

82

extern int __JudyLCascade3(Pjp_t, Pvoid_t);

83

#ifdef JU_64BIT

84

extern int __JudyLCascade4(Pjp_t, Pvoid_t);

85

extern int __JudyLCascade5(Pjp_t, Pvoid_t);

86

extern int __JudyLCascade6(Pjp_t, Pvoid_t);

87

extern int __JudyLCascade7(Pjp_t, Pvoid_t);

88

#endif

89

extern int __JudyLCascadeL(Pjp_t, Pvoid_t);

90

91

extern int __JudyLInsertBranch(Pjp_t Pjp, Word_t Index, Word_t Btype, Pjpm_t);

92

#endif

93

94

95

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

96

// MACROS FOR COMMON CODE:

97

//

98

// Check if Index is an outlier to (that is, not a member of) this expanse:

99

//

100

// An outlier is an Index in-the-expanse of the slot containing the pointer,

101

// but not-in-the-expanse of the "narrow" pointer in that slot. (This means

102

// the Dcd part of the Index differs from the equivalent part of jp_DcdPop0.)

103

// Therefore, the remedy is to put a cJU_JPBRANCH_L* between the narrow pointer

104

// and the object to which it points, and add the outlier Index as an Immediate

105

// in the cJU_JPBRANCH_L*. The "trick" is placing the cJU_JPBRANCH_L* at a

106

// Level that is as low as possible. This is determined by counting the digits

107

// in the existing narrow pointer that are the same as the digits in the new

108

// Index (see __JudyInsertBranch()).

109

//

110

// Note: At some high Levels, cJU_DCDMASK() is all zeros => dead code; assume

111

// the compiler optimizes this out.

112

113

#define JU_CHECK_IF_OUTLIER(Pjp, Index, cLevel, Pjpm) \

114

if (JU_DCDNOTMATCHINDEX(Index, (Pjp)->jp_DcdPop0, cLevel)) \

115

return(__JudyInsertBranch(Pjp, Index, cLevel, Pjpm))

116

117

// Check if an Index is already in a leaf or immediate, after calling

118

// __JudySearchLeaf*() to set Offset:

119

//

120

// A non-negative Offset means the Index already exists, so return 0; otherwise

121

// complement Offset to proceed.

122

123

#ifdef JUDY1

124

#define Pjv ignore // placeholder.

125

#define JU_CHECK_IF_EXISTS(Offset,ignore,Pjpm) \

126

{ \

127

if ((Offset) >= 0) return(0); \

128

(Offset) = ~(Offset); \

129

}

130

#else

131

// For JudyL, also set the value area pointer in the Pjpm:

132

133

#define JU_CHECK_IF_EXISTS(Offset,Pjv,Pjpm) \

134

{ \

135

if ((Offset) >= 0) \

136

{ \

137

(Pjpm)->jpm_PValue = (Pjv) + (Offset); \

138

return(0); \

139

} \

140

(Offset) = ~(Offset); \

141

}

142

#endif

143

144

145

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

146

// __ J U D Y I N S W A L K

147

//

148

// Walk the Judy tree to do a set/insert. This is only called internally, and

149

// recursively. Unlike Judy1Test() and JudyLGet(), the extra time required for

150

// recursion should be negligible compared with the total.

151

//

152

// Return -1 for error (details in JPM), 0 for Index already inserted, 1 for

153

// new Index inserted.

154

155

FUNCTION static int __JudyInsWalk(

156

Pjp_t Pjp, // current JP to descend.

157

Word_t Index, // to insert.

158

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

159

{

160

uint8_t digit; // from Index, current offset into a branch.

161

jp_t newJP; // for creating a new Immed JP.

162

Word_t exppop1; // expanse (leaf) population.

163

int retcode; // return codes: -1, 0, 1.

164

165

#ifdef SUBEXPCOUNTS

166

// Pointer to BranchB/U subexpanse counter:

167

//

168

// Note: Very important for performance reasons (avoids cache fills).

169

170

PWord_t PSubExp = (PWord_t) NULL;

171

#endif

172

173

ContinueInsWalk: // for modifying state without recursing.

174

175

#ifdef TRACEJP

176

JudyPrintJP(Pjp, "i", __LINE__);

177

#endif

178

179

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

180

{

181

182

183

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

184

// JPNULL*:

185

//

186

// Convert JP in place from current null type to cJU_JPIMMED_*_01 by

187

// calculating new JP type.

188

189

case cJU_JPNULL1:

190

case cJU_JPNULL2:

191

case cJU_JPNULL3:

192

#ifdef JU_64BIT

193

case cJU_JPNULL4:

194

case cJU_JPNULL5:

195

case cJU_JPNULL6:

196

case cJU_JPNULL7:

197

#endif

198

assert((Pjp->jp_Addr) == 0);

199

200

(Pjp->jp_DcdPop0) = Index; // truncates.

201

// TBD: Make this a macro:

202

(Pjp->jp_Type) = (Pjp->jp_Type) + cJU_JPIMMED_1_01 - cJU_JPNULL1;

203

#ifdef JUDYL

204

// value area is first word of new Immed_01 JP:

205

Pjpm->jpm_PValue = (Pjv_t) (&(Pjp->jp_Addr));

206

#endif

207

return(1);

208

209

210

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

211

// JPBRANCH_L*:

212

//

213

// If the new Index is not an outlier to the branch's expanse, and the branch

214

// should not be converted to uncompressed, extract the digit and record the

215

// Immediate type to create for a new Immed JP, before going to common code.

216

//

217

// Note: JU_CHECK_IF_OUTLIER() is a no-op for BranchB3[7] on 32[64]-bit.

218

219

#define JU_BRANCH_OUTLIER(DIGIT,POP1,cLEVEL,PJP,INDEX,PJPM) \

220

JU_CHECK_IF_OUTLIER(PJP, INDEX, cLEVEL, PJPM); \

221

(DIGIT) = JU_DIGITATSTATE(INDEX, cLEVEL); \

222

(POP1) = JU_JPBRANCH_POP0((PJP)->jp_DcdPop0, cLEVEL)

223

224

case cJU_JPBRANCH_L2:

225

JU_BRANCH_OUTLIER(digit, exppop1, 2, Pjp, Index, Pjpm);

226

goto JudyBranchL;

227

228

case cJU_JPBRANCH_L3:

229

JU_BRANCH_OUTLIER(digit, exppop1, 3, Pjp, Index, Pjpm);

230

goto JudyBranchL;

231

232

#ifdef JU_64BIT

233

case cJU_JPBRANCH_L4:

234

JU_BRANCH_OUTLIER(digit, exppop1, 4, Pjp, Index, Pjpm);

235

goto JudyBranchL;

236

237

case cJU_JPBRANCH_L5:

238

JU_BRANCH_OUTLIER(digit, exppop1, 5, Pjp, Index, Pjpm);

239

goto JudyBranchL;

240

241

case cJU_JPBRANCH_L6:

242

JU_BRANCH_OUTLIER(digit, exppop1, 6, Pjp, Index, Pjpm);

243

goto JudyBranchL;

244

245

case cJU_JPBRANCH_L7:

246

JU_BRANCH_OUTLIER(digit, exppop1, 7, Pjp, Index, Pjpm);

247

goto JudyBranchL;

248

#endif

249

250

// Similar to common code above, but no outlier check is needed, and the Immed

251

// type depends on the word size:

252

253

case cJU_JPBRANCH_L:

254

{

255

Pjbl_t PjblRaw; // pointer to old linear branch.

256

Pjbl_t Pjbl;

257

Pjbu_t PjbuRaw; // pointer to new uncompressed branch.

258

Pjbu_t Pjbu;

259

Word_t numJPs; // number of JPs = populated expanses.

260

int offset; // in branch.

261

262

digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);

263

exppop1 = Pjpm->jpm_Pop0;

264

265

// fall through:

266

267

// COMMON CODE FOR LINEAR BRANCHES:

268

//

269

// Come here with digit and exppop1 already set.

270

271

JudyBranchL:

272

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

273

Pjbl = P_JBL(PjblRaw);

274

275

// If population under this branch greater than:

276

277

if (exppop1 > JU_BRANCHL_MAX_POP)

278

goto ConvertBranchLtoU;

279

280

numJPs = Pjbl->jbl_NumJPs;

281

282

if ((numJPs == 0) || (numJPs > cJU_BRANCHLMAXJPS))

283

{

284

JU_SET_ERRNO_NONNULL(Pjpm, JU_ERRNO_CORRUPT);

285

return(-1);

286

}

287

288

// Search for a match to the digit:

289

290

offset = __JudySearchLeaf1((Pjll_t) (Pjbl->jbl_Expanse), numJPs,

291

digit);

292

293

// If Index is found, offset is into an array of 1..cJU_BRANCHLMAXJPS JPs:

294

295

if (offset >= 0)

296

{

297

Pjp = (Pjbl->jbl_jp) + offset; // address of next JP.

298

break; // continue walk.

299

}

300

301

// Expanse is missing (not populated) for the passed Index, so insert an Immed

302

// -- if there's room:

303

304

if (numJPs < cJU_BRANCHLMAXJPS)

305

{

306

offset = ~offset; // insertion offset.

307

308

newJP.jp_Addr = 0; // initial value (mainly for JudyL).

309

newJP.jp_DcdPop0 = Index; // truncates.

310

newJP.jp_Type = Pjp->jp_Type +

311

cJU_JPIMMED_1_01-cJU_JPBRANCH_L2;

312

313

JU_INSERTINPLACE(Pjbl->jbl_Expanse, numJPs, offset, digit);

314

JU_INSERTINPLACE(Pjbl->jbl_jp, numJPs, offset, newJP);

315

316

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

317

numJPs + 1, /* IndexSize = */ 1);)

318

++(Pjbl->jbl_NumJPs);

319

#ifdef JUDYL

320

// value area is first word of new Immed 01 JP:

321

Pjpm->jpm_PValue = (Pjv_t) ((Pjbl->jbl_jp) + offset);

322

#endif

323

return(1);

324

}

325

326

327

// MAXED OUT LINEAR BRANCH, CONVERT TO A BITMAP BRANCH, THEN INSERT:

328

//

329

// Copy the linear branch to a bitmap branch.

330

//

331

// TBD: Consider renaming __JudyCreateBranchB() to __JudyConvertBranchLtoB().

332

333

assert((numJPs) <= cJU_BRANCHLMAXJPS);

334

335

if (__JudyCreateBranchB(Pjp, Pjbl->jbl_jp, Pjbl->jbl_Expanse,

336

numJPs, Pjpm) == -1)

337

{

338

return(-1);

339

}

340

341

// Convert jp_Type from linear branch to equivalent bitmap branch:

342

343

(Pjp->jp_Type) += cJU_JPBRANCH_B - cJU_JPBRANCH_L;

344

345

__JudyFreeJBL(PjblRaw, Pjpm); // free old BranchL.

346

347

// Having changed branch types, now do the insert in the new branch type:

348

349

goto ContinueInsWalk;

350

351

352

// OPPORTUNISTICALLY CONVERT FROM BRANCHL TO BRANCHU:

353

//

354

// Memory efficiency is no object because the branch's pop1 is large enough, so

355

// speed up array access. Come here with PjblRaw set. Note: This is goto

356

// code because the previous block used to fall through into it as well, but no

357

// longer.

358

359

ConvertBranchLtoU:

360

361

// Allocate memory for an uncompressed branch:

362

363

if ((PjbuRaw = __JudyAllocJBU(Pjpm)) == (Pjbu_t) NULL)

364

return(-1);

365

Pjbu = P_JBU(PjbuRaw);

366

367

// Set the proper NULL type for most of the uncompressed branch's JPs:

368

369

newJP.jp_Addr = 0;

370

newJP.jp_DcdPop0 = 0;

371

newJP.jp_Type = Pjp->jp_Type - cJU_JPBRANCH_L2 + cJU_JPNULL1;

372

373

// Initialize: Pre-set uncompressed branch to mostly JPNULL*s:

374

375

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

376

Pjbu->jbu_jp[numJPs] = newJP;

377

378

// Copy JPs from linear branch to uncompressed branch:

379

380

{

381

#ifdef SUBEXPCOUNTS

382

Word_t popmask = cJU_POP0MASK((Pjp->jp_Type)

383

- cJU_JPBRANCH_L2 - 2);

384

385

for (numJPs = 0; numJPs < cJU_NUMSUBEXPU; ++numJPs)

386

Pjbu->jbu_subPop1[numJPs] = 0;

387

#endif

388

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

389

{

390

Pjp_t Pjp1 = &(Pjbl->jbl_jp[numJPs]);

391

offset = Pjbl->jbl_Expanse[numJPs];

392

Pjbu->jbu_jp[offset] = *Pjp1;

393

#ifdef SUBEXPCOUNTS

394

Pjbu->jbu_subPop1[offset/cJU_NUMSUBEXPU] +=

395

(Pjp1->jp_DcdPop0) & popmask + 1;

396

#endif

397

}

398

}

399

__JudyFreeJBL(PjblRaw, Pjpm); // free old BranchL.

400

401

// Plug new values into parent JP:

402

403

Pjp->jp_Addr = (Word_t) PjbuRaw;

404

Pjp->jp_Type += cJU_JPBRANCH_U - cJU_JPBRANCH_L; // to BranchU.

405

406

// Save global population of last BranchU conversion:

407

408

Pjpm->jpm_LastUPop0 = Pjpm->jpm_Pop0;

409

goto ContinueInsWalk;

410

411

} // case cJU_JPBRANCH_L.

412

413

414

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

415

// JPBRANCH_B*:

416

//

417

// If the new Index is not an outlier to the branch's expanse, extract the

418

// digit and record the Immediate type to create for a new Immed JP, before

419

// going to common code.

420

//

421

// Note: JU_CHECK_IF_OUTLIER() is a no-op for BranchB3[7] on 32[64]-bit.

422

423

case cJU_JPBRANCH_B2:

424

JU_BRANCH_OUTLIER(digit, exppop1, 2, Pjp, Index, Pjpm);

425

goto JudyBranchB;

426

427

case cJU_JPBRANCH_B3:

428

JU_BRANCH_OUTLIER(digit, exppop1, 3, Pjp, Index, Pjpm);

429

goto JudyBranchB;

430

431

#ifdef JU_64BIT

432

case cJU_JPBRANCH_B4:

433

JU_BRANCH_OUTLIER(digit, exppop1, 4, Pjp, Index, Pjpm);

434

goto JudyBranchB;

435

436

case cJU_JPBRANCH_B5:

437

JU_BRANCH_OUTLIER(digit, exppop1, 5, Pjp, Index, Pjpm);

438

goto JudyBranchB;

439

440

case cJU_JPBRANCH_B6:

441

JU_BRANCH_OUTLIER(digit, exppop1, 6, Pjp, Index, Pjpm);

442

goto JudyBranchB;

443

444

case cJU_JPBRANCH_B7:

445

JU_BRANCH_OUTLIER(digit, exppop1, 7, Pjp, Index, Pjpm);

446

goto JudyBranchB;

447

#endif

448

449

case cJU_JPBRANCH_B:

450

{

451

Pjbb_t Pjbb; // pointer to bitmap branch.

452

Pjbb_t PjbbRaw; // pointer to bitmap branch.

453

Pjp_t Pjp2Raw; // 1 of N arrays of JPs.

454

Pjp_t Pjp2; // 1 of N arrays of JPs.

455

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

456

BITMAPB_t bitmap; // for one subexpanse.

457

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

458

Word_t numJPs; // number of JPs = populated expanses.

459

int offset; // in bitmap branch.

460

461

// Similar to common code above, but no outlier check is needed, and the Immed

462

// type depends on the word size:

463

464

digit = JU_DIGITATSTATE(Index, cJU_ROOTSTATE);

465

exppop1 = Pjpm->jpm_Pop0;

466

467

// fall through:

468

469

470

// COMMON CODE FOR BITMAP BRANCHES:

471

//

472

// Come here with digit and exppop1 already set.

473

474

JudyBranchB:

475

476

// If population increment is greater than.. (300):

477

478

if ((Pjpm->jpm_Pop0 - Pjpm->jpm_LastUPop0) > JU_BTOU_POP_INCREMENT)

479

{

480

481

// If total population of array is greater than.. (750):

482

483

if (Pjpm->jpm_Pop0 > JU_BRANCHB_MAX_POP)

484

{

485

486

// If population under the branch is greater than.. (135):

487

488

if (exppop1 > JU_BRANCHB_MIN_POP)

489

{

490

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

491

492

// Save global population of last BranchU conversion:

493

494

Pjpm->jpm_LastUPop0 = Pjpm->jpm_Pop0;

495

496

goto ContinueInsWalk;

497

}

498

}

499

}

500

501

// CONTINUE TO USE BRANCHB:

502

//

503

// Get pointer to bitmap branch (JBB):

504

505

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

506

Pjbb = P_JBB(PjbbRaw);

507

508

// Form the Int32 offset, and Bit offset values:

509

//

510

// 8 bit Decode | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |

511

// |SubExpanse | Bit offset |

512

//

513

// Get the 1 of 8 expanses from digit, Bits 5..7 = 1 of 8, and get the 32-bit

514

// word that may have a bit set:

515

516

subexp = digit / cJU_BITSPERSUBEXPB;

517

bitmap = JU_JBB_BITMAP(Pjbb, subexp);

518

519

Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);

520

Pjp2 = P_JP(Pjp2Raw);

521

522

// Get the bit position that represents the desired expanse, and get the offset

523

// into the array of JPs for the JP that matches the bit.

524

525

bitmask = JU_BITPOSMASKB(digit);

526

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

527

528

// If JP is already in this expanse, get Pjp and continue the walk:

529

530

if (bitmap & bitmask)

531

{

532

#ifdef SUBEXPCOUNTS

533

PSubExp = &(Pjbb->jbb_Counts[subexp]); // ptr to subexp counts.

534

#endif

535

Pjp = Pjp2 + offset;

536

break; // continue walk.

537

}

538

539

540

// ADD NEW EXPANSE FOR NEW INDEX:

541

//

542

// The new expanse always an cJU_JPIMMED_*_01 containing just the new Index, so

543

// finish setting up an Immed JP.

544

545

newJP.jp_Addr = 0; // initial value (for JudyL).

546

newJP.jp_DcdPop0 = Index; // truncates.

547

newJP.jp_Type = Pjp->jp_Type + cJU_JPIMMED_1_01-cJU_JPBRANCH_B2;

548

549

// Get 1 of the 8 JP arrays and calculate number of JPs in subexpanse array:

550

551

Pjp2Raw = JU_JBB_PJP(Pjbb, subexp);

552

Pjp2 = P_JP(Pjp2Raw);

553

numJPs = __JudyCountBitsB(bitmap);

554

555

// Expand branch JP subarray in-place:

556

557

if (JU_BRANCHBJPGROWINPLACE(numJPs))

558

{

559

assert(numJPs > 0);

560

JU_INSERTINPLACE(Pjp2, numJPs, offset, newJP);

561

#ifdef JUDYL

562

// value area is first word of new Immed 01 JP:

563

Pjpm->jpm_PValue = (Pjv_t) (Pjp2 + offset);

564

#endif

565

}

566

567

// No room, allocate a bigger bitmap branch JP subarray:

568

569

else

570

{

571

Pjp_t PjpnewRaw;

572

Pjp_t Pjpnew;

573

574

if ((PjpnewRaw = __JudyAllocJBBJP(numJPs + 1, Pjpm)) == 0)

575

return(-1);

576

Pjpnew = P_JP(PjpnewRaw);

577

578

// If there was an old JP array, then copy it, insert the new Immed JP, and

579

// free the old array:

580

581

if (numJPs)

582

{

583

JU_INSERTCOPY(Pjpnew, Pjp2, numJPs, offset, newJP);

584

__JudyFreeJBBJP(Pjp2Raw, numJPs, Pjpm);

585

#ifdef JUDYL

586

// value area is first word of new Immed 01 JP:

587

Pjpm->jpm_PValue = (Pjv_t) (Pjpnew + offset);

588

#endif

589

}

590

591

// New JP subarray; point to cJU_JPIMMED_*_01 and place it:

592

593

else

594

{

595

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

596

Pjp = Pjpnew;

597

*Pjp = newJP; // copy to new memory.

598

#ifdef JUDYL

599

// value area is first word of new Immed 01 JP:

600

Pjpm->jpm_PValue = (Pjv_t) (&(Pjp->jp_Addr));

601

#endif

602

}

603

604

// Place new JP subarray in BranchB:

605

606

JU_JBB_PJP(Pjbb, subexp) = PjpnewRaw;

607

608

} // else

609

610

// Set the new Index's bit:

611

612

JU_JBB_BITMAP(Pjbb, subexp) |= bitmask;

613

614

return(1);

615

616

} // case

617

618

619

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

620

// JPBRANCH_U*:

621

//

622

// Just drop through the JP for the correct digit. If the JP turns out to be a

623

// JPNULL*, that's OK, the memory is already allocated, and the next walk

624

// simply places an Immed in it.

625

//

626

#ifdef SUBEXPCOUNTS

627

#define JU_GETSUBEXP(PSubExp,Pjbu,Digit) \

628

(PSubExp) = &((Pjbu)->jbu_subPop1[(Digit) / cJU_NUMSUBEXPU])

629

#else

630

#define JU_GETSUBEXP(PSubExp,Pjbu,Digit) // null.

631

#endif

632

633

#define JU_JBU_PJP_SUBEXP(Pjp,PSubExp,Index,Level) \

634

{ \

635

uint8_t _digit = JU_DIGITATSTATE(Index, Level); \

636

Pjbu_t _Pjbu = P_JBU((Pjp)->jp_Addr); \

637

(Pjp) = &(_Pjbu->jbu_jp[_digit]); \

638

JU_GETSUBEXP(PSubExp, _Pjbu, _digit); \

639

}

640

641

case cJU_JPBRANCH_U2:

642

JU_CHECK_IF_OUTLIER(Pjp, Index, 2, Pjpm);

643

JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 2);

644

break;

645

646

#ifdef JU_64BIT

647

case cJU_JPBRANCH_U3:

648

JU_CHECK_IF_OUTLIER(Pjp, Index, 3, Pjpm);

649

JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 3);

650

break;

651

652

case cJU_JPBRANCH_U4:

653

JU_CHECK_IF_OUTLIER(Pjp, Index, 4, Pjpm);

654

JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 4);

655

break;

656

657

case cJU_JPBRANCH_U5:

658

JU_CHECK_IF_OUTLIER(Pjp, Index, 5, Pjpm);

659

JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 5);

660

break;

661

662

case cJU_JPBRANCH_U6:

663

JU_CHECK_IF_OUTLIER(Pjp, Index, 6, Pjpm);

664

JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 6);

665

break;

666

667

case cJU_JPBRANCH_U7:

668

JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 7);

669

#else

670

case cJU_JPBRANCH_U3:

671

JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, 3);

672

#endif

673

break;

674

675

case cJU_JPBRANCH_U:

676

JU_JBU_PJP_SUBEXP(Pjp, PSubExp, Index, cJU_ROOTSTATE);

677

break;

678

679

680

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

681

// JPLEAF*:

682

//

683

// COMMON CODE FRAGMENTS TO MINIMIZE REDUNDANCY BELOW:

684

//

685

// These are necessary to support performance by function and loop unrolling

686

// while avoiding huge amounts of nearly identical code.

687

//

688

// Prepare to handle a linear leaf: Check for an outlier; set pop1 and pointer

689

// to leaf:

690

691

#ifdef JUDY1

692

#define JU_LEAFVALUE(Pjv) // null.

693

#define JU_LEAFPREPVALUE(Pjv, ValueArea) // null.

694

#else

695

#define JU_LEAFVALUE(Pjv) Pjv_t Pjv

696

#define JU_LEAFPREPVALUE(Pjv, ValueArea) (Pjv) = ValueArea(Pleaf, exppop1)

697

#endif

698

699

#define JU_LEAFPREP(cIS,Type,MaxPop1,ValueArea) \

700

Pjll_t PjllRaw; \

701

Type Pleaf; /* specific type */ \

702

int offset; \

703

JU_LEAFVALUE(Pjv); \

704

\

705

JU_CHECK_IF_OUTLIER(Pjp, Index, cIS, Pjpm); \

706

\

707

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

708

assert(exppop1 <= (MaxPop1)); \

709

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

710

Pleaf = (Type) P_JLL(PjllRaw); \

711

JU_LEAFPREPVALUE(Pjv, ValueArea)

712

713

// Add to, or grow, a linear leaf: Find Index position; if the Index is

714

// absent, if there's room in the leaf, insert the Index [and value of 0] in

715

// place, otherwise grow the leaf:

716

//

717

// Note: These insertions always take place with whole words, using

718

// JU_INSERTINPLACE() or JU_INSERTCOPY().

719

720

#ifdef JUDY1

721

#define JU_LEAFGROWVALUEADD(Pjv,ExpPop1,Offset) // null.

722

#else

723

#define JU_LEAFGROWVALUEADD(Pjv,ExpPop1,Offset) \

724

JU_INSERTINPLACE(Pjv, ExpPop1, Offset, 0); \

725

Pjpm->jpm_PValue = (Pjv) + (Offset)

726

#endif

727

728

#ifdef JUDY1

729

#define JU_LEAFGROWVALUENEW(ValueArea,Pjv,ExpPop1,Offset) // null.

730

#else

731

#define JU_LEAFGROWVALUENEW(ValueArea,Pjv,ExpPop1,Offset) \

732

{ \

733

Pjv_t Pjvnew = ValueArea(Pleafnew, (ExpPop1) + 1); \

734

JU_INSERTCOPY(Pjvnew, Pjv, ExpPop1, Offset, 0); \

735

Pjpm->jpm_PValue = (Pjvnew) + (Offset); \

736

}

737

#endif

738

739

#define JU_LEAFGROW(cIS,Type,MaxPop1,Search,ValueArea,GrowInPlace, \

740

InsertInPlace,InsertCopy,Alloc,Free) \

741

\

742

offset = Search(Pleaf, exppop1, Index); \

743

JU_CHECK_IF_EXISTS(offset, Pjv, Pjpm); \

744

\

745

if (GrowInPlace(exppop1)) /* add to current leaf */ \

746

{ \

747

InsertInPlace(Pleaf, exppop1, offset, Index); \

748

JU_LEAFGROWVALUEADD(Pjv, exppop1, offset); \

749

DBGCODE(JudyCheckSorted((Pjll_t) Pleaf, exppop1 + 1, cIS);) \

750

return(1); \

751

} \

752

\

753

if (exppop1 < (MaxPop1)) /* grow to new leaf */ \

754

{ \

755

Pjll_t PjllnewRaw; \

756

Type Pleafnew; \

757

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

758

Pleafnew = (Type) P_JLL(PjllnewRaw); \

759

InsertCopy(Pleafnew, Pleaf, exppop1, offset, Index); \

760

JU_LEAFGROWVALUENEW(ValueArea, Pjv, exppop1, offset); \

761

DBGCODE(JudyCheckSorted((Pjll_t) Pleafnew, exppop1 + 1, cIS);) \

762

Free(PjllRaw, exppop1, Pjpm); \

763

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

764

return(1); \

765

} \

766

assert(exppop1 == (MaxPop1))

767

768

// Handle linear leaf overflow (cascade): Splay or compress into smaller

769

// leaves:

770

771

#define JU_LEAFCASCADE(MaxPop1,Cascade,Free) \

772

if (Cascade(Pjp, Pjpm) == -1) return(-1); \

773

Free(PjllRaw, MaxPop1, Pjpm); \

774

goto ContinueInsWalk

775

776

// Wrapper around all of the above:

777

778

#define JU_LEAFSET(cIS,Type,MaxPop1,Search,GrowInPlace,InsertInPlace, \

779

InsertCopy,Cascade,Alloc,Free,ValueArea) \

780

{ \

781

JU_LEAFPREP(cIS,Type,MaxPop1,ValueArea); \

782

JU_LEAFGROW(cIS,Type,MaxPop1,Search,ValueArea,GrowInPlace, \

783

InsertInPlace,InsertCopy,Alloc,Free); \

784

JU_LEAFCASCADE(MaxPop1,Cascade,Free); \

785

}

786

787

// END OF MACROS; LEAFL CASES START HERE:

788

//

789

// 64-bit Judy1 does not have 1-byte leaves:

790

791

#if (JUDYL || (! JU_64BIT))

792

793

case cJU_JPLEAF1:

794

795

JU_LEAFSET(1, uint8_t *, cJU_LEAF1_MAXPOP1, __JudySearchLeaf1,

796

JU_LEAF1GROWINPLACE, JU_INSERTINPLACE, JU_INSERTCOPY,

797

__JudyCascade1, __JudyAllocJLL1, __JudyFreeJLL1,

798

JL_LEAF1VALUEAREA);

799

800

#endif // (JUDYL || ! JU_64BIT)

801

802

case cJU_JPLEAF2:

803

804

JU_LEAFSET(2, uint16_t *, cJU_LEAF2_MAXPOP1, __JudySearchLeaf2,

805

JU_LEAF2GROWINPLACE, JU_INSERTINPLACE, JU_INSERTCOPY,

806

__JudyCascade2, __JudyAllocJLL2, __JudyFreeJLL2,

807

JL_LEAF2VALUEAREA);

808

809

case cJU_JPLEAF3:

810

811

JU_LEAFSET(3, uint8_t *, cJU_LEAF3_MAXPOP1, __JudySearchLeaf3,

812

JU_LEAF3GROWINPLACE, JU_INSERTINPLACE3, JU_INSERTCOPY3,

813

__JudyCascade3, __JudyAllocJLL3, __JudyFreeJLL3,

814

JL_LEAF3VALUEAREA);

815

816

#ifdef JU_64BIT

817

case cJU_JPLEAF4:

818

819

JU_LEAFSET(4, uint32_t *, cJU_LEAF4_MAXPOP1, __JudySearchLeaf4,

820

JU_LEAF4GROWINPLACE, JU_INSERTINPLACE, JU_INSERTCOPY,

821

__JudyCascade4, __JudyAllocJLL4, __JudyFreeJLL4,

822

JL_LEAF4VALUEAREA);

823

824

case cJU_JPLEAF5:

825

826

JU_LEAFSET(5, uint8_t *, cJU_LEAF5_MAXPOP1, __JudySearchLeaf5,

827

JU_LEAF5GROWINPLACE, JU_INSERTINPLACE5, JU_INSERTCOPY5,

828

__JudyCascade5, __JudyAllocJLL5, __JudyFreeJLL5,

829

JL_LEAF5VALUEAREA);

830

831

case cJU_JPLEAF6:

832

833

JU_LEAFSET(6, uint8_t *, cJU_LEAF6_MAXPOP1, __JudySearchLeaf6,

834

JU_LEAF6GROWINPLACE, JU_INSERTINPLACE6, JU_INSERTCOPY6,

835

__JudyCascade6, __JudyAllocJLL6, __JudyFreeJLL6,

836

JL_LEAF6VALUEAREA);

837

838

case cJU_JPLEAF7:

839

840

JU_LEAFSET(7, uint8_t *, cJU_LEAF7_MAXPOP1, __JudySearchLeaf7,

841

JU_LEAF7GROWINPLACE, JU_INSERTINPLACE7, JU_INSERTCOPY7,

842

__JudyCascade7, __JudyAllocJLL7, __JudyFreeJLL7,

843

JL_LEAF7VALUEAREA);

844

#endif // JU_64BIT

845

846

847

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

848

// JPLEAF_B1:

849

//

850

// 8 bit Decode | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |

851

// |SubExpanse | Bit offset |

852

//

853

// Note: For JudyL, values are stored in 8 subexpanses, each a linear word

854

// array of up to 32 values each.

855

856

case cJU_JPLEAF_B1:

857

{

858

#ifdef JUDYL

859

Pjv_t PjvRaw; // pointer to value part of the leaf.

860

Pjv_t Pjv; // pointer to value part of the leaf.

861

Pjv_t PjvnewRaw; // new value area.

862

Pjv_t Pjvnew; // new value area.

863

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

864

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

865

BITMAPL_t bitmap; // for one subexpanse.

866

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

867

int offset; // of index in value area.

868

#endif

869

870

JU_CHECK_IF_OUTLIER(Pjp, Index, 1, Pjpm);

871

872

#ifdef JUDY1

873

874

// If Index (bit) is already set, return now:

875

876

if (JU_BITMAPTESTL(P_JLB(Pjp->jp_Addr), Index)) return(0);

877

878

// If bitmap is not full, set the new Index's bit; otherwise convert to a Full:

879

880

if ((exppop1 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0) + 1)

881

< cJU_JPFULLPOPU1_POP0)

882

{

883

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

884

}

885

else

886

{

887

__JudyFreeJLB1((Pjlb_t) (Pjp->jp_Addr), Pjpm); // free LeafB1.

888

Pjp->jp_Type = cJ1_JPFULLPOPU1;

889

Pjp->jp_Addr = 0;

890

}

891

892

#else // JUDYL

893

894

// This is very different from Judy1 because of the need to return a value area

895

// even for an existing Index, or manage the value area for a new Index, and

896

// because JudyL has no Full type:

897

898

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

899

900

digit = JU_DIGITATSTATE(Index, 1);

901

Pjlb = P_JLB(Pjp->jp_Addr);

902

903

// Prepare additional values:

904

905

subexp = digit / cJU_BITSPERSUBEXPL; // which subexpanse.

906

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

907

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

908

Pjv = P_JV(PjvRaw); // corresponding values.

909

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

910

offset = __JudyCountBitsL(bitmap & (bitmask - 1)); // of Index.

911

912

// If Index already exists, get value pointer and exit:

913

914

if (bitmap & bitmask)

915

{

916

assert(Pjv);

917

Pjpm->jpm_PValue = Pjv + offset; // existing value.

918

return(0);

919

}

920

921

// Get the total bits set = expanse population of Value area:

922

923

exppop1 = __JudyCountBitsL(bitmap);

924

925

// If the value area can grow in place, do it:

926

927

if (JL_LEAFVGROWINPLACE(exppop1))

928

{

929

JU_INSERTINPLACE(Pjv, exppop1, offset, 0);

930

JU_JLB_BITMAP(Pjlb, subexp) |= bitmask; // set Index's bit.

931

Pjpm->jpm_PValue = Pjv + offset; // new value area.

932

return(1);

933

}

934

935

// Increase size of value area:

936

937

if ((PjvnewRaw = __JudyLAllocJV(exppop1 + 1, Pjpm))

938

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

939

Pjvnew = P_JV(PjvnewRaw);

940

941

if (exppop1) // have existing value area.

942

{

943

assert(Pjv);

944

JU_INSERTCOPY(Pjvnew, Pjv, exppop1, offset, 0);

945

Pjpm->jpm_PValue = Pjvnew + offset;

946

__JudyLFreeJV(PjvRaw, exppop1, Pjpm); // free old values.

947

}

948

else // first index, new value area:

949

{

950

Pjpm->jpm_PValue = Pjvnew;

951

*(Pjpm->jpm_PValue) = 0;

952

}

953

954

// Set bit for new Index and place new leaf value area in bitmap:

955

956

JU_JLB_BITMAP(Pjlb, subexp) |= bitmask;

957

JL_JLB_PVALUE(Pjlb, subexp) = PjvnewRaw;

958

959

#endif // JUDYL

960

961

return(1);

962

963

} // case

964

965

966

#ifdef JUDY1

967

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

968

// JPFULLPOPU1:

969

//

970

// If Index is not an outlier, then by definition it's already set.

971

972

case cJ1_JPFULLPOPU1:

973

974

JU_CHECK_IF_OUTLIER(Pjp, Index, 1, Pjpm);

975

return(0);

976

#endif

977

978

979

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

980

// JPIMMED*:

981

//

982

// This is some of the most complex code in Judy considering Judy1 versus JudyL

983

// and 32-bit versus 64-bit variations. The following comments attempt to make

984

// this clearer.

985

//

986

// Of the 2 words in a JP, for immediate indexes Judy1 can use 2 words - 1 byte

987

// = 7 [15] bytes, but JudyL can only use 1 word - 1 byte = 3 [7] bytes because

988

// the other word is needed for a value area or a pointer to a value area.

989

//

990

// For both Judy1 and JudyL, cJU_JPIMMED_*_01 indexes are in word 2; otherwise

991

// for Judy1 only, a list of 2 or more indexes starts in word 1. JudyL keeps

992

// the list in word 2 because word 1 is a pointer (to a LeafV, that is, a leaf

993

// containing only values). Furthermore, cJU_JPIMMED_*_01 indexes are stored

994

// all-but-first-byte in jp_DcdPop0, not just the Index Size's bytes.

995

//

996

// TBD: This can be confusing because Doug didn't use data structures for it.

997

// Instead he often directly accesses Pjp for the first word and jp_DcdPop0 for

998

// the second word. It would be nice to use data structs, starting with

999

// jp_1Index and jp_LIndex where possible.

1000

//

1001

// Maximum Immed JP types for Judy1/JudyL, depending on Index Size (cIS):

1002

//

1003

// 32-bit 64-bit

1004

//

1005

// bytes: 7/ 3 15/ 7 (Judy1/JudyL)

1006

//

1007

// cIS

1008

// 1_ 07/03 15/07 (as in: cJ1_JPIMMED_1_07)

1009

// 2_ 03/01 07/03

1010

// 3_ 02/01 05/02

1011

// 4_ 03/01

1012

// 5_ 03/01

1013

// 6_ 02/01

1014

// 7_ 02/01

1015

//

1016

// State transitions while inserting an Index, matching the above table:

1017

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

1018

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

1019

//

1020

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

1021

// |

1022

// | JUDY1 || JU_64BIT JUDY1 && JU_64BIT

1023

// V

1024

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

1025

// 2_01 => [ 2_02 => 2_03 => [ 2_04..07 => ]] Leaf2

1026

// 3_01 => [ 3_02 => [ 3_03..05 => ]] Leaf3

1027

// JU_64BIT only:

1028

// 4_01 => [[ 4_02..03 => ]] Leaf4

1029

// 5_01 => [[ 5_02..03 => ]] Leaf5

1030

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

1031

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

1032

//

1033

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

1034

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

1035

1036

1037

// COMMON CODE FRAGMENTS TO MINIMIZE REDUNDANCY BELOW:

1038

//

1039

// These are necessary to support performance by function and loop unrolling

1040

// while avoiding huge amounts of nearly identical code.

1041

//

1042

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

1043

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

1044

// big ifdefs follow. However, even in the following ifdef'd code, use cJU_*,

1045

// JU_*, and Judy*() instead of cJ1_* / cJL_*, J1_* / JL_*, and

1046

// Judy1*()/JudyL*(), for minimum diffs.

1047

//

1048

// Handle growth of cJU_JPIMMED_*_01 to cJU_JPIMMED_*_02, for an even or odd

1049

// Index Size (cIS), given oldIndex, Index, and Pjll in the context:

1050

//

1051

// Put oldIndex and Index in their proper order. For odd indexes, must copy

1052

// bytes.

1053

1054

#ifdef JUDY1

1055

1056

#define JU_IMMSET_01_COPY_EVEN(ignore1,ignore2) \

1057

if (oldIndex < Index) { Pjll[0] = oldIndex; Pjll[1] = Index; } \

1058

else { Pjll[0] = Index; Pjll[1] = oldIndex; }

1059

1060

#define JU_IMMSET_01_COPY_ODD(cIS,CopyWord) \

1061

if (oldIndex < Index) \

1062

{ \

1063

CopyWord(Pjll + 0, oldIndex); \

1064

CopyWord(Pjll + (cIS), Index); \

1065

} \

1066

else \

1067

{ \

1068

CopyWord(Pjll + 0, Index); \

1069

CopyWord(Pjll + (cIS), oldIndex); \

1070

}

1071

1072

// The "real" *_01 Copy macro:

1073

//

1074

// Trim the high byte off Index, look for a match with the old Index, and if

1075

// none, insert the new Index in the leaf in the correct place, given Pjp and

1076

// Index in the context.

1077

//

1078

// Note: A single immediate index lives in the jp_DcdPop0 field, but two or

1079

// more reside starting at Pjp->jp_1Index.

1080

1081

#define JU_IMMSET_01_COPY(cIS,LeafType,NewJPType,Copy,CopyWord) \

1082

{ \

1083

LeafType Pjll; \

1084

Word_t oldIndex = Pjp->jp_DcdPop0; \

1085

\

1086

Index = JU_TRIMTODCDSIZE(Index); \

1087

if (oldIndex == Index) return(0); \

1088

\

1089

Pjll = (LeafType) (Pjp->jp_1Index); \

1090

Copy(cIS,CopyWord); \

1091

DBGCODE(JudyCheckSorted(Pjll, 2, cIS);) \

1092

\

1093

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

1094

return(1); \

1095

}

1096

1097

#else // JUDYL

1098

1099

// Variations to also handle value areas; see comments above:

1100

//

1101

// For JudyL, Pjv (start of value area) and oldValue are also in the context;

1102

// leave Pjv set to the value area for Index.

1103

1104

#define JU_IMMSET_01_COPY_EVEN(cIS,CopyWord) \

1105

if (oldIndex < Index) \

1106

{ \

1107

Pjll[0] = oldIndex; \

1108

Pjv [0] = oldValue; \

1109

Pjll[1] = Index; \

1110

++Pjv; \

1111

} \

1112

else \

1113

{ \

1114

Pjll[0] = Index; \

1115

Pjll[1] = oldIndex; \

1116

Pjv [1] = oldValue; \

1117

}

1118

1119

#define JU_IMMSET_01_COPY_ODD(cIS,CopyWord) \

1120

if (oldIndex < Index) \

1121

{ \

1122

CopyWord(Pjll + 0, oldIndex); \

1123

CopyWord(Pjll + (cIS), Index); \

1124

Pjv[0] = oldValue; \

1125

++Pjv; \

1126

} \

1127

else \

1128

{ \

1129

CopyWord(Pjll + 0, Index); \

1130

CopyWord(Pjll + (cIS), oldIndex); \

1131

Pjv[1] = oldValue; \

1132

}

1133

1134

// The old value area is in the first word (*Pjp), and Pjv and Pjpm are also in

1135

// the context. Also, unlike Judy1, indexes remain in word 2 (jp_LIndex),

1136

// meaning insert-in-place rather than copy.

1137

//

1138

// Return jpm_PValue pointing to Index's value area. If Index is new, allocate

1139

// a 2-value-leaf and attach it to the JP.

1140

1141

#define JU_IMMSET_01_COPY(cIS,LeafType,NewJPType,Copy,CopyWord) \

1142

{ \

1143

LeafType Pjll; \

1144

Word_t oldIndex = Pjp->jp_DcdPop0; \

1145

Word_t oldValue; \

1146

Pjv_t PjvRaw; \

1147

Pjv_t Pjv; \

1148

\

1149

Index = JU_TRIMTODCDSIZE(Index); \

1150

\

1151

if (oldIndex == Index) \

1152

{ \

1153

Pjpm->jpm_PValue = (Pjv_t) Pjp; \

1154

return(0); \

1155

} \

1156

\

1157

if ((PjvRaw = __JudyLAllocJV(2, Pjpm)) == (Pjv_t) NULL) \

1158

return(-1); \

1159

Pjv = P_JV(PjvRaw); \

1160

\

1161

oldValue = Pjp->jp_Addr; \

1162

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

1163

Pjll = (LeafType) (Pjp->jp_LIndex); \

1164

\

1165

Copy(cIS,CopyWord); \

1166

DBGCODE(JudyCheckSorted(Pjll, 2, cIS);) \

1167

\

1168

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

1169

*Pjv = 0; \

1170

Pjpm->jpm_PValue = Pjv; \

1171

return(1); \

1172

}

1173

1174

// The following is a unique mix of JU_IMMSET_01() and JU_IMMSETCASCADE() for

1175

// going from cJU_JPIMMED_*_01 directly to a cJU_JPLEAF* for JudyL:

1176

//

1177

// If Index is not already set, allocate a leaf, copy the old and new indexes

1178

// into it, clear and return the new value area, and modify the current JP.

1179

// Note that jp_DcdPop is set to a pop0 of 0 for now, and incremented later.

1180

1181

#define JU_IMMSET_01_CASCADE(cIS,LeafType,NewJPType,ValueArea, \

1182

Copy,CopyWord,Alloc) \

1183

{ \

1184

LeafType PjllRaw; \

1185

LeafType Pjll; \

1186

Word_t oldIndex = Pjp->jp_DcdPop0; \

1187

Word_t oldValue; \

1188

Pjv_t Pjv; \

1189

\

1190

Index = JU_TRIMTODCDSIZE(Index); \

1191

\

1192

if (oldIndex == Index) \

1193

{ \

1194

Pjpm->jpm_PValue = (Pjv_t) (&(Pjp->jp_Addr)); \

1195

return(0); \

1196

} \

1197

\

1198

if ((PjllRaw = (LeafType) Alloc(2, Pjpm)) == (LeafType) NULL) \

1199

return(-1); \

1200

Pjll = (LeafType) P_JLL(PjllRaw); \

1201

Pjv = ValueArea(Pjll, 2); \

1202

\

1203

oldValue = Pjp->jp_Addr; \

1204

\

1205

Copy(cIS,CopyWord); \

1206

DBGCODE(JudyCheckSorted(Pjll, 2, cIS);) \

1207

\

1208

*Pjv = 0; \

1209

Pjpm->jpm_PValue = Pjv; \

1210

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

1211

(Pjp->jp_DcdPop0) = (Index & cJU_DCDMASK(cIS)); /* pop0 = 0 */ \

1212

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

1213

\

1214

return(1); \

1215

}

1216

1217

#endif // JUDYL

1218

1219

// Handle growth of cJU_JPIMMED_*_[02..15]:

1220

1221

#ifdef JUDY1

1222

1223

// Insert an Index into an immediate JP that has room for more, if the Index is

1224

// not already present; given Pjp, Index, exppop1, Pjv, and Pjpm in the

1225

// context:

1226

//

1227

// Note: Use this only when the JP format doesn't change, that is, going from

1228

// cJU_JPIMMED_X_0Y to cJU_JPIMMED_X_0Z, where X >= 2 and Y+1 = Z.

1229

//

1230

// Note: Incrementing jp_Type is how to increase the Index population.

1231

1232

#define JU_IMMSETINPLACE(cIS,LeafType,BaseJPType_02,Search,InsertInPlace) \

1233

{ \

1234

LeafType Pjll; \

1235

int offset; \

1236

\

1237

exppop1 = (Pjp->jp_Type) - (BaseJPType_02) + 2; \

1238

offset = Search((Pjll_t) (Pjp->jp_1Index), exppop1, Index); \

1239

\

1240

JU_CHECK_IF_EXISTS(offset, ignore, Pjpm); \

1241

\

1242

Pjll = (LeafType) (Pjp->jp_1Index); \

1243

InsertInPlace(Pjll, exppop1, offset, Index); \

1244

DBGCODE(JudyCheckSorted(Pjll, exppop1 + 1, cIS);) \

1245

++(Pjp->jp_Type); \

1246

return(1); \

1247

}

1248

1249

// Insert an Index into an immediate JP that has no room for more:

1250

//

1251

// If the Index is not already present, do a cascade (to a leaf); given Pjp,

1252

// Index, Pjv, and Pjpm in the context.

1253

1254

#define JU_IMMSETCASCADE(cIS,OldPop1,LeafType,NewJPType, \

1255

ignore,Search,InsertCopy,Alloc) \

1256

{ \

1257

Pjll_t PjllRaw; \

1258

Pjll_t Pjll; \

1259

int offset; \

1260

\

1261

offset = Search((Pjll_t) (Pjp->jp_1Index), (OldPop1), Index); \

1262

JU_CHECK_IF_EXISTS(offset, ignore, Pjpm); \

1263

\

1264

if ((PjllRaw = Alloc((OldPop1) + 1, Pjpm)) == 0) return(-1); \

1265

Pjll = P_JLL(PjllRaw); \

1266

\

1267

InsertCopy((LeafType) Pjll, (LeafType) (Pjp->jp_1Index), \

1268

OldPop1, offset, Index); \

1269

DBGCODE(JudyCheckSorted(Pjll, (OldPop1) + 1, cIS);) \

1270

\

1271

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

1272

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

1273

(Pjp->jp_DcdPop0) = (Index & cJU_DCDMASK(cIS)) + (OldPop1) - 1; \

1274

return(1); \

1275

}

1276

1277

#else // JUDYL

1278

1279

// Variations to also handle value areas; see comments above:

1280

//

1281

// For JudyL, Pjv (start of value area) is also in the context.

1282

//

1283

// TBD: This code makes a true but weak assumption that a JudyL 32-bit 2-index

1284

// value area must be copied to a new 3-index value area. AND it doesn't know

1285

// anything about JudyL 64-bit cases (cJU_JPIMMED_1_0[3-7] only) where the

1286

// value area can grow in place! However, this should not break it, just slow

1287

// it down.

1288

1289

#define JU_IMMSETINPLACE(cIS,LeafType,BaseJPType_02,Search,InsertInPlace) \

1290

{ \

1291

LeafType Pleaf; \

1292

int offset; \

1293

Pjv_t PjvRaw; \

1294

Pjv_t Pjv; \

1295

Pjv_t PjvnewRaw; \

1296

Pjv_t Pjvnew; \

1297

\

1298

exppop1 = (Pjp->jp_Type) - (BaseJPType_02) + 2; \

1299

offset = Search((Pjll_t) (Pjp->jp_LIndex), exppop1, Index); \

1300

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

1301

Pjv = P_JV(PjvRaw); \

1302

\

1303

JU_CHECK_IF_EXISTS(offset, Pjv, Pjpm); \

1304

\

1305

if ((PjvnewRaw = __JudyLAllocJV(exppop1 + 1, Pjpm)) \

1306

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

1307

Pjvnew = P_JV(PjvnewRaw); \

1308

\

1309

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

1310

\

1311

InsertInPlace(Pleaf, exppop1, offset, Index); \

1312

/* see TBD above about this: */ \

1313

JU_INSERTCOPY(Pjvnew, Pjv, exppop1, offset, 0); \

1314

DBGCODE(JudyCheckSorted(Pleaf, exppop1 + 1, cIS);) \

1315

__JudyLFreeJV(PjvRaw, exppop1, Pjpm); \

1316

Pjp->jp_Addr = (Word_t) PjvnewRaw; \

1317

Pjpm->jpm_PValue = Pjvnew + offset; \

1318

\

1319

++(Pjp->jp_Type); \

1320

return(1); \

1321

}

1322

1323

#define JU_IMMSETCASCADE(cIS,OldPop1,LeafType,NewJPType, \

1324

ValueArea,Search,InsertCopy,Alloc) \

1325

{ \

1326

Pjll_t PjllRaw; \

1327

Pjll_t Pjll; \

1328

int offset; \

1329

Pjv_t PjvRaw; \

1330

Pjv_t Pjv; \

1331

Pjv_t Pjvnew; \

1332

\

1333

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

1334

Pjv = P_JV(PjvRaw); \

1335

offset = Search((Pjll_t) (Pjp->jp_LIndex), (OldPop1), Index); \

1336

JU_CHECK_IF_EXISTS(offset, Pjv, Pjpm); \

1337

\

1338

if ((PjllRaw = Alloc((OldPop1) + 1, Pjpm)) == 0) \

1339

return(-1); \

1340

Pjll = P_JLL(PjllRaw); \

1341

InsertCopy((LeafType) Pjll, (LeafType) (Pjp->jp_LIndex), \

1342

OldPop1, offset, Index); \

1343

DBGCODE(JudyCheckSorted(Pjll, (OldPop1) + 1, cIS);) \

1344

\

1345

Pjvnew = ValueArea(Pjll, (OldPop1) + 1); \

1346

JU_INSERTCOPY(Pjvnew, Pjv, OldPop1, offset, 0); \

1347

__JudyLFreeJV(PjvRaw, (OldPop1), Pjpm); \

1348

Pjpm->jpm_PValue = Pjvnew + offset; \

1349

\

1350

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

1351

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

1352

(Pjp->jp_DcdPop0) = (Index & cJU_DCDMASK(cIS)) + (OldPop1) - 1; \

1353

return(1); \

1354

}

1355

#endif // JUDYL

1356

1357

// Common convenience/shorthand wrappers around JU_IMMSET_01_COPY() for

1358

// even/odd index sizes:

1359

1360

#define JU_IMMSET_01( cIS, LeafType, NewJPType) \

1361

JU_IMMSET_01_COPY(cIS, LeafType, NewJPType, JU_IMMSET_01_COPY_EVEN, \

1362

ignore)

1363

1364

#define JU_IMMSET_01_ODD( cIS, NewJPType, CopyWord) \

1365

JU_IMMSET_01_COPY(cIS, uint8_t *, NewJPType, JU_IMMSET_01_COPY_ODD, \

1366

CopyWord)

1367

1368

1369

// END OF MACROS; IMMED CASES START HERE:

1370

1371

// cJU_JPIMMED_*_01 cases:

1372

//

1373

// 1_01 always leads to 1_02:

1374

//

1375

// (1_01 => 1_02 => 1_03 => [ 1_04 => ... => 1_07 => [ 1_08..15 => ]] LeafL)

1376

1377

case cJU_JPIMMED_1_01: JU_IMMSET_01(1, uint8_t *, cJU_JPIMMED_1_02);

1378

1379

// 2_01 leads to 2_02, and 3_01 leads to 3_02, except for JudyL 32-bit, where

1380

// they lead to a leaf:

1381

//

1382

// (2_01 => [ 2_02 => 2_03 => [ 2_04..07 => ]] LeafL)

1383

// (3_01 => [ 3_02 => [ 3_03..05 => ]] LeafL)

1384

1385

#if (JUDY1 || JU_64BIT)

1386

case cJU_JPIMMED_2_01: JU_IMMSET_01(2, uint16_t *, cJU_JPIMMED_2_02);

1387

case cJU_JPIMMED_3_01: JU_IMMSET_01_ODD (3, cJU_JPIMMED_3_02,

1388

JU_COPY3_LONG_TO_PINDEX);

1389

#else

1390

case cJU_JPIMMED_2_01:

1391

JU_IMMSET_01_CASCADE(2, uint16_t *, cJU_JPLEAF2, JL_LEAF2VALUEAREA,

1392

JU_IMMSET_01_COPY_EVEN, ignore,

1393

__JudyAllocJLL2);

1394

case cJU_JPIMMED_3_01:

1395

JU_IMMSET_01_CASCADE(3, uint8_t *, cJU_JPLEAF3, JL_LEAF3VALUEAREA,

1396

JU_IMMSET_01_COPY_ODD,

1397

JU_COPY3_LONG_TO_PINDEX, __JudyAllocJLL3);

1398

#endif

1399

1400

#ifdef JU_64BIT

1401

1402

// [4-7]_01 lead to [4-7]_02 for Judy1, and to leaves for JudyL:

1403

//

1404

// (4_01 => [[ 4_02..03 => ]] LeafL)

1405

// (5_01 => [[ 5_02..03 => ]] LeafL)

1406

// (6_01 => [[ 6_02 => ]] LeafL)

1407

// (7_01 => [[ 7_02 => ]] LeafL)

1408

1409

#ifdef JUDY1

1410

case cJU_JPIMMED_4_01: JU_IMMSET_01(4, uint32_t *, cJ1_JPIMMED_4_02);

1411

case cJU_JPIMMED_5_01: JU_IMMSET_01_ODD(5, cJ1_JPIMMED_5_02,

1412

JU_COPY5_LONG_TO_PINDEX);

1413

case cJU_JPIMMED_6_01: JU_IMMSET_01_ODD(6, cJ1_JPIMMED_6_02,

1414

JU_COPY6_LONG_TO_PINDEX);

1415

case cJU_JPIMMED_7_01: JU_IMMSET_01_ODD(7, cJ1_JPIMMED_7_02,

1416

JU_COPY7_LONG_TO_PINDEX);

1417

#else // JUDYL

1418

case cJU_JPIMMED_4_01:

1419

JU_IMMSET_01_CASCADE(4, uint32_t *, cJU_JPLEAF4, JL_LEAF4VALUEAREA,

1420

JU_IMMSET_01_COPY_EVEN, ignore,

1421

__JudyAllocJLL4);

1422

case cJU_JPIMMED_5_01:

1423

JU_IMMSET_01_CASCADE(5, uint8_t *, cJU_JPLEAF5, JL_LEAF5VALUEAREA,

1424

JU_IMMSET_01_COPY_ODD,

1425

JU_COPY5_LONG_TO_PINDEX, __JudyAllocJLL5);

1426

case cJU_JPIMMED_6_01:

1427

JU_IMMSET_01_CASCADE(6, uint8_t *, cJU_JPLEAF6, JL_LEAF6VALUEAREA,

1428

JU_IMMSET_01_COPY_ODD,

1429

JU_COPY6_LONG_TO_PINDEX, __JudyAllocJLL6);

1430

case cJU_JPIMMED_7_01:

1431

JU_IMMSET_01_CASCADE(7, uint8_t *, cJU_JPLEAF7, JL_LEAF7VALUEAREA,

1432

JU_IMMSET_01_COPY_ODD,

1433

JU_COPY7_LONG_TO_PINDEX, __JudyAllocJLL7);

1434

#endif // JUDYL

1435

#endif // JU_64BIT

1436

1437

// cJU_JPIMMED_1_* cases that can grow in place:

1438

//

1439

// (1_01 => 1_02 => 1_03 => [ 1_04 => ... => 1_07 => [ 1_08..15 => ]] LeafL)

1440

1441

case cJU_JPIMMED_1_02:

1442

#if (JUDY1 || JU_64BIT)

1443

case cJU_JPIMMED_1_03:

1444

case cJU_JPIMMED_1_04:

1445

case cJU_JPIMMED_1_05:

1446

case cJU_JPIMMED_1_06:

1447

#endif

1448

#if (JUDY1 && JU_64BIT)

1449

case cJU_JPIMMED_1_07:

1450

case cJ1_JPIMMED_1_08:

1451

case cJ1_JPIMMED_1_09:

1452

case cJ1_JPIMMED_1_10:

1453

case cJ1_JPIMMED_1_11:

1454

case cJ1_JPIMMED_1_12:

1455

case cJ1_JPIMMED_1_13:

1456

case cJ1_JPIMMED_1_14:

1457

#endif

1458

JU_IMMSETINPLACE(1, uint8_t *, cJU_JPIMMED_1_02, __JudySearchLeaf1,

1459

JU_INSERTINPLACE);

1460

1461

// cJU_JPIMMED_1_* cases that must cascade:

1462

//

1463

// (1_01 => 1_02 => 1_03 => [ 1_04 => ... => 1_07 => [ 1_08..15 => ]] LeafL)

1464

1465

#if (JUDYL && (! JU_64BIT))

1466

case cJU_JPIMMED_1_03:

1467

JU_IMMSETCASCADE(1, 3, uint8_t *, cJU_JPLEAF1, JL_LEAF1VALUEAREA,

1468

__JudySearchLeaf1, JU_INSERTCOPY,

1469

__JudyAllocJLL1);

1470

#endif

1471

#if (JUDY1 && (! JU_64BIT))

1472

case cJU_JPIMMED_1_07:

1473

JU_IMMSETCASCADE(1, 7, uint8_t *, cJU_JPLEAF1, ignore,

1474

__JudySearchLeaf1, JU_INSERTCOPY,

1475

__JudyAllocJLL1);

1476

1477

#endif

1478

#if (JUDYL && JU_64BIT)

1479

case cJU_JPIMMED_1_07:

1480

JU_IMMSETCASCADE(1, 7, uint8_t *, cJU_JPLEAF1, JL_LEAF1VALUEAREA,

1481

__JudySearchLeaf1, JU_INSERTCOPY,

1482

__JudyAllocJLL1);

1483

1484

#endif

1485

#if (JUDY1 && JU_64BIT)

1486

// Special case, as described above, go directly from Immed to LeafB1:

1487

1488

case cJ1_JPIMMED_1_15:

1489

{

1490

int offset;

1491

Pjlb_t PjlbRaw;

1492

Pjlb_t Pjlb;

1493

1494

offset = __JudySearchLeaf1((Pjll_t) Pjp->jp_1Index, 15, Index);

1495

1496

JU_CHECK_IF_EXISTS(offset, ignore, Pjpm);

1497

1498

// Create a bitmap leaf (special case for Judy1 64-bit only, see usage): Set

1499

// new Index in bitmap, copy an Immed1_15 to the bitmap, and set the parent JP

1500

// EXCEPT jp_DcdPop0, leaving any followup to the caller:

1501

1502

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

1503

return(-1);

1504

Pjlb = P_JLB(PjlbRaw);

1505

1506

JU_BITMAPSETL(Pjlb, Index);

1507

1508

for (offset = 0; offset < 15; ++offset)

1509

JU_BITMAPSETL(Pjlb, Pjp->jp_1Index[offset]);

1510

1511

Pjp->jp_Addr = (Word_t) PjlbRaw;

1512

Pjp->jp_Type = cJU_JPLEAF_B1;

1513

1514

// Set jp_DcdPop0 including the current pop0; incremented later:

1515

Pjp->jp_DcdPop0 = (Index & cJU_DCDMASK(1)) + 15 - 1;

1516

return(1);

1517

}

1518

#endif

1519

1520

// cJU_JPIMMED_[2..7]_[02..15] cases that grow in place or cascade:

1521

//

1522

// (2_01 => [ 2_02 => 2_03 => [ 2_04..07 => ]] LeafL)

1523

1524

#if (JUDY1 || JU_64BIT)

1525

case cJU_JPIMMED_2_02:

1526

#endif

1527

#if (JUDY1 && JU_64BIT)

1528

case cJU_JPIMMED_2_03:

1529

case cJ1_JPIMMED_2_04:

1530

case cJ1_JPIMMED_2_05:

1531

case cJ1_JPIMMED_2_06:

1532

#endif

1533

#if (JUDY1 || JU_64BIT)

1534

JU_IMMSETINPLACE(2, uint16_t *, cJU_JPIMMED_2_02, __JudySearchLeaf2,

1535

JU_INSERTINPLACE);

1536

#endif

1537

1538

#undef OLDPOP1

1539

#if ((JUDY1 && (! JU_64BIT)) || (JUDYL && JU_64BIT))

1540

case cJU_JPIMMED_2_03:

1541

#define OLDPOP1 3

1542

#endif

1543

#if (JUDY1 && JU_64BIT)

1544

case cJ1_JPIMMED_2_07:

1545

#define OLDPOP1 7

1546

#endif

1547

#if (JUDY1 || JU_64BIT)

1548

JU_IMMSETCASCADE(2, OLDPOP1, uint16_t *, cJU_JPLEAF2,

1549

JL_LEAF2VALUEAREA, __JudySearchLeaf2,

1550

JU_INSERTCOPY, __JudyAllocJLL2);

1551

#endif

1552

1553

// (3_01 => [ 3_02 => [ 3_03..05 => ]] LeafL)

1554

1555

#if (JUDY1 && JU_64BIT)

1556

case cJU_JPIMMED_3_02:

1557

case cJ1_JPIMMED_3_03:

1558

case cJ1_JPIMMED_3_04:

1559

1560

JU_IMMSETINPLACE(3, uint8_t *, cJU_JPIMMED_3_02, __JudySearchLeaf3,

1561

JU_INSERTINPLACE3);

1562

#endif

1563

1564

#undef OLDPOP1

1565

#if ((JUDY1 && (! JU_64BIT)) || (JUDYL && JU_64BIT))

1566

case cJU_JPIMMED_3_02:

1567

#define OLDPOP1 2

1568

#endif

1569

#if (JUDY1 && JU_64BIT)

1570

case cJ1_JPIMMED_3_05:

1571

#define OLDPOP1 5

1572

#endif

1573

#if (JUDY1 || JU_64BIT)

1574

JU_IMMSETCASCADE(3, OLDPOP1, uint8_t *, cJU_JPLEAF3,

1575

JL_LEAF3VALUEAREA, __JudySearchLeaf3,

1576

JU_INSERTCOPY3, __JudyAllocJLL3);

1577

#endif

1578

1579

#if (JUDY1 && JU_64BIT)

1580

1581

// (4_01 => [[ 4_02..03 => ]] LeafL)

1582

1583

case cJ1_JPIMMED_4_02:

1584

1585

JU_IMMSETINPLACE(4, uint32_t *, cJ1_JPIMMED_4_02, __JudySearchLeaf4,

1586

JU_INSERTINPLACE);

1587

1588

case cJ1_JPIMMED_4_03:

1589

1590

JU_IMMSETCASCADE(4, 3, uint32_t *, cJU_JPLEAF4, ignore,

1591

__JudySearchLeaf4, JU_INSERTCOPY,

1592

__JudyAllocJLL4);

1593

1594

// (5_01 => [[ 5_02..03 => ]] LeafL)

1595

1596

case cJ1_JPIMMED_5_02:

1597

1598

JU_IMMSETINPLACE(5, uint8_t *, cJ1_JPIMMED_5_02, __JudySearchLeaf5,

1599

JU_INSERTINPLACE5);

1600

1601

case cJ1_JPIMMED_5_03:

1602

1603

JU_IMMSETCASCADE(5, 3, uint8_t *, cJU_JPLEAF5, ignore,

1604

__JudySearchLeaf5, JU_INSERTCOPY5,

1605

__JudyAllocJLL5);

1606

1607

// (6_01 => [[ 6_02 => ]] LeafL)

1608

1609

case cJ1_JPIMMED_6_02:

1610

1611

JU_IMMSETCASCADE(6, 2, uint8_t *, cJU_JPLEAF6, ignore,

1612

__JudySearchLeaf6, JU_INSERTCOPY6,

1613

__JudyAllocJLL6);

1614

1615

// (7_01 => [[ 7_02 => ]] LeafL)

1616

1617

case cJ1_JPIMMED_7_02:

1618

1619

JU_IMMSETCASCADE(7, 2, uint8_t *, cJU_JPLEAF7, ignore,

1620

__JudySearchLeaf7, JU_INSERTCOPY7,

1621

__JudyAllocJLL7);

1622

1623

#endif // (JUDY1 && JU_64BIT)

1624

1625

1626

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

1627

// INVALID JP TYPE:

1628

1629

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

1630

1631

} // switch on JP type

1632

1633

{

1634

1635

#ifdef SUBEXPCOUNTS

1636

1637

// This code might seem strange here. However it saves some memory read time

1638

// during insert (~70nS) because a pipelined processor does not need to "stall"

1639

// waiting for the memory read to complete. Hope the compiler is not too smart

1640

// or dumb and moves the code down to where it looks like it belongs (below a

1641

// few lines).

1642

1643

Word_t SubExpCount = 0; // current subexpanse counter.

1644

1645

if (PSubExp != (PWord_t) NULL) // only if BranchB/U.

1646

SubExpCount = PSubExp[0];

1647

#endif

1648

1649

// PROCESS JP -- RECURSIVELY:

1650

//

1651

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

1652

// at this Level.

1653

1654

retcode = __JudyInsWalk(Pjp, Index, Pjpm);

1655

1656

// Successful insert, increment JP and subexpanse count:

1657

1658

if (((Pjp->jp_Type) < cJU_JPIMMED_1_01) && (retcode == 1))

1659

{

1660

#ifdef SUBEXPCOUNTS

1661

1662

// Note: Pjp must be a pointer to a BranchB/U:

1663

1664

if (PSubExp != (PWord_t) NULL) PSubExp[0] = SubExpCount + 1;

1665

#endif

1666

++(Pjp->jp_DcdPop0);

1667

}

1668

}

1669

return(retcode);

1670

1671

} // __JudyInsWalk()

1672

1673

1674

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

1675

// J U D Y 1 S E T

1676

// J U D Y L I N S

1677

//

1678

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

1679

1680

#ifdef JUDY1

1681

FUNCTION int Judy1Set(

1682

#else

1683

FUNCTION PPvoid_t JudyLIns(

1684

#endif

1685

PPvoid_t PPArray, // in which to insert.

1686

Word_t Index, // to insert.

1687

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

1688

{

1689

#ifdef JUDY1

1690

#define Pjv ignore // placeholders for macros.

1691

#define Pjvnew ignore

1692

#else

1693

Pjv_t Pjv; // value area in old leaf.

1694

Pjv_t Pjvnew; // value area in new leaf.

1695

#endif

1696

Pjpm_t Pjpm; // array-global info.

1697

int offset; // position in which to store new Index.

1698

1699

1700

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

1701

1702

if (PPArray == (PPvoid_t) NULL)

1703

{

1704

JU_SET_ERRNO(PJError, JU_ERRNO_NULLPPARRAY);

1705

JUDY1CODE(return(JERRI );)

1706

JUDYLCODE(return(PPJERR);)

1707

}

1708

1709

1710

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

1711

// PROCESS TOP LEVEL "JAP" BRANCHES AND LEAVES:

1712

1713

switch (JAPTYPE(*PPArray))

1714

{

1715

1716

1717

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

1718

// JAPNULL (EMPTY ARRAY): BUILD A JAP LEAF WITH ONE INDEX:

1719

1720

case cJU_JAPNULL:

1721

{

1722

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

1723

Pjlw_t Pjlwnew;

1724

1725

if (Pjlw != (Pjlw_t) NULL) goto NotJudyArray;

1726

1727

// A valid empty array (null pointer), so create an array of population == 1:

1728

1729

Pjlwnew = __JudyAllocJLW(1);

1730

JUDY1CODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI );)

1731

JUDYLCODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, PPJERR);)

1732

1733

#if (LOW_POP && JUDYL)

1734

1735

Pjlwnew[0] = Index;

1736

Pjlwnew[1] = 0; // value area.

1737

1738

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

1739

return((PPvoid_t) (Pjlwnew + 1));

1740

1741

#else // Both JUDY1 and JUDYL without LOW_POP

1742

1743

Pjlwnew[0] = 1 - 1; // pop0 = 0.

1744

Pjlwnew[1] = Index;

1745

1746

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

1747

DBGCODE(JudyCheckPop(*PPArray);)

1748

1749

JUDY1CODE(return(1); )

1750

JUDYLCODE(Pjlwnew[2] = 0; ) // value area.

1751

JUDYLCODE(return((PPvoid_t) (Pjlwnew + 2)); )

1752

1753

} // cJU_JAPNULL

1754

1755

#endif // Both JUDY1 and JUDYL without LOW_POP

1756

1757

1758

#if (LOW_POP && JUDYL)

1759

1760

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

1761

// JAPLEAF_POPU1:

1762

//

1763

// TBD: It is still debatable whether it is faster to have POPU1 and POPU2

1764

// types. It needs to be measured. This is a lot of fuss for a 1 and 2

1765

// element arrays. -- Doug

1766

//

1767

// First check if Index is already inserted

1768

1769

case cJL_JAPLEAF_POPU1:

1770

{

1771

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

1772

Pjlw_t Pjlwnew;

1773

1774

if (Pjlw[0] == Index)

1775

{

1776

DBGCODE(JudyCheckPop(*PPArray);)

1777

return((PPvoid_t) (Pjlw + 1));

1778

}

1779

1780

// Obtain memory for new, larger JAP leaf, and populate it:

1781

1782

Pjlwnew = __JudyAllocJLW(2);

1783

JU_CHECKALLOC(Pjlw_t, Pjlwnew, PPJERR);

1784

1785

// Do a fast copy/insert in sorted order:

1786

//

1787

// Note: CI2() is shorthand.

1788

1789

#define CI2(Offset,i0,i1,v0,v1) \

1790

{ \

1791

offset = (Offset); \

1792

Pjlwnew[0] = (i0); \

1793

Pjlwnew[1] = (i1); \

1794

Pjvnew [0] = (v0); \

1795

Pjvnew [1] = (v1); \

1796

}

1797

1798

Pjv = JL_LEAFWVALUEAREA(Pjlw, 1);

1799

Pjvnew = JL_LEAFWVALUEAREA(Pjlwnew, 2);

1800

1801

if (Index < Pjlw[0]) CI2(0, Index, Pjlw[0], 0, Pjv[0])

1802

else CI2(1, Pjlw[0], Index, Pjv[0], 0)

1803

1804

// Free old leaf and set new leaf type in root pointer:

1805

1806

__JudyFreeJLW(Pjlw, 1, NULL);

1807

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

1808

1809

DBGCODE(JudyCheckPop(*PPArray);)

1810

return((PPvoid_t) (Pjvnew + offset));

1811

1812

} //cJL_JAPLEAF_POPU1

1813

1814

1815

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

1816

// JAPLEAF_POPU2:

1817

//

1818

// First check if Index is already inserted:

1819

//

1820

case cJL_JAPLEAF_POPU2:

1821

{

1822

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

1823

Pjlw_t Pjlwnew;

1824

1825

if (Pjlw[0] == Index)

1826

{

1827

DBGCODE(JudyCheckPop(*PPArray);)

1828

return((PPvoid_t) (Pjlw + 0 + 2));

1829

}

1830

if (Pjlw[1] == Index)

1831

{

1832

DBGCODE(JudyCheckPop(*PPArray);)

1833

return((PPvoid_t) (Pjlw + 1 + 2));

1834

}

1835

1836

// Obtain memory for new, larger JAP leaf, and populate it:

1837

1838

Pjlwnew = __JudyAllocJLW(3);

1839

JU_CHECKALLOC(Pjlw_t, Pjlwnew, PPJERR);

1840

1841

Pjlwnew[0] = 3 - 1; // pop0 = 2.

1842

1843

// Do a fast copy/insert in sorted order:

1844

//

1845

// Note: CI3() is shorthand.

1846

1847

1848

#define CI3(Offset,i0,i1,i2,v0,v1,v2) \

1849

{ \

1850

offset = (Offset); \

1851

Pjlwnew[1] = (i0); \

1852

Pjlwnew[2] = (i1); \

1853

Pjlwnew[3] = (i2); \

1854

Pjvnew [0] = (v0); \

1855

Pjvnew [1] = (v1); \

1856

Pjvnew [2] = (v2); \

1857

}

1858

1859

Pjv = JL_LEAFWVALUEAREA(Pjlw, 2);

1860

Pjvnew = JL_LEAFWVALUEAREA(Pjlwnew, 3);

1861

1862

if (Index < Pjlw[0])

1863

CI3(0, Index, Pjlw[0], Pjlw[1], 0, Pjv[0], Pjv[1])

1864

else if (Index < Pjlw[1])

1865

CI3(1, Pjlw[0], Index, Pjlw[1], Pjv[0], 0, Pjv[1])

1866

else

1867

CI3(2, Pjlw[0], Pjlw[1], Index, Pjv[0], Pjv[1], 0)

1868

1869

// Free old leaf and set new leaf type in root pointer:

1870

1871

__JudyFreeJLW(Pjlw, 2, NULL);

1872

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

1873

1874

DBGCODE(JudyCheckPop(*PPArray);)

1875

return((PPvoid_t) (Pjvnew + offset));

1876

1877

} // cJL_JAPLEAF_POPU2

1878

1879

#endif // JUDYL && LOW_POP

1880

1881

1882

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

1883

// JAPLEAF, OTHER SIZE:

1884

1885

case cJU_JAPLEAF:

1886

{

1887

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

1888

Pjlw_t Pjlwnew;

1889

Word_t pop1 = Pjlw[0] + 1;

1890

assert(pop1 <= cJU_JAPLEAF_MAXPOP1);

1891

1892

#ifdef JUDYL

1893

Pjv = JL_LEAFWVALUEAREA(Pjlw, pop1);

1894

#endif

1895

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

1896

1897

if (offset >= 0) // index is already valid:

1898

{

1899

DBGCODE(JudyCheckPop(*PPArray);)

1900

JUDY1CODE(return(0); )

1901

JUDYLCODE(return((PPvoid_t) (Pjv + offset)); )

1902

}

1903

1904

offset = ~offset;

1905

1906

// Insert index in cases where no new memory is needed:

1907

1908

if (JU_LEAFWGROWINPLACE(pop1))

1909

{

1910

++Pjlw[0]; // increase population.

1911

1912

JU_INSERTINPLACE(Pjlw + 1, pop1, offset, Index);

1913

#ifdef JUDYL

1914

JU_INSERTINPLACE(Pjv, pop1, offset, 0);

1915

#endif

1916

DBGCODE(JudyCheckPop(*PPArray);)

1917

DBGCODE(JudyCheckSorted(Pjlw + 1, pop1 + 1, cJU_ROOTSTATE);)

1918

1919

JUDY1CODE(return(1); )

1920

JUDYLCODE(return((PPvoid_t) (Pjv + offset)); )

1921

}

1922

1923

// Insert index into a new, larger leaf:

1924

1925

if (pop1 < cJU_JAPLEAF_MAXPOP1) // can grow to a larger leaf.

1926

{

1927

Pjlwnew = __JudyAllocJLW(pop1 + 1);

1928

JUDY1CODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, JERRI );)

1929

JUDYLCODE(JU_CHECKALLOC(Pjlw_t, Pjlwnew, PPJERR);)

1930

1931

Pjlwnew[0] = pop1; // set pop0 in new leaf.

1932

1933

JU_INSERTCOPY(Pjlwnew + 1, Pjlw + 1, pop1, offset, Index);

1934

#ifdef JUDYL

1935

Pjvnew = JL_LEAFWVALUEAREA(Pjlwnew, pop1 + 1);

1936

JU_INSERTCOPY(Pjvnew, Pjv, pop1, offset, 0);

1937

#endif

1938

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

1939

1940

__JudyFreeJLW(Pjlw, pop1, NULL);

1941

1942

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

1943

DBGCODE(JudyCheckPop(*PPArray);)

1944

1945

JUDY1CODE(return(1); )

1946

JUDYLCODE(return((PPvoid_t) (Pjvnew + offset)); )

1947

}

1948

1949

assert(pop1 == cJU_JAPLEAF_MAXPOP1);

1950

1951

// Leaf at max size => cannot insert new index, so cascade instead:

1952

//

1953

// Upon cascading from a JAP leaf to the first branch, must allocate and

1954

// initialize a JPM.

1955

1956

Pjpm = __JudyAllocJPM();

1957

JUDY1CODE(JU_CHECKALLOC(Pjpm_t, Pjpm, JERRI );)

1958

JUDYLCODE(JU_CHECKALLOC(Pjpm_t, Pjpm, PPJERR);)

1959

1960

(Pjpm->jpm_Pop0) = cJU_JAPLEAF_MAXPOP1 - 1;

1961

(Pjpm->jpm_JP.jp_Addr) = (Word_t) Pjlw;

1962

(Pjpm->jpm_JP.jp_Type) = cJU_JAPLEAF;

1963

1964

if (__JudyCascadeL(&(Pjpm->jpm_JP), Pjpm) == -1)

1965

{

1966

JU_COPY_ERRNO(PJError, Pjpm);

1967

JUDY1CODE(return(JERRI );)

1968

JUDYLCODE(return(PPJERR);)

1969

}

1970

1971

// Note: No need to pass Pjpm for memory decrement; JAPLEAF memory is never

1972

// counted in a JPM at all:

1973

1974

__JudyFreeJLW(Pjlw, cJU_JAPLEAF_MAXPOP1, NULL);

1975

*PPArray = (Pvoid_t) ((Word_t) Pjpm | cJU_JAPBRANCH);

1976

1977

goto JAPBranch;

1978

1979

} // JU_JAPLEAF

1980

1981

1982

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

1983

// JAPBRANCH:

1984

1985

case cJU_JAPBRANCH:

1986

{

1987

int retcode; // really only needed for Judy1, but free for JudyL.

1988

1989

Pjpm = P_JPM(*PPArray);

1990

JAPBranch:

1991

retcode = __JudyInsWalk(&(Pjpm->jpm_JP), Index, Pjpm);

1992

1993

if (retcode == -1)

1994

{

1995

JU_COPY_ERRNO(PJError, Pjpm);

1996

JUDY1CODE(return(JERRI );)

1997

JUDYLCODE(return(PPJERR);)

1998

}

1999

2000

if (retcode == 1) ++(Pjpm->jpm_Pop0); // incr total array popu.

2001

2002

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

2003

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

2004

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

2005

DBGCODE(JudyCheckPop(*PPArray);)

2006

2007

#ifdef JUDY1

2008

assert((retcode == 0) || (retcode == 1));

2009

return(retcode); // == JU_RET_*_JPM().

2010

#else

2011

assert(Pjpm->jpm_PValue != (Pjv_t) NULL);

2012

return((PPvoid_t) Pjpm->jpm_PValue);

2013

#endif

2014

}

2015

2016

2017

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

2018

// INVALID JAP TYPE:

2019

2020

default:

2021

2022

NotJudyArray:

2023

JUDY1CODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDY1); return(JERRI );)

2024

JUDYLCODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDYL); return(PPJERR);)

2025

2026

} // switch

2027

2028

/*NOTREACHED*/

2029

2030

} // Judy1Set() / JudyLIns()