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