db2/hash/hash.src

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996, 1997, 1998
   5  *      Sleepycat Software.  All rights reserved.
   6  */
   7 /*
   8  * Copyright (c) 1995, 1996
   9  *      Margo Seltzer.  All rights reserved.
  10  */
  11 /*
  12  * Copyright (c) 1995, 1996
  13  *      The President and Fellows of Harvard University.  All rights reserved.
  14  *
  15  * This code is derived from software contributed to Berkeley by
  16  * Margo Seltzer.
  17  *
  18  * Redistribution and use in source and binary forms, with or without
  19  * modification, are permitted provided that the following conditions
  20  * are met:
  21  * 1. Redistributions of source code must retain the above copyright
  22  *    notice, this list of conditions and the following disclaimer.
  23  * 2. Redistributions in binary form must reproduce the above copyright
  24  *    notice, this list of conditions and the following disclaimer in the
  25  *    documentation and/or other materials provided with the distribution.
  26  * 3. All advertising materials mentioning features or use of this software
  27  *    must display the following acknowledgement:
  28  *      This product includes software developed by the University of
  29  *      California, Berkeley and its contributors.
  30  * 4. Neither the name of the University nor the names of its contributors
  31  *    may be used to endorse or promote products derived from this software
  32  *    without specific prior written permission.
  33  *
  34  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  35  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  36  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  37  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  38  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  39  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  40  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  41  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  42  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  43  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  44  * SUCH DAMAGE.
  45  *
  46  *      @(#)hash.src    10.3 (Sleepycat) 4/10/98
  47  */
  48
  49 /*
  50  * This is the source file used to create the logging functions for the
  51  * hash package.  Each access method (or set of routines wishing to register
  52  * record types with the transaction system) should have a file like this.
  53  * Each type of log record and its parameters is defined.  The basic
  54  * format of a record definition is:
  55  *
  56  * BEGIN        <RECORD_TYPE>
  57  * ARG|STRING|POINTER   <variable name> <variable type> <printf format>
  58  * ...
  59  * END
  60  * ARG the argument is a simple parameter of the type * specified.
  61  * DBT the argument is a DBT (db.h) containing a length and pointer.
  62  * PTR the argument is a pointer to the data type specified; the entire
  63  *     type should be logged.
  64  *
  65  * There are a set of shell scripts of the form xxx.sh that generate c
  66  * code and or h files to process these.  (This is probably better done
  67  * in a single PERL script, but for now, this works.)
  68  *
  69  * The DB recovery system requires the following three fields appear in
  70  * every record, and will assign them to the per-record-type structures
  71  * as well as making them the first parameters to the appropriate logging
  72  * call.
  73  * rectype:     record-type, identifies the structure and log/read call
  74  * txnid:       transaction id, a DBT in this implementation
  75  * prev:        the last LSN for this transaction
  76  */
  77
  78 /*
  79  * Use the argument of PREFIX as the prefix for all record types,
  80  * routines, id numbers, etc.
  81  */
  82 PREFIX  ham
  83
  84 /*
  85  * HASH-insdel: used for hash to insert/delete a pair of entries onto a master
  86  * page. The pair might be regular key/data pairs or they might be the
  87  * structures that refer to off page items, duplicates or offpage duplicates.
  88  *  opcode - PUTPAIR/DELPAIR + big masks
  89  *  fileid - identifies the file referenced
  90  *  pgno - page within file
  91  *  ndx - index on the page of the item being added (item index)
  92  *  pagelsn - lsn on the page before the update
  93  *  key - the key being inserted
  94  *  data - the data being inserted
  95  */
  96 BEGIN insdel
  97 ARG     opcode          u_int32_t       lu
  98 ARG     fileid          u_int32_t       lu
  99 ARG     pgno            db_pgno_t       lu
 100 ARG     ndx             u_int32_t       lu
 101 POINTER pagelsn         DB_LSN *        lu
 102 DBT     key             DBT             s
 103 DBT     data            DBT             s
 104 END
 105
 106 /*
 107  * Used to add and remove overflow pages.
 108  * prev_pgno is the previous page that is going to get modified to
 109  *      point to this one.  If this is the first page in a chain
 110  *      then prev_pgno should be PGNO_INVALID.
 111  * new_pgno is the page being allocated.
 112  * next_pgno is the page that follows this one.  On allocation,
 113  *      this should be PGNO_INVALID.  For deletes, it may exist.
 114  * pagelsn is the old lsn on the page.
 115  */
 116 BEGIN newpage
 117 ARG     opcode          u_int32_t       lu
 118 ARG     fileid          u_int32_t       lu
 119 ARG     prev_pgno       db_pgno_t       lu
 120 POINTER prevlsn         DB_LSN *        lu
 121 ARG     new_pgno        db_pgno_t       lu
 122 POINTER pagelsn         DB_LSN *        lu
 123 ARG     next_pgno       db_pgno_t       lu
 124 POINTER nextlsn         DB_LSN *        lu
 125 END
 126
 127 /*
 128  * Splitting requires two types of log messages.  The first
 129  * logs the meta-data of the split.  The second logs the
 130  * data on the original page.  To redo the split, we have
 131  * to visit the new page (pages) and add the items back
 132  * on the page if they are not yet there.
 133  * For the meta-data split
 134  *      bucket: max_bucket in table before split
 135  *      ovflpoint: overflow point before split.
 136  *      spares: spares[ovflpoint] before split.
 137  */
 138 BEGIN splitmeta
 139 ARG     fileid          u_int32_t       lu
 140 ARG     bucket          u_int32_t       lu
 141 ARG     ovflpoint       u_int32_t       lu
 142 ARG     spares          u_int32_t       lu
 143 POINTER metalsn         DB_LSN *        lu
 144 END
 145
 146 BEGIN splitdata
 147 ARG     fileid          u_int32_t       lu
 148 ARG     opcode          u_int32_t       lu
 149 ARG     pgno            db_pgno_t       lu
 150 DBT     pageimage       DBT             s
 151 POINTER pagelsn         DB_LSN *        lu
 152 END
 153
 154 /*
 155  * HASH-replace: is used for hash to handle partial puts that only
 156  * affect a single master page.
 157  *  fileid - identifies the file referenced
 158  *  pgno - page within file
 159  *  ndx - index on the page of the item being modified (item index)
 160  *  pagelsn - lsn on the page before the update
 161  *  off - offset in the old item where the new item is going.
 162  *  olditem - DBT that describes the part of the item being replaced.
 163  *  newitem - DBT of the new item.
 164  *  makedup - this was a replacement that made an item a duplicate.
 165  */
 166 BEGIN replace
 167 ARG     fileid          u_int32_t       lu
 168 ARG     pgno            db_pgno_t       lu
 169 ARG     ndx             u_int32_t       lu
 170 POINTER pagelsn         DB_LSN *        lu
 171 ARG     off             int32_t         ld
 172 DBT     olditem         DBT             s
 173 DBT     newitem         DBT             s
 174 ARG     makedup         u_int32_t       lu
 175 END
 176
 177 /*
 178  * HASH-newpgno: is used to record getting/deleting a new page number.
 179  * This doesn't require much data modification, just modifying the
 180  * meta-data.
 181  * pgno is the page being allocated/freed.
 182  * free_pgno is the next_pgno on the free list.
 183  * old_type was the type of a page being deallocated.
 184  * old_pgno was the next page number before the deallocation.  We use it
 185  *      to indicate whether we incremented the spares count or not
 186  *      during this allocation.
 187  */
 188 BEGIN newpgno
 189 ARG     opcode          u_int32_t       lu
 190 ARG     fileid          u_int32_t       lu
 191 ARG     pgno            db_pgno_t       lu
 192 ARG     free_pgno       db_pgno_t       lu
 193 ARG     old_type        u_int32_t       lu
 194 ARG     old_pgno        db_pgno_t       lu
 195 ARG     new_type        u_int32_t       lu
 196 POINTER pagelsn         DB_LSN *        lu
 197 POINTER metalsn         DB_LSN *        lu
 198 END
 199
 200 /*
 201  * ovfl: initialize a set of overflow pages.
 202  */
 203 BEGIN ovfl
 204 ARG     fileid          u_int32_t       lu
 205 ARG     start_pgno      db_pgno_t       lu
 206 ARG     npages          u_int32_t       lu
 207 ARG     free_pgno       db_pgno_t       lu
 208 ARG     ovflpoint       u_int32_t       lu
 209 POINTER metalsn         DB_LSN *        lu
 210 END
 211
 212 /*
 213  * Used when we empty the first page in a bucket and there are pages
 214  * after it.  The page after it gets copied into the bucket page (since
 215  * bucket pages have to be in fixed locations).
 216  * pgno: the bucket page
 217  * pagelsn: the old LSN on the bucket page
 218  * next_pgno: the page number of the next page
 219  * nnext_pgno: page after next_pgno (may need to change its prev)
 220  * nnextlsn: the LSN of nnext_pgno.
 221  */
 222 BEGIN copypage
 223 ARG     fileid          u_int32_t       lu
 224 ARG     pgno            db_pgno_t       lu
 225 POINTER pagelsn         DB_LSN *        lu
 226 ARG     next_pgno       db_pgno_t       lu
 227 POINTER nextlsn         DB_LSN *        lu
 228 ARG     nnext_pgno      db_pgno_t       lu
 229 POINTER nnextlsn        DB_LSN *        lu
 230 DBT     page            DBT             s
 231 END