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