~drizzle-trunk/drizzle/development : revision 1

mysys/hash.c

This program is free software; you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation; version 2 of the License.

This program is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with this program; if not, write to the Free Software

Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */

/* The hash functions used for saveing keys */

/* One of key_length or key_length_offset must be given */

/* Key length of 0 isn't allowed */

#include "mysys_priv.h"

#include <m_string.h>

#include <m_ctype.h>

#include "hash.h"

#define NO_RECORD ((uint) -1)

#define LOWFIND 1

#define LOWUSED 2

#define HIGHFIND 4

#define HIGHUSED 8

typedef struct st_hash_info {

uint next; /* index to next key */

uchar *data; /* data for current entry */

} HASH_LINK;

static uint hash_mask(uint hashnr,uint buffmax,uint maxlength);

static void movelink(HASH_LINK *array,uint pos,uint next_link,uint newlink);

static int hashcmp(const HASH *hash, HASH_LINK *pos, const uchar *key,

size_t length);

static uint calc_hash(const HASH *hash, const uchar *key, size_t length)

{

ulong nr1=1, nr2=4;

hash->charset->coll->hash_sort(hash->charset,(uchar*) key,length,&nr1,&nr2);

return nr1;

}

my_bool

_hash_init(HASH *hash,uint growth_size, CHARSET_INFO *charset,

ulong size, size_t key_offset, size_t key_length,

hash_get_key get_key,

void (*free_element)(void*),uint flags CALLER_INFO_PROTO)

{

DBUG_ENTER("hash_init");

DBUG_PRINT("enter",("hash: 0x%lx size: %u", (long) hash, (uint) size));

hash->records=0;

if (my_init_dynamic_array_ci(&hash->array, sizeof(HASH_LINK), size,

growth_size))

{

hash->free=0; /* Allow call to hash_free */

DBUG_RETURN(1);

}

hash->key_offset=key_offset;

hash->key_length=key_length;

hash->blength=1;

hash->get_key=get_key;

hash->free=free_element;

hash->flags=flags;

hash->charset=charset;

DBUG_RETURN(0);

}

Call hash->free on all elements in hash.

SYNOPSIS

hash_free_elements()

hash hash table

NOTES:

Sets records to 0

static inline void hash_free_elements(HASH *hash)

{

if (hash->free)

{

HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*);

HASH_LINK *end= data + hash->records;

while (data < end)

(*hash->free)((data++)->data);

}

hash->records=0;

}

100

Free memory used by hash.

101

102

SYNOPSIS

103

hash_free()

104

hash the hash to delete elements of

105

106

NOTES: Hash can't be reused without calling hash_init again.

107

108

109

void hash_free(HASH *hash)

110

{

111

DBUG_ENTER("hash_free");

112

DBUG_PRINT("enter",("hash: 0x%lx", (long) hash));

113

114

hash_free_elements(hash);

115

hash->free= 0;

116

delete_dynamic(&hash->array);

117

DBUG_VOID_RETURN;

118

}

119

120

121

122

Delete all elements from the hash (the hash itself is to be reused).

123

124

SYNOPSIS

125

my_hash_reset()

126

hash the hash to delete elements of

127

128

129

void my_hash_reset(HASH *hash)

130

{

131

DBUG_ENTER("my_hash_reset");

132

DBUG_PRINT("enter",("hash: 0x%lxd", (long) hash));

133

134

hash_free_elements(hash);

135

reset_dynamic(&hash->array);

136

/* Set row pointers so that the hash can be reused at once */

137

hash->blength= 1;

138

DBUG_VOID_RETURN;

139

}

140

141

/* some helper functions */

142

143

144

This function is char* instead of uchar* as HPUX11 compiler can't

145

handle inline functions that are not defined as native types

146

147

148

static inline char*

149

hash_key(const HASH *hash, const uchar *record, size_t *length,

150

my_bool first)

151

{

152

if (hash->get_key)

153

return (char*) (*hash->get_key)(record,length,first);

154

*length=hash->key_length;

155

return (char*) record+hash->key_offset;

156

}

157

158

/* Calculate pos according to keys */

159

160

static uint hash_mask(uint hashnr,uint buffmax,uint maxlength)

161

{

162

if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));

163

return (hashnr & ((buffmax >> 1) -1));

164

}

165

166

static uint hash_rec_mask(const HASH *hash, HASH_LINK *pos,

167

uint buffmax, uint maxlength)

168

{

169

size_t length;

170

uchar *key= (uchar*) hash_key(hash,pos->data,&length,0);

171

return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);

172

}

173

174

175

176

/* for compilers which can not handle inline */

177

static

178

#if !defined(__USLC__) && !defined(__sgi)

179

inline

180

#endif

181

unsigned int rec_hashnr(HASH *hash,const uchar *record)

182

{

183

size_t length;

184

uchar *key= (uchar*) hash_key(hash,record,&length,0);

185

return calc_hash(hash,key,length);

186

}

187

188

189

uchar* hash_search(const HASH *hash, const uchar *key, size_t length)

190

{

191

HASH_SEARCH_STATE state;

192

return hash_first(hash, key, length, &state);

193

}

194

195

196

Search after a record based on a key

197

198

NOTE

199

Assigns the number of the found record to HASH_SEARCH_STATE state

200

201

202

uchar* hash_first(const HASH *hash, const uchar *key, size_t length,

203

HASH_SEARCH_STATE *current_record)

204

{

205

HASH_LINK *pos;

206

uint flag,idx;

207

DBUG_ENTER("hash_first");

208

209

flag=1;

210

if (hash->records)

211

{

212

idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length),

213

hash->blength,hash->records);

214

215

{

216

pos= dynamic_element(&hash->array,idx,HASH_LINK*);

217

if (!hashcmp(hash,pos,key,length))

218

{

219

DBUG_PRINT("exit",("found key at %d",idx));

220

*current_record= idx;

221

DBUG_RETURN (pos->data);

222

}

223

if (flag)

224

{

225

flag=0; /* Reset flag */

226

if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)

227

break; /* Wrong link */

228

}

229

}

230

while ((idx=pos->next) != NO_RECORD);

231

}

232

*current_record= NO_RECORD;

233

DBUG_RETURN(0);

234

}

235

236

/* Get next record with identical key */

237

/* Can only be called if previous calls was hash_search */

238

239

uchar* hash_next(const HASH *hash, const uchar *key, size_t length,

240

HASH_SEARCH_STATE *current_record)

241

{

242

HASH_LINK *pos;

243

uint idx;

244

245

if (*current_record != NO_RECORD)

246

{

247

HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*);

248

for (idx=data[*current_record].next; idx != NO_RECORD ; idx=pos->next)

249

{

250

pos=data+idx;

251

if (!hashcmp(hash,pos,key,length))

252

{

253

*current_record= idx;

254

return pos->data;

255

}

256

}

257

*current_record= NO_RECORD;

258

}

259

return 0;

260

}

261

262

263

/* Change link from pos to new_link */

264

265

static void movelink(HASH_LINK *array,uint find,uint next_link,uint newlink)

266

{

267

HASH_LINK *old_link;

268

269

{

270

old_link=array+next_link;

271

}

272

while ((next_link=old_link->next) != find);

273

old_link->next= newlink;

274

return;

275

}

276

277

278

Compare a key in a record to a whole key. Return 0 if identical

279

280

SYNOPSIS

281

hashcmp()

282

hash hash table

283

pos position of hash record to use in comparison

284

key key for comparison

285

length length of key

286

287

NOTES:

288

If length is 0, comparison is done using the length of the

289

record being compared against.

290

291

RETURN

292

= 0 key of record == key

293

!= 0 key of record != key

294

295

296

static int hashcmp(const HASH *hash, HASH_LINK *pos, const uchar *key,

297

size_t length)

298

{

299

size_t rec_keylength;

300

uchar *rec_key= (uchar*) hash_key(hash,pos->data,&rec_keylength,1);

301

return ((length && length != rec_keylength) ||

302

my_strnncoll(hash->charset, (uchar*) rec_key, rec_keylength,

303

(uchar*) key, rec_keylength));

304

}

305

306

307

/* Write a hash-key to the hash-index */

308

309

my_bool my_hash_insert(HASH *info,const uchar *record)

310

{

311

int flag;

312

size_t idx;

313

uint halfbuff,hash_nr,first_index;

314

uchar *ptr_to_rec,*ptr_to_rec2;

315

HASH_LINK *data,*empty,*gpos,*gpos2,*pos;

316

317

if (HASH_UNIQUE & info->flags)

318

{

319

uchar *key= (uchar*) hash_key(info, record, &idx, 1);

320

if (hash_search(info, key, idx))

321

return(TRUE); /* Duplicate entry */

322

}

323

324

flag=0;

325

if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))

326

return(TRUE); /* No more memory */

327

328

data=dynamic_element(&info->array,0,HASH_LINK*);

329

halfbuff= info->blength >> 1;

330

331

idx=first_index=info->records-halfbuff;

332

if (idx != info->records) /* If some records */

333

{

334

335

{

336

pos=data+idx;

337

hash_nr=rec_hashnr(info,pos->data);

338

if (flag == 0) /* First loop; Check if ok */

339

if (hash_mask(hash_nr,info->blength,info->records) != first_index)

340

break;

341

if (!(hash_nr & halfbuff))

342

{ /* Key will not move */

343

if (!(flag & LOWFIND))

344

{

345

if (flag & HIGHFIND)

346

{

347

flag=LOWFIND | HIGHFIND;

348

/* key shall be moved to the current empty position */

349

gpos=empty;

350

ptr_to_rec=pos->data;

351

empty=pos; /* This place is now free */

352

}

353

else

354

{

355

flag=LOWFIND | LOWUSED; /* key isn't changed */

356

gpos=pos;

357

ptr_to_rec=pos->data;

358

}

359

}

360

else

361

{

362

if (!(flag & LOWUSED))

363

{

364

/* Change link of previous LOW-key */

365

gpos->data=ptr_to_rec;

366

gpos->next= (uint) (pos-data);

367

flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);

368

}

369

gpos=pos;

370

ptr_to_rec=pos->data;

371

}

372

}

373

else

374

{ /* key will be moved */

375

if (!(flag & HIGHFIND))

376

{

377

flag= (flag & LOWFIND) | HIGHFIND;

378

/* key shall be moved to the last (empty) position */

379

gpos2 = empty; empty=pos;

380

ptr_to_rec2=pos->data;

381

}

382

else

383

{

384

if (!(flag & HIGHUSED))

385

{

386

/* Change link of previous hash-key and save */

387

gpos2->data=ptr_to_rec2;

388

gpos2->next=(uint) (pos-data);

389

flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);

390

}

391

gpos2=pos;

392

ptr_to_rec2=pos->data;

393

}

394

}

395

}

396

while ((idx=pos->next) != NO_RECORD);

397

398

if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)

399

{

400

gpos->data=ptr_to_rec;

401

gpos->next=NO_RECORD;

402

}

403

if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)

404

{

405

gpos2->data=ptr_to_rec2;

406

gpos2->next=NO_RECORD;

407

}

408

}

409

/* Check if we are at the empty position */

410

411

idx=hash_mask(rec_hashnr(info,record),info->blength,info->records+1);

412

pos=data+idx;

413

if (pos == empty)

414

{

415

pos->data=(uchar*) record;

416

pos->next=NO_RECORD;

417

}

418

else

419

{

420

/* Check if more records in same hash-nr family */

421

empty[0]=pos[0];

422

gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);

423

if (pos == gpos)

424

{

425

pos->data=(uchar*) record;

426

pos->next=(uint) (empty - data);

427

}

428

else

429

{

430

pos->data=(uchar*) record;

431

pos->next=NO_RECORD;

432

movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));

433

}

434

}

435

if (++info->records == info->blength)

436

info->blength+= info->blength;

437

return(0);

438

}

439

440

441

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

442

** Remove one record from hash-table. The record with the same record

443

** ptr is removed.

444

** if there is a free-function it's called for record if found

445

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

446

447

my_bool hash_delete(HASH *hash,uchar *record)

448

{

449

uint blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;

450

HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;

451

DBUG_ENTER("hash_delete");

452

if (!hash->records)

453

DBUG_RETURN(1);

454

455

blength=hash->blength;

456

data=dynamic_element(&hash->array,0,HASH_LINK*);

457

/* Search after record with key */

458

pos=data+ hash_mask(rec_hashnr(hash,record),blength,hash->records);

459

gpos = 0;

460

461

while (pos->data != record)

462

{

463

gpos=pos;

464

if (pos->next == NO_RECORD)

465

DBUG_RETURN(1); /* Key not found */

466

pos=data+pos->next;

467

}

468

469

if ( --(hash->records) < hash->blength >> 1) hash->blength>>=1;

470

lastpos=data+hash->records;

471

472

/* Remove link to record */

473

empty=pos; empty_index=(uint) (empty-data);

474

if (gpos)

475

gpos->next=pos->next; /* unlink current ptr */

476

else if (pos->next != NO_RECORD)

477

{

478

empty=data+(empty_index=pos->next);

479

pos->data=empty->data;

480

pos->next=empty->next;

481

}

482

483

if (empty == lastpos) /* last key at wrong pos or no next link */

484

goto exit;

485

486

/* Move the last key (lastpos) */

487

lastpos_hashnr=rec_hashnr(hash,lastpos->data);

488

/* pos is where lastpos should be */

489

pos=data+hash_mask(lastpos_hashnr,hash->blength,hash->records);

490

if (pos == empty) /* Move to empty position. */

491

{

492

empty[0]=lastpos[0];

493

goto exit;

494

}

495

pos_hashnr=rec_hashnr(hash,pos->data);

496

/* pos3 is where the pos should be */

497

pos3= data+hash_mask(pos_hashnr,hash->blength,hash->records);

498

if (pos != pos3)

499

{ /* pos is on wrong posit */

500

empty[0]=pos[0]; /* Save it here */

501

pos[0]=lastpos[0]; /* This should be here */

502

movelink(data,(uint) (pos-data),(uint) (pos3-data),empty_index);

503

goto exit;

504

}

505

pos2= hash_mask(lastpos_hashnr,blength,hash->records+1);

506

if (pos2 == hash_mask(pos_hashnr,blength,hash->records+1))

507

{ /* Identical key-positions */

508

if (pos2 != hash->records)

509

{

510

empty[0]=lastpos[0];

511

movelink(data,(uint) (lastpos-data),(uint) (pos-data),empty_index);

512

goto exit;

513

}

514

idx= (uint) (pos-data); /* Link pos->next after lastpos */

515

}

516

else idx= NO_RECORD; /* Different positions merge */

517

518

empty[0]=lastpos[0];

519

movelink(data,idx,empty_index,pos->next);

520

pos->next=empty_index;

521

522

exit:

523

VOID(pop_dynamic(&hash->array));

524

if (hash->free)

525

(*hash->free)((uchar*) record);

526

DBUG_RETURN(0);

527

}

528

529

530

Update keys when record has changed.

531

This is much more efficent than using a delete & insert.

532

533

534

my_bool hash_update(HASH *hash, uchar *record, uchar *old_key,

535

size_t old_key_length)

536

{

537

uint new_index,new_pos_index,blength,records,empty;

538

size_t idx;

539

HASH_LINK org_link,*data,*previous,*pos;

540

DBUG_ENTER("hash_update");

541

542

if (HASH_UNIQUE & hash->flags)

543

{

544

HASH_SEARCH_STATE state;

545

uchar *found, *new_key= (uchar*) hash_key(hash, record, &idx, 1);

546

if ((found= hash_first(hash, new_key, idx, &state)))

547

{

548

549

{

550

if (found != record)

551

DBUG_RETURN(1); /* Duplicate entry */

552

}

553

while ((found= hash_next(hash, new_key, idx, &state)));

554

}

555

}

556

557

data=dynamic_element(&hash->array,0,HASH_LINK*);

558

blength=hash->blength; records=hash->records;

559

560

/* Search after record with key */

561

562

idx=hash_mask(calc_hash(hash, old_key,(old_key_length ?

563

old_key_length :

564

hash->key_length)),

565

blength,records);

566

new_index=hash_mask(rec_hashnr(hash,record),blength,records);

567

if (idx == new_index)

568

DBUG_RETURN(0); /* Nothing to do (No record check) */

569

previous=0;

570

for (;;)

571

{

572

573

if ((pos= data+idx)->data == record)

574

break;

575

previous=pos;

576

if ((idx=pos->next) == NO_RECORD)

577

DBUG_RETURN(1); /* Not found in links */

578

}

579

org_link= *pos;

580

empty=idx;

581

582

/* Relink record from current chain */

583

584

if (!previous)

585

{

586

if (pos->next != NO_RECORD)

587

{

588

empty=pos->next;

589

*pos= data[pos->next];

590

}

591

}

592

else

593

previous->next=pos->next; /* unlink pos */

594

595

/* Move data to correct position */

596

if (new_index == empty)

597

{

598

599

At this point record is unlinked from the old chain, thus it holds

600

random position. By the chance this position is equal to position

601

for the first element in the new chain. That means updated record

602

is the only record in the new chain.

603

604

if (empty != idx)

605

{

606

607

Record was moved while unlinking it from the old chain.

608

Copy data to a new position.

609

610

data[empty]= org_link;

611

}

612

data[empty].next= NO_RECORD;

613

DBUG_RETURN(0);

614

}

615

pos=data+new_index;

616

new_pos_index=hash_rec_mask(hash,pos,blength,records);

617

if (new_index != new_pos_index)

618

{ /* Other record in wrong position */

619

data[empty] = *pos;

620

movelink(data,new_index,new_pos_index,empty);

621

org_link.next=NO_RECORD;

622

data[new_index]= org_link;

623

}

624

else

625

{ /* Link in chain at right position */

626

org_link.next=data[new_index].next;

627

data[empty]=org_link;

628

data[new_index].next=empty;

629

}

630

DBUG_RETURN(0);

631

}

632

633

634

uchar *hash_element(HASH *hash,ulong idx)

635

{

636

if (idx < hash->records)

637

return dynamic_element(&hash->array,idx,HASH_LINK*)->data;

638

return 0;

639

}

640

641

642

643

Replace old row with new row. This should only be used when key

644

isn't changed

645

646

647

void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record, uchar *new_row)

648

{

649

if (*current_record != NO_RECORD) /* Safety */

650

dynamic_element(&hash->array, *current_record, HASH_LINK*)->data= new_row;

651

}

652

653

654

#ifndef DBUG_OFF

655

656

my_bool hash_check(HASH *hash)

657

{

658

int error;

659

uint i,rec_link,found,max_links,seek,links,idx;

660

uint records,blength;

661

HASH_LINK *data,*hash_info;

662

663

records=hash->records; blength=hash->blength;

664

data=dynamic_element(&hash->array,0,HASH_LINK*);

665

error=0;

666

667

for (i=found=max_links=seek=0 ; i < records ; i++)

668

{

669

if (hash_rec_mask(hash,data+i,blength,records) == i)

670

{

671

found++; seek++; links=1;

672

for (idx=data[i].next ;

673

idx != NO_RECORD && found < records + 1;

674

idx=hash_info->next)

675

{

676

if (idx >= records)

677

{

678

DBUG_PRINT("error",

679

("Found pointer outside array to %d from link starting at %d",

680

idx,i));

681

error=1;

682

}

683

hash_info=data+idx;

684

seek+= ++links;

685

if ((rec_link=hash_rec_mask(hash,hash_info,blength,records)) != i)

686

{

687

DBUG_PRINT("error",

688

("Record in wrong link at %d: Start %d Record: 0x%lx Record-link %d",

689

idx, i, (long) hash_info->data, rec_link));

690

error=1;

691

}

692

else

693

found++;

694

}

695

if (links > max_links) max_links=links;

696

}

697

}

698

if (found != records)

699

{

700

DBUG_PRINT("error",("Found %u of %u records", found, records));

701

error=1;

702

}

703

if (records)

704

DBUG_PRINT("info",

705

("records: %u seeks: %d max links: %d hitrate: %.2f",

706

records,seek,max_links,(float) seek / (float) records));

707

return error;

708

}

709

#endif

Older »