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