2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
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)
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
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
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 $ */
29 * Copyright (c) 1988 by Sun Microsystems, Inc.
41 #include "isam_impl.h"
42 #include <sys/types.h>
45 extern int _iskeycmp();
47 static void _readallrecords(), _attach_dups_serial();
48 static Blkno _buildbtree();
49 static int _duplicate_exist();
50 static void checkavailfd(void);
53 * _amaddindex(isfhandle, keydesc, errcode)
55 * _amaddindex() build a secondary index
58 * isfhandle Handle of ISAM file
59 * keydesc Key descriptor
62 * errcode error status of the operation
68 _amaddindex(Bytearray *isfhandle, struct keydesc *keydesc, struct errcode *errcode)
78 * Check if 1 UNIX file decriptor is available.
83 * Get FCB corresponding to the isfhandle handle.
85 if ((fcb = _openfcb(isfhandle, errcode)) == NULL) {
91 * Check that the limit on the number of keys is not exceeded.
93 if (fcb->nkeys >= MAXNKEYS) {
94 _amseterrcode(errcode, ETOOMANY);
99 * Update information in FCB from CNTL page on the disk
101 (void)_isfcb_cntlpg_r(fcb);
104 * Check key descriptor for validity.
106 if (_validate_keydesc(keydesc, fcb->minreclen) != ISOK) {
107 _amseterrcode(errcode, EBADKEY);
112 * Convert key descriptor to internal form.
114 _iskey_xtoi (&keydesc2, keydesc);
116 /* Check if key already exists. */
117 if (_isfcb_findkey(fcb ,&keydesc2) != (Keydesc2 *) 0) {
118 _amseterrcode(errcode, EKEXISTS);
123 * Open (or even create) .ind file if that is not open (created) yet.
125 if (_open2_indfile(fcb) != ISOK) {
126 _amseterrcode(errcode, EACCES);
131 * Create index structure.
133 if ((err = _create_index(fcb ,&keydesc2)) != ISOK) {
134 _amseterrcode(errcode, err);
139 * Add key descriptor to FCB.
141 if (_isfcb_altkeyadd(fcb, &keydesc2) == ISERROR) {
142 _amseterrcode(errcode, ETOOMANY);
146 _amseterrcode(errcode, ISOK);
154 * Update CNTL Page from the FCB.
156 (void)_isfcb_cntlpg_w(fcb);
168 * Restore FCB from CNTL page.
170 if (fcb) (void)_isfcb_cntlpg_r(fcb);
177 * _amaddprimary(isfhandle, keydesc, errcode)
179 * _amaddprimary() build primary key
182 * isfhandle Handle of ISAM file
183 * keydesc Key descriptor
186 * errcode error status of the operation
192 _amaddprimary(Bytearray *isfhandle, struct keydesc *keydesc, struct errcode *errcode)
201 * Check if 1 UNIX file decriptor is available.
206 * Get FCB corresponding to the isfhandle handle.
208 if ((fcb = _openfcb(isfhandle, errcode)) == NULL) {
214 * Check that the limit on the numbrer of keys is not exceeded.
216 if (fcb->nkeys >= MAXNKEYS) {
217 _amseterrcode(errcode, ETOOMANY);
222 * Update information in FCB from CNTL page on the disk
224 (void)_isfcb_cntlpg_r(fcb);
227 * Check key descriptor for validity.
229 if (_validate_keydesc(keydesc, fcb->minreclen) != ISOK) {
230 _amseterrcode(errcode, EBADKEY);
235 * Convert key descriptor to internal form.
237 _iskey_xtoi (&keydesc2, keydesc);
239 /* Check if key already exists. */
240 if (_isfcb_findkey(fcb ,&keydesc2) != (Keydesc2 *) 0) {
241 _amseterrcode(errcode, EKEXISTS);
246 * Check that primary key does not already exist.
248 if (!FCB_NOPRIMARY_KEY(fcb)) {
249 _amseterrcode(errcode, EKEXISTS);
254 * Open (or even create) .ind file if that is not open (created) yet.
256 if (_open2_indfile(fcb) != ISOK) {
257 _amseterrcode(errcode, EACCES);
262 * Create index structure.
264 if ((err = _create_index(fcb ,&keydesc2)) != ISOK) {
265 _amseterrcode(errcode, err);
270 * Add key descriptor to FCB.
272 if (_isfcb_primkeyadd(fcb, &keydesc2) == ISERROR) {
273 _amseterrcode(errcode, ETOOMANY);
277 _amseterrcode(errcode, ISOK);
285 * Update CNTL Page from the FCB.
287 (void)_isfcb_cntlpg_w(fcb);
298 * Restore FCB from CNTL page.
300 if (fcb) (void)_isfcb_cntlpg_r(fcb);
309 * Read data file, extract key from record, sort keys, create index.
310 * Check unique constraint, create duplicate serial numbers.
313 int _create_index(Fcb *fcb, Keydesc2 *pkeydesc2)
316 int keylength = pkeydesc2->k2_len;
319 * Set comparison function for sorting.
321 * nparts + 1 is used to compare keys that allow duplicates.
322 * The (nparts + 1) comparison will never be reached on ISNODUPS key.
324 _iskeycmp_set(pkeydesc2, pkeydesc2->k2_nparts+1);
327 * Handle empty file as a special case, to avoid nasty behavior
328 * in buildbtree() arithmetics.
330 if (fcb->nrecords == 0L) {
331 pkeydesc2->k2_rootnode = _buildbtree(fcb, pkeydesc2, (Issort *) NULL);
337 * Create a sorter for this key descriptor.
339 srt = _issort_create(keylength, (int)fcb->nrecords, _iskeycmp);
342 * Read sequentially all records, extract keys, and
343 * insert the keys into the sorter.
345 _readallrecords(fcb, srt, pkeydesc2);
347 _issort_sort(srt); /* Sort the keys */
350 * Check for potential duplicates if the index is ISNODUPS.
352 if (!ALLOWS_DUPS2(pkeydesc2)) {
353 if (_duplicate_exist(srt, keylength)) {
354 _issort_destroy(srt);
360 * Attach duplicate serial numbers to the keys that are ISDUPS.
362 if (ALLOWS_DUPS2(pkeydesc2)) {
363 _attach_dups_serial(srt, pkeydesc2);
367 * Allocate and build the B-tree
369 pkeydesc2->k2_rootnode = _buildbtree(fcb, pkeydesc2, srt);
371 _issort_destroy(srt); /* Destroy sorter */
379 * REad all records, extract keys, and insert them into sorter.
383 _readallrecords(Fcb *fcb, Issort *srt, Keydesc2 *pkeydesc2)
385 char record [ISMAXRECLEN];
386 char keybuf [MAXKEYSIZE];
389 int (*rec_read)() = (fcb->varflag?_vlrec_read:_flrec_read);
391 for (recnum = 1; recnum <= fcb->lastrecno; recnum++) {
393 if (rec_read(fcb, record, recnum, &reclen) != ISOK)
394 continue; /* Skip deleted record */
397 * Zero out the entire key buffer to allow for using
398 * memcmp() as comparison function to compare whole keys.
400 memset(keybuf, 0, pkeydesc2->k2_len);
403 * Extract key parts from record buffer.
405 _iskey_extract(pkeydesc2, record, keybuf);
410 strecno(recnum, keybuf + KEY_RECNO_OFF);
412 _issort_insert(srt, keybuf); /* Insert key into sorter */
419 * _attach_dups_serial()
421 * Attach serial numbers to duplicate keys
425 _attach_dups_serial(Issort *srt, Keydesc2 *pkeydesc2)
427 int netkeylength = pkeydesc2->k2_len - RECNOSIZE - DUPIDSIZE;
429 char *lastkey = NULL;
434 while ((curkey = _issort_read(srt))) {
435 if (lastkey && memcmp(lastkey + RECNOSIZE + DUPIDSIZE,
436 curkey + RECNOSIZE + DUPIDSIZE,
443 * Store serial number in the key.
445 stdupser(dup_serial, curkey + KEY_DUPS_OFF);
458 _buildbtree(Fcb *fcb, Keydesc2 *pkeydesc2, Issort *srt)
460 Bufhdr *_allockpage();
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];
470 int keylength = pkeydesc2->k2_len;
471 int leafcapac = getkeysperleaf(keylength);
472 int nleafcapac = getkeyspernode(keylength);
474 int blocks_in_this_level, blocks_in_prev_level;
475 int slack = ISLEAFSLACK;
479 * Handle an empty B-tree as a special case.
481 if (fcb->nrecords == 0) {
482 (void)_allockpage(fcb, leafcapac, 0, pageblkno + 0);
483 return (pageblkno[0]);
487 * COMPRESS changes the fill factor to 100%
489 if ((pkeydesc2->k2_flags & COMPRESS) == COMPRESS)
493 * Figure out fill factors for each level.
495 perleaf = ((double)leafcapac * (100.0 - (double) slack)) / 100.0;
498 * Make it more robust.
500 if (perleaf >= leafcapac)
503 if (perleaf < leafcapac/2 + 1)
504 perleaf = leafcapac/2 + 1;
507 * Iterativelly determince values in keyspernode[] and one_mode[]
509 blocks_in_this_level = nrecords / perleaf;
510 if (blocks_in_this_level * leafcapac < nrecords)
511 blocks_in_this_level++;
513 keyspernode[0] = nrecords / blocks_in_this_level;
514 one_more[0] = nrecords % blocks_in_this_level;
517 for (depth = 1; blocks_in_this_level > 1; depth++) {
518 blocks_in_prev_level = blocks_in_this_level;
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;
525 if (depth >= ISMAXBTRLEVEL)
526 _isfatal_error("Too many levels in B-tree");
529 * Make sure that we start reading keys from the beginning.
534 * Boot the Main loop.
536 for (i = 0; i < depth ; i++) {
537 curindex[i] = ISPAGESIZE; /* Any big number will do */
546 while ((keyp = _issort_read(srt)) != (char *) NULL) {
548 if (curindex[0] >= keyspernode[0] + (one_more[0] > 0)) {
551 * Commit all changed buffers here to avoid buffer pool overflow.
554 _isdisk_commit1(nodebufhd[0]);
558 /* Allocate new leaf. */
559 nodebufhd[0] = _allockpage(fcb, leafcapac, 0, pageblkno+0);
560 nodebuf[0] = nodebufhd[0]->isb_buffer;
565 /* Copy key into the page. */
566 memcpy( nodebuf[0] + BT_KEYS_OFF + keylength * curindex[0],keyp,
568 stshort((short) curindex[0] + 1, nodebuf[0] + BT_NKEYS_OFF);
570 if (curindex[0]++ == 0) { /* Store first key in */
573 for (i = 1;i < depth; i++) {
574 if (curindex[i] >= keyspernode[i] + (one_more[i] > 0)) {
578 _isdisk_commit1(nodebufhd[i]);
580 nodebufhd[i] = _allockpage(fcb, nleafcapac, i, pageblkno+i);
581 nodebuf[i] = nodebufhd[i]->isb_buffer;
586 /* Copy key into page. */
587 memcpy( nodebuf[i] + BT_KEYS_OFF + keylength * curindex[i],keyp,
590 /* Store pointer to level below. */
591 stblkno(pageblkno[i-1], nodebuf[i] + ISPAGESIZE -
592 (curindex[i]+1) * BLKNOSIZE);
594 stshort((short) curindex[i] + 1, nodebuf[i] + BT_NKEYS_OFF);
595 if (curindex[i]++ > 0) {
603 return (pageblkno [depth - 1]); /* Return blkno of B-tree root */
609 * Return 1 if there are duplicates in the sorted key object.
612 Static int _duplicate_exist(Issort *srt, int keylength)
615 char *lastkey = (char *) 0;
616 int netkeylength = keylength - RECNOSIZE;
620 while ((curkey = _issort_read(srt))) {
621 if (lastkey && memcmp(lastkey + RECNOSIZE, curkey + RECNOSIZE,
623 return 1; /* Duplicate key found */
627 return 0; /* No duplicates found */
636 Bytearray *isfhandle2;
639 * Check that there are UNIX file descriptors available.
641 while (_watchfd_check() < 1) {
643 * Find victim (LRU FCB) and close it.
645 if((isfhandle2 = _mngfcb_victim()) == NULL)
646 _isfatal_error ("_openfcb() cannot find LRU victim");
648 fcb = _mngfcb_find(isfhandle2);
649 (void) _watchfd_decr(_isfcb_nfds(fcb));
651 _mngfcb_delete(isfhandle2);