cde/lib/tt/mini_isam/isamaddindex.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /*%%  (c) Copyright 1993, 1994 Hewlett-Packard Company                   */
  24 /*%%  (c) Copyright 1993, 1994 International Business Machines Corp.     */
  25 /*%%  (c) Copyright 1993, 1994 Sun Microsystems, Inc.                    */
  26 /*%%  (c) Copyright 1993, 1994 Novell, Inc.                              */
  27 /*%%  $XConsortium: isamaddindex.c /main/3 1995/10/23 11:34:12 rswiston $                                                        */
  28 #ifndef lint
  29 static char sccsid[] = "@(#)isamaddindex.c 1.14 89/09/14 Copyr 1988 Sun Micro";
  30 #endif
  31 /*
  32  * Copyright (c) 1988 by Sun Microsystems, Inc.
  33  */
  34
  35 /*
  36  * isaddindex.c
  37  *
  38  * Description:
  39  *      Add secondary index
  40  *
  41  *
  42  */
  43
  44 #include "isam_impl.h"
  45 #include <sys/types.h>
  46 #include <sys/stat.h>
  47
  48 extern int _iskeycmp();
  49
  50 static void _readallrecords(), _attach_dups_serial();
  51 static Blkno _buildbtree();
  52 static int _duplicate_exist();
  53 static checkavailfd();
  54
  55 /*
  56  * _amaddindex(isfhandle, keydesc,  errcode)
  57  *
  58  * _amaddindex() build a secondary index
  59  *
  60  * Input params:
  61  *      isfhandle       Handle of ISAM file
  62  *      keydesc         Key descriptor
  63  *
  64  * Output params:
  65  *      errcode         error status of the operation
  66  *
  67  */
  68
  69 /*ARGSUSED*/
  70 int
  71 _amaddindex(isfhandle, keydesc, errcode)
  72     Bytearray           *isfhandle;
  73     struct keydesc      *keydesc;
  74     struct errcode      *errcode;
  75 {
  76     Fcb                 *fcb = NULL;
  77     Keydesc2            keydesc2;
  78     int                 err;
  79
  80
  81     _isam_entryhook();
  82
  83     /*
  84      * Check if 1 UNIX file decriptor is available.
  85      */
  86     checkavailfd();
  87
  88     /*
  89      * Get FCB corresponding to the isfhandle handle.
  90      */
  91     if ((fcb = _openfcb(isfhandle, errcode)) == NULL) {
  92         _isam_exithook();
  93         return (ISERROR);
  94     }
  95
  96     /*
  97      * Check that the limit on the number of keys is not exceeded.
  98      */
  99     if (fcb->nkeys >= MAXNKEYS) {
 100         _amseterrcode(errcode, ETOOMANY);
 101         goto ERROR;
 102     }
 103
 104     /*
 105      * Update information in FCB from CNTL page on the disk
 106      */
 107     (void)_isfcb_cntlpg_r(fcb);
 108
 109     /*
 110      * Check key descriptor for validity.
 111      */
 112     if (_validate_keydesc(keydesc, fcb->minreclen) != ISOK) {
 113         _amseterrcode(errcode, EBADKEY);
 114         goto ERROR;
 115     }
 116
 117     /*
 118      * Convert key descriptor to internal form.
 119      */
 120     _iskey_xtoi (&keydesc2, keydesc);
 121
 122     /* Check if key already exists. */
 123     if (_isfcb_findkey(fcb ,&keydesc2) != (Keydesc2 *) 0) {
 124         _amseterrcode(errcode, EKEXISTS);
 125         goto ERROR;
 126     }
 127
 128     /*
 129      * Open (or even create) .ind file if that is not open (created) yet.
 130      */
 131     if (_open2_indfile(fcb) != ISOK) {
 132         _amseterrcode(errcode, EACCES);
 133         goto ERROR;
 134     }
 135
 136     /*
 137      * Create index structure.
 138      */
 139     if ((err = _create_index(fcb ,&keydesc2)) != ISOK) {
 140         _amseterrcode(errcode, err);
 141         goto ERROR;
 142     }
 143
 144     /*
 145      * Add key descriptor to FCB.
 146      */
 147     if (_isfcb_altkeyadd(fcb, &keydesc2) == ISERROR) {
 148         _amseterrcode(errcode, ETOOMANY);
 149         goto ERROR;
 150     }
 151
 152     _amseterrcode(errcode, ISOK);
 153
 154     _issignals_mask();
 155     _isdisk_commit();
 156     _isdisk_sync();
 157     _isdisk_inval();
 158
 159     /*
 160      * Update CNTL Page from the FCB.
 161      */
 162     (void)_isfcb_cntlpg_w(fcb);
 163     _issignals_unmask();
 164
 165     _isam_exithook();
 166     return (ISOK);
 167
 168  ERROR:
 169
 170     _isdisk_rollback();
 171     _isdisk_inval();
 172
 173     /*
 174      * Restore FCB from CNTL page.
 175      */
 176     if (fcb) (void)_isfcb_cntlpg_r(fcb);
 177
 178     _isam_exithook();
 179     return (ISERROR);
 180 }
 181
 182 /*
 183  * _amaddprimary(isfhandle, keydesc, errcode)
 184  *
 185  * _amaddprimary() build primary key
 186  *
 187  * Input params:
 188  *      isfhandle       Handle of ISAM file
 189  *      keydesc         Key descriptor
 190  *
 191  * Output params:
 192  *      errcode         error status of the operation
 193  *
 194  */
 195
 196 /*ARGSUSED*/
 197 int
 198 _amaddprimary(isfhandle, keydesc, errcode)
 199     Bytearray           *isfhandle;
 200     struct keydesc      *keydesc;
 201     struct errcode      *errcode;
 202 {
 203     Fcb                 *fcb = NULL;
 204     Keydesc2            keydesc2;
 205     int                 err;
 206
 207     _isam_entryhook();
 208
 209     /*
 210      * Check if 1 UNIX file decriptor is available.
 211      */
 212     checkavailfd();
 213
 214     /*
 215      * Get FCB corresponding to the isfhandle handle.
 216      */
 217     if ((fcb = _openfcb(isfhandle, errcode)) == NULL) {
 218         _isam_exithook();
 219         return (ISERROR);
 220     }
 221
 222     /*
 223      * Check that the limit on the numbrer of keys is not exceeded.
 224      */
 225     if (fcb->nkeys >= MAXNKEYS) {
 226         _amseterrcode(errcode, ETOOMANY);
 227         goto ERROR;
 228     }
 229
 230     /*
 231      * Update information in FCB from CNTL page on the disk
 232      */
 233     (void)_isfcb_cntlpg_r(fcb);
 234
 235     /*
 236      * Check key descriptor for validity.
 237      */
 238     if (_validate_keydesc(keydesc, fcb->minreclen) != ISOK) {
 239         _amseterrcode(errcode, EBADKEY);
 240         goto ERROR;
 241     }
 242
 243     /*
 244      * Convert key descriptor to internal form.
 245      */
 246     _iskey_xtoi (&keydesc2, keydesc);
 247
 248     /* Check if key already exists. */
 249     if (_isfcb_findkey(fcb ,&keydesc2) != (Keydesc2 *) 0) {
 250         _amseterrcode(errcode, EKEXISTS);
 251         goto ERROR;
 252     }
 253
 254     /*
 255      * Check that primary key does not already exist.
 256      */
 257     if (!FCB_NOPRIMARY_KEY(fcb)) {
 258         _amseterrcode(errcode, EKEXISTS);
 259         goto ERROR;
 260     }
 261
 262     /*
 263      * Open (or even create) .ind file if that is not open (created) yet.
 264      */
 265     if (_open2_indfile(fcb) != ISOK) {
 266         _amseterrcode(errcode, EACCES);
 267         goto ERROR;
 268     }
 269
 270     /*
 271      * Create index structure.
 272      */
 273     if ((err = _create_index(fcb ,&keydesc2)) != ISOK) {
 274         _amseterrcode(errcode, err);
 275         goto ERROR;
 276     }
 277
 278     /*
 279      * Add key descriptor to FCB.
 280      */
 281     if (_isfcb_primkeyadd(fcb, &keydesc2) == ISERROR) {
 282         _amseterrcode(errcode, ETOOMANY);
 283         goto ERROR;
 284     }
 285
 286     _amseterrcode(errcode, ISOK);
 287
 288     _issignals_mask();
 289     _isdisk_commit();
 290     _isdisk_sync();
 291     _isdisk_inval();
 292
 293     /*
 294      * Update CNTL Page from the FCB.
 295      */
 296     (void)_isfcb_cntlpg_w(fcb);
 297     _issignals_unmask();
 298
 299     _isam_exithook();
 300     return (ISOK);
 301
 302  ERROR:
 303     _isdisk_rollback();
 304     _isdisk_inval();
 305
 306     /*
 307      * Restore FCB from CNTL page.
 308      */
 309     if (fcb) (void)_isfcb_cntlpg_r(fcb);
 310
 311     _isam_exithook();
 312     return (ISERROR);
 313 }
 314
 315 /*
 316  * _create_index()
 317  *
 318  * Read data file, extract key from record, sort keys, create index.
 319  * Check unique constraint, create duplicate serial numbers.
 320  */
 321
 322 int _create_index(fcb, pkeydesc2)
 323     Fcb                 *fcb;
 324     Keydesc2            *pkeydesc2;
 325 {
 326     Issort              *srt;
 327     int                 keylength = pkeydesc2->k2_len;
 328
 329     /*
 330      * Set comparison function for sorting.
 331      *
 332      * nparts + 1 is used to compare keys that allow duplicates.
 333      * The (nparts + 1) comparison will never be reached on ISNODUPS key.
 334      */
 335     _iskeycmp_set(pkeydesc2, pkeydesc2->k2_nparts+1);
 336
 337     /*
 338      * Handle empty file as a special case, to avoid nasty behavior
 339      * in buildbtree() arithmetics.
 340      */
 341     if (fcb->nrecords == 0L) {
 342         pkeydesc2->k2_rootnode = _buildbtree(fcb, pkeydesc2, (Issort *) NULL);
 343         return (ISOK);
 344     }
 345
 346
 347     /*
 348      * Create a sorter for this key descriptor.
 349      */
 350     srt = _issort_create(keylength, (int)fcb->nrecords, _iskeycmp);
 351
 352     /*
 353      * Read sequentially all records, extract keys, and
 354      * insert the keys into the sorter.
 355      */
 356     _readallrecords(fcb, srt, pkeydesc2);
 357
 358     _issort_sort(srt);                       /* Sort the keys */
 359
 360     /*
 361      * Check for potential duplicates if the index is ISNODUPS.
 362      */
 363     if (!ALLOWS_DUPS2(pkeydesc2)) {
 364         if (_duplicate_exist(srt, keylength)) {
 365             _issort_destroy(srt);
 366             return (EDUPL);
 367         }
 368     }
 369
 370     /*
 371      * Attach duplicate serial numbers to the keys that are ISDUPS.
 372      */
 373     if (ALLOWS_DUPS2(pkeydesc2)) {
 374         _attach_dups_serial(srt, pkeydesc2);
 375     }
 376
 377     /*
 378      * Allocate and build the B-tree
 379      */
 380     pkeydesc2->k2_rootnode = _buildbtree(fcb, pkeydesc2, srt);
 381
 382     _issort_destroy(srt);                    /* Destroy sorter */
 383
 384     return (ISOK);
 385 }
 386
 387 /*
 388  * _readallrecords()
 389  *
 390  * REad all records, extract keys, and insert them into sorter.
 391  */
 392
 393 Static void
 394 _readallrecords(fcb, srt, pkeydesc2)
 395     Fcb                 *fcb;
 396     Issort              *srt;
 397     Keydesc2            *pkeydesc2;
 398 {
 399         char            record [ISMAXRECLEN];
 400         char            keybuf [MAXKEYSIZE];
 401         Recno           recnum;
 402         int             reclen = 0;
 403         int             (*rec_read)() = (fcb->varflag?_vlrec_read:_flrec_read);
 404
 405         for (recnum = 1; recnum <= fcb->lastrecno; recnum++) {
 406
 407                 if (rec_read(fcb, record, recnum, &reclen) != ISOK)
 408                         continue;            /* Skip deleted record */
 409
 410                 /*
 411                  * Zero out the entire key buffer to allow for using
 412                  * memcmp() as comparison function to compare whole keys.
 413                  */
 414                 memset(keybuf, 0, pkeydesc2->k2_len);
 415
 416                 /*
 417                  * Extract key parts from record buffer.
 418                  */
 419                 _iskey_extract(pkeydesc2, record, keybuf);
 420
 421                 /*
 422                  *  Add recno to key
 423                  */
 424                 strecno(recnum, keybuf + KEY_RECNO_OFF);
 425
 426                 _issort_insert(srt, keybuf); /* Insert key into sorter */
 427
 428
 429         }
 430 }
 431
 432 /*
 433  * _attach_dups_serial()
 434  *
 435  * Attach serial numbers to duplicate keys
 436  */
 437
 438 Static void
 439 _attach_dups_serial(srt, pkeydesc2)
 440     Issort              *srt;
 441     Keydesc2            *pkeydesc2;
 442 {
 443     int                 netkeylength = pkeydesc2->k2_len - RECNOSIZE - DUPIDSIZE;
 444     char                *curkey;
 445     char                *lastkey = NULL;
 446     int                 dup_serial = 1;
 447
 448     _issort_rewind(srt);
 449
 450     while (curkey = _issort_read(srt)) {
 451         if (lastkey && memcmp(lastkey + RECNOSIZE + DUPIDSIZE,
 452                               curkey + RECNOSIZE + DUPIDSIZE,
 453                                netkeylength) == 0)
 454             dup_serial++;
 455         else
 456             dup_serial = 1;
 457
 458         /*
 459          * Store serial number in the key.
 460          */
 461         stdupser(dup_serial, curkey + KEY_DUPS_OFF);
 462
 463         lastkey = curkey;
 464     }
 465 }
 466
 467 /*
 468  * _buildbtree()
 469  *
 470  * Create B-tree.
 471  */
 472
 473 Static Blkno
 474 _buildbtree(fcb, pkeydesc2, srt)
 475     Fcb                 *fcb;
 476     Keydesc2            *pkeydesc2;
 477     Issort              *srt;
 478 {
 479     Bufhdr              *_allockpage();
 480     int                 depth;
 481     int                 nrecords = fcb->nrecords;
 482     int                 keyspernode[ISMAXBTRLEVEL];
 483     int                 one_more[ISMAXBTRLEVEL];
 484     char                *nodebuf[ISMAXBTRLEVEL];
 485     Bufhdr              *nodebufhd[ISMAXBTRLEVEL];
 486     Blkno               pageblkno[ISMAXBTRLEVEL];
 487     int                 curindex[ISMAXBTRLEVEL];
 488     char                *keyp;
 489     int                 keylength = pkeydesc2->k2_len;
 490     int                 leafcapac = getkeysperleaf(keylength);
 491     int                 nleafcapac = getkeyspernode(keylength);
 492     int                 perleaf;
 493     int                 blocks_in_this_level, blocks_in_prev_level;
 494     int                 slack = ISLEAFSLACK;
 495     int                 i;
 496
 497     /*
 498      * Handle an empty B-tree as a special case.
 499      */
 500     if (fcb->nrecords == 0) {
 501         (void)_allockpage(fcb, leafcapac, 0, pageblkno + 0);
 502         return (pageblkno[0]);
 503     }
 504
 505     /*
 506      * COMPRESS changes the fill factor to 100%
 507      */
 508     if ((pkeydesc2->k2_flags & COMPRESS) == COMPRESS)
 509         slack = 0;
 510
 511     /*
 512      * Figure out fill factors for each level.
 513      */
 514     perleaf = ((double)leafcapac * (100.0 - (double) slack)) / 100.0;
 515
 516     /*
 517      * Make it more robust.
 518      */
 519     if (perleaf >= leafcapac)
 520         perleaf = leafcapac;
 521
 522     if (perleaf < leafcapac/2 + 1)
 523         perleaf = leafcapac/2 + 1;
 524
 525     /*
 526      * Iterativelly determince values in keyspernode[] and one_mode[]
 527      */
 528     blocks_in_this_level = nrecords / perleaf;
 529     if (blocks_in_this_level * leafcapac < nrecords)
 530         blocks_in_this_level++;
 531
 532     keyspernode[0] = nrecords / blocks_in_this_level;
 533     one_more[0] = nrecords % blocks_in_this_level;
 534
 535
 536     for (depth = 1; blocks_in_this_level > 1; depth++) {
 537         blocks_in_prev_level = blocks_in_this_level;
 538
 539         blocks_in_this_level = (blocks_in_prev_level-1) / nleafcapac + 1;
 540         keyspernode[depth] = blocks_in_prev_level / blocks_in_this_level;
 541         one_more[depth] = blocks_in_prev_level % blocks_in_this_level;
 542     }
 543
 544     if (depth >= ISMAXBTRLEVEL)
 545         _isfatal_error("Too many levels in B-tree");
 546
 547     /*
 548      * Make sure that we start reading keys from the beginning.
 549      */
 550     _issort_rewind(srt);
 551
 552     /*
 553      * Boot the Main loop.
 554      */
 555     for (i = 0; i < depth ; i++) {
 556         curindex[i] = ISPAGESIZE;            /* Any big number will do */
 557         one_more[i]++;
 558         nodebufhd[i] = NULL;
 559     }
 560
 561     /*
 562      * Main loop.
 563      */
 564     while ((keyp = _issort_read(srt)) != (char *) NULL) {
 565
 566         if (curindex[0] >= keyspernode[0] + (one_more[0] > 0)) {
 567
 568             /*
 569              * Commit all changed buffers here to avoid buffer pool overflow.
 570              */
 571             if (nodebufhd[0]) {
 572                 _isdisk_commit1(nodebufhd[0]);
 573                 _isdisk_sync();
 574             }
 575
 576             /* Allocate new leaf. */
 577             nodebufhd[0] = _allockpage(fcb, leafcapac, 0, pageblkno+0);
 578             nodebuf[0] = nodebufhd[0]->isb_buffer;
 579             one_more[0]--;
 580             curindex[0] = 0;
 581         }
 582
 583         /* Copy key into the page. */
 584         memcpy( nodebuf[0] + BT_KEYS_OFF + keylength * curindex[0],keyp,
 585               keylength);
 586         stshort((short) curindex[0] + 1, nodebuf[0] + BT_NKEYS_OFF);
 587
 588         if (curindex[0]++ == 0) {            /* Store first key in  */
 589                                              /* higher levels */
 590
 591             for (i = 1;i < depth; i++) {
 592                 if (curindex[i] >= keyspernode[i] + (one_more[i] > 0)) {
 593
 594                     /* Unfix buffer. */
 595                     if (nodebufhd[i])
 596                         _isdisk_commit1(nodebufhd[i]);
 597
 598                     nodebufhd[i] = _allockpage(fcb, nleafcapac, i,  pageblkno+i);
 599                     nodebuf[i] = nodebufhd[i]->isb_buffer;
 600                     one_more[i]--;
 601                     curindex[i] = 0;
 602                 }
 603
 604                 /* Copy key into page. */
 605                 memcpy( nodebuf[i] + BT_KEYS_OFF + keylength * curindex[i],keyp,
 606                        keylength);
 607
 608                 /* Store pointer to level below. */
 609                 stblkno(pageblkno[i-1], nodebuf[i] + ISPAGESIZE -
 610                         (curindex[i]+1) * BLKNOSIZE);
 611
 612                 stshort((short) curindex[i] + 1, nodebuf[i] + BT_NKEYS_OFF);
 613                 if (curindex[i]++ > 0) {
 614                     break;
 615                 }
 616             }
 617         }
 618
 619     }
 620
 621     return (pageblkno [depth - 1]);          /* Return blkno of B-tree root */
 622 }
 623
 624 /*
 625  * _duplicate_exist()
 626  *
 627  * Return 1 if there are duplicates in the sorted key object.
 628  */
 629
 630 Static int _duplicate_exist(srt, keylength)
 631     Issort      *srt;
 632     int         keylength;
 633 {
 634     char        *curkey;
 635     char        *lastkey = (char *) 0;
 636     int         netkeylength = keylength - RECNOSIZE;
 637
 638     _issort_rewind(srt);
 639
 640     while (curkey = _issort_read(srt)) {
 641             if (lastkey && memcmp(lastkey + RECNOSIZE, curkey + RECNOSIZE,
 642                                   netkeylength) == 0)
 643                     return 1;                /* Duplicate key found */
 644
 645             lastkey = curkey;
 646     }
 647     return 0;                                /* No duplicates found */
 648 }
 649
 650
 651
 652 Static
 653 checkavailfd()
 654 {
 655     Fcb                 *fcb;
 656     Bytearray           *isfhandle2;
 657
 658     /*
 659      * Check that there are UNIX file descriptors available.
 660      */
 661     while (_watchfd_check() < 1) {
 662         /*
 663          * Find victim (LRU FCB) and close it.
 664          */
 665         if((isfhandle2 = _mngfcb_victim()) == NULL)
 666             _isfatal_error ("_openfcb() cannot find LRU victim");
 667
 668         fcb = _mngfcb_find(isfhandle2);
 669         (void) _watchfd_decr(_isfcb_nfds(fcb));
 670         _isfcb_close(fcb);
 671         _mngfcb_delete(isfhandle2);
 672     }
 673 }