cde/lib/DtSearch/raima/keyfcns.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 /* $XConsortium: keyfcns.c /main/3 1996/08/12 12:34:31 cde-ibm $ */
  24 /*
  25  *   COMPONENT_NAME: austext
  26  *
  27  *   FUNCTIONS: NODE_WIDTH
  28  *              Pi
  29  *              close_slots
  30  *              d_keyread
  31  *              delete
  32  *              expand
  33  *              key_bldcom
  34  *              key_boundary
  35  *              key_close
  36  *              key_cmpcpy
  37  *              key_delete
  38  *              key_found
  39  *              key_init
  40  *              key_insert
  41  *              key_locpos
  42  *              key_open
  43  *              key_reset
  44  *              key_scan
  45  *              keycmp
  46  *              node_search
  47  *              open_slots
  48  *              split_node
  49  *              split_root
  50  *
  51  *   ORIGINS: 157
  52  *
  53  *   OBJECT CODE ONLY SOURCE MATERIALS
  54  */
  55 /*---------------------------------------------------------------------------
  56    db_VISTA Key File/Field Manipulation Functions
  57    ----------------------------------------------
  58    An implementation of the B-tree indexing method  described in
  59    "Sorting and Searching: The Art of Computer Programming, Vol III",
  60    Knuth, Donald E., Addison-Wesley, 1975. pp 473-480.
  61
  62    A more detailed description of the generic algorithms can be found
  63    in "Fundamentals of Data Structures in Pascal", Horowitz & Sahni,
  64    Computer Science Press, 1984. pp 491-512.
  65
  66    A tutorial survey of B-tree methods can be found in "The Ubiquitous
  67    B-Tree", Comer, D., ACM Computing Surveys, Vol 11, No. 2, June 1979.
  68
  69    (C) Copyright 1985, 1986, 1987 by Raima Corp.
  70
  71 ---------------------------------------------------------------------------*/
  72
  73 /* ********************** EDIT HISTORY *******************************
  74
  75  SCR    DATE    INI                   DESCRIPTION
  76 ----- --------- --- -----------------------------------------------------
  77   158 15-JUN-88 RSC added compliment flag to key_bldcom
  78    42 15-JUN-88 RSC make keynext 4X faster!!
  79       04-Aug-88 RTK MULTI_TASK changes
  80   310 10-Aug-88 RSC cleanup function prototypes
  81   420 16-Sep-88 RTK Several missing FAR pointers
  82   420 16-Sep-88 RTK np_ptr not initialized in d_prkeys
  83   536 06-Jan-89 RSC pointer can go negative in node_search if 1st slot matches
  84       21-Feb-89 RSC add consistency check to key_locpos
  85       16-Mar-89 WLW reset table pointers in d_keyread
  86
  87 */
  88 #include <stdio.h>
  89 #include "vista.h"
  90 #include "dbtype.h"
  91
  92 /* Data definitions used for the B-tree algorithms */
  93
  94 /* node number of root */
  95 #define ROOT_ADDR 1L
  96
  97 /* null node pointer */
  98 #define NULL_NODE -1L
  99
 100 /* index file node structure */
 101 typedef struct {
 102    LONG     last_chgd;    /* date/time of last change of this node */
 103    INT      used_slots;   /* current # of used slots in node */
 104    char     slots[1];     /* start of slot area */
 105 } NODE;
 106 /* Number of used slots plus orphan */
 107 #define  NODE_WIDTH(node)     ((node)->used_slots*slot_len + sizeof(F_ADDR))
 108
 109 /* last status value */
 110 #define KEYEOF -1
 111 #define KEYINIT 0
 112 #define KEYFOUND 1
 113 #define KEYNOTFOUND 2
 114 #define KEYREPOS 3
 115
 116 /* Internal function prototypes */
 117 static int node_search(P1(CONST char FAR *) Pi(DB_ADDR FAR *)
 118                                       Pi(NODE FAR *) Pi(int *) Pi(int *)
 119                                       Pi(F_ADDR *));
 120 static int keycmp(P1(CONST char FAR *) Pi(KEY_SLOT FAR *)
 121                                     Pi(DB_ADDR FAR *));
 122 static int expand(P1(CONST char FAR *) Pi(DB_ADDR) Pi(F_ADDR));
 123 static int split_root(P1(NODE FAR *));
 124 static int split_node(P1(F_ADDR) Pi(NODE FAR *));
 125 static int delete(P0);
 126 static void open_slots(P1(NODE FAR *) Pi(int) Pi(int));
 127 static void close_slots(P1(NODE FAR *) Pi(int) Pi(int));
 128 static void key_found(P1(DB_ADDR *));
 129
 130 #ifdef   ONE_DB
 131 #define  prefix   keyno
 132 #endif
 133
 134 static KEY_INFO FAR *curkey;
 135 static int key_len;
 136 static int key_data;
 137 static int slot_len;
 138 static int max_slots;
 139 static int mid_slot;
 140 static int keyfile;
 141 static INT fldno;
 142 static FIELD_ENTRY FAR *cfld_ptr;
 143 static INT keyno;
 144 #ifndef  ONE_DB
 145 static INT prefix;
 146 #endif
 147 static int unique;
 148
 149
 150 /* Open B-tree key field index processing
 151 */
 152 int
 153 key_open()
 154 {
 155    int fd_lc;                   /* loop control */
 156    long t;               /* total keys thru level l */
 157    int  l;               /* level number */
 158    int i;       /* field subscript */
 159    FIELD_ENTRY FAR *fld_ptr;
 160    KEY_INFO FAR *ki_ptr;
 161    FILE_ENTRY FAR *file_ptr;
 162
 163    /*           child ptr      key number   */
 164    key_data = sizeof(F_ADDR) + sizeof(INT);
 165
 166    /* count total number of key fields */
 167    no_of_keys = 0;
 168    for (fd_lc = size_fd - old_size_fd, fld_ptr = &field_table[old_size_fd];
 169         --fd_lc >= 0; ++fld_ptr) {
 170       if (fld_ptr->fd_key != NOKEY )
 171          ++no_of_keys;
 172    }
 173    if ( no_of_keys ) {
 174       key_info =
 175         /* Macro references must be on one line for some compilers */
 176         (KEY_INFO FAR *)
 177         ALLOC(&db_global.Key_info, no_of_keys*sizeof(KEY_INFO), "key_info");
 178       if ( ! key_info )
 179          return( dberr(S_NOMEMORY) );
 180       for (i = 0, fld_ptr = &field_table[old_size_fd];
 181            i < size_fd; ++i, ++fld_ptr) {
 182          if ( fld_ptr->fd_key != NOKEY ) {
 183             ki_ptr = &key_info[fld_ptr->fd_keyno];
 184             ki_ptr->level = 0;
 185             ki_ptr->lstat = KEYINIT;
 186             ki_ptr->fldno = i;
 187             ki_ptr->keyfile = fld_ptr->fd_keyfile;
 188             ki_ptr->dba = NULL_DBA;
 189             file_ptr = &file_table[fld_ptr->fd_keyfile];
 190             ki_ptr->keyval =
 191                 /* Macro references must be on one line for some compilers */
 192                 ALLOC(&ki_ptr->Keyval, file_ptr->ft_slsize, db_avname);
 193             if ( ! ki_ptr->keyval )
 194                return( dberr(S_NOMEMORY) );
 195             MEM_UNLOCK(&ki_ptr->Keyval);
 196             /* compute maximum possible levels */
 197             for (t = file_ptr->ft_slots, l = 1; t < MAXRECORDS; ++l)
 198                t *= file_ptr->ft_slots;
 199             ki_ptr->max_lvls = ++l;
 200             ki_ptr->node_path =
 201                 (NODE_PATH FAR *)
 202                 ALLOC(&ki_ptr->Node_path, l*sizeof(NODE_PATH), db_avname);
 203             if ( ! ki_ptr->node_path )
 204                return( dberr(S_NOMEMORY) );
 205             byteset(ki_ptr->node_path, 0, l*sizeof(NODE_PATH));
 206             MEM_UNLOCK(&ki_ptr->Node_path);
 207          }
 208       }
 209    }
 210    return( db_status = S_OKAY );
 211 }
 212
 213
 214
 215 /* Close key field processing
 216 */
 217 void key_close()
 218 {
 219    int k;
 220    KEY_INFO FAR *ki_ptr;
 221
 222    if ( key_info ) {
 223       /* free memory allocated for key functions */
 224       for (k = 0, ki_ptr = key_info; k < no_of_keys; ++k, ++ki_ptr) {
 225          MEM_UNLOCK(&ki_ptr->Node_path);
 226          FREE(&ki_ptr->Node_path);
 227          MEM_UNLOCK(&ki_ptr->Keyval);
 228          FREE(&ki_ptr->Keyval);
 229       }
 230       MEM_UNLOCK(&db_global.Key_info);
 231       FREE(&db_global.Key_info);
 232    }
 233 }
 234
 235
 236 /* Initialize key function operation
 237 */
 238 int
 239 key_init(field )
 240 int field;  /* field number to be processed */
 241 {
 242    FIELD_ENTRY FAR *fld_ptr;
 243    FILE_ENTRY FAR *file_ptr;
 244
 245    fld_ptr = &field_table[field];
 246    if ( fld_ptr->fd_key == NOKEY )
 247       return( dberr(S_NOTKEY) );
 248
 249    fldno     = field;
 250    cfld_ptr  = fld_ptr;
 251    keyno     = fld_ptr->fd_keyno;
 252 #ifndef  ONE_DB
 253    prefix    = keyno - curr_db_table->key_offset;
 254 #endif
 255    key_len   = fld_ptr->fd_len;
 256    keyfile   = fld_ptr->fd_keyfile;
 257    file_ptr  = &file_table[keyfile];
 258    slot_len  = file_ptr->ft_slsize;
 259    max_slots = file_ptr->ft_slots;
 260    mid_slot  = max_slots/2;
 261    curkey    = &key_info[keyno];
 262    unique    = (fld_ptr->fd_key == UNIQUE);
 263    dio_setdef( keyfile );
 264
 265    return( db_status = S_OKAY );
 266 }
 267
 268
 269
 270 /* Reset key_info last status to reposition keys on file "fno"
 271 */
 272 int
 273 key_reset(fno )
 274 FILE_NO fno;
 275 {
 276    int i;
 277    KEY_INFO FAR *ki_ptr;
 278
 279    for (i = 0, ki_ptr = key_info; i < no_of_keys; ++i, ++ki_ptr) {
 280       if (((fno == size_ft) || (ki_ptr->keyfile == fno)) &&
 281           ((ki_ptr->lstat == KEYFOUND) || (ki_ptr->lstat == KEYNOTFOUND)))
 282          ki_ptr->lstat = KEYREPOS;
 283    }
 284    return( db_status = S_OKAY );
 285 }
 286
 287
 288
 289 /* Locate proper key position on B-tree
 290 */
 291 int
 292 key_locpos(key_val, dba)
 293 CONST char FAR *key_val; /* key search value */
 294 DB_ADDR FAR *dba;        /* database address of located key */
 295 {
 296    NODE FAR *node;   /* pointer to current node */
 297    F_ADDR child;     /* page number of child node */
 298    F_ADDR pg;        /* page number of current node */
 299    int stat;         /* saves node search status */
 300    int slot, slot_pos;
 301    int match_lvl;    /* lowest level with duplicate key */
 302    NODE_PATH FAR *np_ptr;
 303    char FAR *node_slot_ptr;
 304
 305    match_lvl = -1;
 306    MEM_LOCK(&curkey->Node_path);
 307    for (curkey->level = 0, np_ptr = curkey->node_path, pg = ROOT_ADDR;
 308         TRUE;
 309         ++curkey->level, ++np_ptr, pg = child) {
 310       /* read in next node */
 311       if ( dio_get(pg, (char FAR * FAR *)&node, NOPGHOLD) != S_OKAY ) {
 312          MEM_UNLOCK(&curkey->Node_path);
 313          return( db_status );
 314       }
 315
 316       np_ptr->node = pg;
 317       if ( curkey->level == 0 && node->used_slots == 0 ) {
 318          np_ptr->slot = 0;
 319          curkey->lstat = KEYEOF;
 320          MEM_UNLOCK(&curkey->Node_path);
 321          return( db_status = S_NOTFOUND );
 322       }
 323       else if (node->used_slots == 0)
 324          return( dberr( S_SYSERR ) );   /* non-root nodes can't be empty */
 325
 326       /* search node for key */
 327       stat = node_search(key_val, ((*dba == NULL_DBA) ? NULL : dba), node,
 328                          &slot, &slot_pos, &child);
 329       np_ptr->slot = slot;
 330
 331       node_slot_ptr = &node->slots[slot_pos];
 332       if ( stat == S_OKAY ) {
 333          if ( unique || *dba != NULL_DBA )
 334             break;
 335
 336          /* mark level as having matching key */
 337          match_lvl = curkey->level;
 338
 339          /* save the key value */
 340          bytecpy(&key_type, node_slot_ptr, slot_len);
 341       }
 342       /* check for end of search */
 343       if ( child == NULL_NODE )
 344          break;
 345    }
 346    if ( match_lvl >= 0 ) {
 347       /* set to lowest duplicate key */
 348       curkey->level = match_lvl;
 349       db_status = S_OKAY;
 350       curkey->lstat = KEYFOUND;
 351    }
 352    else if ( stat == S_OKAY ) {
 353       bytecpy(&key_type, node_slot_ptr, slot_len);
 354       db_status = S_OKAY;
 355       curkey->lstat = KEYFOUND;
 356    }
 357    else {
 358       /* key not found - save key at positioned slot */
 359       if ( np_ptr->slot > 0 )
 360          node_slot_ptr -= slot_len;
 361       bytecpy(&key_type, node_slot_ptr, slot_len);
 362       curkey->lstat = KEYNOTFOUND;
 363       db_status = S_NOTFOUND;
 364    }
 365    MEM_UNLOCK(&curkey->Node_path);
 366    MEM_LOCK(&curkey->Keyval);
 367    /* save key value and database address for possible repositioning */
 368    bytecpy(curkey->keyval, key_type.ks.data, key_len);
 369    MEM_UNLOCK(&curkey->Keyval);
 370    bytecpy(&curkey->dba, &key_type.ks.data[key_len], sizeof(DB_ADDR));
 371
 372    /* return database address for d_keyfind */
 373    if ( *dba == NULL_DBA )
 374       bytecpy(dba, &curkey->dba, sizeof(DB_ADDR));
 375
 376    return( db_status );
 377 }
 378
 379
 380
 381 /* Search node for key value
 382 */
 383 static int node_search(key_val, dba, node, slotno, slot_offset,
 384                                          child)
 385 CONST char FAR *key_val; /* key being searched */
 386 DB_ADDR FAR *dba;    /* database address included in comparison if not null */
 387 NODE    FAR *node;   /* node being searched */
 388 int     *slotno; /* slot number of key position in node */
 389 int     *slot_offset; /* slot position offset */
 390 F_ADDR  *child;  /* child ptr of located key */
 391 {
 392    int cmp, i, l, u, slot_pos;
 393    char FAR *node_slot_ptr;
 394
 395    /* perform binary search on node */
 396    l = 0;
 397    u = node->used_slots - 1;
 398    while ( u >= l ) {
 399       i = (l + u)/2;
 400       node_slot_ptr = &node->slots[slot_pos = i*slot_len];
 401       if ( (cmp = keycmp(key_val, (KEY_SLOT FAR *)node_slot_ptr, dba)) < 0 )
 402          u = i - 1;
 403       else if ( cmp > 0 )
 404          l = i + 1;
 405       else if ( i && !unique && !dba ) {
 406          /* backup to lowest duplicate in node */
 407          while (keycmp(key_val, (KEY_SLOT FAR *)(node_slot_ptr -= slot_len),
 408                        dba) == 0) {
 409             slot_pos -= slot_len;
 410             if (--i == 0) goto have_slot;
 411          }
 412          node_slot_ptr += slot_len;
 413          goto have_slot;
 414       }
 415       else
 416          goto have_slot;
 417    }
 418 have_slot:
 419    if ( cmp > 0 ) { /* always return next highest position */
 420       ++i;
 421       node_slot_ptr += slot_len;
 422       slot_pos += slot_len;
 423    }
 424    /* return child pointer from located slot */
 425    bytecpy(child, node_slot_ptr, sizeof(F_ADDR));
 426
 427    /* return slot number */
 428    *slotno = i;
 429    *slot_offset = slot_pos;
 430
 431    return( db_status = (cmp == 0 ? S_OKAY : S_NOTFOUND) );
 432 }
 433
 434
 435
 436 /* Compare key value
 437 */
 438 static int keycmp(key_val, slot, dba)
 439 CONST char FAR *key_val;  /* key value */
 440 KEY_SLOT FAR *slot;    /* pointer to key slot to be compared */
 441 DB_ADDR FAR *dba;     /* database address included in comparison if not null */
 442 {
 443 /*
 444    returns < 0 if key_val < slot
 445            > 0 if key_val > slot
 446            = 0 if key_val == slot
 447 */
 448    int cmp;
 449
 450    if (((cmp = INTcmp((char FAR *)&prefix, (char FAR *)&slot->keyno)) == 0) &&
 451        ((cmp = fldcmp(cfld_ptr, key_val, slot->data)) == 0) &&
 452        dba)
 453       cmp = ADDRcmp(dba, (DB_ADDR FAR *)&slot->data[key_len]);
 454
 455    return( cmp );
 456 }
 457
 458
 459 /* Scan thru key field
 460 */
 461 int
 462 key_scan(fcn, dba )
 463 int fcn;       /* next or prev */
 464 DB_ADDR *dba;  /* db address of scanned record */
 465 {
 466    F_ADDR child;
 467    NODE FAR *node;
 468    NODE_PATH FAR *np_ptr;
 469    char FAR *node_slot_ptr;
 470
 471    /* locate next key on file */
 472    switch ( curkey->lstat ) {
 473       case KEYINIT:
 474       case KEYEOF:
 475          return( key_boundary(((fcn == KEYNEXT) ? KEYFRST : KEYLAST), dba) );
 476       case KEYREPOS:
 477          MEM_LOCK(&curkey->Keyval);
 478          key_locpos(curkey->keyval, &curkey->dba);
 479          MEM_UNLOCK(&curkey->Keyval);
 480          if (db_status != S_OKAY)
 481             break;
 482          /* PASS THROUGH */
 483       case KEYFOUND:
 484          MEM_LOCK(&curkey->Node_path);
 485          if (fcn == KEYNEXT)
 486             ++curkey->node_path[curkey->level].slot;
 487          MEM_UNLOCK(&curkey->Node_path);
 488    }
 489    MEM_LOCK(&curkey->Node_path);
 490    np_ptr = &curkey->node_path[curkey->level];
 491    if (dio_get(np_ptr->node, (char FAR * FAR *)&node, NOPGHOLD) != S_OKAY) {
 492       MEM_UNLOCK(&curkey->Node_path);
 493       return( db_status );
 494    }
 495    node_slot_ptr = &node->slots[np_ptr->slot*slot_len];
 496    bytecpy(&child, node_slot_ptr, sizeof(F_ADDR));
 497    if (child == NULL_NODE) {
 498       if (fcn == KEYPREV) {
 499          --np_ptr->slot;
 500          node_slot_ptr -= slot_len;
 501       }
 502       while (((fcn == KEYNEXT) && (np_ptr->slot >= node->used_slots)) ||
 503              ((fcn == KEYPREV) && (np_ptr->slot < 0))) {
 504          if (curkey->level <= 0) {
 505             /* return end of file */
 506             curkey->lstat = KEYEOF;
 507             MEM_UNLOCK(&curkey->Node_path);
 508             return( db_status = S_NOTFOUND );
 509          }
 510          --curkey->level;
 511          node_slot_ptr = NULL;
 512          if (dio_get((--np_ptr)->node, (char FAR * FAR *)&node,
 513                      NOPGHOLD) != S_OKAY) {
 514             MEM_UNLOCK(&curkey->Node_path);
 515             return( db_status );
 516          }
 517          if (fcn == KEYPREV)
 518             --np_ptr->slot;
 519       }
 520       if (node_slot_ptr == NULL)
 521          node_slot_ptr = &node->slots[np_ptr->slot*slot_len];
 522    }
 523    else do { /* move down to leaf node */
 524       if ( dio_get(child, (char FAR * FAR *)&node, NOPGHOLD) != S_OKAY ) {
 525          MEM_UNLOCK(&curkey->Node_path);
 526          return( db_status );
 527       }
 528       ++curkey->level;
 529       (++np_ptr)->node = child;
 530       if (fcn == KEYNEXT) {
 531          np_ptr->slot = 0;
 532          node_slot_ptr = node->slots;
 533       }
 534       else {
 535          np_ptr->slot = node->used_slots;
 536          node_slot_ptr = &node->slots[np_ptr->slot*slot_len];
 537       }
 538       bytecpy(&child, node_slot_ptr, sizeof(F_ADDR));
 539    } while ( child != NULL_NODE );
 540
 541    if (np_ptr->slot == node->used_slots) {
 542       --np_ptr->slot;
 543       node_slot_ptr -= slot_len;
 544    }
 545
 546    bytecpy(&key_type, node_slot_ptr, slot_len);
 547    if (key_type.ks.keyno == prefix)
 548       key_found(dba);
 549    else {
 550       curkey->lstat = KEYEOF;
 551       db_status = S_NOTFOUND;
 552    }
 553    MEM_UNLOCK(&curkey->Node_path);
 554    return( db_status );
 555 }
 556
 557
 558 /* Key has been found.  Save appropriate information
 559 */
 560 static void key_found(dba)
 561 DB_ADDR *dba;
 562 {
 563    MEM_LOCK(&curkey->Keyval);
 564    /* save key value and database address for possible repositioning */
 565    bytecpy(curkey->keyval, key_type.ks.data, key_len);
 566    MEM_UNLOCK(&curkey->Keyval);
 567    bytecpy(&curkey->dba, &key_type.ks.data[key_len], sizeof(DB_ADDR));
 568
 569    /* return found db addr */
 570    *dba = curkey->dba;
 571
 572    curkey->lstat = KEYFOUND;            /*[42] FOUND a match */
 573    db_status = S_OKAY;
 574 }
 575
 576
 577 /* Find key boundary
 578 */
 579 int
 580 key_boundary(fcn, dba )
 581 int  fcn;     /* KEYFRST or KEYLAST */
 582 DB_ADDR *dba; /* to get dba of first or last key */
 583 {
 584    F_ADDR pg;         /* node number */
 585    NODE FAR *node;        /* pointer to node contents in cache */
 586    int cmp;           /* keycmp result */
 587    int match_lvl;     /* lowest level containing matched key */
 588    int lvl;  /* node_path level variable */
 589    int slot; /* slot position in node */
 590    NODE_PATH FAR *np_ptr;
 591    char FAR *node_slot_ptr;
 592
 593    if ( fcn == KEYFIND ) {
 594       curkey->lstat = KEYINIT;
 595       return( db_status = S_OKAY );
 596    }
 597    curkey->lstat = KEYNOTFOUND;
 598
 599    /* traverse B-tree for first or last key with specified prefix */
 600    match_lvl = -1;
 601    pg = ROOT_ADDR;
 602    MEM_LOCK(&curkey->Node_path);
 603    for (lvl = 0; TRUE; ++lvl) {
 604       /* read next node */
 605       if ( dio_get(pg, (char FAR * FAR *)&node, NOPGHOLD) != S_OKAY ) {
 606          MEM_UNLOCK(&curkey->Node_path);
 607          return( db_status );
 608       }
 609       if ( node->used_slots == 0 ) {
 610          /* must not be anything on file */
 611          curkey->lstat = KEYEOF;
 612          MEM_UNLOCK(&curkey->Node_path);
 613          return( db_status = S_NOTFOUND );
 614       }
 615       if ( fcn == KEYFRST ) {
 616          for (slot = 0, node_slot_ptr = node->slots;
 617               slot < node->used_slots;
 618               ++slot, node_slot_ptr += slot_len) {
 619             if ((cmp = INTcmp((char FAR *)&prefix,
 620                            (char FAR *)(node_slot_ptr + sizeof(F_ADDR)))) <= 0)
 621                break;
 622          }
 623       }
 624       else { /* KEYLAST */
 625          for (slot = node->used_slots - 1,
 626                                  node_slot_ptr = &node->slots[slot*slot_len];
 627               slot >= 0;
 628               --slot, node_slot_ptr -= slot_len) {
 629             if ((cmp = INTcmp((char FAR *)&prefix,
 630                            (char FAR *)(node_slot_ptr + sizeof(F_ADDR)))) >= 0)
 631                break;
 632          }
 633       }
 634       /* save node path position */
 635       np_ptr = &curkey->node_path[lvl];
 636       np_ptr->node = pg;
 637       np_ptr->slot = slot;
 638
 639       if ( cmp == 0 ) {
 640          /* save matched level & key value */
 641          match_lvl = lvl;
 642          bytecpy(&key_type, node_slot_ptr, slot_len);
 643       }
 644       /* fetch appropriate child pointer */
 645       if (fcn == KEYLAST)
 646          node_slot_ptr += slot_len;
 647       bytecpy(&pg, node_slot_ptr, sizeof(F_ADDR));
 648
 649       if ( pg == NULL_NODE ) break;
 650    }
 651    if ( match_lvl >= 0 ) {
 652       curkey->level = match_lvl;
 653       key_found(dba);
 654       curkey->lstat = KEYREPOS;         /*[42] Need to reposition */
 655    }
 656    else {
 657       /* no keys on file with requested prefix */
 658       curkey->level = 0;
 659       curkey->lstat = KEYEOF;
 660       db_status = S_NOTFOUND;
 661    }
 662    MEM_UNLOCK(&curkey->Node_path);
 663    return( db_status );
 664 }
 665
 666
 667 /* Insert key field into B-tree
 668 */
 669 int
 670 key_insert(fld, key_val, dba )
 671 int fld;      /* key field number */
 672 CONST char FAR *key_val; /* key value */
 673 DB_ADDR dba;  /* record's database address */
 674 {
 675    int stat;
 676
 677    /* initialize key function operation */
 678    if ( key_init(fld) != S_OKAY ) return( db_status );
 679
 680    /* locate insertion point */
 681    if ( key_locpos(key_val, &dba) == S_NOTFOUND ) {
 682       /* expand node to include key */
 683       if ( (stat = expand(key_val, dba, NULL_NODE)) == S_OKAY ) {
 684          /* save key value and database address for possible repositioning */
 685          MEM_LOCK(&curkey->Keyval);
 686          bytecpy(curkey->keyval, key_val, key_len);
 687          MEM_UNLOCK(&curkey->Keyval);
 688          curkey->dba = dba;
 689
 690          /* reset key position */
 691          key_reset(curkey->keyfile);
 692       }
 693       db_status = stat;
 694    }
 695    else if ( db_status == S_OKAY )
 696       dberr(S_SYSERR);
 697
 698    return( db_status );
 699 }
 700
 701
 702
 703 /* Expand node for new key
 704 */
 705 static int expand(key_val, dba, brother )
 706 CONST char FAR *key_val;    /* key value */
 707 DB_ADDR dba;     /* record's database address */
 708 F_ADDR brother;  /* page number of brother node */
 709 {
 710    F_ADDR pg;
 711    NODE FAR *node;
 712    NODE_PATH FAR *np_ptr;
 713    int slot_pos;
 714    char FAR *node_slot_ptr;
 715
 716    MEM_LOCK(&curkey->Node_path);
 717    np_ptr = &curkey->node_path[curkey->level];
 718
 719    if (dio_get(pg = np_ptr->node, (char FAR * FAR *)&node, PGHOLD) != S_OKAY) {
 720       MEM_UNLOCK(&curkey->Node_path);
 721       return( db_status );
 722    }
 723    if ( node->used_slots >= max_slots ) {
 724       MEM_UNLOCK(&curkey->Node_path);
 725       return( dberr(S_KEYERR) );
 726    }
 727    node_slot_ptr = &node->slots[slot_pos = np_ptr->slot*slot_len];
 728    open_slots(node, slot_pos, 1);
 729
 730    /* copy brother into opened slot's child pointer */
 731    bytecpy(node_slot_ptr + slot_len, &brother, sizeof(F_ADDR));
 732    /* copy keyno into current slot */
 733    bytecpy(node_slot_ptr + sizeof(F_ADDR), &prefix, sizeof(INT));
 734
 735    node_slot_ptr += key_data;
 736    /* clear slot data area to zeros */
 737    byteset(node_slot_ptr, 0, slot_len - key_data);
 738
 739    /* copy keyval into current slot */
 740    if ( cfld_ptr->fd_type == CHARACTER && cfld_ptr->fd_dim[1] == 0 )
 741       strncpy(node_slot_ptr, key_val, key_len);
 742    else
 743       bytecpy(node_slot_ptr, key_val, key_len);
 744
 745    /* copy database address into current slot */
 746    bytecpy(node_slot_ptr + key_len, &dba, sizeof(DB_ADDR));
 747
 748    if ( node->used_slots == max_slots ) {
 749       if ( pg == ROOT_ADDR )
 750          split_root(node);
 751       else
 752          split_node(pg, node);
 753    }
 754    else
 755       dio_touch(pg);
 756
 757    MEM_UNLOCK(&curkey->Node_path);
 758    return( db_status );
 759 }
 760
 761
 762
 763 /* Split node into two nodes
 764 */
 765 static int split_node(l_pg, l_node )
 766 F_ADDR l_pg;  /* left node's page number */
 767 NODE FAR *l_node; /* left node buffer */
 768 {
 769    F_ADDR r_pg;
 770    NODE FAR *r_node;
 771    char key_val[256];
 772    DB_ADDR dba;
 773    char FAR *l_node_slot_ptr;
 774
 775    /* extract middle key */
 776    l_node_slot_ptr = &l_node->slots[mid_slot*slot_len];
 777    bytecpy(&prefix, l_node_slot_ptr + sizeof(F_ADDR), sizeof(INT));
 778 #ifndef  ONE_DB
 779    keyno = prefix + curr_db_table->key_offset;
 780 #endif
 781    fldno = key_info[keyno].fldno;
 782    cfld_ptr = &field_table[fldno];
 783    key_len = cfld_ptr->fd_len;
 784    bytecpy(key_val, l_node_slot_ptr + key_data, key_len);
 785    bytecpy(&dba, l_node_slot_ptr + key_data + key_len, sizeof(DB_ADDR));
 786
 787    /* divide left node */
 788    l_node->used_slots = mid_slot;
 789
 790    /* allocate new right node */
 791    if ((dio_pzalloc(keyfile, &r_pg) != S_OKAY) ||
 792        (dio_get(r_pg, (char FAR * FAR *)&r_node, PGHOLD) != S_OKAY))
 793       return( db_status );
 794
 795    /* copy slots from left node at slot mid_slot+1 into right node */
 796    r_node->used_slots = max_slots - (mid_slot + 1);
 797    l_node_slot_ptr += slot_len;
 798    bytecpy(r_node->slots, l_node_slot_ptr, NODE_WIDTH(r_node));
 799
 800    dio_touch(l_pg);
 801    dio_touch(r_pg);
 802
 803    --curkey->level;
 804
 805    /* expand parent slot to include middle key and new right node ptr */
 806    return( expand(key_val, dba, r_pg) );
 807 }
 808
 809
 810 /* Split root node
 811 */
 812 static int split_root(node )
 813 NODE FAR *node;
 814 {
 815    F_ADDR l_pg, r_pg;
 816    NODE FAR *l_node, FAR *r_node;
 817    int slot_pos;
 818    char FAR *node_slot_ptr;
 819
 820    /* allocate two new nodes */
 821    if ((dio_pzalloc(keyfile, &l_pg) != S_OKAY) ||
 822        (dio_pzalloc(keyfile, &r_pg) != S_OKAY) ||
 823        (dio_get(l_pg, (char FAR * FAR *)&l_node, PGHOLD) != S_OKAY) ||
 824        (dio_get(r_pg, (char FAR * FAR *)&r_node, PGHOLD) != S_OKAY))
 825       return( db_status );
 826
 827    /* copy 0..max_slots/2-1 keys from root into left node */
 828    l_node->used_slots = mid_slot;
 829    slot_pos = mid_slot*slot_len;
 830    bytecpy(l_node->slots, node->slots, NODE_WIDTH(l_node));
 831
 832    /* copy max_slots/2+1..max_slots from root into right node */
 833    r_node->used_slots = max_slots - (mid_slot + 1);
 834    node_slot_ptr = &node->slots[slot_pos += slot_len];
 835    bytecpy(r_node->slots, node_slot_ptr, NODE_WIDTH(r_node));
 836
 837    /* copy mid_slot into slot[0] of root */
 838    bytecpy(node->slots, node_slot_ptr - slot_len, slot_len);
 839
 840    /* copy left page number into p[0] of root */
 841    bytecpy(node->slots, &l_pg, sizeof(F_ADDR));
 842
 843    /* copy right page number into p[1] of root */
 844    bytecpy(&node->slots[slot_len], &r_pg, sizeof(F_ADDR));
 845
 846    /* reset number of used slots in root */
 847    node->used_slots = 1;
 848
 849    dio_touch(l_pg);
 850    dio_touch(r_pg);
 851    dio_touch(ROOT_ADDR);
 852
 853    return( db_status );
 854 }
 855
 856
 857
 858 /* Delete key from B-tree
 859 */
 860 int
 861 key_delete(fld, key_val, dba )
 862 int fld;
 863 char CONST FAR *key_val;
 864 DB_ADDR dba;
 865 {
 866    int stat;
 867
 868    /* initialize key function operation */
 869    if ( key_init(fld) != S_OKAY ) return( db_status );
 870
 871    /* locate key to be deleted */
 872    if ((stat = key_locpos(key_val, &dba)) == S_OKAY) {
 873       if ( (stat = delete()) == S_OKAY ) {
 874          /* save key value and database address for possible repositioning */
 875          MEM_LOCK(&curkey->Keyval);
 876          bytecpy(curkey->keyval, key_val, key_len);
 877          MEM_UNLOCK(&curkey->Keyval);
 878          curkey->dba = dba;
 879
 880          /* reset key position */
 881          key_reset(curkey->keyfile);
 882       }
 883    }
 884    return( db_status = stat );
 885 }
 886
 887
 888
 889 /* Delete key at current node_path position
 890 */
 891 static int delete()
 892 {
 893    F_ADDR pg, p_pg, l_pg, r_pg;
 894    NODE FAR *node;
 895    NODE FAR *p_node;
 896    NODE FAR *l_node;
 897    NODE FAR *r_node;
 898    int amt, slot_pos;
 899    NODE_PATH FAR *np_ptr;
 900    char FAR *node_slot_ptr;
 901    char FAR *p_node_slot_ptr;
 902    char FAR *l_node_slot_ptr;
 903    char FAR *r_node_slot_ptr;
 904
 905    MEM_LOCK(&curkey->Node_path);
 906    np_ptr = &curkey->node_path[curkey->level];
 907
 908    /* read node containing key to be deleted */
 909    if (dio_get(pg = np_ptr->node, (char FAR * FAR *)&node, PGHOLD) != S_OKAY) {
 910       MEM_UNLOCK(&curkey->Node_path);
 911       return( db_status );
 912    }
 913    /* copy pointer to right sub-tree */
 914    slot_pos = np_ptr->slot*slot_len;
 915    node_slot_ptr = &node->slots[slot_pos];
 916    bytecpy(&r_pg, node_slot_ptr + slot_len, sizeof(F_ADDR));
 917
 918    if ( r_pg != NULL_NODE ) {
 919       /* find leftmost descendent of right sub-tree */
 920       ++np_ptr->slot;
 921       do {
 922          if ( dio_get(r_pg, (char FAR * FAR *)&r_node, NOPGHOLD) != S_OKAY ) {
 923             MEM_UNLOCK(&curkey->Node_path);
 924             return( db_status );
 925          }
 926          ++curkey->level;
 927          ++np_ptr;
 928          np_ptr->node = r_pg;
 929          np_ptr->slot = 0;
 930          bytecpy(&r_pg, r_node->slots, sizeof(F_ADDR));
 931       } while ( r_pg != NULL_NODE );
 932
 933       /* copy key from leaf into node */
 934       node_slot_ptr += sizeof(F_ADDR);
 935       r_node_slot_ptr = &r_node->slots[sizeof(F_ADDR)];
 936       bytecpy(node_slot_ptr, r_node_slot_ptr, slot_len - sizeof(F_ADDR));
 937       dio_touch(pg);
 938
 939       /* set up to delete key from leaf */
 940       /* (this is more efficient than a recursive call) */
 941       slot_pos = 0;
 942       node_slot_ptr = node->slots;
 943       if (dio_get(pg = np_ptr->node, (char FAR * FAR *)&node, PGHOLD) != S_OKAY) {
 944          MEM_UNLOCK(&curkey->Node_path);
 945          return( db_status );
 946       }
 947    }
 948 shrink: /* delete key from leaf (shrink node ) */
 949    close_slots(node, slot_pos, 1);
 950
 951    /* check if necessary to adjust nodes */
 952    if ((curkey->level > 0) && (node->used_slots < mid_slot)) {
 953       /* read in parent node */
 954       if (dio_get(p_pg = (np_ptr - 1)->node, (char FAR * FAR *)&p_node,
 955                   PGHOLD) != S_OKAY) {
 956          MEM_UNLOCK(&curkey->Node_path);
 957          return( db_status );
 958       }
 959       slot_pos = (np_ptr - 1)->slot*slot_len;
 960       node_slot_ptr = &node->slots[slot_pos];
 961       if ((np_ptr - 1)->slot == p_node->used_slots ) {
 962          /* pg is right node */
 963          r_pg = pg;
 964          r_node = node;
 965
 966          /* parent slot position should bisect left & right nodes */
 967          --(np_ptr - 1)->slot;
 968          slot_pos -= slot_len;
 969
 970          /* read left node */
 971          p_node_slot_ptr = &p_node->slots[slot_pos];
 972          bytecpy(&l_pg, p_node_slot_ptr, sizeof(F_ADDR));
 973          if ( dio_get(l_pg, (char FAR * FAR *)&l_node, PGHOLD) != S_OKAY ) {
 974             MEM_UNLOCK(&curkey->Node_path);
 975             return( db_status );
 976          }
 977       }
 978       else {
 979          /* pg is left node */
 980          l_pg = pg;
 981          l_node = node;
 982
 983          /* read right node */
 984          p_node_slot_ptr = &p_node->slots[slot_pos + slot_len];
 985          bytecpy(&r_pg, p_node_slot_ptr, sizeof(F_ADDR));
 986          if (dio_get(r_pg, (char FAR * FAR *)&r_node, PGHOLD) != S_OKAY) {
 987             MEM_UNLOCK(&curkey->Node_path);
 988             return( db_status );
 989          }
 990       }
 991       if ((l_node->used_slots + r_node->used_slots + 1) < max_slots) {
 992          /* combine left and right nodes */
 993          if ((curkey->level == 1) && (p_node->used_slots == 1)) {
 994             /* shrink down to root */
 995             /* copy right node data into root */
 996             p_node_slot_ptr = &p_node->slots[slot_len];
 997             bytecpy(p_node_slot_ptr, r_node->slots, NODE_WIDTH(r_node));
 998             p_node->used_slots = r_node->used_slots + 1;
 999             r_node->used_slots = 0;
1000             dio_touch(r_pg);
1001
1002             /* copy left node data into root */
1003             open_slots(p_node, 0, l_node->used_slots);
1004             bytecpy(p_node->slots, l_node->slots, NODE_WIDTH(l_node));
1005             l_node->used_slots = 0;
1006             dio_touch(l_pg);
1007
1008             dio_touch(p_pg);
1009
1010             /* free node pages */
1011             dio_pzdel(keyfile, r_pg);
1012             dio_pzdel(keyfile, l_pg);
1013             MEM_UNLOCK(&curkey->Node_path);
1014             return( db_status );
1015          }
1016          /* open space for l_node->used_slots+1 slots in right node */
1017          open_slots(r_node, 0, l_node->used_slots + 1);
1018
1019          /* move left node slots into right node */
1020          amt = NODE_WIDTH(l_node);
1021          r_node_slot_ptr = r_node->slots;
1022          bytecpy(r_node_slot_ptr, l_node->slots, amt);
1023
1024          /* move parent slot data into right node */
1025          r_node_slot_ptr += amt;
1026          p_node_slot_ptr = &p_node->slots[slot_pos + sizeof(F_ADDR)];
1027          bytecpy(r_node_slot_ptr, p_node_slot_ptr, slot_len - sizeof(F_ADDR));
1028
1029          dio_touch(r_pg);
1030          dio_touch(l_pg);
1031
1032          /* delete left node */
1033          l_node->used_slots = 0;
1034          if ( dio_pzdel(keyfile, l_pg) != S_OKAY ) {
1035             MEM_UNLOCK(&curkey->Node_path);
1036             return( db_status );
1037          }
1038          /* decrement level & make parent node current node */
1039          --curkey->level;
1040          --np_ptr;
1041          pg = p_pg;
1042          node = p_node;
1043          goto shrink;  /* delete slot from parent */
1044       }
1045       /* acquire needed key from sibling */
1046       if ((l_node->used_slots + 1) < r_node->used_slots) {
1047          /* get key from right node */
1048
1049          /* move parent slot to end of left node */
1050          l_node_slot_ptr = &l_node->slots[NODE_WIDTH(l_node)];
1051          p_node_slot_ptr = &p_node->slots[slot_pos + sizeof(F_ADDR)];
1052          bytecpy(l_node_slot_ptr, p_node_slot_ptr, slot_len - sizeof(F_ADDR));
1053
1054          ++l_node->used_slots;
1055
1056          /* copy slot 0 child from right node to left node orphan */
1057          l_node_slot_ptr += slot_len - sizeof(F_ADDR);
1058          r_node_slot_ptr = r_node->slots;
1059          bytecpy(l_node_slot_ptr, r_node_slot_ptr, sizeof(F_ADDR));
1060
1061          /* move slot 0 of right node to parent */
1062          r_node_slot_ptr += sizeof(F_ADDR);
1063          bytecpy(p_node_slot_ptr, r_node_slot_ptr, slot_len - sizeof(F_ADDR));
1064
1065          /* delete slot 0 from right node */
1066          close_slots(r_node, 0, 1);
1067       }
1068       else if ((r_node->used_slots + 1) < l_node->used_slots) {
1069          /* get key from left node */
1070
1071          /* open one slot at front of right node */
1072          open_slots(r_node, 0, 1);
1073
1074          /* move parent slot to slot 0 of right node */
1075          r_node_slot_ptr = &r_node->slots[sizeof(F_ADDR)];
1076          p_node_slot_ptr = &p_node->slots[slot_pos + sizeof(F_ADDR)];
1077          bytecpy(r_node_slot_ptr, p_node_slot_ptr, slot_len - sizeof(F_ADDR));
1078
1079          /* move end slot of left node to parent */
1080          l_node_slot_ptr = &l_node->slots[NODE_WIDTH(l_node) - slot_len];
1081          bytecpy(p_node_slot_ptr, l_node_slot_ptr, slot_len - sizeof(F_ADDR));
1082
1083          /* move left orphan to child of slot 0 in right node */
1084          l_node_slot_ptr += slot_len - sizeof(F_ADDR);
1085          bytecpy(r_node->slots, l_node_slot_ptr, sizeof(F_ADDR));
1086
1087          /* delete end slot from left node */
1088          --l_node->used_slots;
1089       }
1090       dio_touch(l_pg);
1091       dio_touch(r_pg);
1092       dio_touch(p_pg);
1093    }
1094    else {
1095       dio_touch(pg);
1096    }
1097    MEM_UNLOCK(&curkey->Node_path);
1098    return( db_status );
1099 }
1100
1101
1102
1103 /* Open n slots in node
1104 */
1105 static void open_slots(node, slot_pos, n)
1106 NODE FAR *node;
1107 int slot_pos;
1108 int n;
1109 {
1110    char FAR *dst, FAR *src;
1111    int amt, w, nw;
1112
1113    nw = NODE_WIDTH(node);
1114    w = n*slot_len;
1115    src = &node->slots[nw];
1116    dst = src + w;
1117    amt = nw - slot_pos;
1118    while (amt--)
1119       *--dst = *--src;
1120
1121    node->used_slots += n;
1122 }
1123
1124
1125
1126 /* Close n slots in node
1127 */
1128 static void close_slots(node, slot_pos, n)
1129 NODE FAR *node;
1130 int slot_pos;
1131 int n;
1132 {
1133    char FAR *dst, FAR *src;
1134    int w, amt;
1135
1136    node->used_slots -= n;
1137
1138    w = n*slot_len;
1139    dst = &node->slots[slot_pos];
1140    src = dst + w;
1141    amt = NODE_WIDTH(node) - slot_pos;
1142    while (amt--)
1143       *dst++ = *src++;
1144 }
1145
1146
1147
1148
1149 /* Read value of last key scanned
1150 */
1151 int
1152 d_keyread(key_val TASK_PARM)
1153 char FAR *key_val;
1154 TASK_DECL
1155 {
1156    int kt_lc;                   /* loop control */
1157 #ifndef  NO_FLOAT
1158    float fv;
1159    double dv;
1160 #endif
1161    char FAR *fptr;
1162    char FAR *kptr;
1163    FIELD_ENTRY FAR *fld_ptr;
1164    KEY_ENTRY FAR *key_ptr;
1165
1166    DB_ENTER(NO_DB_ID TASK_ID LOCK_SET(RECORD_IO));
1167
1168    if ((curkey->lstat != KEYFOUND) &&
1169        (curkey->lstat != KEYNOTFOUND) &&
1170        (curkey->lstat != KEYREPOS)) {
1171       RETURN( dberr(S_KEYSEQ) );
1172    }
1173    /* clear key area */
1174    byteset(key_val, '\0', cfld_ptr->fd_len);
1175
1176    if ( cfld_ptr->fd_type == COMKEY ) {
1177       /* copy compound key fields */
1178       for (kt_lc = size_kt - cfld_ptr->fd_ptr,
1179                                 key_ptr = &key_table[cfld_ptr->fd_ptr];
1180            (--kt_lc >= 0) && (key_ptr->kt_key == fldno); ++key_ptr) {
1181          fld_ptr = &field_table[key_ptr->kt_field];
1182          fptr = key_type.ks.data + key_ptr->kt_ptr;
1183          kptr = key_val + key_ptr->kt_ptr;
1184          if ( key_ptr->kt_sort == 'd' ) {
1185             switch ( fld_ptr->fd_type ) {
1186 #ifndef  NO_FLOAT
1187                case FLOAT:
1188                   bytecpy(&fv, fptr, sizeof(float));
1189                   fv = (float)0.0 - fv;
1190                   bytecpy(kptr, &fv, sizeof(float));
1191                   break;
1192                case DOUBLE:
1193                   bytecpy(&dv, fptr, sizeof(double));
1194                   dv = 0.0 - dv;
1195                   bytecpy(kptr, &dv, sizeof(double));
1196                   break;
1197 #endif
1198                case CHARACTER:
1199                   key_cmpcpy(kptr, fptr, fld_ptr->fd_len);
1200                   if ( fld_ptr->fd_dim[0] > 1 && fld_ptr->fd_dim[1] == 0 ) {
1201                      /* make sure a null byte is at the end */
1202                      kptr[fld_ptr->fd_len-1] = '\0';
1203                   }
1204                   break;
1205                default:
1206                   key_cmpcpy(kptr, fptr, fld_ptr->fd_len);
1207             }
1208          }
1209          else {
1210             bytecpy(kptr, fptr, fld_ptr->fd_len);
1211          }
1212       }
1213    }
1214    else if ( cfld_ptr->fd_type == CHARACTER && cfld_ptr->fd_dim[1] == 0 )
1215       strncpy(key_val, key_type.ks.data, key_len);
1216    else
1217       bytecpy(key_val, key_type.ks.data, key_len);
1218
1219    RETURN( db_status = S_OKAY );
1220 }
1221
1222
1223
1224 /* Build compound key value from record
1225 */
1226 int
1227 key_bldcom(fld, rec, key, cflag )
1228 int   fld; /* compound key field number */
1229 char FAR *rec; /* ptr to record data */
1230 char FAR *key; /* ptr to array to recv constructed key */
1231 int cflag; /* TRUE to compliment compound descending keys */
1232 {
1233    int kt_lc;                   /* loop control */
1234 #ifndef  NO_FLOAT
1235    float fv;
1236    double dv;
1237 #endif
1238    char FAR *fptr;
1239    FIELD_ENTRY FAR *fld_ptr, FAR *kfld_ptr;
1240    KEY_ENTRY FAR *key_ptr;
1241
1242    /* clear key area */
1243    fld_ptr = &field_table[fld];
1244    byteset(key, '\0', fld_ptr->fd_len);
1245
1246    /* create compound key value */
1247    rec -= record_table[fld_ptr->fd_rec].rt_data;
1248    for (kt_lc = size_kt - fld_ptr->fd_ptr,
1249                                         key_ptr = &key_table[fld_ptr->fd_ptr];
1250         (--kt_lc >= 0) && (key_ptr->kt_key == fld); ++key_ptr) {
1251       kfld_ptr = &field_table[key_ptr->kt_field];
1252       fptr = rec + kfld_ptr->fd_ptr;
1253
1254       /* Complement descending keys if permitted (cflag) */
1255       if ( cflag && ( key_ptr->kt_sort == 'd' )) {
1256          switch ( kfld_ptr->fd_type ) {
1257 #ifndef  NO_FLOAT
1258             case FLOAT:
1259                bytecpy(&fv, fptr, sizeof(float));
1260                fv = (float)0.0 - fv;
1261                bytecpy(&key[key_ptr->kt_ptr], &fv, sizeof(float));
1262                break;
1263             case DOUBLE:
1264                bytecpy(&dv, fptr, sizeof(double));
1265                dv = 0.0 - dv;
1266                bytecpy(&key[key_ptr->kt_ptr], &dv, sizeof(double));
1267                break;
1268 #endif
1269             case CHARACTER:
1270                key_cmpcpy(key+key_ptr->kt_ptr, fptr, kfld_ptr->fd_len);
1271                if ( kfld_ptr->fd_dim[0] > 1 && kfld_ptr->fd_dim[1] == 0 ) {
1272                   /* make sure a null byte is at the end */
1273                   *(key + key_ptr->kt_ptr + kfld_ptr->fd_len - 1) = '\0';
1274                }
1275                break;
1276             default:
1277                key_cmpcpy(key+key_ptr->kt_ptr, fptr, kfld_ptr->fd_len);
1278          }
1279       }
1280       else {
1281          bytecpy(&key[key_ptr->kt_ptr], fptr, kfld_ptr->fd_len);
1282       }
1283    }
1284    return( db_status = S_OKAY );
1285 }
1286
1287
1288
1289 /* Complement and copy bytes
1290 */
1291 void key_cmpcpy(s1, s2, n)
1292 char FAR *s1;
1293 char FAR *s2;
1294 INT n;
1295 {
1296    while ( n-- ) {
1297       *s1++ = ~(*s2++);
1298    }
1299 }
1300 /* vpp -nOS2 -dUNIX -nBSD -nVANILLA_BSD -nVMS -nMEMLOCK -nWINDOWS -nFAR_ALLOC -f/usr/users/master/config/nonwin keyfcns.c */