~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.32 $ $Source: /judy/src/JudyCommon/JudyPrevNextEmpty.c $

19

//

20

// Judy*PrevEmpty() and Judy*NextEmpty() functions for Judy1 and JudyL.

21

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

22

//

23

// Compile with -DJUDYNEXT for the Judy*NextEmpty() function; otherwise

24

// defaults to Judy*PrevEmpty().

25

//

26

// Compile with -DTRACEJPSE to trace JP traversals.

27

//

28

// This file is separate from JudyPrevNext.c because it differs too greatly for

29

// ifdefs. This might be a bit surprising, but there are two reasons:

30

//

31

// - First, down in the details, searching for an empty index (SearchEmpty) is

32

// remarkably asymmetric with searching for a valid index (SearchValid),

33

// mainly with respect to: No return of a value area for JudyL; partially-

34

// full versus totally-full JPs; and handling of narrow pointers.

35

//

36

// - Second, we chose to implement SearchEmpty without a backtrack stack or

37

// backtrack engine, partly as an experiment, and partly because we think

38

// restarting from the top of the tree is less likely for SearchEmpty than

39

// for SearchValid, because empty indexes are more likely than valid indexes.

40

//

41

// A word about naming: A prior version of this feature (see 4.13) was named

42

// Judy*Free(), but there were concerns about that being read as a verb rather

43

// than an adjective. After prolonged debate and based on user input, we

44

// changed "Free" to "Empty".

45

46

#if (! (JUDY1 || JUDYL))

47

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

48

#endif

49

50

#ifndef JUDYNEXT

51

#ifndef JUDYPREV

52

#define JUDYPREV 1 // neither set => use default.

53

#endif

54

#endif

55

56

#ifdef JUDY1

57

#include "Judy1.h"

58

#else

59

#include "JudyL.h"

60

#endif

61

62

#include "JudyPrivate1L.h"

63

64

#ifdef TRACEJPSE

65

#include "JudyPrintJP.c"

66

#endif

67

68

69

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

70

// J U D Y 1 P R E V E M P T Y

71

// J U D Y 1 N E X T E M P T Y

72

// J U D Y L P R E V E M P T Y

73

// J U D Y L N E X T E M P T Y

74

//

75

// See the manual entry for the API.

76

//

77

// OVERVIEW OF Judy*PrevEmpty() / Judy*NextEmpty():

78

//

79

// See also for comparison the equivalent comments in JudyPrevNext.c.

80

//

81

// Take the caller's *PIndex and subtract/add 1, but watch out for

82

// underflow/overflow, which means "no previous/next empty index found." Use a

83

// reentrant switch statement (state machine, see SMGetRestart and

84

// SMGetContinue) to decode Index, starting with the JAP (PArray), through a

85

// JPM and branches, if any, down to an immediate or a leaf. Look for Index in

86

// that immediate or leaf, and if not found (invalid index), return success

87

// (Index is empty).

88

//

89

// This search can result in a dead end where taking a different path is

90

// required. There are four kinds of dead ends:

91

//

92

// BRANCH PRIMARY dead end: Encountering a fully-populated JP for the

93

// appropriate digit in Index. Search sideways in the branch for the

94

// previous/next absent/null/non-full JP, and if one is found, set Index to the

95

// highest/lowest index possible in that JP's expanse. Then if the JP is an

96

// absent or null JP, return success; otherwise for a non-full JP, traverse

97

// through the partially populated JP.

98

//

99

// BRANCH SECONDARY dead end: Reaching the end of a branch during a sideways

100

// search after a branch primary dead end. Set Index to the lowest/highest

101

// index possible in the whole branch's expanse (one higher/lower than the

102

// previous/next branch's expanse), then restart at the top of the tree, which

103

// includes pre-decrementing/incrementing Index (again) and watching for

104

// underflow/overflow (again).

105

//

106

// LEAF PRIMARY dead end: Finding a valid (non-empty) index in an immediate or

107

// leaf matching Index. Search sideways in the immediate/leaf for the

108

// previous/next empty index; if found, set *PIndex to match and return success.

109

//

110

// LEAF SECONDARY dead end: Reaching the end of an immediate or leaf during a

111

// sideways search after a leaf primary dead end. Just as for a branch

112

// secondary dead end, restart at the top of the tree with Index set to the

113

// lowest/highest index possible in the whole immediate/leaf's expanse.

114

// TBD: If leaf secondary dead end occurs, could shortcut and treat it as a

115

// branch primary dead end; but this would require remembering the parent

116

// branch's type and offset (a "one-deep stack"), and also wrestling with

117

// narrow pointers, at least for leaves (but not for immediates).

118

//

119

// Note some ASYMMETRIES between SearchValid and SearchEmpty:

120

//

121

// - The SearchValid code, upon descending through a narrow pointer, if Index

122

// is outside the expanse of the subsidiary node (effectively a secondary

123

// dead end), must decide whether to backtrack or findlimit. But the

124

// SearchEmpty code simply returns success (Index is empty).

125

//

126

// - Similarly, the SearchValid code, upon finding no previous/next index in

127

// the expanse of a narrow pointer (again, a secondary dead end), can simply

128

// start to backtrack at the parent JP. But the SearchEmpty code would have

129

// to first determine whether or not the parent JP's narrow expanse contains

130

// a previous/next empty index outside the subexpanse. Rather than keeping a

131

// parent state stack and backtracking this way, upon a secondary dead end,

132

// the SearchEmpty code simply restarts at the top of the tree, whether or

133

// not a narrow pointer is involved. Again, see the equivalent comments in

134

// JudyPrevNext.c for comparison.

135

//

136

// This function is written iteratively for speed, rather than recursively.

137

//

138

// TBD: We'd like to enhance this function to make successive searches faster.

139

// This would require saving some previous state, including the previous Index

140

// returned, and in which leaf it was found. If the next call is for the same

141

// Index and the array has not been modified, start at the same leaf. This

142

// should be much easier to implement since this is iterative rather than

143

// recursive code.

144

145

#ifdef JUDY1

146

#ifdef JUDYPREV

147

FUNCTION int Judy1PrevEmpty(

148

#else

149

FUNCTION int Judy1NextEmpty(

150

#endif

151

#else

152

#ifdef JUDYPREV

153

FUNCTION int JudyLPrevEmpty(

154

#else

155

FUNCTION int JudyLNextEmpty(

156

#endif

157

#endif

158

Pcvoid_t PArray, // Judy array to search.

159

Word_t * const PIndex, // starting point and result.

160

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

161

{

162

Word_t Index; // fast copy, in a register.

163

Word_t JAPtype; // type part of PArray.

164

Pjp_t Pjp; // current JP.

165

Pjbl_t Pjbl; // Pjp->jp_Addr masked and cast to types:

166

Pjbb_t Pjbb;

167

Pjbu_t Pjbu;

168

Pjlb_t Pjlb;

169

PWord_t Pword; // alternate name for use by GET* macros.

170

171

Word_t digit; // next digit to decode from Index.

172

Word_t digits; // current state in SM = digits left to decode.

173

Word_t pop0; // in a leaf.

174

Word_t pop0mask; // precalculated to avoid variable shifts.

175

long offset; // within a branch or leaf (can be large).

176

int subexp; // subexpanse in a bitmap branch.

177

BITMAPB_t bitposmaskB; // bit in bitmap for bitmap branch.

178

BITMAPL_t bitposmaskL; // bit in bitmap for bitmap leaf.

179

Word_t possfullJP1; // JP types for possibly full subexpanses:

180

Word_t possfullJP2;

181

Word_t possfullJP3;

182

183

184

// ----------------------------------------------------------------------------

185

// M A C R O S

186

//

187

// These are intended to make the code a bit more readable and less redundant.

188

189

190

// CHECK FOR NULL JP:

191

//

192

// TBD: In principle this can be reduced (here and in other *.c files) to just

193

// the latter clause since no Type should ever be below cJU_JPNULL1, but in

194

// fact some root pointer types can be lower, so for safety do both checks.

195

196

#define JPNULL(Type) (((Type) >= cJU_JPNULL1) && ((Type) <= cJU_JPNULLMAX))

197

198

199

// CHECK FOR A FULL JP:

200

//

201

// Given a JP, indicate if it is fully populated. Use digits, pop0mask, and

202

// possfullJP1..3 in the context.

203

//

204

// This is a difficult problem because it requires checking the Pop0 bits for

205

// all-ones, but the number of bytes depends on the JP type, which is not

206

// directly related to the parent branch's type or level -- the JP's child

207

// could be under a narrow pointer (hence not full). The simple answer

208

// requires switching on or otherwise calculating the JP type, which could be

209

// slow. Instead, in SMPREPB* precalculate pop0mask and also record in

210

// possfullJP1..3 the child JP (branch) types that could possibly be full (one

211

// level down), and use them here. For level-2 branches (with digits == 2),

212

// the test for a full child depends on Judy1/JudyL.

213

//

214

// Note: This cannot be applied to the JP in a JPM because it doesn't have

215

// enough pop0 digits.

216

//

217

// TBD: JPFULL_BRANCH diligently checks for BranchL or BranchB, where neither

218

// of those can ever be full as it turns out. Could just check for a BranchU

219

// at the right level. Also, pop0mask might be overkill, it's not used much,

220

// so perhaps just call cJU_POP0MASK(digits - 1) here?

221

//

222

// First, JPFULL_BRANCH checks for a full expanse for a JP whose child can be a

223

// branch, that is, a JP in a branch at level 3 or higher:

224

225

#define JPFULL_BRANCH(Pjp) \

226

((((((Pjp)->jp_DcdPop0) ^ cJU_ALLONES) & pop0mask) == 0) \

227

&& ((((Pjp)->jp_Type) == possfullJP1) \

228

|| (((Pjp)->jp_Type) == possfullJP2) \

229

|| (((Pjp)->jp_Type) == possfullJP3)))

230

231

#ifdef JUDY1

232

#define JPFULL(Pjp) \

233

((digits == 2) ? \

234

(((Pjp)->jp_Type) == cJ1_JPFULLPOPU1) : JPFULL_BRANCH(Pjp))

235

#else

236

#define JPFULL(Pjp) \

237

((digits == 2) ? \

238

((((Pjp)->jp_Type) == cJU_JPLEAF_B1) \

239

&& ((((Pjp)->jp_DcdPop0) & cJU_POP0MASK(1)) == cJU_POP0MASK(1))) : \

240

JPFULL_BRANCH(Pjp))

241

#endif

242

243

244

// RETURN SUCCESS:

245

//

246

// This hides the need to set *PIndex back to the local value of Index -- use a

247

// local value for faster operation. Note that the caller's *PIndex is ALWAYS

248

// modified upon success, at least decremented/incremented.

249

250

#define RET_SUCCESS { *PIndex = Index; return(1); }

251

252

253

// RETURN A CORRUPTION:

254

255

#define RET_CORRUPT { JU_SET_ERRNO(PJError, JU_ERRNO_CORRUPT); return(JERRI); }

256

257

258

// SEARCH A BITMAP BRANCH:

259

//

260

// This is a weak analog of __JudySearchLeaf*() for bitmap branches. Return

261

// the actual or next-left position, base 0, of Digit in a BITMAPB_t bitmap

262

// (subexpanse of a full bitmap), also given a Bitposmask for Digit. The

263

// position is the offset within the set bits.

264

//

265

// Unlike __JudySearchLeaf*(), the offset is not returned bit-complemented if

266

// Digit's bit is unset, because the caller can check the bitmap themselves to

267

// determine that. Also, if Digit's bit is unset, the returned offset is to

268

// the next-left JP or index (including -1), not to the "ideal" position for

269

// the index = next-right JP or index.

270

//

271

// Shortcut and skip calling __JudyCountBitsB() if the bitmap is full, in which

272

// case (Digit % cJU_BITSPERSUBEXPB) itself is the base-0 offset.

273

274

#define SEARCHBITMAPB(Bitmap,Digit,Bitposmask) \

275

(((Bitmap) == cJU_FULLBITMAPB) ? (Digit % cJU_BITSPERSUBEXPB) : \

276

__JudyCountBitsB((Bitmap) & JU_MASKLOWERINC(Bitposmask)) - 1)

277

278

#ifdef JUDYPREV

279

// Equivalent to search for the highest offset in Bitmap, that is, one less

280

// than the number of bits set:

281

282

#define SEARCHBITMAPMAXB(Bitmap) \

283

(((Bitmap) == cJU_FULLBITMAPB) ? cJU_BITSPERSUBEXPB - 1 : \

284

__JudyCountBitsB(Bitmap) - 1)

285

#endif

286

287

288

// CHECK DECODE BYTES:

289

//

290

// Check Decode bytes in a JP against the equivalent portion of Index. If they

291

// don't match, Index is outside the subexpanse of a narrow pointer, hence is

292

// empty.

293

294

#define CHECKDCD(cDigits) \

295

if (JU_DCDNOTMATCHINDEX(Index, Pjp->jp_DcdPop0, cDigits)) RET_SUCCESS

296

297

298

// REVISE REMAINDER OF INDEX:

299

//

300

// Put one digit in place in Index and clear/set the lower digits, if any, so

301

// the resulting Index is at the start/end of an expanse, or just clear/set the

302

// least digits.

303

//

304

// Actually, to make simple use of JU_LEASTBYTESMASK, first clear/set all least

305

// digits of Index including the digit to be overridden, then set the value of

306

// that one digit. If Digits == 1 the first operation is redundant, but either

307

// very fast or even removed by the optimizer.

308

309

#define CLEARLEASTDIGITS(Digits) Index &= ~JU_LEASTBYTESMASK(Digits)

310

#define SETLEASTDIGITS( Digits) Index |= JU_LEASTBYTESMASK(Digits)

311

312

#define CLEARLEASTDIGITS_D(Digit,Digits) \

313

{ \

314

CLEARLEASTDIGITS(Digits); \

315

JU_SETDIGIT(Index, Digit, Digits); \

316

}

317

318

#define SETLEASTDIGITS_D(Digit,Digits) \

319

{ \

320

SETLEASTDIGITS(Digits); \

321

JU_SETDIGIT(Index, Digit, Digits); \

322

}

323

324

325

// SET REMAINDER OF INDEX AND THEN RETURN OR CONTINUE:

326

327

#define SET_AND_RETURN(OpLeastDigits,Digit,Digits) \

328

{ \

329

OpLeastDigits(Digit, Digits); \

330

RET_SUCCESS; \

331

}

332

333

#define SET_AND_CONTINUE(OpLeastDigits,Digit,Digits) \

334

{ \

335

OpLeastDigits(Digit, Digits); \

336

goto SMGetContinue; \

337

}

338

339

340

// PREPARE TO HANDLE A JAP OR JP BRANCH IN THE STATE MACHINE:

341

//

342

// Extract a state-dependent digit from Index in a "constant" way, then jump to

343

// common code for multiple cases.

344

//

345

// TBD: Should this macro do more, such as preparing variable-shift masks for

346

// use in CLEARLEASTDIGITS and SETLEASTDIGITS?

347

348

#define SMPREPB(cDigits,Next,PossFullJP1,PossFullJP2,PossFullJP3) \

349

digits = (cDigits); \

350

digit = JU_DIGITATSTATE(Index, cDigits); \

351

pop0mask = cJU_POP0MASK((cDigits) - 1); /* for branch's JPs */ \

352

possfullJP1 = (PossFullJP1); \

353

possfullJP2 = (PossFullJP2); \

354

possfullJP3 = (PossFullJP3); \

355

goto Next

356

357

// Variations for specific-level branches and for shorthands:

358

//

359

// Note: SMPREPB2 need not initialize possfullJP* because JPFULL does not use

360

// them for digits == 2, but gcc -Wall isn't quite smart enough to see this, so

361

// waste a bit of time and space to get rid of the warning:

362

363

#define SMPREPB2(Next) \

364

digits = 2; \

365

digit = JU_DIGITATSTATE(Index, 2); \

366

pop0mask = cJU_POP0MASK(1); /* for branch's JPs */ \

367

possfullJP1 = possfullJP2 = possfullJP3 = 0; \

368

goto Next

369

370

#define SMPREPB3(Next) SMPREPB(3, Next, cJU_JPBRANCH_L2, \

371

cJU_JPBRANCH_B2, \

372

cJU_JPBRANCH_U2)

373

#ifndef JU_64BIT

374

#define SMPREPBL(Next) SMPREPB(cJU_ROOTSTATE, Next, cJU_JPBRANCH_L3, \

375

cJU_JPBRANCH_B3, \

376

cJU_JPBRANCH_U3)

377

#else

378

#define SMPREPB4(Next) SMPREPB(4, Next, cJU_JPBRANCH_L3, \

379

cJU_JPBRANCH_B3, \

380

cJU_JPBRANCH_U3)

381

#define SMPREPB5(Next) SMPREPB(5, Next, cJU_JPBRANCH_L4, \

382

cJU_JPBRANCH_B4, \

383

cJU_JPBRANCH_U4)

384

#define SMPREPB6(Next) SMPREPB(6, Next, cJU_JPBRANCH_L5, \

385

cJU_JPBRANCH_B5, \

386

cJU_JPBRANCH_U5)

387

#define SMPREPB7(Next) SMPREPB(7, Next, cJU_JPBRANCH_L6, \

388

cJU_JPBRANCH_B6, \

389

cJU_JPBRANCH_U6)

390

#define SMPREPBL(Next) SMPREPB(cJU_ROOTSTATE, Next, cJU_JPBRANCH_L7, \

391

cJU_JPBRANCH_B7, \

392

cJU_JPBRANCH_U7)

393

#endif

394

395

396

// RESTART AFTER SECONDARY DEAD END:

397

//

398

// Set Index to the first/last index in the branch or leaf subexpanse and start

399

// over at the top of the tree.

400

401

#ifdef JUDYPREV

402

#define SMRESTART(Digits) { CLEARLEASTDIGITS(Digits); goto SMGetRestart; }

403

#else

404

#define SMRESTART(Digits) { SETLEASTDIGITS( Digits); goto SMGetRestart; }

405

#endif

406

407

408

// CHECK EDGE OF LEAF'S EXPANSE:

409

//

410

// Given the LSBs of the lowest/highest valid index in a leaf (or equivalently

411

// in an immediate JP), the level (index size) of the leaf, and the full index

412

// to return (as Index in the context) already set to the full index matching

413

// the lowest/highest one, determine if there is an empty index in the leaf's

414

// expanse below/above the lowest/highest index, which is true if the

415

// lowest/highest index is not at the "edge" of the leaf's expanse based on its

416

// LSBs. If so, return Index decremented/incremented; otherwise restart at the

417

// top of the tree.

418

//

419

// Note: In many cases Index is already at the right spot and calling

420

// SMRESTART instead of just going directly to SMGetRestart is a bit of

421

// overkill.

422

//

423

// Note: Variable shift occurs if Digits is not a constant.

424

425

#ifdef JUDYPREV

426

#define LEAF_EDGE(MinIndex,Digits) \

427

{ \

428

if (MinIndex) { --Index; RET_SUCCESS; } \

429

SMRESTART(Digits); \

430

}

431

#else

432

#define LEAF_EDGE(MaxIndex,Digits) \

433

{ \

434

if ((MaxIndex) != JU_LEASTBYTES(cJU_ALLONES, Digits)) \

435

{ ++Index; RET_SUCCESS; } \

436

SMRESTART(Digits); \

437

}

438

#endif

439

440

// Same as above except Index is not already set to match the lowest/highest

441

// index, so do that before decrementing/incrementing it:

442

443

#ifdef JUDYPREV

444

#define LEAF_EDGE_SET(MinIndex,Digits) \

445

{ \

446

if (MinIndex) \

447

{ JU_SETDIGITS(Index, MinIndex, Digits); --Index; RET_SUCCESS; } \

448

SMRESTART(Digits); \

449

}

450

#else

451

#define LEAF_EDGE_SET(MaxIndex,Digits) \

452

{ \

453

if ((MaxIndex) != JU_LEASTBYTES(cJU_ALLONES, Digits)) \

454

{ JU_SETDIGITS(Index, MaxIndex, Digits); ++Index; RET_SUCCESS; } \

455

SMRESTART(Digits); \

456

}

457

#endif

458

459

460

// FIND A HOLE (EMPTY INDEX) IN AN IMMEDIATE OR LEAF:

461

//

462

// Given an index location in a leaf (or equivalently an immediate JP) known to

463

// contain a usable hole (an empty index less/greater than Index), and the LSBs

464

// of a minimum/maximum index to locate, find the previous/next empty index and

465

// return it.

466

//

467

// Note: "Even" index sizes (1,2,4[,8] bytes) have corresponding native C

468

// types; "odd" index sizes don't, but they are not represented here because

469

// they are handled completely differently; see elsewhere.

470

471

#ifdef JUDYPREV

472

473

#define LEAF_HOLE_EVEN(cDigits,Pjll,IndexLSB) \

474

{ \

475

while (*(Pjll) > (IndexLSB)) --(Pjll); /* too high */ \

476

if (*(Pjll) < (IndexLSB)) RET_SUCCESS /* Index is empty */ \

477

while (*(--(Pjll)) == --(IndexLSB)) /* null, find a hole */;\

478

JU_SETDIGITS(Index, IndexLSB, cDigits); \

479

RET_SUCCESS; \

480

}

481

#else

482

#define LEAF_HOLE_EVEN(cDigits,Pjll,IndexLSB) \

483

{ \

484

while (*(Pjll) < (IndexLSB)) ++(Pjll); /* too low */ \

485

if (*(Pjll) > (IndexLSB)) RET_SUCCESS /* Index is empty */ \

486

while (*(++(Pjll)) == ++(IndexLSB)) /* null, find a hole */;\

487

JU_SETDIGITS(Index, IndexLSB, cDigits); \

488

RET_SUCCESS; \

489

}

490

#endif

491

492

493

// SEARCH FOR AN EMPTY INDEX IN AN IMMEDIATE OR LEAF:

494

//

495

// Given a pointer to the first index in a leaf (or equivalently an immediate

496

// JP), the population of the leaf, and a first empty Index to find (inclusive,

497

// as Index in the context), where Index is known to fall within the expanse of

498

// the leaf to search, efficiently find the previous/next empty index in the

499

// leaf, if any. For simplicity the following overview is stated in terms of

500

// Judy*NextEmpty() only, but the same concepts apply symmetrically for

501

// Judy*PrevEmpty(). Also, in each case the comparisons are for the LSBs of

502

// Index and leaf indexes, according to the leaf's level.

503

//

504

// 1. If Index is GREATER than the last (highest) index in the leaf

505

// (maxindex), return success, Index is empty. (Remember, Index is known

506

// to be in the leaf's expanse.)

507

//

508

// 2. If Index is EQUAL to maxindex: If maxindex is not at the edge of the

509

// leaf's expanse, increment Index and return success, there is an empty

510

// Index one higher than any in the leaf; otherwise restart with Index

511

// reset to the upper edge of the leaf's expanse. Note: This might cause

512

// an extra cache line fill, but this is OK for repeatedly-called search

513

// code, and it saves CPU time.

514

//

515

// 3. If Index is LESS than maxindex, check for "dense to end of leaf":

516

// Subtract Index from maxindex, and back up that many slots in the leaf.

517

// If the resulting offset is not before the start of the leaf then compare

518

// the index at this offset (baseindex) with Index:

519

//

520

// 3a. If GREATER, the leaf must be corrupt, since indexes are sorted and

521

// there are no duplicates.

522

//

523

// 3b. If EQUAL, the leaf is "dense" from Index to maxindex, meaning there is

524

// no reason to search it. "Slide right" to the high end of the leaf

525

// (modify Index to maxindex) and continue with step 2 above.

526

//

527

// 3c. If LESS, continue with step 4.

528

//

529

// 4. If the offset based on maxindex minus Index falls BEFORE the start of

530

// the leaf, or if, per 3c above, baseindex is LESS than Index, the leaf is

531

// guaranteed "not dense to the end" and a usable empty Index must exist.

532

// This supports a more efficient search loop. Start at the FIRST index in

533

// the leaf, or one BEYOND baseindex, respectively, and search the leaf as

534

// follows, comparing each current index (currindex) with Index:

535

//

536

// 4a. If LESS, keep going to next index. Note: This is certain to terminate

537

// because maxindex is known to be greater than Index, hence the loop can

538

// be small and fast.

539

//

540

// 4b. If EQUAL, loop and increment Index until finding currindex greater than

541

// Index, and return success with the modified Index.

542

//

543

// 4c. If GREATER, return success, Index (unmodified) is empty.

544

//

545

// Note: These are macros rather than functions for speed.

546

547

#ifdef JUDYPREV

548

549

#define JSLE_EVEN(Addr,Pop0,cDigits,LeafType) \

550

{ \

551

LeafType * PjllLSB = (LeafType *) (Addr); \

552

LeafType IndexLSB = Index; /* auto-masking */ \

553

\

554

/* Index before or at start of leaf: */ \

555

\

556

if (*PjllLSB >= IndexLSB) /* no need to search */ \

557

{ \

558

if (*PjllLSB > IndexLSB) RET_SUCCESS; /* Index empty */ \

559

LEAF_EDGE(*PjllLSB, cDigits); \

560

} \

561

\

562

/* Index in or after leaf: */ \

563

\

564

offset = IndexLSB - *PjllLSB; /* tentative offset */ \

565

if (offset <= (Pop0)) /* can check density */ \

566

{ \

567

PjllLSB += offset; /* move to slot */ \

568

\

569

if (*PjllLSB <= IndexLSB) /* dense or corrupt */ \

570

{ \

571

if (*PjllLSB == IndexLSB) /* dense, check edge */ \

572

LEAF_EDGE_SET(PjllLSB[-offset], cDigits); \

573

RET_CORRUPT; \

574

} \

575

--PjllLSB; /* not dense, start at previous */ \

576

} \

577

else PjllLSB = ((LeafType *) (Addr)) + (Pop0); /* start at max */ \

578

\

579

LEAF_HOLE_EVEN(cDigits, PjllLSB, IndexLSB); \

580

}

581

582

// JSLE_ODD is completely different from JSLE_EVEN because it's important to

583

// minimize copying odd indexes to compare them (see 4.14). Furthermore, a

584

// very complex version (4.17, but abandoned before fully debugged) that

585

// avoided calling __JudySearchLeaf*() ran twice as fast as 4.14, but still

586

// half as fast as SearchValid. Doug suggested that to minimize complexity and

587

// share common code we should use __JudySearchLeaf*() for the initial search

588

// to establish if Index is empty, which should be common. If Index is valid

589

// in a leaf or immediate indexes, odds are good that an empty Index is nearby,

590

// so for simplicity just use a *COPY* function to linearly search the

591

// remainder.

592

//

593

// TBD: Pathological case? Average performance should be good, but worst-case

594

// might suffer. When Search says the initial Index is valid, so a linear

595

// copy-and-compare is begun, if the caller builds fairly large leaves with

596

// dense clusters AND frequently does a SearchEmpty at one end of such a

597

// cluster, performance won't be very good. Might a dense-check help? This

598

// means checking offset against the index at offset, and then against the

599

// first/last index in the leaf. We doubt the pathological case will appear

600

// much in real applications because they will probably alternate SearchValid

601

// and SearchEmpty calls.

602

603

#define JSLE_ODD(cDigits,Pjll,Pop0,Search,Copy) \

604

{ \

605

Word_t IndexLSB; /* least bytes only */ \

606

Word_t IndexFound; /* in leaf */ \

607

\

608

if ((offset = Search(Pjll, (Pop0) + 1, Index)) < 0) \

609

RET_SUCCESS; /* Index is empty */ \

610

\

611

IndexLSB = JU_LEASTBYTES(Index, cDigits); \

612

offset *= (cDigits); \

613

\

614

while ((offset -= (cDigits)) >= 0) \

615

{ /* skip until empty or start */ \

616

Copy(IndexFound, ((uint8_t *) (Pjll)) + offset); \

617

if (IndexFound != (--IndexLSB)) /* found an empty */ \

618

{ JU_SETDIGITS(Index, IndexLSB, cDigits); RET_SUCCESS; }\

619

} \

620

LEAF_EDGE_SET(IndexLSB, cDigits); \

621

}

622

623

#else // JUDYNEXT

624

625

#define JSLE_EVEN(Addr,Pop0,cDigits,LeafType) \

626

{ \

627

LeafType * PjllLSB = ((LeafType *) (Addr)) + (Pop0); \

628

LeafType IndexLSB = Index; /* auto-masking */ \

629

\

630

/* Index at or after end of leaf: */ \

631

\

632

if (*PjllLSB <= IndexLSB) /* no need to search */ \

633

{ \

634

if (*PjllLSB < IndexLSB) RET_SUCCESS; /* Index empty */\

635

LEAF_EDGE(*PjllLSB, cDigits); \

636

} \

637

\

638

/* Index before or in leaf: */ \

639

\

640

offset = *PjllLSB - IndexLSB; /* tentative offset */ \

641

if (offset <= (Pop0)) /* can check density */ \

642

{ \

643

PjllLSB -= offset; /* move to slot */ \

644

\

645

if (*PjllLSB >= IndexLSB) /* dense or corrupt */ \

646

{ \

647

if (*PjllLSB == IndexLSB) /* dense, check edge */ \

648

LEAF_EDGE_SET(PjllLSB[offset], cDigits); \

649

RET_CORRUPT; \

650

} \

651

++PjllLSB; /* not dense, start at next */ \

652

} \

653

else PjllLSB = (LeafType *) (Addr); /* start at minimum */ \

654

\

655

LEAF_HOLE_EVEN(cDigits, PjllLSB, IndexLSB); \

656

}

657

658

#define JSLE_ODD(cDigits,Pjll,Pop0,Search,Copy) \

659

{ \

660

Word_t IndexLSB; /* least bytes only */ \

661

Word_t IndexFound; /* in leaf */ \

662

int offsetmax; /* in bytes */ \

663

\

664

if ((offset = Search(Pjll, (Pop0) + 1, Index)) < 0) \

665

RET_SUCCESS; /* Index is empty */ \

666

\

667

IndexLSB = JU_LEASTBYTES(Index, cDigits); \

668

offset *= (cDigits); \

669

offsetmax = (Pop0) * (cDigits); /* single multiply */ \

670

\

671

while ((offset += (cDigits)) <= offsetmax) \

672

{ /* skip until empty or end */ \

673

Copy(IndexFound, ((uint8_t *) (Pjll)) + offset); \

674

if (IndexFound != (++IndexLSB)) /* found an empty */ \

675

{ JU_SETDIGITS(Index, IndexLSB, cDigits); RET_SUCCESS; } \

676

} \

677

LEAF_EDGE_SET(IndexLSB, cDigits); \

678

}

679

680

#endif // JUDYNEXT

681

682

// Note: Immediate indexes never fill a single index group, so for odd index

683

// sizes, save time by calling JSLE_ODD_IMM instead of JSLE_ODD.

684

685

#define __JudySearchLeafEmpty1(Addr,Pop0) \

686

JSLE_EVEN(Addr, Pop0, 1, uint8_t)

687

688

#define __JudySearchLeafEmpty2(Addr,Pop0) \

689

JSLE_EVEN(Addr, Pop0, 2, uint16_t)

690

691

#define __JudySearchLeafEmpty3(Addr,Pop0) \

692

JSLE_ODD(3, Addr, Pop0, __JudySearchLeaf3, JU_COPY3_PINDEX_TO_LONG)

693

694

#ifndef JU_64BIT

695

696

#define __JudySearchLeafEmptyL(Addr,Pop0) \

697

JSLE_EVEN(Addr, Pop0, 4, Word_t)

698

699

#else

700

701

#define __JudySearchLeafEmpty4(Addr,Pop0) \

702

JSLE_EVEN(Addr, Pop0, 4, uint32_t)

703

704

#define __JudySearchLeafEmpty5(Addr,Pop0) \

705

JSLE_ODD(5, Addr, Pop0, __JudySearchLeaf5, JU_COPY5_PINDEX_TO_LONG)

706

707

#define __JudySearchLeafEmpty6(Addr,Pop0) \

708

JSLE_ODD(6, Addr, Pop0, __JudySearchLeaf6, JU_COPY6_PINDEX_TO_LONG)

709

710

#define __JudySearchLeafEmpty7(Addr,Pop0) \

711

JSLE_ODD(7, Addr, Pop0, __JudySearchLeaf7, JU_COPY7_PINDEX_TO_LONG)

712

713

#define __JudySearchLeafEmptyL(Addr,Pop0) \

714

JSLE_EVEN(Addr, Pop0, 8, Word_t)

715

716

#endif // JU_64BIT

717

718

719

// ----------------------------------------------------------------------------

720

// START OF CODE:

721

//

722

// CHECK FOR SHORTCUTS:

723

//

724

// Error out if PIndex is null.

725

726

if (PIndex == (PWord_t) NULL)

727

{

728

JU_SET_ERRNO(PJError, JU_ERRNO_NULLPINDEX);

729

return(JERRI);

730

}

731

732

Index = *PIndex; // fast local copy.

733

734

// Set and pre-decrement/increment Index, watching for underflow/overflow:

735

//

736

// An out-of-bounds Index means failure: No previous/next empty index.

737

738

SMGetRestart: // return here with revised Index.

739

740

#ifdef JUDYPREV

741

if (Index-- == 0) return(0);

742

#else

743

if (++Index == 0) return(0);

744

#endif

745

746

// An empty array with an in-bounds (not underflowed/overflowed) Index means

747

// success:

748

//

749

// Note: This check is redundant after restarting at SMGetRestart, but should

750

// take insignificant time.

751

752

if (PArray == (Pvoid_t) NULL) RET_SUCCESS;

753

754

755

// ----------------------------------------------------------------------------

756

// HANDLE JAP:

757

//

758

// Check the JAP type. For JAP branches, traverse the JPM; handle JAP leaves

759

// directly; but look for the most common cases first.

760

761

JAPtype = JAPTYPE(PArray);

762

763

if (JAPtype == cJU_JAPBRANCH)

764

{

765

Pjpm_t Pjpm = P_JPM(PArray);

766

Pjp = &(Pjpm->jpm_JP);

767

768

if ((Pjp->jp_Addr) == 0) RET_CORRUPT;

769

goto SMGetContinue;

770

}

771

772

773

// ----------------------------------------------------------------------------

774

// ROOT-LEVEL LEAF that starts with a Pop0 word; just look within the leaf:

775

//

776

// If Index is not in the leaf, return success; otherwise return the first

777

// empty Index, if any, below/above where it would belong.

778

779

if (JAPtype == cJU_JAPLEAF)

780

{

781

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

782

pop0 = Pjlw[0];

783

784

#if (! (LOW_POP && JUDYL))

785

if (pop0 == 0) // special case.

786

{

787

#ifdef JUDYPREV

788

if ((Index != Pjlw[1]) || (Index-- != 0)) RET_SUCCESS;

789

#else

790

if ((Index != Pjlw[1]) || (++Index != 0)) RET_SUCCESS;

791

#endif

792

return(0); // no previous/next empty index.

793

}

794

#endif // (! (LOW_POP && JUDYL))

795

796

__JudySearchLeafEmptyL(Pjlw + 1, pop0);

797

}

798

799

800

#if (LOW_POP && JUDYL)

801

802

// ----------------------------------------------------------------------------

803

// ROOT-LEVEL LEAF, pop1 = 1; just look within the leaf:

804

805

// If Index != leaf's index, Index is empty; otherwise decrement/increment

806

// Index to previous/next empty index, but avoid wrapping past/to zero:

807

808

if (JAPtype == cJL_JAPLEAF_POPU1)

809

{

810

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

811

812

#ifdef JUDYPREV

813

if ((Index != Pjlw[0]) || (Index-- != 0)) RET_SUCCESS;

814

#else

815

if ((Index != Pjlw[0]) || (++Index != 0)) RET_SUCCESS;

816

#endif

817

return(0); // no previous/next empty index.

818

}

819

820

821

822

// ----------------------------------------------------------------------------

823

// ROOT-LEVEL LEAF, pop1 = 2; just look within the leaf:

824

//

825

if (JAPtype == cJL_JAPLEAF_POPU2)

826

{

827

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

828

829

assert(Pjlw[0] < Pjlw[1]); // valid Leaf2.

830

#ifdef JUDYPREV

831

assert(Pjlw[1] != 0); // valid Leaf2.

832

if (Index > Pjlw[1]) RET_SUCCESS; // Index is empty.

833

if (Index == Pjlw[1]) --Index; // try next lower.

834

if (Index > Pjlw[0]) RET_SUCCESS; // Index is empty.

835

if (Index == Pjlw[0]) --Index; // use next lower.

836

if (Index == cJU_ALLONES) return(0); // wrapped => no prev empty.

837

#else

838

assert(Pjlw[0] != cJU_ALLONES); // valid Leaf2.

839

if (Index < Pjlw[0]) RET_SUCCESS; // Index is empty.

840

if (Index == Pjlw[0]) ++Index; // try next higher.

841

if (Index < Pjlw[1]) RET_SUCCESS; // Index is empty.

842

if (Index == Pjlw[1]) ++Index; // use next higher.

843

if (Index == 0) return(0); // wrapped => no next empty.

844

#endif

845

RET_SUCCESS;

846

}

847

#endif // (LOW_POP && JUDYL)

848

849

850

// ----------------------------------------------------------------------------

851

// INVALID JAP TYPE:

852

853

JUDY1CODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDY1));

854

JUDYLCODE(JU_SET_ERRNO(PJError, JU_ERRNO_NOTJUDYL));

855

return(JERRI);

856

857

858

// ============================================================================

859

// STATE MACHINE -- GET INDEX:

860

//

861

// Search for Index (already decremented/incremented so as to be an inclusive

862

// search). If not found (empty index), return success. Otherwise do a

863

// previous/next search, and if successful modify Index to the empty index

864

// found. See function header comments.

865

//

866

// ENTRY: Pjp points to next JP to interpret, whose Decode bytes have not yet

867

// been checked.

868

//

869

// Note: Check Decode bytes at the start of each loop, not after looking up a

870

// new JP, so it's easy to do constant shifts/masks.

871

//

872

// EXIT: Return, or branch to SMGetRestart with modified Index, or branch to

873

// SMGetContinue with a modified Pjp, as described elsewhere.

874

//

875

// WARNING: For run-time efficiency the following cases replicate code with

876

// varying constants, rather than using common code with variable values!

877

878

SMGetContinue: // return here for next branch/leaf.

879

880

#ifdef TRACEJPSE

881

JudyPrintJP(Pjp, "sf", __LINE__);

882

#endif

883

884

switch (Pjp->jp_Type)

885

{

886

887

888

// ----------------------------------------------------------------------------

889

// LINEAR BRANCH:

890

//

891

// Check Decode bytes, if any, in the current JP, then search for a JP for the

892

// next digit in Index.

893

894

case cJU_JPBRANCH_L2: CHECKDCD(2); SMPREPB2(SMBranchL);

895

case cJU_JPBRANCH_L3: CHECKDCD(3); SMPREPB3(SMBranchL);

896

#ifdef JU_64BIT

897

case cJU_JPBRANCH_L4: CHECKDCD(4); SMPREPB4(SMBranchL);

898

case cJU_JPBRANCH_L5: CHECKDCD(5); SMPREPB5(SMBranchL);

899

case cJU_JPBRANCH_L6: CHECKDCD(6); SMPREPB6(SMBranchL);

900

case cJU_JPBRANCH_L7: CHECKDCD(7); SMPREPB7(SMBranchL);

901

#endif

902

case cJU_JPBRANCH_L: SMPREPBL(SMBranchL);

903

904

// Common code (state-independent) for all cases of linear branches:

905

906

SMBranchL:

907

Pjbl = P_JBL(Pjp->jp_Addr);

908

909

// First, check if Index's expanse (digit) is below/above the first/last

910

// populated expanse in the BranchL, in which case Index is empty; otherwise

911

// find the offset of the lowest/highest populated expanse at or above/below

912

// digit, if any:

913

//

914

// Note: The for-loop is guaranteed to exit eventually because the first/last

915

// expanse is known to be a terminator.

916

//

917

// Note: Cannot use __JudySearchLeaf*Empty1() here because it only applies to

918

// leaves and does not know about partial versus full JPs, unlike the use of

919

// __JudySearchLeaf1() for BranchL's in SearchValid code. Also, since linear

920

// leaf expanse lists are small, don't waste time calling __JudySearchLeaf1(),

921

// just scan the expanse list.

922

923

#ifdef JUDYPREV

924

if ((Pjbl->jbl_Expanse[0]) > digit) RET_SUCCESS;

925

926

for (offset = (Pjbl->jbl_NumJPs) - 1; /* null */; --offset)

927

#else

928

if ((Pjbl->jbl_Expanse[(Pjbl->jbl_NumJPs) - 1]) < digit)

929

RET_SUCCESS;

930

931

for (offset = 0; /* null */; ++offset)

932

#endif

933

{

934

935

// Too low/high, keep going; or too high/low, meaning the loop passed a hole

936

// and the initial Index is empty:

937

938

#ifdef JUDYPREV

939

if ((Pjbl->jbl_Expanse[offset]) > digit) continue;

940

if ((Pjbl->jbl_Expanse[offset]) < digit) RET_SUCCESS;

941

#else

942

if ((Pjbl->jbl_Expanse[offset]) < digit) continue;

943

if ((Pjbl->jbl_Expanse[offset]) > digit) RET_SUCCESS;

944

#endif

945

946

// Found expanse matching digit; if it's not full, traverse through it:

947

948

if (! JPFULL((Pjbl->jbl_jp) + offset))

949

{

950

Pjp = (Pjbl->jbl_jp) + offset;

951

goto SMGetContinue;

952

}

953

954

// Common code: While searching for a lower/higher hole or a non-full JP, upon

955

// finding a lower/higher hole, adjust Index using the revised digit and

956

// return; or upon finding a consecutive lower/higher expanse, if the expanse's

957

// JP is non-full, modify Index and traverse through the JP:

958

959

#define BRANCHL_CHECK(OpIncDec,OpLeastDigits,Digit,Digits) \

960

{ \

961

if ((Pjbl->jbl_Expanse[offset]) != OpIncDec digit) \

962

SET_AND_RETURN(OpLeastDigits, Digit, Digits); \

963

\

964

if (! JPFULL((Pjbl->jbl_jp) + offset)) \

965

{ \

966

Pjp = (Pjbl->jbl_jp) + offset; \

967

SET_AND_CONTINUE(OpLeastDigits, Digit, Digits); \

968

} \

969

}

970

971

// BranchL primary dead end: Expanse matching Index/digit is full (rare except

972

// for dense/sequential indexes):

973

//

974

// Search for a lower/higher hole, a non-full JP, or the end of the expanse

975

// list, while decrementing/incrementing digit.

976

977

#ifdef JUDYPREV

978

while (--offset >= 0)

979

BRANCHL_CHECK(--, SETLEASTDIGITS_D, digit, digits)

980

#else

981

while (++offset < Pjbl->jbl_NumJPs)

982

BRANCHL_CHECK(++, CLEARLEASTDIGITS_D, digit, digits)

983

#endif

984

985

// Passed end of BranchL expanse list after finding a matching but full

986

// expanse:

987

//

988

// Digit now matches the lowest/highest expanse, which is a full expanse; if

989

// digit is at the end of BranchL's expanse (no hole before/after), break out

990

// of the loop; otherwise modify Index to the next lower/higher digit and

991

// return success:

992

993

#ifdef JUDYPREV

994

if (digit == 0) break;

995

--digit; SET_AND_RETURN(SETLEASTDIGITS_D, digit, digits);

996

#else

997

if (digit == JU_LEASTBYTES(cJU_ALLONES, 1)) break;

998

++digit; SET_AND_RETURN(CLEARLEASTDIGITS_D, digit, digits);

999

#endif

1000

} // for-loop

1001

1002

// BranchL secondary dead end, no non-full previous/next JP:

1003

1004

SMRESTART(digits);

1005

1006

1007

// ----------------------------------------------------------------------------

1008

// BITMAP BRANCH:

1009

//

1010

// Check Decode bytes, if any, in the current JP, then search for a JP for the

1011

// next digit in Index.

1012

1013

case cJU_JPBRANCH_B2: CHECKDCD(2); SMPREPB2(SMBranchB);

1014

case cJU_JPBRANCH_B3: CHECKDCD(3); SMPREPB3(SMBranchB);

1015

#ifdef JU_64BIT

1016

case cJU_JPBRANCH_B4: CHECKDCD(4); SMPREPB4(SMBranchB);

1017

case cJU_JPBRANCH_B5: CHECKDCD(5); SMPREPB5(SMBranchB);

1018

case cJU_JPBRANCH_B6: CHECKDCD(6); SMPREPB6(SMBranchB);

1019

case cJU_JPBRANCH_B7: CHECKDCD(7); SMPREPB7(SMBranchB);

1020

#endif

1021

case cJU_JPBRANCH_B: SMPREPBL(SMBranchB);

1022

1023

// Common code (state-independent) for all cases of bitmap branches:

1024

1025

SMBranchB:

1026

Pjbb = P_JBB(Pjp->jp_Addr);

1027

1028

// Locate the digit's JP in the subexpanse list, if present:

1029

1030

subexp = digit / cJU_BITSPERSUBEXPB;

1031

assert(subexp < cJU_NUMSUBEXPB); // falls in expected range.

1032

bitposmaskB = JU_BITPOSMASKB(digit);

1033

1034

// Absent JP = no JP matches current digit in Index:

1035

1036

// if (! JU_BITMAPTESTB(Pjbb, digit)) // slower.

1037

if (! (JU_JBB_BITMAP(Pjbb, subexp) & bitposmaskB)) // faster.

1038

RET_SUCCESS;

1039

1040

// Non-full JP matches current digit in Index:

1041

//

1042

// Iterate to the subsidiary non-full JP.

1043

1044

offset = SEARCHBITMAPB(JU_JBB_BITMAP(Pjbb, subexp), digit,

1045

bitposmaskB);

1046

// not negative since at least one bit is set:

1047

assert(offset >= 0);

1048

assert(offset < (int) cJU_BITSPERSUBEXPB);

1049

1050

// Watch for null JP subarray pointer with non-null bitmap (a corruption):

1051

1052

if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp)))

1053

== (Pjp_t) NULL) RET_CORRUPT;

1054

1055

Pjp += offset;

1056

if (! JPFULL(Pjp)) goto SMGetContinue;

1057

1058

// BranchB primary dead end:

1059

//

1060

// Upon hitting a full JP in a BranchB for the next digit in Index, search

1061

// sideways for a previous/next absent JP (unset bit) or non-full JP (set bit

1062

// with non-full JP); first in the current bitmap subexpanse, then in

1063

// lower/higher subexpanses. Upon entry, Pjp points to a known-unusable JP,

1064

// ready to decrement/increment.

1065

//

1066

// Note: The preceding code is separate from this loop because Index does not

1067

// need revising (see SET_AND_*()) if the initial index is an empty index.

1068

//

1069

// TBD: For speed, shift bitposmaskB instead of using JU_BITMAPTESTB or

1070

// JU_BITPOSMASKB, but this shift has knowledge of bit order that really should

1071

// be encapsulated in a header file.

1072

1073

#define BRANCHB_CHECKBIT(OpLeastDigits) \

1074

if (! (JU_JBB_BITMAP(Pjbb, subexp) & bitposmaskB)) /* absent JP */ \

1075

SET_AND_RETURN(OpLeastDigits, digit, digits)

1076

1077

#define BRANCHB_CHECKJPFULL(OpLeastDigits) \

1078

if (! JPFULL(Pjp)) \

1079

SET_AND_CONTINUE(OpLeastDigits, digit, digits)

1080

1081

#define BRANCHB_STARTSUBEXP(OpLeastDigits) \

1082

if (! JU_JBB_BITMAP(Pjbb, subexp)) /* empty subexpanse, shortcut */ \

1083

SET_AND_RETURN(OpLeastDigits, digit, digits) \

1084

if ((Pjp = P_JP(JU_JBB_PJP(Pjbb, subexp))) == (Pjp_t) NULL) RET_CORRUPT

1085

1086

#ifdef JUDYPREV

1087

1088

--digit; // skip initial digit.

1089

bitposmaskB >>= 1; // see TBD above.

1090

1091

BranchBNextSubexp: // return here to check next bitmap subexpanse.

1092

1093

while (bitposmaskB) // more bits to check in subexp.

1094

{

1095

BRANCHB_CHECKBIT(SETLEASTDIGITS_D);

1096

--Pjp; // previous in subarray.

1097

BRANCHB_CHECKJPFULL(SETLEASTDIGITS_D);

1098

assert(digit >= 0);

1099

--digit;

1100

bitposmaskB >>= 1;

1101

}

1102

1103

if (subexp-- > 0) // more subexpanses.

1104

{

1105

BRANCHB_STARTSUBEXP(SETLEASTDIGITS_D);

1106

Pjp += SEARCHBITMAPMAXB(JU_JBB_BITMAP(Pjbb, subexp)) + 1;

1107

bitposmaskB = (1U << (cJU_BITSPERSUBEXPB - 1));

1108

goto BranchBNextSubexp;

1109

}

1110

1111

#else // JUDYNEXT

1112

1113

++digit; // skip initial digit.

1114

bitposmaskB <<= 1; // note: BITMAPB_t.

1115

1116

BranchBNextSubexp: // return here to check next bitmap subexpanse.

1117

1118

while (bitposmaskB) // more bits to check in subexp.

1119

{

1120

BRANCHB_CHECKBIT(CLEARLEASTDIGITS_D);

1121

++Pjp; // previous in subarray.

1122

BRANCHB_CHECKJPFULL(CLEARLEASTDIGITS_D);

1123

assert(digit < cJU_SUBEXPPERSTATE);

1124

++digit;

1125

bitposmaskB <<= 1; // note: BITMAPB_t.

1126

}

1127

1128

if (++subexp < cJU_NUMSUBEXPB) // more subexpanses.

1129

{

1130

BRANCHB_STARTSUBEXP(CLEARLEASTDIGITS_D);

1131

--Pjp; // pre-decrement.

1132

bitposmaskB = 1;

1133

goto BranchBNextSubexp;

1134

}

1135

1136

#endif // JUDYNEXT

1137

1138

// BranchB secondary dead end, no non-full previous/next JP:

1139

1140

SMRESTART(digits);

1141

1142

1143

// ----------------------------------------------------------------------------

1144

// UNCOMPRESSED BRANCH:

1145

//

1146

// Check Decode bytes, if any, in the current JP, then search for a JP for the

1147

// next digit in Index.

1148

1149

case cJU_JPBRANCH_U2: CHECKDCD(2); SMPREPB2(SMBranchU);

1150

case cJU_JPBRANCH_U3: CHECKDCD(3); SMPREPB3(SMBranchU);

1151

#ifdef JU_64BIT

1152

case cJU_JPBRANCH_U4: CHECKDCD(4); SMPREPB4(SMBranchU);

1153

case cJU_JPBRANCH_U5: CHECKDCD(5); SMPREPB5(SMBranchU);

1154

case cJU_JPBRANCH_U6: CHECKDCD(6); SMPREPB6(SMBranchU);

1155

case cJU_JPBRANCH_U7: CHECKDCD(7); SMPREPB7(SMBranchU);

1156

#endif

1157

case cJU_JPBRANCH_U: SMPREPBL(SMBranchU);

1158

1159

// Common code (state-independent) for all cases of uncompressed branches:

1160

1161

SMBranchU:

1162

Pjbu = P_JBU(Pjp->jp_Addr);

1163

Pjp = (Pjbu->jbu_jp) + digit;

1164

1165

// Absent JP = null JP for current digit in Index:

1166

1167

if (JPNULL(Pjp->jp_Type)) RET_SUCCESS;

1168

1169

// Non-full JP matches current digit in Index:

1170

//

1171

// Iterate to the subsidiary JP.

1172

1173

if (! JPFULL(Pjp)) goto SMGetContinue;

1174

1175

// BranchU primary dead end:

1176

//

1177

// Upon hitting a full JP in a BranchU for the next digit in Index, search

1178

// sideways for a previous/next null or non-full JP. BRANCHU_CHECKJP() is

1179

// shorthand for common code.

1180

//

1181

// Note: The preceding code is separate from this loop because Index does not

1182

// need revising (see SET_AND_*()) if the initial index is an empty index.

1183

1184

#define BRANCHU_CHECKJP(OpIncDec,OpLeastDigits) \

1185

{ \

1186

OpIncDec Pjp; \

1187

\

1188

if (JPNULL(Pjp->jp_Type)) \

1189

SET_AND_RETURN(OpLeastDigits, digit, digits) \

1190

\

1191

if (! JPFULL(Pjp)) \

1192

SET_AND_CONTINUE(OpLeastDigits, digit, digits) \

1193

}

1194

1195

#ifdef JUDYPREV

1196

while (digit-- > 0)

1197

BRANCHU_CHECKJP(--, SETLEASTDIGITS_D);

1198

#else

1199

while (++digit < cJU_BRANCHUNUMJPS)

1200

BRANCHU_CHECKJP(++, CLEARLEASTDIGITS_D);

1201

#endif

1202

1203

// BranchU secondary dead end, no non-full previous/next JP:

1204

1205

SMRESTART(digits);

1206

1207

1208

// ----------------------------------------------------------------------------

1209

// LINEAR LEAF:

1210

//

1211

// Check Decode bytes, if any, in the current JP, then search the leaf for the

1212

// previous/next empty index starting at Index. Primary leaf dead end is

1213

// hidden within __JudySearchLeaf*Empty*(). In case of secondary leaf dead

1214

// end, restart at the top of the tree.

1215

//

1216

// Note: Pword is the name known to GET*; think of it as Pjlw.

1217

1218

#define SMLEAFL(cDigits,Func) \

1219

Pword = (PWord_t) P_JLW(Pjp->jp_Addr); \

1220

pop0 = JU_JPLEAF_POP0(Pjp->jp_DcdPop0); \

1221

Func(Pword, pop0)

1222

1223

#if (JUDYL || (! JU_64BIT))

1224

case cJU_JPLEAF1: CHECKDCD(1); SMLEAFL(1, __JudySearchLeafEmpty1);

1225

#endif

1226

case cJU_JPLEAF2: CHECKDCD(2); SMLEAFL(2, __JudySearchLeafEmpty2);

1227

case cJU_JPLEAF3: CHECKDCD(3); SMLEAFL(3, __JudySearchLeafEmpty3);

1228

1229

#ifdef JU_64BIT

1230

case cJU_JPLEAF4: CHECKDCD(4); SMLEAFL(4, __JudySearchLeafEmpty4);

1231

case cJU_JPLEAF5: CHECKDCD(5); SMLEAFL(5, __JudySearchLeafEmpty5);

1232

case cJU_JPLEAF6: CHECKDCD(6); SMLEAFL(6, __JudySearchLeafEmpty6);

1233

case cJU_JPLEAF7: CHECKDCD(7); SMLEAFL(7, __JudySearchLeafEmpty7);

1234

#endif

1235

1236

1237

// ----------------------------------------------------------------------------

1238

// BITMAP LEAF:

1239

//

1240

// Check Decode bytes, if any, in the current JP, then search the leaf for the

1241

// previous/next empty index starting at Index.

1242

1243

case cJU_JPLEAF_B1:

1244

1245

CHECKDCD(1);

1246

1247

Pjlb = P_JLB(Pjp->jp_Addr);

1248

digit = JU_DIGITATSTATE(Index, 1);

1249

subexp = digit / cJU_BITSPERSUBEXPL;

1250

bitposmaskL = JU_BITPOSMASKL(digit);

1251

assert(subexp < cJU_NUMSUBEXPL); // falls in expected range.

1252

1253

// Absent index = no index matches current digit in Index:

1254

1255

// if (! JU_BITMAPTESTL(Pjlb, digit)) // slower.

1256

if (! (JU_JLB_BITMAP(Pjlb, subexp) & bitposmaskL)) // faster.

1257

RET_SUCCESS;

1258

1259

// LeafB1 primary dead end:

1260

//

1261

// Upon hitting a valid (non-empty) index in a LeafB1 for the last digit in

1262

// Index, search sideways for a previous/next absent index, first in the

1263

// current bitmap subexpanse, then in lower/higher subexpanses.

1264

// LEAFB1_CHECKBIT() is shorthand for common code to handle one bit in one

1265

// bitmap subexpanse.

1266

//

1267

// Note: The preceding code is separate from this loop because Index does not

1268

// need revising (see SET_AND_*()) if the initial index is an empty index.

1269

//

1270

// TBD: For speed, shift bitposmaskL instead of using JU_BITMAPTESTL or

1271

// JU_BITPOSMASKL, but this shift has knowledge of bit order that really should

1272

// be encapsulated in a header file.

1273

1274

#define LEAFB1_CHECKBIT(OpLeastDigits) \

1275

if (! (JU_JLB_BITMAP(Pjlb, subexp) & bitposmaskL)) \

1276

SET_AND_RETURN(OpLeastDigits, digit, 1)

1277

1278

#define LEAFB1_STARTSUBEXP(OpLeastDigits) \

1279

if (! JU_JLB_BITMAP(Pjlb, subexp)) /* empty subexp */ \

1280

SET_AND_RETURN(OpLeastDigits, digit, 1)

1281

1282

#ifdef JUDYPREV

1283

1284

--digit; // skip initial digit.

1285

bitposmaskL >>= 1; // see TBD above.

1286

1287

LeafB1NextSubexp: // return here to check next bitmap subexpanse.

1288

1289

while (bitposmaskL) // more bits to check in subexp.

1290

{

1291

LEAFB1_CHECKBIT(SETLEASTDIGITS_D);

1292

assert(digit >= 0);

1293

--digit;

1294

bitposmaskL >>= 1;

1295

}

1296

1297

if (subexp-- > 0) // more subexpanses.

1298

{

1299

LEAFB1_STARTSUBEXP(SETLEASTDIGITS_D);

1300

bitposmaskL = (1UL << (cJU_BITSPERSUBEXPL - 1));

1301

goto LeafB1NextSubexp;

1302

}

1303

1304

#else // JUDYNEXT

1305

1306

++digit; // skip initial digit.

1307

bitposmaskL <<= 1; // note: BITMAPL_t.

1308

1309

LeafB1NextSubexp: // return here to check next bitmap subexpanse.

1310

1311

while (bitposmaskL) // more bits to check in subexp.

1312

{

1313

LEAFB1_CHECKBIT(CLEARLEASTDIGITS_D);

1314

assert(digit < cJU_SUBEXPPERSTATE);

1315

++digit;

1316

bitposmaskL <<= 1; // note: BITMAPL_t.

1317

}

1318

1319

if (++subexp < cJU_NUMSUBEXPL) // more subexpanses.

1320

{

1321

LEAFB1_STARTSUBEXP(CLEARLEASTDIGITS_D);

1322

bitposmaskL = 1;

1323

goto LeafB1NextSubexp;

1324

}

1325

1326

#endif // JUDYNEXT

1327

1328

// LeafB1 secondary dead end, no empty index:

1329

1330

SMRESTART(1);

1331

1332

1333

#ifdef JUDY1

1334

// ----------------------------------------------------------------------------

1335

// FULL POPULATION:

1336

//

1337

// If the Decode bytes do not match, Index is empty (without modification);

1338

// otherwise restart.

1339

1340

case cJ1_JPFULLPOPU1:

1341

1342

CHECKDCD(1);

1343

SMRESTART(1);

1344

#endif

1345

1346

1347

// ----------------------------------------------------------------------------

1348

// IMMEDIATE:

1349

//

1350

// Pop1 = 1 Immediate JPs:

1351

//

1352

// If Index is not in the immediate JP, return success; otherwise check if

1353

// there is an empty index below/above the immediate JP's index, and if so,

1354

// return success with modified Index, else restart.

1355

//

1356

// Note: Doug says it's fast enough to calculate the index size (digits) in

1357

// the following; no need to set it separately for each case.

1358

1359

case cJU_JPIMMED_1_01:

1360

case cJU_JPIMMED_2_01:

1361

case cJU_JPIMMED_3_01:

1362

#ifdef JU_64BIT

1363

case cJU_JPIMMED_4_01:

1364

case cJU_JPIMMED_5_01:

1365

case cJU_JPIMMED_6_01:

1366

case cJU_JPIMMED_7_01:

1367

#endif

1368

if ((Pjp->jp_DcdPop0) != JU_TRIMTODCDSIZE(Index)) RET_SUCCESS;

1369

digits = (Pjp->jp_Type) - cJU_JPIMMED_1_01 + 1;

1370

LEAF_EDGE(JU_LEASTBYTES(Pjp->jp_DcdPop0, digits), digits);

1371

1372

// Immediate JPs with Pop1 > 1:

1373

1374

#define IMM_MULTI(Func,BaseJPType) \

1375

JUDY1CODE(Pword = (PWord_t) (Pjp->jp_1Index);) \

1376

JUDYLCODE(Pword = (PWord_t) (Pjp->jp_LIndex);) \

1377

Func(Pword, (Pjp->jp_Type) - (BaseJPType) + 1)

1378

1379

case cJU_JPIMMED_1_02:

1380

case cJU_JPIMMED_1_03:

1381

#if (JUDY1 || JU_64BIT)

1382

case cJU_JPIMMED_1_04:

1383

case cJU_JPIMMED_1_05:

1384

case cJU_JPIMMED_1_06:

1385

case cJU_JPIMMED_1_07:

1386

#endif

1387

#if (JUDY1 && JU_64BIT)

1388

case cJ1_JPIMMED_1_08:

1389

case cJ1_JPIMMED_1_09:

1390

case cJ1_JPIMMED_1_10:

1391

case cJ1_JPIMMED_1_11:

1392

case cJ1_JPIMMED_1_12:

1393

case cJ1_JPIMMED_1_13:

1394

case cJ1_JPIMMED_1_14:

1395

case cJ1_JPIMMED_1_15:

1396

#endif

1397

IMM_MULTI(__JudySearchLeafEmpty1, cJU_JPIMMED_1_02);

1398

1399

#if (JUDY1 || JU_64BIT)

1400

case cJU_JPIMMED_2_02:

1401

case cJU_JPIMMED_2_03:

1402

#endif

1403

#if (JUDY1 && JU_64BIT)

1404

case cJ1_JPIMMED_2_04:

1405

case cJ1_JPIMMED_2_05:

1406

case cJ1_JPIMMED_2_06:

1407

case cJ1_JPIMMED_2_07:

1408

#endif

1409

#if (JUDY1 || JU_64BIT)

1410

IMM_MULTI(__JudySearchLeafEmpty2, cJU_JPIMMED_2_02);

1411

#endif

1412

1413

#if (JUDY1 || JU_64BIT)

1414

case cJU_JPIMMED_3_02:

1415

#endif

1416

#if (JUDY1 && JU_64BIT)

1417

case cJ1_JPIMMED_3_03:

1418

case cJ1_JPIMMED_3_04:

1419

case cJ1_JPIMMED_3_05:

1420

#endif

1421

#if (JUDY1 || JU_64BIT)

1422

IMM_MULTI(__JudySearchLeafEmpty3, cJU_JPIMMED_3_02);

1423

#endif

1424

1425

#if (JUDY1 && JU_64BIT)

1426

case cJ1_JPIMMED_4_02:

1427

case cJ1_JPIMMED_4_03:

1428

IMM_MULTI(__JudySearchLeafEmpty4, cJ1_JPIMMED_4_02);

1429

1430

case cJ1_JPIMMED_5_02:

1431

case cJ1_JPIMMED_5_03:

1432

IMM_MULTI(__JudySearchLeafEmpty5, cJ1_JPIMMED_5_02);

1433

1434

case cJ1_JPIMMED_6_02:

1435

IMM_MULTI(__JudySearchLeafEmpty6, cJ1_JPIMMED_6_02);

1436

1437

case cJ1_JPIMMED_7_02:

1438

IMM_MULTI(__JudySearchLeafEmpty7, cJ1_JPIMMED_7_02);

1439

#endif

1440

1441

1442

// ----------------------------------------------------------------------------

1443

// INVALID JP TYPE:

1444

1445

default: RET_CORRUPT;

1446

1447

} // SMGet switch.

1448

1449

} // Judy1PrevEmpty() / Judy1NextEmpty() / JudyLPrevEmpty() / JudyLNextEmpty()