/ Liren Large Software Subsidy 7 / 07.iso / c / c006 / 1.ddi / BTINSPLT.C

< prev

next >

MacOS 8.1

Win98

DOS

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| ff 01 00 00 00 5c 43 42 | 54 52 45 45 5c 4c 49 42 |.....\CB|TREE\LIB|
|00000010| 52 41 52 59 5c 42 54 49 | 4e 53 50 4c 54 2e 43 00 |RARY\BTI|NSPLT.C.|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000050| 00 00 00 1b 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000060| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000080| 2f 2a 20 28 43 29 20 43 | 6f 70 79 72 69 67 68 74 |/* (C) C|opyright|
|00000090| 20 31 39 38 34 2c 38 35 | 2c 38 36 2c 38 37 20 57 | 1984,85|,86,87 W|
|000000a0| 61 6c 74 65 72 20 4c 2e | 20 50 65 61 63 6f 63 6b |alter L.| Peacock|
|000000b0| 20 20 20 41 6c 6c 20 52 | 69 67 68 74 73 20 52 65 |   All R|ights Re|
|000000c0| 73 65 72 76 65 64 20 20 | 20 20 2a 2f 0d 0a 2f 2a |served  |  */../*|
|000000d0| 20 42 20 54 20 49 20 4e | 20 53 20 50 20 4c 20 54 | B T I N| S P L T|
|000000e0| 20 2e 20 43 20 20 20 20 | 20 37 2f 32 34 2f 38 34 | . C    | 7/24/84|
|000000f0| 20 20 20 2a 2f 0d 0a 0d | 0a 2f 2a 2d 2d 2d 2d 2d |   */...|./*-----|
|00000100| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000110| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000120| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000130| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000140| 2d 2d 2d 2d 2d 2d 2d 20 | 0d 0a 20 2a 20 69 6e 73 |------- |.. * ins|
|00000150| 65 72 74 6b 79 28 29 20 | 69 73 20 75 73 65 64 20 |ertky() |is used |
|00000160| 74 6f 20 69 6e 73 65 72 | 74 20 61 20 6e 65 77 20 |to inser|t a new |
|00000170| 6b 65 79 20 69 6e 74 6f | 20 74 68 65 20 42 2b 74 |key into| the B+t|
|00000180| 72 65 65 20 69 6e 64 65 | 78 20 70 61 67 65 2e 0d |ree inde|x page..|
|00000190| 0a 20 2a 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |. *-----|--------|
|000001a0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000001b0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000001c0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000001d0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2a 2f |--------|------*/|
|000001e0| 0d 0a 0d 0a 23 69 6e 63 | 6c 75 64 65 20 22 63 62 |....#inc|lude "cb|
|000001f0| 74 72 65 65 2e 68 22 0d | 0a 0d 0a 2f 2a 20 74 68 |tree.h".|.../* th|
|00000200| 69 73 20 66 75 6e 63 74 | 69 6f 6e 20 6d 75 73 74 |is funct|ion must|
|00000210| 20 4e 4f 54 20 62 65 20 | 63 61 6c 6c 65 64 20 75 | NOT be |called u|
|00000220| 6e 6c 65 73 73 20 74 68 | 65 72 65 20 69 73 20 52 |nless th|ere is R|
|00000230| 45 41 4c 4c 59 20 65 6e | 6f 75 67 68 20 72 6f 6f |EALLY en|ough roo|
|00000240| 6d 20 2a 2f 0d 0a 2f 2a | 20 69 6e 20 74 68 65 20 |m */../*| in the |
|00000250| 62 74 70 61 67 65 20 74 | 6f 20 68 6f 6c 64 20 74 |btpage t|o hold t|
|00000260| 68 65 20 6e 65 77 20 6b | 65 79 20 2a 2f 0d 0a 0d |he new k|ey */...|
|00000270| 0a 76 6f 69 64 20 69 6e | 73 65 72 74 6b 79 28 70 |.void in|sertky(p|
|00000280| 62 6c 6b 2c 20 68 64 72 | 6c 6f 63 2c 20 73 72 63 |blk, hdr|loc, src|
|00000290| 68 6b 65 79 2c 20 6b 65 | 79 6c 65 6e 29 20 20 2f |hkey, ke|ylen)  /|
|000002a0| 2a 20 69 6e 73 65 72 74 | 20 6b 65 79 20 69 6e 74 |* insert| key int|
|000002b0| 6f 20 62 74 70 61 67 65 | 20 2a 2f 0d 0a 0d 0a 42 |o btpage| */....B|
|000002c0| 54 49 44 58 42 4c 4b 20 | 2a 70 62 6c 6b 3b 0d 0a |TIDXBLK |*pblk;..|
|000002d0| 69 6e 74 20 68 64 72 6c | 6f 63 3b 0d 0a 63 68 61 |int hdrl|oc;..cha|
|000002e0| 72 20 2a 73 72 63 68 6b | 65 79 3b 0d 0a 75 6e 73 |r *srchk|ey;..uns|
|000002f0| 69 67 6e 65 64 20 6b 65 | 79 6c 65 6e 3b 0d 0a 7b |igned ke|ylen;..{|
|00000300| 0d 0a 20 20 20 65 78 74 | 65 72 6e 20 63 68 61 72 |..   ext|ern char|
|00000310| 20 2a 63 61 6c 6c 6f 63 | 28 29 2c 20 2a 73 74 72 | *calloc|(), *str|
|00000320| 73 61 76 65 28 29 3b 0d | 0a 20 20 20 63 68 61 72 |save();.|.   char|
|00000330| 20 2a 63 70 3b 0d 0a 0d | 0a 20 20 20 2f 2a 20 69 | *cp;...|.   /* i|
|00000340| 66 20 6e 65 63 65 73 73 | 61 72 79 2c 20 67 65 74 |f necess|ary, get|
|00000350| 20 6d 65 6d 6f 72 79 20 | 66 6f 72 20 6e 65 77 20 | memory |for new |
|00000360| 6b 65 79 20 2a 2f 0d 0a | 20 20 20 69 66 20 28 70 |key */..|   if (p|
|00000370| 62 6c 6b 2d 3e 62 6c 6b | 61 6c 6c 6f 63 20 3c 3d |blk->blk|alloc <=|
|00000380| 20 70 62 6c 6b 2d 3e 63 | 65 6c 6c 69 63 6e 74 29 | pblk->c|ellicnt)|
|00000390| 0d 0a 20 20 20 7b 0d 0a | 20 20 20 20 20 20 63 70 |..   {..|      cp|
|000003a0| 20 3d 20 73 74 72 73 61 | 76 65 28 73 72 63 68 6b | = strsa|ve(srchk|
|000003b0| 65 79 2c 20 6b 65 79 6c | 65 6e 29 3b 0d 0a 20 20 |ey, keyl|en);..  |
|000003c0| 20 20 20 20 70 62 6c 6b | 2d 3e 62 6c 6b 61 6c 6c |    pblk|->blkall|
|000003d0| 6f 63 2b 2b 3b 0d 0a 20 | 20 20 7d 0d 0a 20 20 20 |oc++;.. |  }..   |
|000003e0| 65 6c 73 65 0d 0a 20 20 | 20 7b 0d 0a 20 20 20 20 |else..  | {..    |
|000003f0| 20 20 63 70 20 3d 20 70 | 62 6c 6b 2d 3e 62 74 70 |  cp = p|blk->btp|
|00000400| 61 67 65 5b 70 62 6c 6b | 2d 3e 63 65 6c 6c 69 63 |age[pblk|->cellic|
|00000410| 6e 74 5d 2e 73 6b 65 79 | 6e 6d 65 3b 20 20 20 20 |nt].skey|nme;    |
|00000420| 20 2f 2a 20 72 65 2d 75 | 73 65 20 74 6f 70 20 6f | /* re-u|se top o|
|00000430| 6e 65 20 2a 2f 0d 0a 20 | 20 20 20 20 20 73 74 72 |ne */.. |     str|
|00000440| 6e 6e 63 70 79 28 63 70 | 2c 20 73 72 63 68 6b 65 |nncpy(cp|, srchke|
|00000450| 79 2c 20 6b 65 79 6c 65 | 6e 29 3b 0d 0a 20 20 20 |y, keyle|n);..   |
|00000460| 7d 0d 0a 0d 0a 20 20 20 | 2f 2a 20 6f 70 65 6e 20 |}....   |/* open |
|00000470| 75 70 20 61 20 73 6c 6f | 74 20 2a 2f 0d 0a 20 20 |up a slo|t */..  |
|00000480| 20 62 6c 6b 73 68 66 74 | 28 70 62 6c 6b 2d 3e 62 | blkshft|(pblk->b|
|00000490| 74 70 61 67 65 20 2b 20 | 68 64 72 6c 6f 63 20 2b |tpage + |hdrloc +|
|000004a0| 20 31 2c 20 70 62 6c 6b | 2d 3e 62 74 70 61 67 65 | 1, pblk|->btpage|
|000004b0| 20 2b 20 68 64 72 6c 6f | 63 2c 0d 0a 20 20 20 20 | + hdrlo|c,..    |
|000004c0| 20 20 20 20 20 70 62 6c | 6b 2d 3e 63 65 6c 6c 69 |     pbl|k->celli|
|000004d0| 63 6e 74 20 2d 20 68 64 | 72 6c 6f 63 2c 20 53 5a |cnt - hd|rloc, SZ|
|000004e0| 42 54 49 44 58 29 3b 0d | 0a 20 20 20 2b 2b 70 62 |BTIDX);.|.   ++pb|
|000004f0| 6c 6b 2d 3e 63 65 6c 6c | 69 63 6e 74 3b 20 20 20 |lk->cell|icnt;   |
|00000500| 20 2f 2a 20 61 64 6a 75 | 73 74 20 63 65 6c 6c 20 | /* adju|st cell |
|00000510| 63 6f 75 6e 74 20 2a 2f | 0d 0a 0d 0a 20 20 20 70 |count */|....   p|
|00000520| 62 6c 6b 2d 3e 62 74 70 | 61 67 65 5b 68 64 72 6c |blk->btp|age[hdrl|
|00000530| 6f 63 5d 2e 73 6b 65 79 | 6e 6d 65 20 3d 20 63 70 |oc].skey|nme = cp|
|00000540| 3b 20 20 20 20 2f 2a 20 | 6e 65 77 20 6f 6e 65 20 |;    /* |new one |
|00000550| 67 6f 65 73 20 68 65 72 | 65 20 2a 2f 0d 0a 7d 0d |goes her|e */..}.|
|00000560| 0a 0d 0a 0d 0a 2f 2a 20 | 20 20 73 70 6c 74 6e 6f |...../* |  spltno|
|00000570| 64 65 3a 20 66 75 6e 63 | 74 69 6f 6e 20 74 6f 20 |de: func|tion to |
|00000580| 73 70 6c 69 74 20 62 74 | 72 65 65 20 6e 6f 64 65 |split bt|ree node|
|00000590| 20 20 20 20 20 20 20 2a | 2f 0d 0a 2f 2a 2d 2d 2d |       *|/../*---|
|000005a0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000005b0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000005c0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000005d0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000005e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 20 0d 0a 20 2a 20 73 |--------|- .. * s|
|000005f0| 70 6c 74 6e 6f 64 65 28 | 29 20 69 73 20 63 61 6c |pltnode(|) is cal|
|00000600| 6c 65 64 20 77 68 65 6e | 20 61 20 6b 65 79 20 69 |led when| a key i|
|00000610| 6e 73 65 72 74 69 6f 6e | 20 77 69 6c 6c 20 72 65 |nsertion| will re|
|00000620| 73 75 6c 74 20 69 6e 20 | 74 68 65 20 69 6e 64 65 |sult in |the inde|
|00000630| 78 20 70 61 67 65 20 0d | 0a 20 2a 20 63 6f 6e 74 |x page .|. * cont|
|00000640| 61 69 6e 69 6e 67 20 6d | 6f 72 65 20 74 68 61 6e |aining m|ore than|
|00000650| 20 74 68 65 20 6d 61 78 | 20 63 65 6c 6c 73 20 73 | the max| cells s|
|00000660| 70 65 63 69 66 69 65 64 | 20 64 75 72 69 6e 67 20 |pecified| during |
|00000670| 42 54 53 45 54 55 50 2e | 45 58 45 2e 20 20 20 54 |BTSETUP.|EXE.   T|
|00000680| 68 65 0d 0a 20 2a 20 69 | 6e 64 65 78 20 6e 6f 64 |he.. * i|ndex nod|
|00000690| 65 20 77 69 6c 6c 20 62 | 65 20 73 70 6c 69 74 20 |e will b|e split |
|000006a0| 69 6e 74 6f 20 74 77 6f | 20 70 61 67 65 73 20 6f |into two| pages o|
|000006b0| 66 20 65 71 75 61 6c 20 | 73 69 7a 65 20 2b 2f 2d |f equal |size +/-|
|000006c0| 20 31 2e 0d 0a 20 2a 2d | 2d 2d 2d 2d 2d 2d 2d 2d | 1... *-|--------|
|000006d0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000006e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000006f0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000700| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000710| 2d 2d 2a 2f 0d 0a 0d 0a | 76 6f 69 64 20 73 70 6c |--*/....|void spl|
|00000720| 74 6e 6f 64 65 28 70 62 | 6c 6b 2c 20 6e 75 62 6c |tnode(pb|lk, nubl|
|00000730| 6b 2c 20 73 70 6c 69 74 | 70 74 29 0d 0a 42 54 49 |k, split|pt)..BTI|
|00000740| 44 58 42 4c 4b 20 2a 70 | 62 6c 6b 3b 0d 0a 42 54 |DXBLK *p|blk;..BT|
|00000750| 49 44 58 42 4c 4b 20 2a | 6e 75 62 6c 6b 3b 20 20 |IDXBLK *|nublk;  |
|00000760| 20 20 20 2f 2a 20 74 68 | 69 73 20 62 65 74 74 65 |   /* th|is bette|
|00000770| 72 20 62 65 20 61 6e 20 | 65 6d 70 74 79 20 69 6e |r be an |empty in|
|00000780| 64 65 78 20 62 6c 6f 63 | 6b 20 2a 2f 0d 0a 75 6e |dex bloc|k */..un|
|00000790| 73 69 67 6e 65 64 20 20 | 73 70 6c 69 74 70 74 3b |signed  |splitpt;|
|000007a0| 0d 0a 7b 0d 0a 20 20 20 | 75 77 6f 72 64 20 63 6f |..{..   |uword co|
|000007b0| 75 6e 74 3b 0d 0a 20 20 | 20 75 77 6f 72 64 20 75 |unt;..  | uword u|
|000007c0| 3b 0d 0a 0d 0a 20 20 20 | 63 6f 75 6e 74 20 3d 20 |;....   |count = |
|000007d0| 70 62 6c 6b 2d 3e 63 65 | 6c 6c 69 63 6e 74 20 2d |pblk->ce|llicnt -|
|000007e0| 20 73 70 6c 69 74 70 74 | 3b 20 20 20 2f 2a 20 23 | splitpt|;   /* #|
|000007f0| 20 62 6c 6f 63 6b 73 20 | 74 6f 20 6d 6f 76 65 20 | blocks |to move |
|00000800| 2a 2f 0d 0a 0d 0a 20 20 | 20 2f 2a 20 66 72 65 65 |*/....  | /* free|
|00000810| 20 75 70 20 73 70 61 63 | 65 20 69 6e 20 6e 75 62 | up spac|e in nub|
|00000820| 6c 6b 20 66 6f 72 20 63 | 6f 70 79 20 2a 2f 0d 0a |lk for c|opy */..|
|00000830| 20 20 20 75 20 3d 20 4d | 49 4e 28 6e 75 62 6c 6b |   u = M|IN(nublk|
|00000840| 2d 3e 62 6c 6b 61 6c 6c | 6f 63 2c 20 63 6f 75 6e |->blkall|oc, coun|
|00000850| 74 29 3b 20 20 20 20 2f | 2a 20 23 20 74 6f 20 66 |t);    /|* # to f|
|00000860| 72 65 65 20 75 70 20 69 | 6e 20 6e 75 62 6c 6b 20 |ree up i|n nublk |
|00000870| 2a 2f 0d 0a 20 20 20 6e | 75 62 6c 6b 2d 3e 62 6c |*/..   n|ublk->bl|
|00000880| 6b 61 6c 6c 6f 63 20 2d | 3d 20 75 3b 20 20 20 20 |kalloc -|= u;    |
|00000890| 20 20 2f 2a 20 72 65 64 | 75 63 65 20 61 6c 6c 6f |  /* red|uce allo|
|000008a0| 63 61 74 69 6f 6e 20 63 | 6f 75 6e 74 20 2a 2f 0d |cation c|ount */.|
|000008b0| 0a 20 20 20 77 68 69 6c | 65 20 28 75 2d 2d 29 0d |.   whil|e (u--).|
|000008c0| 0a 20 20 20 20 20 20 46 | 52 45 45 28 6e 75 62 6c |.      F|REE(nubl|
|000008d0| 6b 2d 3e 62 74 70 61 67 | 65 5b 75 5d 2e 73 6b 65 |k->btpag|e[u].ske|
|000008e0| 79 6e 6d 65 29 3b 0d 0a | 0d 0a 20 20 20 2f 2a 20 |ynme);..|..   /* |
|000008f0| 63 6f 70 79 20 27 63 6f | 75 6e 74 27 20 62 6c 6f |copy 'co|unt' blo|
|00000900| 63 6b 73 20 66 72 6f 6d | 20 70 62 6c 6b 2d 3e 62 |cks from| pblk->b|
|00000910| 74 70 61 67 65 20 74 6f | 20 6e 75 62 6c 6b 2d 3e |tpage to| nublk->|
|00000920| 62 74 70 61 67 65 20 2a | 2f 0d 0a 20 20 20 62 6c |btpage *|/..   bl|
|00000930| 6b 73 68 66 74 28 6e 75 | 62 6c 6b 2d 3e 62 74 70 |kshft(nu|blk->btp|
|00000940| 61 67 65 2c 20 70 62 6c | 6b 2d 3e 62 74 70 61 67 |age, pbl|k->btpag|
|00000950| 65 20 2b 20 73 70 6c 69 | 74 70 74 2c 20 63 6f 75 |e + spli|tpt, cou|
|00000960| 6e 74 2c 20 53 5a 42 54 | 49 44 58 29 3b 0d 0a 20 |nt, SZBT|IDX);.. |
|00000970| 20 20 6e 75 62 6c 6b 2d | 3e 62 6c 6b 61 6c 6c 6f |  nublk-|>blkallo|
|00000980| 63 20 2b 3d 20 63 6f 75 | 6e 74 3b 0d 0a 20 20 20 |c += cou|nt;..   |
|00000990| 6e 75 62 6c 6b 2d 3e 63 | 65 6c 6c 69 63 6e 74 20 |nublk->c|ellicnt |
|000009a0| 20 3d 20 63 6f 75 6e 74 | 3b 0d 0a 20 20 20 70 62 | = count|;..   pb|
|000009b0| 6c 6b 2d 3e 62 6c 6b 61 | 6c 6c 6f 63 20 20 2d 3d |lk->blka|lloc  -=|
|000009c0| 20 63 6f 75 6e 74 3b 0d | 0a 20 20 20 70 62 6c 6b | count;.|.   pblk|
|000009d0| 2d 3e 63 65 6c 6c 69 63 | 6e 74 20 20 2d 3d 20 63 |->cellic|nt  -= c|
|000009e0| 6f 75 6e 74 3b 0d 0a 0d | 0a 20 20 20 2f 2a 20 63 |ount;...|.   /* c|
|000009f0| 6f 6c 6c 61 70 73 65 20 | 65 78 63 65 73 73 20 73 |ollapse |excess s|
|00000a00| 74 75 66 66 20 69 6e 20 | 70 62 6c 6b 20 6f 76 65 |tuff in |pblk ove|
|00000a10| 72 20 73 74 75 66 66 20 | 6a 75 73 74 20 6d 6f 76 |r stuff |just mov|
|00000a20| 65 64 20 2a 2f 0d 0a 20 | 20 20 69 66 20 28 28 75 |ed */.. |  if ((u|
|00000a30| 20 3d 20 70 62 6c 6b 2d | 3e 62 6c 6b 61 6c 6c 6f | = pblk-|>blkallo|
|00000a40| 63 20 2d 20 70 62 6c 6b | 2d 3e 63 65 6c 6c 69 63 |c - pblk|->cellic|
|00000a50| 6e 74 29 20 21 3d 20 30 | 29 20 20 20 20 2f 2a 20 |nt) != 0|)    /* |
|00000a60| 23 20 65 78 63 65 73 73 | 20 62 6c 6f 63 6b 73 20 |# excess| blocks |
|00000a70| 2a 2f 0d 0a 20 20 20 20 | 20 20 62 6c 6b 73 68 66 |*/..    |  blkshf|
|00000a80| 74 28 70 62 6c 6b 2d 3e | 62 74 70 61 67 65 20 2b |t(pblk->|btpage +|
|00000a90| 20 73 70 6c 69 74 70 74 | 2c 20 70 62 6c 6b 2d 3e | splitpt|, pblk->|
|00000aa0| 62 74 70 61 67 65 20 2b | 20 73 70 6c 69 74 70 74 |btpage +| splitpt|
|00000ab0| 20 2b 20 63 6f 75 6e 74 | 2c 20 75 2c 0d 0a 20 20 | + count|, u,..  |
|00000ac0| 20 20 20 20 20 20 20 20 | 20 20 53 5a 42 54 49 44 |        |  SZBTID|
|00000ad0| 58 29 3b 0d 0a 7d 0d 0a |                         |X);..}..|        |
+--------+-------------------------+-------------------------+--------+--------+