home *** CD-ROM | disk | FTP | other *** search
view JSON data
|
view as text
|
open on a Mac
|
open on a PC
This file was processed as: SHell self-extracting ARchive
(archive/shar).
You can browse this item here: 39
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 100%
| dexvert
| Newsgroup Content (archive/news)
| magic
| Supported |
| 100%
| dexvert
| SHell self-extracting ARchive (archive/shar)
| magic
| Supported |
| 100%
| dexvert
| Internet Message Format (text/imf)
| magic
| Supported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| news or mail, ASCII text
| default
| |
| 100%
| TrID
| E-Mail message (Var. 2)
| default
| |
| 100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
| 100%
| siegfried
| fmt/329 Shell Archive Format
| default
| |
| 100%
| detectItEasy
| Format: plain text[LF]
| default (weak)
| |
| 100%
| xdgMime
| message/rfc822
| default
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 46 72 6f 6d 3a 20 73 63 | 68 77 61 72 74 7a 40 75 |From: sc|hwartz@u|
|00000010| 77 2d 74 61 6f 73 2e 55 | 55 43 50 20 28 4d 69 63 |w-taos.U|UCP (Mic|
|00000020| 68 61 65 6c 20 46 2e 20 | 53 63 68 77 61 72 74 7a |hael F. |Schwartz|
|00000030| 29 0a 4e 65 77 73 67 72 | 6f 75 70 73 3a 20 63 6f |).Newsgr|oups: co|
|00000040| 6d 70 2e 73 6f 75 72 63 | 65 73 2e 6d 69 73 63 0a |mp.sourc|es.misc.|
|00000050| 53 75 62 6a 65 63 74 3a | 20 6d 61 6c 74 72 61 63 |Subject:| maltrac|
|00000060| 65 20 2d 2d 20 74 72 61 | 63 65 20 75 6e 2d 66 72 |e -- tra|ce un-fr|
|00000070| 65 65 28 29 27 64 20 73 | 70 61 63 65 20 77 69 74 |ee()'d s|pace wit|
|00000080| 68 20 64 62 78 20 28 6d | 61 79 62 65 20 6f 74 68 |h dbx (m|aybe oth|
|00000090| 65 72 73 3f 29 0a 4d 65 | 73 73 61 67 65 2d 49 44 |ers?).Me|ssage-ID|
|000000a0| 3a 20 3c 32 38 33 35 40 | 6e 63 6f 61 73 74 2e 55 |: <2835@|ncoast.U|
|000000b0| 55 43 50 3e 0a 44 61 74 | 65 3a 20 31 30 20 4a 75 |UCP>.Dat|e: 10 Ju|
|000000c0| 6c 20 38 37 20 30 32 3a | 30 30 3a 33 34 20 47 4d |l 87 02:|00:34 GM|
|000000d0| 54 0a 53 65 6e 64 65 72 | 3a 20 61 6c 6c 62 65 72 |T.Sender|: allber|
|000000e0| 79 40 6e 63 6f 61 73 74 | 2e 55 55 43 50 0a 4c 69 |y@ncoast|.UUCP.Li|
|000000f0| 6e 65 73 3a 20 31 34 34 | 33 0a 41 70 70 72 6f 76 |nes: 144|3.Approv|
|00000100| 65 64 3a 20 61 6c 6c 62 | 65 72 79 40 6e 63 6f 61 |ed: allb|ery@ncoa|
|00000110| 73 74 2e 55 55 43 50 0a | 58 2d 41 72 63 68 69 76 |st.UUCP.|X-Archiv|
|00000120| 65 3a 20 63 6f 6d 70 2e | 73 6f 75 72 63 65 73 2e |e: comp.|sources.|
|00000130| 6d 69 73 63 2f 38 37 30 | 37 2f 33 39 0a 0a 5b 49 |misc/870|7/39..[I|
|00000140| 20 68 61 76 65 20 61 20 | 6d 61 6c 6c 6f 63 20 70 | have a |malloc p|
|00000150| 61 63 6b 61 67 65 20 6f | 66 20 6d 79 20 6f 77 6e |ackage o|f my own|
|00000160| 20 77 68 69 63 68 20 6c | 65 74 73 20 79 6f 75 20 | which l|ets you |
|00000170| 63 61 6c 6c 20 5f 6d 61 | 6c 6c 64 6d 70 28 29 20 |call _ma|lldmp() |
|00000180| 74 6f 20 64 75 6d 70 0a | 74 68 65 20 6d 61 6c 6c |to dump.|the mall|
|00000190| 6f 63 2f 66 72 65 65 20 | 6c 69 73 74 73 2c 20 5f |oc/free |lists, _|
|000001a0| 6d 61 6c 6c 63 68 6b 28 | 29 20 74 6f 20 69 6e 73 |mallchk(|) to ins|
|000001b0| 75 72 65 20 74 68 65 20 | 6c 69 73 74 20 70 6f 69 |ure the |list poi|
|000001c0| 6e 74 65 72 73 20 61 72 | 65 20 76 61 6c 69 64 2c |nters ar|e valid,|
|000001d0| 0a 61 6e 64 20 73 65 74 | 20 61 20 66 6c 61 67 20 |.and set| a flag |
|000001e0| 74 6f 20 70 72 69 6e 74 | 20 61 6c 6c 20 63 61 6c |to print| all cal|
|000001f0| 6c 73 20 74 6f 20 6d 61 | 6c 6c 6f 63 28 29 20 6f |ls to ma|lloc() o|
|00000200| 72 20 66 72 65 65 28 29 | 2e 20 20 53 65 6e 64 20 |r free()|. Send |
|00000210| 6d 61 69 6c 20 66 6f 72 | 0a 69 6e 66 6f 2e 20 20 |mail for|.info. |
|00000220| 2b 2b 62 73 61 5d 0a 0a | 2d 20 4d 69 63 68 61 65 |++bsa]..|- Michae|
|00000230| 6c 20 53 63 68 77 61 72 | 74 7a 0a 20 20 55 6e 69 |l Schwar|tz. Uni|
|00000240| 76 65 72 73 69 74 79 20 | 6f 66 20 57 61 73 68 69 |versity |of Washi|
|00000250| 6e 67 74 6f 6e 20 43 6f | 6d 70 75 74 65 72 20 53 |ngton Co|mputer S|
|00000260| 63 69 65 6e 63 65 20 44 | 65 70 61 72 74 6d 65 6e |cience D|epartmen|
|00000270| 74 0a 20 20 53 65 61 74 | 74 6c 65 2c 20 57 61 73 |t. Seat|tle, Was|
|00000280| 68 69 6e 67 74 6f 6e 2c | 20 55 53 41 0a 20 20 73 |hington,| USA. s|
|00000290| 63 68 77 61 72 74 7a 40 | 63 73 2e 77 61 73 68 69 |chwartz@|cs.washi|
|000002a0| 6e 67 74 6f 6e 2e 65 64 | 75 20 20 28 41 52 50 41 |ngton.ed|u (ARPA|
|000002b0| 4e 45 54 29 0a 20 20 73 | 63 68 77 61 72 74 7a 25 |NET). s|chwartz%|
|000002c0| 63 73 2e 77 61 73 68 69 | 6e 67 74 6f 6e 2e 65 64 |cs.washi|ngton.ed|
|000002d0| 75 40 72 65 6c 61 79 2e | 63 73 2e 6e 65 74 20 20 |u@relay.|cs.net |
|000002e0| 28 43 53 4e 45 54 29 0a | 20 20 2e 2e 2e 7b 61 6c |(CSNET).| ...{al|
|000002f0| 6c 65 67 72 61 2c 63 61 | 69 70 2c 69 68 6e 70 34 |legra,ca|ip,ihnp4|
|00000300| 2c 6e 69 6b 65 7d 21 75 | 77 2d 62 65 61 76 65 72 |,nike}!u|w-beaver|
|00000310| 21 73 63 68 77 61 72 74 | 7a 20 20 28 55 55 43 50 |!schwart|z (UUCP|
|00000320| 29 0a 0a 23 21 2f 62 69 | 6e 2f 73 68 0a 23 20 54 |)..#!/bi|n/sh.# T|
|00000330| 68 69 73 20 69 73 20 61 | 20 73 68 65 6c 6c 20 61 |his is a| shell a|
|00000340| 72 63 68 69 76 65 2c 20 | 6d 65 61 6e 69 6e 67 3a |rchive, |meaning:|
|00000350| 0a 23 20 31 2e 20 52 65 | 6d 6f 76 65 20 65 76 65 |.# 1. Re|move eve|
|00000360| 72 79 74 68 69 6e 67 20 | 61 62 6f 76 65 20 74 68 |rything |above th|
|00000370| 65 20 23 21 2f 62 69 6e | 2f 73 68 20 6c 69 6e 65 |e #!/bin|/sh line|
|00000380| 2e 0a 23 20 32 2e 20 53 | 61 76 65 20 74 68 65 20 |..# 2. S|ave the |
|00000390| 72 65 73 75 6c 74 69 6e | 67 20 74 65 78 74 20 69 |resultin|g text i|
|000003a0| 6e 20 61 20 66 69 6c 65 | 2e 0a 23 20 33 2e 20 45 |n a file|..# 3. E|
|000003b0| 78 65 63 75 74 65 20 74 | 68 65 20 66 69 6c 65 20 |xecute t|he file |
|000003c0| 77 69 74 68 20 2f 62 69 | 6e 2f 73 68 20 28 6e 6f |with /bi|n/sh (no|
|000003d0| 74 20 63 73 68 29 20 74 | 6f 20 63 72 65 61 74 65 |t csh) t|o create|
|000003e0| 20 74 68 65 20 66 69 6c | 65 73 3a 0a 23 09 52 45 | the fil|es:.#.RE|
|000003f0| 41 44 4d 45 0a 23 09 62 | 74 72 65 65 2e 63 0a 23 |ADME.#.b|tree.c.#|
|00000400| 09 62 74 72 65 65 2e 68 | 0a 23 09 6d 61 6b 65 66 |.btree.h|.#.makef|
|00000410| 69 6c 65 0a 23 09 6d 61 | 6c 74 72 61 63 65 2e 63 |ile.#.ma|ltrace.c|
|00000420| 0a 23 09 74 65 73 74 2e | 63 0a 23 20 54 68 69 73 |.#.test.|c.# This|
|00000430| 20 61 72 63 68 69 76 65 | 20 63 72 65 61 74 65 64 | archive| created|
|00000440| 3a 20 53 75 6e 20 41 70 | 72 20 20 35 20 32 33 3a |: Sun Ap|r 5 23:|
|00000450| 32 38 3a 34 39 20 31 39 | 38 37 0a 65 78 70 6f 72 |28:49 19|87.expor|
|00000460| 74 20 50 41 54 48 3b 20 | 50 41 54 48 3d 2f 62 69 |t PATH; |PATH=/bi|
|00000470| 6e 3a 24 50 41 54 48 0a | 65 63 68 6f 20 73 68 61 |n:$PATH.|echo sha|
|00000480| 72 3a 20 65 78 74 72 61 | 63 74 69 6e 67 20 22 27 |r: extra|cting "'|
|00000490| 52 45 41 44 4d 45 27 22 | 20 27 28 36 34 35 32 20 |README'"| '(6452 |
|000004a0| 63 68 61 72 61 63 74 65 | 72 73 29 27 0a 69 66 20 |characte|rs)'.if |
|000004b0| 74 65 73 74 20 2d 66 20 | 27 52 45 41 44 4d 45 27 |test -f |'README'|
|000004c0| 0a 74 68 65 6e 0a 09 65 | 63 68 6f 20 73 68 61 72 |.then..e|cho shar|
|000004d0| 3a 20 6f 76 65 72 2d 77 | 72 69 74 69 6e 67 20 65 |: over-w|riting e|
|000004e0| 78 69 73 74 69 6e 67 20 | 66 69 6c 65 20 22 27 52 |xisting |file "'R|
|000004f0| 45 41 44 4d 45 27 22 0a | 66 69 0a 73 65 64 20 27 |EADME'".|fi.sed '|
|00000500| 73 2f 5e 58 2f 2f 27 20 | 3c 3c 20 5c 53 48 41 52 |s/^X//' |<< \SHAR|
|00000510| 5f 45 4f 46 20 3e 20 27 | 52 45 41 44 4d 45 27 0a |_EOF > '|README'.|
|00000520| 58 09 09 09 20 20 4d 61 | 6c 6c 6f 63 20 4c 65 61 |X... Ma|lloc Lea|
|00000530| 6b 20 54 72 61 63 65 20 | 50 61 63 6b 61 67 65 0a |k Trace |Package.|
|00000540| 58 0a 58 09 09 09 20 20 | 20 20 20 62 79 20 4d 69 |X.X... | by Mi|
|00000550| 63 68 61 65 6c 20 53 63 | 68 77 61 72 74 7a 0a 58 |chael Sc|hwartz.X|
|00000560| 09 20 20 20 20 20 55 6e | 69 76 65 72 73 69 74 79 |. Un|iversity|
|00000570| 20 6f 66 20 57 61 73 68 | 69 6e 67 74 6f 6e 20 43 | of Wash|ington C|
|00000580| 6f 6d 70 75 74 65 72 20 | 53 63 69 65 6e 63 65 20 |omputer |Science |
|00000590| 44 65 70 61 72 74 6d 65 | 6e 74 0a 58 09 09 09 20 |Departme|nt.X... |
|000005a0| 20 20 53 65 61 74 74 6c | 65 2c 20 57 61 73 68 69 | Seattl|e, Washi|
|000005b0| 6e 67 74 6f 6e 2c 20 55 | 53 41 0a 58 09 09 20 20 |ngton, U|SA.X.. |
|000005c0| 20 20 73 63 68 77 61 72 | 74 7a 40 63 73 2e 77 61 | schwar|tz@cs.wa|
|000005d0| 73 68 69 6e 67 74 6f 6e | 2e 65 64 75 20 20 28 41 |shington|.edu (A|
|000005e0| 52 50 41 4e 45 54 29 0a | 58 09 20 20 20 20 20 20 |RPANET).|X. |
|000005f0| 20 73 63 68 77 61 72 74 | 7a 25 63 73 2e 77 61 73 | schwart|z%cs.was|
|00000600| 68 69 6e 67 74 6f 6e 2e | 65 64 75 40 72 65 6c 61 |hington.|edu@rela|
|00000610| 79 2e 63 73 2e 6e 65 74 | 20 20 28 43 53 4e 45 54 |y.cs.net| (CSNET|
|00000620| 29 0a 58 09 20 20 20 20 | 2e 2e 2e 7b 61 6c 6c 65 |).X. |...{alle|
|00000630| 67 72 61 2c 63 61 69 70 | 2c 69 68 6e 70 34 2c 6e |gra,caip|,ihnp4,n|
|00000640| 69 6b 65 7d 21 75 77 2d | 62 65 61 76 65 72 21 73 |ike}!uw-|beaver!s|
|00000650| 63 68 77 61 72 74 7a 20 | 20 28 55 55 43 50 29 0a |chwartz | (UUCP).|
|00000660| 58 0a 58 09 09 09 09 20 | 20 41 70 72 69 6c 20 31 |X.X.... | April 1|
|00000670| 39 38 37 0a 58 0a 58 31 | 2e 20 44 65 73 63 72 69 |987.X.X1|. Descri|
|00000680| 70 74 69 6f 6e 0a 58 0a | 58 54 68 69 73 20 70 61 |ption.X.|XThis pa|
|00000690| 63 6b 61 67 65 20 69 73 | 20 64 65 73 69 67 6e 65 |ckage is| designe|
|000006a0| 64 20 74 6f 20 68 65 6c | 70 20 74 72 61 63 65 20 |d to hel|p trace |
|000006b0| 64 79 6e 61 6d 69 63 20 | 6d 65 6d 6f 72 79 20 61 |dynamic |memory a|
|000006c0| 6c 6c 6f 63 61 74 69 6f | 6e 20 6c 65 61 6b 73 2e |llocatio|n leaks.|
|000006d0| 0a 58 49 74 20 77 6f 72 | 6b 73 20 62 79 20 70 72 |.XIt wor|ks by pr|
|000006e0| 6f 76 69 64 69 6e 67 20 | 74 68 65 20 73 74 61 6e |oviding |the stan|
|000006f0| 64 61 72 64 20 6d 61 6c | 6c 6f 63 2f 66 72 65 65 |dard mal|loc/free|
|00000700| 2f 72 65 61 6c 6c 6f 63 | 20 69 6e 74 65 72 66 61 |/realloc| interfa|
|00000710| 63 65 2c 20 62 75 74 20 | 61 74 0a 58 74 68 65 20 |ce, but |at.Xthe |
|00000720| 73 61 6d 65 20 74 69 6d | 65 20 6b 65 65 70 69 6e |same tim|e keepin|
|00000730| 67 20 74 72 61 63 6b 20 | 6f 66 20 61 6c 6c 20 6d |g track |of all m|
|00000740| 61 6c 6c 6f 63 27 64 20 | 62 75 66 66 65 72 73 2c |alloc'd |buffers,|
|00000750| 20 69 6e 63 6c 75 64 69 | 6e 67 20 74 68 65 69 72 | includi|ng their|
|00000760| 20 73 69 7a 65 2c 0a 58 | 6f 72 64 65 72 20 6f 66 | size,.X|order of|
|00000770| 20 63 61 6c 6c 2c 20 61 | 6e 64 20 61 64 64 72 65 | call, a|nd addre|
|00000780| 73 73 2e 20 20 54 68 61 | 74 20 77 61 79 2c 20 61 |ss. Tha|t way, a|
|00000790| 74 20 61 6e 79 20 70 6f | 69 6e 74 20 64 75 72 69 |t any po|int duri|
|000007a0| 6e 67 20 74 68 65 20 65 | 78 65 63 75 74 69 6f 6e |ng the e|xecution|
|000007b0| 20 6f 66 0a 58 79 6f 75 | 72 20 70 72 6f 67 72 61 | of.Xyou|r progra|
|000007c0| 6d 2c 20 79 6f 75 20 63 | 61 6e 20 73 65 65 20 77 |m, you c|an see w|
|000007d0| 68 61 74 20 6d 61 6c 6c | 6f 63 27 64 20 62 75 66 |hat mall|oc'd buf|
|000007e0| 66 65 72 73 20 68 61 76 | 65 6e 27 74 20 79 65 74 |fers hav|en't yet|
|000007f0| 20 62 65 65 6e 20 66 72 | 65 65 64 2e 0a 58 49 74 | been fr|eed..XIt|
|00000800| 20 69 73 20 70 61 72 74 | 69 63 75 6c 61 72 6c 79 | is part|icularly|
|00000810| 20 75 73 65 66 75 6c 20 | 77 68 65 6e 20 79 6f 75 | useful |when you|
|00000820| 72 20 70 72 6f 67 72 61 | 6d 20 70 65 72 66 6f 72 |r progra|m perfor|
|00000830| 6d 73 20 6d 61 6e 79 20 | 61 6c 6c 6f 63 61 74 69 |ms many |allocati|
|00000840| 6f 6e 73 0a 58 62 65 66 | 6f 72 65 20 72 65 61 63 |ons.Xbef|ore reac|
|00000850| 68 69 6e 67 20 73 6f 6d | 65 20 73 74 65 61 64 79 |hing som|e steady|
|00000860| 20 73 74 61 74 65 2c 20 | 61 6e 64 20 68 65 6e 63 | state, |and henc|
|00000870| 65 20 79 6f 75 20 77 61 | 6e 74 20 74 6f 20 69 67 |e you wa|nt to ig|
|00000880| 6e 6f 72 65 0a 58 74 68 | 65 20 69 6e 69 74 69 61 |nore.Xth|e initia|
|00000890| 6c 20 61 6c 6c 6f 63 61 | 74 69 6f 6e 73 20 61 6e |l alloca|tions an|
|000008a0| 64 20 63 6f 6e 63 65 6e | 74 72 61 74 65 20 6f 6e |d concen|trate on|
|000008b0| 20 77 68 65 72 65 20 73 | 74 65 61 64 79 2d 73 74 | where s|teady-st|
|000008c0| 61 74 65 0a 58 6c 65 61 | 6b 73 20 6f 63 63 75 72 |ate.Xlea|ks occur|
|000008d0| 2e 0a 58 0a 58 54 68 65 | 20 69 64 65 61 20 69 73 |..X.XThe| idea is|
|000008e0| 20 74 68 61 74 20 79 6f | 75 20 68 61 76 65 20 73 | that yo|u have s|
|000008f0| 6f 6d 65 20 63 6f 64 65 | 20 28 75 73 75 61 6c 6c |ome code| (usuall|
|00000900| 79 20 61 20 73 65 72 76 | 65 72 29 20 74 68 61 74 |y a serv|er) that|
|00000910| 20 6c 6f 6f 6b 73 20 61 | 73 20 66 6f 6c 6c 6f 77 | looks a|s follow|
|00000920| 73 3a 0a 58 09 69 6e 69 | 74 69 61 6c 69 7a 61 74 |s:.X.ini|tializat|
|00000930| 69 6f 6e 20 63 6f 64 65 | 3b 0a 58 09 64 6f 20 7b |ion code|;.X.do {|
|00000940| 0a 58 09 09 2e 2e 2e 0a | 58 09 7d 20 77 68 69 6c |.X......|X.} whil|
|00000950| 65 20 28 31 29 3b 20 2f | 2a 20 6d 61 69 6e 20 6c |e (1); /|* main l|
|00000960| 6f 6f 70 20 2a 2f 0a 58 | 0a 58 54 68 65 72 65 20 |oop */.X|.XThere |
|00000970| 6d 69 67 68 74 20 62 65 | 20 73 6f 6d 65 20 64 79 |might be| some dy|
|00000980| 6e 61 6d 69 63 20 61 6c | 6c 6f 63 61 74 69 6f 6e |namic al|location|
|00000990| 20 64 75 72 69 6e 67 20 | 74 68 65 20 69 6e 69 74 | during |the init|
|000009a0| 69 61 6c 69 7a 61 74 69 | 6f 6e 2c 0a 58 62 75 74 |ializati|on,.Xbut|
|000009b0| 20 74 68 69 73 20 69 73 | 6e 27 74 20 77 68 65 72 | this is|n't wher|
|000009c0| 65 20 74 68 65 20 6d 65 | 6d 6f 72 79 20 6c 65 61 |e the me|mory lea|
|000009d0| 6b 20 69 73 2c 20 73 69 | 6e 63 65 20 69 74 27 73 |k is, si|nce it's|
|000009e0| 20 61 20 6f 6e 65 2d 73 | 68 6f 74 20 61 6c 6c 6f | a one-s|hot allo|
|000009f0| 63 61 74 69 6f 6e 0a 58 | 28 69 2e 65 2e 2c 20 61 |cation.X|(i.e., a|
|00000a00| 74 20 77 6f 72 73 74 20 | 74 68 65 20 69 6e 69 74 |t worst |the init|
|00000a10| 69 61 6c 69 7a 61 74 69 | 6f 6e 20 77 61 73 74 65 |ializati|on waste|
|00000a20| 73 20 73 6f 6d 65 20 6d | 65 6d 6f 72 79 2c 20 62 |s some m|emory, b|
|00000a30| 75 74 20 64 6f 65 73 6e | 27 74 0a 58 63 6f 6e 74 |ut doesn|'t.Xcont|
|00000a40| 69 6e 75 61 6c 6c 79 20 | 6c 65 61 6b 20 69 74 29 |inually |leak it)|
|00000a50| 2e 20 20 54 68 65 72 65 | 20 6d 69 67 68 74 20 61 |. There| might a|
|00000a60| 6c 73 6f 20 62 65 20 73 | 6f 6d 65 20 64 79 6e 61 |lso be s|ome dyna|
|00000a70| 6d 69 63 20 61 6c 6c 6f | 63 61 74 69 6f 6e 20 69 |mic allo|cation i|
|00000a80| 6e 0a 58 74 68 65 20 66 | 69 72 73 74 20 66 65 77 |n.Xthe f|irst few|
|00000a90| 20 69 74 65 72 61 74 69 | 6f 6e 73 20 6f 66 20 74 | iterati|ons of t|
|00000aa0| 68 65 20 6d 61 69 6e 20 | 6c 6f 6f 70 2c 20 75 6e |he main |loop, un|
|00000ab0| 74 69 6c 20 61 20 22 73 | 74 65 61 64 79 20 73 74 |til a "s|teady st|
|00000ac0| 61 74 65 22 20 69 73 0a | 58 72 65 61 63 68 65 64 |ate" is.|Xreached|
|00000ad0| 20 28 65 2e 67 2e 2c 20 | 75 6e 74 69 6c 20 73 6f | (e.g., |until so|
|00000ae0| 6d 65 20 63 61 63 68 65 | 20 67 65 74 73 20 66 69 |me cache| gets fi|
|00000af0| 6c 6c 65 64 29 2e 20 20 | 49 6e 20 62 6f 74 68 20 |lled). |In both |
|00000b00| 63 61 73 65 73 20 28 69 | 6e 69 74 69 61 6c 69 7a |cases (i|nitializ|
|00000b10| 61 74 69 6f 6e 0a 58 61 | 6e 64 20 70 72 65 2d 73 |ation.Xa|nd pre-s|
|00000b20| 74 65 61 64 79 20 73 74 | 61 74 65 20 69 74 65 72 |teady st|ate iter|
|00000b30| 61 74 69 6f 6e 73 29 2c | 20 74 68 65 72 65 20 6d |ations),| there m|
|00000b40| 61 79 20 62 65 20 6d 61 | 6e 79 20 61 6c 6c 6f 63 |ay be ma|ny alloc|
|00000b50| 61 74 69 6f 6e 20 63 61 | 6c 6c 73 2c 20 62 75 74 |ation ca|lls, but|
|00000b60| 0a 58 79 6f 75 20 64 6f | 6e 27 74 20 72 65 61 6c |.Xyou do|n't real|
|00000b70| 6c 79 20 77 61 6e 74 20 | 74 6f 20 6c 6f 6f 6b 20 |ly want |to look |
|00000b80| 61 74 20 74 68 65 6d 3b | 20 72 61 74 68 65 72 2c |at them;| rather,|
|00000b90| 20 79 6f 75 20 77 61 6e | 74 20 74 6f 20 6c 6f 6f | you wan|t to loo|
|00000ba0| 6b 20 61 74 20 77 68 61 | 74 0a 58 6d 65 6d 6f 72 |k at wha|t.Xmemor|
|00000bb0| 79 20 69 73 6e 27 74 20 | 62 65 69 6e 67 20 66 72 |y isn't |being fr|
|00000bc0| 65 65 27 64 20 6f 6e 63 | 65 20 73 74 65 61 64 79 |ee'd onc|e steady|
|00000bd0| 20 73 74 61 74 65 20 68 | 61 73 20 62 65 65 6e 20 | state h|as been |
|00000be0| 72 65 61 63 68 65 64 2e | 20 20 54 68 69 73 0a 58 |reached.| This.X|
|00000bf0| 70 61 63 6b 61 67 65 20 | 68 65 6c 70 73 20 79 6f |package |helps yo|
|00000c00| 75 20 74 6f 20 73 65 65 | 20 74 68 65 20 73 74 61 |u to see| the sta|
|00000c10| 74 65 20 6f 66 20 6d 65 | 6d 6f 72 79 20 61 6c 6c |te of me|mory all|
|00000c20| 6f 63 61 74 69 6f 6e 20 | 61 66 74 65 72 20 73 74 |ocation |after st|
|00000c30| 65 61 64 79 0a 58 73 74 | 61 74 65 20 68 61 73 20 |eady.Xst|ate has |
|00000c40| 62 65 65 6e 20 72 65 61 | 63 68 65 64 2e 0a 58 0a |been rea|ched..X.|
|00000c50| 58 42 75 67 20 72 65 70 | 6f 72 74 73 20 61 6e 64 |XBug rep|orts and|
|00000c60| 20 73 75 67 67 65 73 74 | 69 6f 6e 73 20 66 6f 72 | suggest|ions for|
|00000c70| 20 69 6d 70 72 6f 76 65 | 6d 65 6e 74 73 20 61 72 | improve|ments ar|
|00000c80| 65 20 77 65 6c 63 6f 6d | 65 2e 0a 58 0a 58 32 2e |e welcom|e..X.X2.|
|00000c90| 20 49 6e 73 74 72 75 63 | 74 69 6f 6e 73 0a 58 0a | Instruc|tions.X.|
|00000ca0| 58 54 6f 20 75 73 65 20 | 74 68 69 73 20 70 61 63 |XTo use |this pac|
|00000cb0| 6b 61 67 65 2c 20 74 61 | 6b 65 20 79 6f 75 72 20 |kage, ta|ke your |
|00000cc0| 66 61 76 6f 72 69 74 65 | 20 6d 61 6c 6c 6f 63 2f |favorite| malloc/|
|00000cd0| 66 72 65 65 2f 72 65 61 | 6c 6c 6f 63 20 63 6f 64 |free/rea|lloc cod|
|00000ce0| 65 2c 0a 58 61 6e 64 20 | 63 68 61 6e 67 65 20 74 |e,.Xand |change t|
|00000cf0| 68 65 20 72 6f 75 74 69 | 6e 65 20 6e 61 6d 65 73 |he routi|ne names|
|00000d00| 20 61 73 20 66 6f 6c 6c | 6f 77 73 3a 0a 58 0a 58 | as foll|ows:.X.X|
|00000d10| 09 6d 61 6c 6c 6f 63 20 | 2d 3e 20 6d 6d 61 6c 6c |.malloc |-> mmall|
|00000d20| 6f 63 0a 58 09 66 72 65 | 65 20 2d 3e 20 66 66 72 |oc.X.fre|e -> ffr|
|00000d30| 65 65 0a 58 09 72 65 61 | 6c 6c 6f 63 20 2d 3e 20 |ee.X.rea|lloc -> |
|00000d40| 72 72 65 61 6c 6c 6f 63 | 0a 58 0a 58 59 6f 75 27 |rrealloc|.X.XYou'|
|00000d50| 6c 6c 20 70 72 6f 62 61 | 62 6c 79 20 61 6c 73 6f |ll proba|bly also|
|00000d60| 20 6e 65 65 64 20 74 6f | 20 61 64 64 20 74 68 65 | need to| add the|
|00000d70| 20 66 6f 6c 6c 6f 77 69 | 6e 67 20 6c 69 6e 65 20 | followi|ng line |
|00000d80| 74 6f 20 74 68 65 20 62 | 65 67 69 6e 6e 69 6e 67 |to the b|eginning|
|00000d90| 20 6f 66 0a 58 79 6f 75 | 72 20 6d 61 6c 6c 6f 63 | of.Xyou|r malloc|
|00000da0| 2e 63 3a 0a 58 0a 58 09 | 63 68 61 72 20 2a 6d 61 |.c:.X.X.|char *ma|
|00000db0| 6c 6c 6f 63 28 29 3b 0a | 58 0a 58 28 62 65 63 61 |lloc();.|X.X(beca|
|00000dc0| 75 73 65 20 72 65 61 6c | 6c 6f 63 20 73 74 69 6c |use real|loc stil|
|00000dd0| 6c 20 63 61 6c 6c 73 20 | 6d 61 6c 6c 6f 63 2c 20 |l calls |malloc, |
|00000de0| 62 75 74 20 6d 61 6c 6c | 6f 63 20 69 73 20 6e 6f |but mall|oc is no|
|00000df0| 20 6c 6f 6e 67 65 72 20 | 64 65 66 69 6e 65 64 20 | longer |defined |
|00000e00| 69 6e 0a 58 74 68 61 74 | 20 66 69 6c 65 29 2e 20 |in.Xthat| file). |
|00000e10| 20 54 68 65 6e 20 6c 69 | 6e 6b 20 74 68 65 20 70 | Then li|nk the p|
|00000e20| 72 6f 67 72 61 6d 20 74 | 6f 20 62 65 20 6c 65 61 |rogram t|o be lea|
|00000e30| 6b 2d 74 72 61 63 65 64 | 20 77 69 74 68 20 6d 61 |k-traced| with ma|
|00000e40| 6c 74 72 61 63 65 2e 6f | 2c 0a 58 62 74 72 65 65 |ltrace.o|,.Xbtree|
|00000e50| 2e 6f 2c 20 61 6e 64 20 | 28 79 6f 75 72 20 6d 6f |.o, and |(your mo|
|00000e60| 64 69 66 69 65 64 29 20 | 6d 61 6c 6c 6f 63 2e 6f |dified) |malloc.o|
|00000e70| 2e 20 20 49 20 77 6f 75 | 6c 64 20 68 61 76 65 20 |. I wou|ld have |
|00000e80| 69 6e 63 6c 75 64 65 64 | 20 6d 79 20 6d 61 6c 6c |included| my mall|
|00000e90| 6f 63 2e 63 2c 0a 58 62 | 75 74 20 69 74 27 73 20 |oc.c,.Xb|ut it's |
|00000ea0| 74 68 65 20 63 6f 70 79 | 72 69 67 68 74 65 64 20 |the copy|righted |
|00000eb0| 42 53 44 20 34 2e 33 20 | 63 6f 64 65 2c 20 61 6e |BSD 4.3 |code, an|
|00000ec0| 64 20 62 65 73 69 64 65 | 73 2c 20 74 68 65 72 65 |d beside|s, there|
|00000ed0| 20 61 72 65 20 70 6c 65 | 6e 74 79 0a 58 6f 66 20 | are ple|nty.Xof |
|00000ee0| 70 75 62 6c 69 63 20 64 | 6f 6d 61 69 6e 20 6d 61 |public d|omain ma|
|00000ef0| 6c 6c 6f 63 27 73 20 61 | 76 61 69 6c 61 62 6c 65 |lloc's a|vailable|
|00000f00| 20 28 65 2e 67 2e 2c 20 | 69 6e 20 76 6f 6c 75 6d | (e.g., |in volum|
|00000f10| 65 20 36 20 6f 66 20 6d | 6f 64 2e 73 6f 75 72 63 |e 6 of m|od.sourc|
|00000f20| 65 73 29 2e 0a 58 0a 58 | 54 6f 20 74 72 61 63 65 |es)..X.X|To trace|
|00000f30| 20 61 20 6c 65 61 6b 2c | 20 74 61 6b 65 20 74 68 | a leak,| take th|
|00000f40| 65 20 65 78 61 6d 70 6c | 65 20 70 72 6f 67 72 61 |e exampl|e progra|
|00000f50| 6d 20 73 6b 65 6c 65 74 | 6f 6e 2c 20 61 6e 64 20 |m skelet|on, and |
|00000f60| 61 75 67 6d 65 6e 74 20 | 69 74 20 61 73 0a 58 66 |augment |it as.Xf|
|00000f70| 6f 6c 6c 6f 77 73 3a 0a | 58 09 65 78 74 65 72 6e |ollows:.|X.extern|
|00000f80| 20 69 6e 74 20 4d 61 6c | 54 72 61 63 65 45 6e 62 | int Mal|TraceEnb|
|00000f90| 6c 64 3b 0a 58 09 65 78 | 74 65 72 6e 20 69 6e 74 |ld;.X.ex|tern int|
|00000fa0| 20 4d 61 6c 42 72 6b 4e | 75 6d 3b 0a 58 09 69 6e | MalBrkN|um;.X.in|
|00000fb0| 69 74 69 61 6c 69 7a 61 | 74 69 6f 6e 20 63 6f 64 |itializa|tion cod|
|00000fc0| 65 3b 0a 58 09 64 6f 20 | 7b 0a 58 09 09 2e 2e 2e |e;.X.do |{.X.....|
|00000fd0| 0a 58 09 09 69 66 20 28 | 20 73 74 65 61 64 79 20 |.X..if (| steady |
|00000fe0| 73 74 61 74 65 20 72 65 | 61 63 68 65 64 29 0a 58 |state re|ached).X|
|00000ff0| 09 09 09 4d 61 6c 54 72 | 61 63 65 45 6e 62 6c 64 |...MalTr|aceEnbld|
|00001000| 20 3d 20 31 3b 0a 58 09 | 09 2e 2e 2e 0a 58 09 09 | = 1;.X.|.....X..|
|00001010| 61 74 20 65 6e 64 20 6f | 66 20 66 69 72 73 74 20 |at end o|f first |
|00001020| 73 74 65 61 64 79 2d 73 | 74 61 74 65 20 63 79 63 |steady-s|tate cyc|
|00001030| 6c 65 3a 0a 58 09 09 09 | 50 4d 61 6c 28 2d 31 30 |le:.X...|PMal(-10|
|00001040| 29 3b 09 2f 2a 20 70 72 | 69 6e 74 20 6c 61 73 74 |);./* pr|int last|
|00001050| 20 31 30 20 28 73 61 79 | 29 20 6d 61 6c 6c 6f 63 | 10 (say|) malloc|
|00001060| 27 73 0a 58 09 09 09 09 | 09 20 20 20 74 68 61 74 |'s.X....|. that|
|00001070| 20 68 61 76 65 6e 27 74 | 20 79 65 74 20 62 65 65 | haven't| yet bee|
|00001080| 6e 20 66 72 65 65 27 64 | 20 2a 2f 0a 58 09 7d 20 |n free'd| */.X.} |
|00001090| 77 68 69 6c 65 20 28 31 | 29 3b 20 2f 2a 20 6d 61 |while (1|); /* ma|
|000010a0| 69 6e 20 6c 6f 6f 70 20 | 2a 2f 0a 58 0a 58 54 68 |in loop |*/.X.XTh|
|000010b0| 65 6e 20 63 6f 6d 70 69 | 6c 65 20 74 68 65 20 70 |en compi|le the p|
|000010c0| 72 6f 67 72 61 6d 20 77 | 69 74 68 20 2d 67 2c 20 |rogram w|ith -g, |
|000010d0| 61 6e 64 20 72 75 6e 20 | 69 74 2e 20 20 41 74 20 |and run |it. At |
|000010e0| 74 68 65 20 65 6e 64 20 | 6f 66 20 74 68 65 20 66 |the end |of the f|
|000010f0| 69 72 73 74 0a 58 63 79 | 63 6c 65 2c 20 50 4d 61 |irst.Xcy|cle, PMa|
|00001100| 6c 20 77 69 6c 6c 20 70 | 72 69 6e 74 20 61 20 6c |l will p|rint a l|
|00001110| 69 73 74 20 6f 66 20 74 | 68 65 20 6c 61 73 74 20 |ist of t|he last |
|00001120| 31 30 20 6d 61 6c 6c 6f | 63 27 73 20 74 68 61 74 |10 mallo|c's that|
|00001130| 20 68 61 76 65 6e 27 74 | 20 79 65 74 20 62 65 65 | haven't| yet bee|
|00001140| 6e 0a 58 66 72 65 65 64 | 2e 20 20 28 50 4d 61 6c |n.Xfreed|. (PMal|
|00001150| 28 6e 29 20 77 69 6c 6c | 20 70 72 69 6e 74 20 74 |(n) will| print t|
|00001160| 68 65 20 66 69 72 73 74 | 20 6e 20 65 6e 74 72 69 |he first| n entri|
|00001170| 65 73 20 69 66 20 6e 20 | 3e 20 30 2c 20 74 68 65 |es if n |> 0, the|
|00001180| 20 6c 61 73 74 20 2d 6e | 0a 58 65 6e 74 72 69 65 | last -n|.Xentrie|
|00001190| 73 20 69 66 20 6e 20 3c | 20 30 2c 20 61 6e 64 20 |s if n <| 0, and |
|000011a0| 61 6c 6c 20 65 6e 74 72 | 69 65 73 20 69 66 20 6e |all entr|ies if n|
|000011b0| 20 3d 3d 20 30 29 2e 20 | 20 4e 6f 74 65 20 74 68 | == 0). | Note th|
|000011c0| 65 20 73 65 71 75 65 6e | 63 65 20 6e 75 6d 62 65 |e sequen|ce numbe|
|000011d0| 72 20 6f 66 0a 58 6f 6e | 65 20 6f 66 20 74 68 65 |r of.Xon|e of the|
|000011e0| 73 65 20 6d 61 6c 6c 6f | 63 73 2c 20 61 6e 64 20 |se mallo|cs, and |
|000011f0| 74 68 65 6e 20 67 6f 20 | 69 6e 74 6f 20 64 62 78 |then go |into dbx|
|00001200| 20 6f 6e 20 74 68 65 20 | 70 72 6f 67 72 61 6d 2c | on the |program,|
|00001210| 20 61 6e 64 20 70 75 74 | 20 61 0a 58 62 72 65 61 | and put| a.Xbrea|
|00001220| 6b 70 6f 69 6e 74 20 73 | 6f 6d 65 77 68 65 72 65 |kpoint s|omewhere|
|00001230| 20 69 6e 20 74 68 65 20 | 69 6e 69 74 69 61 6c 69 | in the |initiali|
|00001240| 7a 61 74 69 6f 6e 20 63 | 6f 64 65 2c 20 61 6e 64 |zation c|ode, and|
|00001250| 20 72 75 6e 20 74 68 65 | 20 70 72 6f 67 72 61 6d | run the| program|
|00001260| 2e 20 20 57 68 65 6e 0a | 58 79 6f 75 20 68 69 74 |. When.|Xyou hit|
|00001270| 20 74 68 65 20 62 72 65 | 61 6b 70 6f 69 6e 74 2c | the bre|akpoint,|
|00001280| 20 75 73 65 20 64 62 78 | 20 74 6f 20 73 65 74 20 | use dbx| to set |
|00001290| 4d 61 6c 42 72 6b 4e 75 | 6d 20 74 6f 20 74 68 65 |MalBrkNu|m to the|
|000012a0| 20 6e 75 6d 62 65 72 20 | 6f 66 20 74 68 65 0a 58 | number |of the.X|
|000012b0| 6d 61 6c 6c 6f 63 20 79 | 6f 75 20 6a 75 73 74 20 |malloc y|ou just |
|000012c0| 6e 6f 74 69 63 65 64 2c | 20 61 6e 64 20 73 65 74 |noticed,| and set|
|000012d0| 20 61 20 62 72 65 61 6b | 20 69 6e 20 4d 61 6c 42 | a break| in MalB|
|000012e0| 72 65 61 6b 2e 20 20 54 | 68 65 6e 2c 20 63 6f 6e |reak. T|hen, con|
|000012f0| 74 69 6e 75 65 20 74 68 | 65 0a 58 70 72 6f 67 72 |tinue th|e.Xprogr|
|00001300| 61 6d 2e 20 20 57 68 65 | 6e 20 74 68 65 20 6d 61 |am. Whe|n the ma|
|00001310| 6c 6c 6f 63 20 63 61 6c | 6c 20 69 6e 20 71 75 65 |lloc cal|l in que|
|00001320| 73 74 69 6f 6e 20 69 73 | 20 72 65 61 63 68 65 64 |stion is| reached|
|00001330| 2c 20 4d 61 6c 42 72 65 | 61 6b 20 77 69 6c 6c 20 |, MalBre|ak will |
|00001340| 67 65 74 0a 58 63 61 6c | 6c 65 64 2c 20 62 72 65 |get.Xcal|led, bre|
|00001350| 61 6b 69 6e 67 2c 20 61 | 6e 64 20 67 69 76 69 6e |aking, a|nd givin|
|00001360| 67 20 79 6f 75 20 61 20 | 63 68 61 6e 63 65 20 74 |g you a |chance t|
|00001370| 6f 20 65 78 61 6d 69 6e | 65 20 74 68 65 20 73 74 |o examin|e the st|
|00001380| 61 74 65 20 6f 66 20 74 | 68 65 0a 58 70 72 6f 67 |ate of t|he.Xprog|
|00001390| 72 61 6d 20 61 74 20 74 | 68 65 20 74 69 6d 65 20 |ram at t|he time |
|000013a0| 6f 66 20 74 68 69 73 20 | 28 70 6f 74 65 6e 74 69 |of this |(potenti|
|000013b0| 61 6c 6c 79 20 6c 65 61 | 6b 69 6e 67 29 20 6d 61 |ally lea|king) ma|
|000013c0| 6c 6c 6f 63 20 63 61 6c | 6c 2e 20 20 49 6e 20 63 |lloc cal|l. In c|
|000013d0| 61 73 65 0a 58 74 68 69 | 73 20 63 61 6c 6c 20 69 |ase.Xthi|s call i|
|000013e0| 73 20 73 74 69 6c 6c 20 | 77 69 74 68 69 6e 20 74 |s still |within t|
|000013f0| 68 65 20 73 74 65 61 64 | 79 2d 73 74 61 74 65 20 |he stead|y-state |
|00001400| 73 65 74 75 70 20 28 69 | 74 20 69 73 20 73 6f 6d |setup (i|t is som|
|00001410| 65 74 69 6d 65 73 20 64 | 69 66 66 69 63 75 6c 74 |etimes d|ifficult|
|00001420| 0a 58 74 6f 20 66 69 6e | 64 20 77 68 65 72 65 20 |.Xto fin|d where |
|00001430| 74 68 65 20 73 65 74 75 | 70 20 65 6e 64 73 29 2c |the setu|p ends),|
|00001440| 20 79 6f 75 20 63 61 6e | 20 75 73 65 20 64 62 78 | you can| use dbx|
|00001450| 20 74 6f 20 63 61 6c 6c | 20 4e 65 78 74 4d 61 6c | to call| NextMal|
|00001460| 2c 20 74 6f 20 73 65 74 | 0a 58 4d 61 6b 42 72 6b |, to set|.XMakBrk|
|00001470| 4e 75 6d 20 74 6f 20 62 | 65 20 74 68 65 20 6e 65 |Num to b|e the ne|
|00001480| 78 74 20 74 72 61 63 65 | 64 20 6d 61 6c 6c 6f 63 |xt trace|d malloc|
|00001490| 20 63 61 6c 6c 2e 0a 58 | 0a 58 32 2e 31 20 55 73 | call..X|.X2.1 Us|
|000014a0| 61 67 65 20 44 65 74 61 | 69 6c 73 0a 58 0a 58 54 |age Deta|ils.X.XT|
|000014b0| 68 69 73 20 74 65 63 68 | 6e 69 71 75 65 20 69 73 |his tech|nique is|
|000014c0| 20 6e 6f 74 20 61 70 70 | 6c 69 63 61 62 6c 65 20 | not app|licable |
|000014d0| 74 6f 20 73 69 74 75 61 | 74 69 6f 6e 73 20 77 68 |to situa|tions wh|
|000014e0| 65 72 65 20 74 68 65 20 | 73 74 65 61 64 79 20 73 |ere the |steady s|
|000014f0| 74 61 74 65 0a 58 61 6c | 6c 6f 63 61 74 69 6f 6e |tate.Xal|location|
|00001500| 20 62 65 68 61 76 69 6f | 72 20 28 69 2e 65 2e 2c | behavio|r (i.e.,|
|00001510| 20 6f 72 64 65 72 20 61 | 6e 64 20 73 69 7a 65 20 | order a|nd size |
|00001520| 6f 66 20 6d 61 6c 6c 6f | 63 20 72 65 71 75 65 73 |of mallo|c reques|
|00001530| 74 73 29 20 65 78 68 69 | 62 69 74 73 0a 58 76 61 |ts) exhi|bits.Xva|
|00001540| 72 69 61 74 69 6f 6e 2c | 20 65 2e 67 2e 2c 20 64 |riation,| e.g., d|
|00001550| 75 65 20 74 6f 20 70 73 | 65 75 64 6f 2d 72 61 6e |ue to ps|eudo-ran|
|00001560| 64 6f 6d 69 7a 61 74 69 | 6f 6e 20 6f 72 20 69 6e |domizati|on or in|
|00001570| 74 65 72 61 63 74 69 6f | 6e 20 77 69 74 68 20 6f |teractio|n with o|
|00001580| 74 68 65 72 0a 58 70 72 | 6f 63 65 73 73 65 73 20 |ther.Xpr|ocesses |
|00001590| 76 69 61 20 6e 6f 6e 2d | 64 65 74 65 72 6d 69 6e |via non-|determin|
|000015a0| 69 73 74 69 63 61 6c 6c | 79 20 6f 72 64 65 72 65 |isticall|y ordere|
|000015b0| 64 20 6d 65 73 73 61 67 | 65 20 65 78 63 68 61 6e |d messag|e exchan|
|000015c0| 67 65 73 2e 20 20 49 6e | 20 73 75 63 68 0a 58 73 |ges. In| such.Xs|
|000015d0| 69 74 75 61 74 69 6f 6e | 73 20 79 6f 75 20 63 61 |ituation|s you ca|
|000015e0| 6e 20 73 6f 6d 65 74 69 | 6d 65 73 20 69 6e 68 69 |n someti|mes inhi|
|000015f0| 62 69 74 20 74 68 65 20 | 76 61 72 69 61 74 69 6f |bit the |variatio|
|00001600| 6e 20 64 75 72 69 6e 67 | 20 64 65 62 75 67 67 69 |n during| debuggi|
|00001610| 6e 67 20 28 65 2e 67 2e | 2c 0a 58 62 79 20 66 6f |ng (e.g.|,.Xby fo|
|00001620| 72 63 69 6e 67 20 69 6e | 74 65 72 61 63 74 69 6f |rcing in|teractio|
|00001630| 6e 73 20 74 6f 20 6f 63 | 63 75 72 20 69 6e 20 74 |ns to oc|cur in t|
|00001640| 68 65 20 73 61 6d 65 20 | 6f 72 64 65 72 20 65 61 |he same |order ea|
|00001650| 63 68 20 74 69 6d 65 29 | 2e 0a 58 41 6c 74 65 72 |ch time)|..XAlter|
|00001660| 6e 61 74 69 76 65 6c 79 | 2c 20 79 6f 75 20 63 61 |natively|, you ca|
|00001670| 6e 20 75 73 65 20 64 62 | 78 20 74 6f 20 73 65 74 |n use db|x to set|
|00001680| 20 4d 61 6c 42 72 65 61 | 6b 53 69 7a 65 20 74 6f | MalBrea|kSize to|
|00001690| 20 62 65 20 74 68 65 20 | 73 69 7a 65 20 6f 66 20 | be the |size of |
|000016a0| 74 68 65 0a 58 6d 61 6c | 6c 6f 63 20 72 65 71 75 |the.Xmal|loc requ|
|000016b0| 65 73 74 20 61 74 20 77 | 68 69 63 68 20 74 6f 20 |est at w|hich to |
|000016c0| 68 61 76 65 20 4d 61 6c | 42 72 65 61 6b 20 63 61 |have Mal|Break ca|
|000016d0| 6c 6c 65 64 2c 20 74 6f | 20 72 65 61 63 68 20 61 |lled, to| reach a|
|000016e0| 20 62 72 65 61 6b 70 6f | 69 6e 74 0a 58 28 73 69 | breakpo|int.X(si|
|000016f0| 6d 69 6c 61 72 20 74 6f | 20 74 68 65 20 4d 61 6c |milar to| the Mal|
|00001700| 42 72 6b 4e 75 6d 20 73 | 63 68 65 6d 65 20 64 65 |BrkNum s|cheme de|
|00001710| 73 63 72 69 62 65 64 20 | 61 62 6f 76 65 29 2e 20 |scribed |above). |
|00001720| 20 54 68 69 73 20 63 61 | 6e 20 62 65 20 75 73 65 | This ca|n be use|
|00001730| 66 75 6c 20 77 68 65 6e | 0a 58 74 68 65 20 6f 72 |ful when|.Xthe or|
|00001740| 64 65 72 20 6f 66 20 6d | 61 6c 6c 6f 63 73 20 69 |der of m|allocs i|
|00001750| 73 6e 27 74 20 66 69 78 | 65 64 2c 20 62 75 74 20 |sn't fix|ed, but |
|00001760| 61 20 70 61 72 74 69 63 | 75 6c 61 72 20 73 69 7a |a partic|ular siz|
|00001770| 65 20 6b 65 65 70 73 20 | 73 68 6f 77 69 6e 67 20 |e keeps |showing |
|00001780| 75 70 20 69 6e 0a 58 74 | 68 65 20 6c 69 73 74 20 |up in.Xt|he list |
|00001790| 6f 66 20 6d 61 6c 6c 6f | 63 27 73 20 74 68 61 74 |of mallo|c's that|
|000017a0| 20 68 61 76 65 6e 27 74 | 20 79 65 74 20 62 65 65 | haven't| yet bee|
|000017b0| 6e 20 66 72 65 65 27 64 | 2e 0a 58 0a 58 54 68 65 |n free'd|..X.XThe|
|000017c0| 72 65 20 69 73 20 61 6c | 73 6f 20 61 20 72 6f 75 |re is al|so a rou|
|000017d0| 74 69 6e 65 20 63 61 6c | 6c 65 64 20 55 6e 74 72 |tine cal|led Untr|
|000017e0| 61 63 65 64 46 72 65 65 | 20 74 68 61 74 20 67 65 |acedFree| that ge|
|000017f0| 74 73 20 63 61 6c 6c 65 | 64 20 77 68 65 6e 20 61 |ts calle|d when a|
|00001800| 20 66 72 65 65 0a 58 63 | 61 6c 6c 20 69 73 20 6d | free.Xc|all is m|
|00001810| 61 64 65 20 6f 6e 20 61 | 6e 20 61 64 64 72 65 73 |ade on a|n addres|
|00001820| 73 20 74 68 61 74 20 77 | 61 73 20 6e 6f 74 20 6d |s that w|as not m|
|00001830| 61 6c 6c 6f 63 27 64 20 | 77 69 74 68 20 74 72 61 |alloc'd |with tra|
|00001840| 63 69 6e 67 20 65 6e 61 | 62 6c 65 64 0a 58 28 61 |cing ena|bled.X(a|
|00001850| 67 61 69 6e 2c 20 74 68 | 69 73 20 72 6f 75 74 69 |gain, th|is routi|
|00001860| 6e 65 20 69 73 20 70 72 | 65 73 65 6e 74 20 74 6f |ne is pr|esent to|
|00001870| 20 61 6c 6c 6f 77 20 6f | 6e 65 20 74 6f 20 73 65 | allow o|ne to se|
|00001880| 74 20 64 62 78 20 62 72 | 65 61 6b 70 6f 69 6e 74 |t dbx br|eakpoint|
|00001890| 73 20 66 6f 72 0a 58 74 | 68 69 73 20 65 76 65 6e |s for.Xt|his even|
|000018a0| 74 29 2e 20 20 54 68 69 | 73 20 63 6f 75 6c 64 20 |t). Thi|s could |
|000018b0| 65 69 74 68 65 72 20 69 | 6e 64 69 63 61 74 65 20 |either i|ndicate |
|000018c0| 61 20 66 72 65 65 20 63 | 61 6c 6c 20 6f 6e 20 61 |a free c|all on a|
|000018d0| 6e 20 61 64 64 72 65 73 | 73 20 74 68 61 74 0a 58 |n addres|s that.X|
|000018e0| 69 73 6e 27 74 20 6d 61 | 6c 6c 6f 63 27 64 20 28 |isn't ma|lloc'd (|
|000018f0| 61 20 62 75 67 29 20 6f | 72 20 61 20 66 72 65 65 |a bug) o|r a free|
|00001900| 20 63 61 6c 6c 20 6f 6e | 20 61 6e 20 61 64 64 72 | call on| an addr|
|00001910| 65 73 73 20 74 68 61 74 | 20 77 61 73 20 6d 61 6c |ess that| was mal|
|00001920| 6c 6f 63 27 64 20 77 69 | 74 68 0a 58 74 72 61 63 |loc'd wi|th.Xtrac|
|00001930| 69 6e 67 20 64 69 73 61 | 62 6c 65 64 2e 20 20 59 |ing disa|bled. Y|
|00001940| 6f 75 20 63 61 6e 20 64 | 65 74 65 72 6d 69 6e 65 |ou can d|etermine|
|00001950| 20 69 66 20 69 74 20 77 | 61 73 20 6f 66 20 74 68 | if it w|as of th|
|00001960| 65 20 66 6f 72 6d 65 72 | 20 6e 61 74 75 72 65 20 |e former| nature |
|00001970| 62 79 0a 58 67 6f 69 6e | 67 20 74 68 72 6f 75 67 |by.Xgoin|g throug|
|00001980| 68 20 74 68 65 20 73 74 | 61 6e 64 61 72 64 20 6d |h the st|andard m|
|00001990| 61 6c 6c 6f 63 20 63 6f | 64 65 2e 20 20 46 6f 72 |alloc co|de. For|
|000019a0| 20 65 78 61 6d 70 6c 65 | 2c 20 69 6e 20 74 68 65 | example|, in the|
|000019b0| 20 42 53 44 20 63 6f 64 | 65 2c 20 79 6f 75 0a 58 | BSD cod|e, you.X|
|000019c0| 63 61 6e 20 73 65 74 20 | 74 68 65 20 73 77 69 74 |can set |the swit|
|000019d0| 63 68 65 73 20 2d 44 44 | 45 42 55 47 20 61 6e 64 |ches -DD|EBUG and|
|000019e0| 20 2d 44 52 43 48 45 43 | 4b 20 74 6f 20 63 68 65 | -DRCHEC|K to che|
|000019f0| 63 6b 20 66 6f 72 20 74 | 68 69 73 20 61 6e 64 20 |ck for t|his and |
|00001a00| 6f 74 68 65 72 0a 58 74 | 79 70 65 73 20 6f 66 20 |other.Xt|ypes of |
|00001a10| 62 75 67 73 2e 20 20 41 | 6c 74 65 72 6e 61 74 69 |bugs. A|lternati|
|00001a20| 76 65 6c 79 2c 20 79 6f | 75 20 63 61 6e 20 65 6e |vely, yo|u can en|
|00001a30| 61 62 6c 65 20 74 72 61 | 63 69 6e 67 20 66 72 6f |able tra|cing fro|
|00001a40| 6d 20 74 68 65 20 76 65 | 72 79 0a 58 62 65 67 69 |m the ve|ry.Xbegi|
|00001a50| 6e 6e 69 6e 67 20 6f 66 | 20 79 6f 75 72 20 70 72 |nning of| your pr|
|00001a60| 6f 67 72 61 6d 2c 20 61 | 6e 64 20 74 68 65 6e 20 |ogram, a|nd then |
|00001a70| 61 6e 79 20 74 69 6d 65 | 20 55 6e 74 72 61 63 65 |any time| Untrace|
|00001a80| 64 46 72 65 65 20 67 65 | 74 73 20 63 61 6c 6c 65 |dFree ge|ts calle|
|00001a90| 64 2c 20 69 74 0a 58 69 | 6e 64 69 63 61 74 65 73 |d, it.Xi|ndicates|
|00001aa0| 20 61 20 66 72 65 65 20 | 63 61 6c 6c 20 6f 6e 20 | a free |call on |
|00001ab0| 61 6e 20 61 64 64 72 65 | 73 73 73 20 74 68 61 74 |an addre|sss that|
|00001ac0| 20 69 73 6e 27 74 20 6d | 61 6c 6c 6f 63 27 64 2e | isn't m|alloc'd.|
|00001ad0| 0a 58 0a 58 33 2e 20 49 | 6e 74 65 72 61 63 74 69 |.X.X3. I|nteracti|
|00001ae0| 76 65 20 44 65 6d 6f 0a | 58 0a 58 59 6f 75 20 63 |ve Demo.|X.XYou c|
|00001af0| 61 6e 20 74 72 79 20 6f | 75 74 20 74 68 69 73 20 |an try o|ut this |
|00001b00| 70 61 63 6b 61 67 65 20 | 69 6e 74 65 72 61 63 74 |package |interact|
|00001b10| 69 76 65 6c 79 20 62 79 | 20 6d 61 6b 69 6e 67 20 |ively by| making |
|00001b20| 74 68 65 20 70 72 6f 67 | 72 61 6d 20 27 74 65 73 |the prog|ram 'tes|
|00001b30| 74 27 2e 0a 58 4e 6f 74 | 65 20 74 68 61 74 20 69 |t'..XNot|e that i|
|00001b40| 66 20 79 6f 75 20 74 65 | 6c 6c 20 69 74 20 74 6f |f you te|ll it to|
|00001b50| 20 66 72 65 65 20 73 6f | 6d 65 20 6d 65 6d 6f 72 | free so|me memor|
|00001b60| 79 20 74 68 61 74 20 77 | 61 73 20 6e 6f 74 20 6d |y that w|as not m|
|00001b70| 61 6c 6c 6f 63 27 64 20 | 28 77 69 74 68 0a 58 4d |alloc'd |(with.XM|
|00001b80| 61 6c 54 72 61 63 65 45 | 6e 62 6c 64 20 3d 20 31 |alTraceE|nbld = 1|
|00001b90| 29 2c 20 69 74 20 77 69 | 6c 6c 20 67 69 76 65 20 |), it wi|ll give |
|00001ba0| 79 6f 75 20 61 20 77 61 | 72 6e 69 6e 67 20 61 6e |you a wa|rning an|
|00001bb0| 64 20 74 68 65 6e 20 74 | 72 79 20 74 6f 20 66 72 |d then t|ry to fr|
|00001bc0| 65 65 20 74 68 65 0a 58 | 61 64 64 72 65 73 73 20 |ee the.X|address |
|00001bd0| 61 6e 79 77 61 79 20 28 | 66 6f 72 20 74 68 65 20 |anyway (|for the |
|00001be0| 72 65 61 73 6f 6e 73 20 | 65 78 70 6c 61 69 6e 65 |reasons |explaine|
|00001bf0| 64 20 65 61 72 6c 69 65 | 72 29 2e 20 20 54 68 69 |d earlie|r). Thi|
|00001c00| 73 20 6d 61 79 20 6f 72 | 20 6d 61 79 20 6e 6f 74 |s may or| may not|
|00001c10| 0a 58 63 61 75 73 65 20 | 6d 61 6c 6c 6f 63 2f 66 |.Xcause |malloc/f|
|00001c20| 72 65 65 20 74 6f 20 67 | 65 74 20 69 6e 74 6f 20 |ree to g|et into |
|00001c30| 61 20 62 61 64 20 73 74 | 61 74 65 3b 20 69 6e 20 |a bad st|ate; in |
|00001c40| 42 53 44 20 6d 61 6c 6c | 6f 63 20 74 68 69 73 20 |BSD mall|oc this |
|00001c50| 63 61 6e 20 63 61 75 73 | 65 20 61 0a 58 63 6f 72 |can caus|e a.Xcor|
|00001c60| 65 20 64 75 6d 70 2c 20 | 66 6f 72 20 69 6e 73 74 |e dump, |for inst|
|00001c70| 61 6e 63 65 2e 0a 58 0a | 58 34 2e 20 41 63 6b 6e |ance..X.|X4. Ackn|
|00001c80| 6f 6c 65 64 67 65 6d 65 | 6e 74 73 2c 20 48 69 73 |oledgeme|nts, His|
|00001c90| 74 6f 72 79 0a 58 0a 58 | 54 68 61 6e 6b 73 20 74 |tory.X.X|Thanks t|
|00001ca0| 6f 20 52 69 63 68 61 72 | 64 20 48 65 6c 6c 69 65 |o Richar|d Hellie|
|00001cb0| 72 20 66 72 6f 6d 20 74 | 68 65 20 55 6e 69 76 65 |r from t|he Unive|
|00001cc0| 72 73 69 74 79 20 6f 66 | 20 4b 65 6e 74 20 61 74 |rsity of| Kent at|
|00001cd0| 20 43 61 6e 74 65 72 62 | 75 72 79 0a 58 28 72 6c | Canterb|ury.X(rl|
|00001ce0| 68 40 75 6b 63 2e 55 55 | 43 50 29 20 66 6f 72 20 |h@ukc.UU|CP) for |
|00001cf0| 74 68 65 20 62 74 72 65 | 65 20 70 61 63 6b 61 67 |the btre|e packag|
|00001d00| 65 20 28 77 68 69 63 68 | 20 49 20 6d 6f 64 69 66 |e (which| I modif|
|00001d10| 69 65 64 20 73 6c 69 67 | 68 74 6c 79 20 66 6f 72 |ied slig|htly for|
|00001d20| 20 74 68 65 0a 58 63 75 | 72 72 65 6e 74 20 70 61 | the.Xcu|rrent pa|
|00001d30| 63 6b 61 67 65 29 2e 20 | 20 49 20 70 72 6f 62 61 |ckage). | I proba|
|00001d40| 62 6c 79 20 63 6f 75 6c | 64 20 68 61 76 65 20 69 |bly coul|d have i|
|00001d50| 6d 70 6c 65 6d 65 6e 74 | 65 64 20 6d 79 20 74 72 |mplement|ed my tr|
|00001d60| 61 63 65 20 70 61 63 6b | 61 67 65 20 6d 6f 72 65 |ace pack|age more|
|00001d70| 0a 58 65 66 66 69 63 69 | 65 6e 74 6c 79 20 74 68 |.Xeffici|ently th|
|00001d80| 61 6e 20 69 74 20 77 6f | 72 6b 73 20 63 75 72 72 |an it wo|rks curr|
|00001d90| 65 6e 74 6c 79 20 28 65 | 2e 67 2e 2c 20 62 79 20 |ently (e|.g., by |
|00001da0| 69 6e 63 6f 72 70 6f 72 | 61 74 69 6e 67 20 74 68 |incorpor|ating th|
|00001db0| 65 20 6c 69 6e 6b 65 64 | 2d 6c 69 73 74 0a 58 61 |e linked|-list.Xa|
|00001dc0| 6e 64 20 62 74 72 65 65 | 20 6e 6f 64 65 73 20 69 |nd btree| nodes i|
|00001dd0| 6e 74 6f 20 74 68 65 20 | 6d 61 6c 6c 6f 63 20 68 |nto the |malloc h|
|00001de0| 65 61 64 65 72 20 6e 6f | 64 65 73 29 2c 20 62 75 |eader no|des), bu|
|00001df0| 74 20 49 20 77 61 73 20 | 6d 6f 72 65 20 69 6e 74 |t I was |more int|
|00001e00| 6f 20 68 61 63 6b 69 6e | 67 0a 58 73 6f 6d 65 74 |o hackin|g.Xsomet|
|00001e10| 68 69 6e 67 20 74 6f 67 | 65 74 68 65 72 20 71 75 |hing tog|ether qu|
|00001e20| 69 63 6b 6c 79 20 74 68 | 61 74 20 77 6f 75 6c 64 |ickly th|at would|
|00001e30| 20 73 6f 6c 76 65 20 6d | 79 20 70 72 6f 62 6c 65 | solve m|y proble|
|00001e40| 6d 73 20 74 68 61 6e 20 | 6d 61 6b 69 6e 67 0a 58 |ms than |making.X|
|00001e50| 65 66 66 69 63 69 65 6e | 74 20 63 6f 64 65 2e 20 |efficien|t code. |
|00001e60| 20 42 65 73 69 64 65 73 | 2c 20 74 68 69 73 20 63 | Besides|, this c|
|00001e70| 6f 64 65 20 64 6f 65 73 | 6e 27 74 20 6e 65 65 64 |ode does|n't need|
|00001e80| 20 74 6f 20 62 65 20 65 | 66 66 69 63 69 65 6e 74 | to be e|fficient|
|00001e90| 2c 20 73 69 6e 63 65 0a | 58 69 74 27 73 20 6f 6e |, since.|Xit's on|
|00001ea0| 6c 79 20 70 6c 75 67 67 | 65 64 20 69 6e 20 64 75 |ly plugg|ed in du|
|00001eb0| 72 69 6e 67 20 64 65 62 | 75 67 67 69 6e 67 2e 0a |ring deb|ugging..|
|00001ec0| 53 48 41 52 5f 45 4f 46 | 0a 69 66 20 74 65 73 74 |SHAR_EOF|.if test|
|00001ed0| 20 36 34 35 32 20 2d 6e | 65 20 22 60 77 63 20 2d | 6452 -n|e "`wc -|
|00001ee0| 63 20 27 52 45 41 44 4d | 45 27 60 22 0a 74 68 65 |c 'READM|E'`".the|
|00001ef0| 6e 0a 09 65 63 68 6f 20 | 73 68 61 72 3a 20 65 72 |n..echo |shar: er|
|00001f00| 72 6f 72 20 74 72 61 6e | 73 6d 69 74 74 69 6e 67 |ror tran|smitting|
|00001f10| 20 22 27 52 45 41 44 4d | 45 27 22 20 27 28 73 68 | "'READM|E'" '(sh|
|00001f20| 6f 75 6c 64 20 68 61 76 | 65 20 62 65 65 6e 20 36 |ould hav|e been 6|
|00001f30| 34 35 32 20 63 68 61 72 | 61 63 74 65 72 73 29 27 |452 char|acters)'|
|00001f40| 0a 66 69 0a 65 63 68 6f | 20 73 68 61 72 3a 20 65 |.fi.echo| shar: e|
|00001f50| 78 74 72 61 63 74 69 6e | 67 20 22 27 62 74 72 65 |xtractin|g "'btre|
|00001f60| 65 2e 63 27 22 20 27 28 | 31 34 35 37 31 20 63 68 |e.c'" '(|14571 ch|
|00001f70| 61 72 61 63 74 65 72 73 | 29 27 0a 69 66 20 74 65 |aracters|)'.if te|
|00001f80| 73 74 20 2d 66 20 27 62 | 74 72 65 65 2e 63 27 0a |st -f 'b|tree.c'.|
|00001f90| 74 68 65 6e 0a 09 65 63 | 68 6f 20 73 68 61 72 3a |then..ec|ho shar:|
|00001fa0| 20 6f 76 65 72 2d 77 72 | 69 74 69 6e 67 20 65 78 | over-wr|iting ex|
|00001fb0| 69 73 74 69 6e 67 20 66 | 69 6c 65 20 22 27 62 74 |isting f|ile "'bt|
|00001fc0| 72 65 65 2e 63 27 22 0a | 66 69 0a 73 65 64 20 27 |ree.c'".|fi.sed '|
|00001fd0| 73 2f 5e 58 2f 2f 27 20 | 3c 3c 20 5c 53 48 41 52 |s/^X//' |<< \SHAR|
|00001fe0| 5f 45 4f 46 20 3e 20 27 | 62 74 72 65 65 2e 63 27 |_EOF > '|btree.c'|
|00001ff0| 0a 58 2f 2a 2a 2a 0a 58 | 0a 58 2a 20 6d 6f 64 75 |.X/***.X|.X* modu|
|00002000| 6c 65 20 6e 61 6d 65 3a | 0a 58 09 62 74 72 65 65 |le name:|.X.btree|
|00002010| 2e 63 0a 58 2a 20 66 75 | 6e 63 74 69 6f 6e 3a 0a |.c.X* fu|nction:.|
|00002020| 58 09 50 72 6f 76 69 64 | 65 20 61 20 6c 69 62 72 |X.Provid|e a libr|
|00002030| 61 72 79 20 6f 66 20 72 | 6f 75 74 69 6e 65 73 20 |ary of r|outines |
|00002040| 66 6f 72 20 63 72 65 61 | 74 69 6e 67 20 61 6e 64 |for crea|ting and|
|00002050| 20 6d 61 6e 69 70 75 6c | 61 74 69 6e 67 0a 58 09 | manipul|ating.X.|
|00002060| 42 2d 54 72 65 65 73 2e | 20 20 54 68 65 20 22 6f |B-Trees.| The "o|
|00002070| 72 64 65 72 22 20 6f 66 | 20 74 68 65 20 42 2d 54 |rder" of| the B-T|
|00002080| 72 65 65 20 69 73 20 63 | 6f 6e 74 72 6f 6c 6c 65 |ree is c|ontrolle|
|00002090| 64 20 62 79 20 61 20 6d | 61 6e 69 66 65 73 74 0a |d by a m|anifest.|
|000020a0| 58 09 63 6f 6e 73 74 61 | 6e 74 2e 0a 58 0a 58 09 |X.consta|nt..X.X.|
|000020b0| 54 68 69 73 20 6d 6f 64 | 75 6c 65 20 72 75 6e 73 |This mod|ule runs|
|000020c0| 20 73 74 61 6e 64 2d 61 | 6c 6f 6e 65 20 77 69 74 | stand-a|lone wit|
|000020d0| 68 20 61 20 64 75 6d 6d | 79 20 6d 61 69 6e 20 70 |h a dumm|y main p|
|000020e0| 72 6f 67 72 61 6d 0a 58 | 09 69 66 20 74 68 65 20 |rogram.X|.if the |
|000020f0| 73 79 6d 62 6f 6c 20 53 | 54 41 4e 44 5f 41 4c 4f |symbol S|TAND_ALO|
|00002100| 4e 45 20 69 73 20 64 65 | 66 69 6e 65 64 2e 0a 58 |NE is de|fined..X|
|00002110| 2a 20 69 6e 74 65 72 66 | 61 63 65 20 72 6f 75 74 |* interf|ace rout|
|00002120| 69 6e 65 73 3a 0a 58 09 | 42 54 52 45 45 0a 58 09 |ines:.X.|BTREE.X.|
|00002130| 49 6e 73 65 72 74 28 64 | 74 6d 2c 20 74 72 65 65 |Insert(d|tm, tree|
|00002140| 29 09 49 6e 73 65 72 74 | 20 44 41 54 55 4d 20 64 |).Insert| DATUM d|
|00002150| 74 6d 20 69 6e 74 6f 20 | 42 2d 74 72 65 65 20 22 |tm into |B-tree "|
|00002160| 74 72 65 65 22 2c 0a 58 | 09 09 09 09 72 65 74 75 |tree",.X|....retu|
|00002170| 72 6e 69 6e 67 20 61 20 | 72 65 66 65 72 65 6e 63 |rning a |referenc|
|00002180| 65 20 74 6f 20 74 68 65 | 20 75 70 64 61 74 65 64 |e to the| updated|
|00002190| 0a 58 09 09 09 09 74 72 | 65 65 2e 0a 58 09 42 54 |.X....tr|ee..X.BT|
|000021a0| 52 45 45 0a 58 09 44 65 | 6c 65 74 65 28 6b 65 79 |REE.X.De|lete(key|
|000021b0| 2c 20 74 72 65 65 29 09 | 52 65 6d 6f 76 65 20 74 |, tree).|Remove t|
|000021c0| 68 65 20 65 6e 74 72 79 | 20 61 73 73 6f 63 69 61 |he entry| associa|
|000021d0| 74 65 64 20 77 69 74 68 | 20 22 6b 65 79 22 0a 58 |ted with| "key".X|
|000021e0| 09 09 09 09 66 72 6f 6d | 20 74 68 65 20 42 2d 54 |....from| the B-T|
|000021f0| 72 65 65 2e 20 20 52 65 | 74 75 72 6e 73 20 61 20 |ree. Re|turns a |
|00002200| 72 65 66 65 72 65 6e 63 | 65 0a 58 09 09 09 09 74 |referenc|e.X....t|
|00002210| 6f 20 74 68 65 20 75 70 | 64 61 74 65 64 20 74 72 |o the up|dated tr|
|00002220| 65 65 2e 0a 58 09 0a 58 | 09 44 41 54 55 4d 20 2a |ee..X..X|.DATUM *|
|00002230| 0a 58 09 53 65 61 72 63 | 68 28 6b 65 79 2c 20 74 |.X.Searc|h(key, t|
|00002240| 72 65 65 29 09 4c 6f 6f | 6b 20 66 6f 72 20 6b 65 |ree).Loo|k for ke|
|00002250| 79 20 22 6b 65 79 22 20 | 69 6e 20 42 2d 74 72 65 |y "key" |in B-tre|
|00002260| 65 20 22 74 72 65 65 22 | 2e 0a 58 09 09 09 09 52 |e "tree"|..X....R|
|00002270| 65 74 75 72 6e 20 61 20 | 72 65 66 65 72 65 6e 63 |eturn a |referenc|
|00002280| 65 20 74 6f 20 74 68 65 | 20 6d 61 74 63 68 69 6e |e to the| matchin|
|00002290| 67 0a 58 09 09 09 09 44 | 41 54 55 4d 20 69 66 20 |g.X....D|ATUM if |
|000022a0| 66 6f 75 6e 64 2c 20 65 | 6c 73 65 20 4e 55 4c 4c |found, e|lse NULL|
|000022b0| 2e 0a 58 0a 58 09 41 70 | 70 6c 79 28 74 2c 20 66 |..X.X.Ap|ply(t, f|
|000022c0| 75 6e 63 29 09 09 41 70 | 70 6c 69 65 73 20 66 75 |unc)..Ap|plies fu|
|000022d0| 6e 63 74 69 6f 6e 20 22 | 66 75 6e 63 22 20 74 6f |nction "|func" to|
|000022e0| 20 65 76 65 72 79 20 63 | 65 6c 6c 0a 58 09 09 09 | every c|ell.X...|
|000022f0| 09 69 6e 20 74 68 65 20 | 42 2d 54 72 65 65 20 2d |.in the |B-Tree -|
|00002300| 2d 20 75 73 65 73 20 61 | 6e 20 69 6e 6f 72 64 65 |- uses a|n inorde|
|00002310| 72 0a 58 09 09 09 09 74 | 72 61 76 65 72 73 61 6c |r.X....t|raversal|
|00002320| 2e 0a 58 2a 20 6c 69 62 | 72 61 72 69 65 73 20 75 |..X* lib|raries u|
|00002330| 73 65 64 3a 0a 58 09 73 | 74 61 6e 64 61 72 64 0a |sed:.X.s|tandard.|
|00002340| 58 2a 20 63 6f 6d 70 69 | 6c 65 20 74 69 6d 65 20 |X* compi|le time |
|00002350| 70 61 72 61 6d 65 74 65 | 72 73 3a 0a 58 09 63 63 |paramete|rs:.X.cc|
|00002360| 20 2d 4f 20 2d 63 20 62 | 74 72 65 65 2e 63 0a 58 | -O -c b|tree.c.X|
|00002370| 2a 20 68 69 73 74 6f 72 | 79 3a 0a 58 09 52 69 63 |* histor|y:.X.Ric|
|00002380| 68 61 72 64 20 48 65 6c | 6c 69 65 72 2c 20 55 6e |hard Hel|lier, Un|
|00002390| 69 76 65 72 73 69 74 79 | 20 6f 66 20 4b 65 6e 74 |iversity| of Kent|
|000023a0| 20 61 74 20 43 61 6e 74 | 65 72 62 75 72 79 2c 0a | at Cant|erbury,.|
|000023b0| 58 09 77 6f 72 6b 69 6e | 67 20 66 72 6f 6d 20 22 |X.workin|g from "|
|000023c0| 41 6c 67 6f 72 69 74 68 | 6d 73 2b 44 61 74 61 20 |Algorith|ms+Data |
|000023d0| 53 74 72 75 63 74 75 72 | 65 73 20 3d 20 50 72 6f |Structur|es = Pro|
|000023e0| 67 72 61 6d 73 22 0a 58 | 09 62 79 20 4e 2e 57 69 |grams".X|.by N.Wi|
|000023f0| 72 74 68 20 2d 2d 20 61 | 6c 73 6f 2c 20 22 44 61 |rth -- a|lso, "Da|
|00002400| 74 61 20 53 74 72 75 63 | 74 75 72 65 73 20 61 6e |ta Struc|tures an|
|00002410| 64 20 50 72 6f 67 72 61 | 6d 20 44 65 73 69 67 6e |d Progra|m Design|
|00002420| 22 20 62 79 20 42 2e 4b | 72 75 73 65 0a 58 09 50 |" by B.K|ruse.X.P|
|00002430| 75 62 2e 20 50 72 65 6e | 74 69 63 65 2d 48 61 6c |ub. Pren|tice-Hal|
|00002440| 6c 2e 0a 58 0a 58 09 4d | 6f 64 69 66 69 65 64 20 |l..X.X.M|odified |
|00002450| 66 6f 72 20 75 73 65 20 | 69 6e 20 64 79 6e 61 6d |for use |in dynam|
|00002460| 69 63 20 6d 65 6d 6f 72 | 79 20 61 6c 6c 6f 63 61 |ic memor|y alloca|
|00002470| 74 69 6f 6e 20 6c 65 61 | 6b 20 74 72 61 63 65 20 |tion lea|k trace |
|00002480| 74 6f 6f 6c 0a 58 09 62 | 79 20 4d 69 6b 65 20 53 |tool.X.b|y Mike S|
|00002490| 63 68 77 61 72 74 7a 2c | 20 33 2d 32 30 2d 38 37 |chwartz,| 3-20-87|
|000024a0| 2e 20 20 57 65 20 63 61 | 6c 6c 20 6d 6d 61 6c 6c |. We ca|ll mmall|
|000024b0| 6f 63 20 61 6e 64 20 66 | 66 72 65 65 20 69 6e 73 |oc and f|free ins|
|000024c0| 74 65 61 64 20 6f 66 0a | 58 09 6d 61 6c 6c 6f 63 |tead of.|X.malloc|
|000024d0| 20 61 6e 64 20 66 72 65 | 65 20 68 65 72 65 2c 20 | and fre|e here, |
|000024e0| 73 69 6e 63 65 20 6d 61 | 6c 6c 6f 63 20 61 6e 64 |since ma|lloc and|
|000024f0| 20 66 72 65 65 20 63 61 | 6c 6c 20 74 68 69 73 20 | free ca|ll this |
|00002500| 62 74 72 65 65 20 70 61 | 63 6b 61 67 65 0a 58 09 |btree pa|ckage.X.|
|00002510| 69 6e 20 74 68 65 20 64 | 79 6e 61 6d 69 63 20 6d |in the d|ynamic m|
|00002520| 65 6d 6f 72 79 20 61 6c | 6c 6f 63 61 74 69 6f 6e |emory al|location|
|00002530| 20 6c 65 61 6b 20 64 65 | 74 65 63 74 69 6f 6e 20 | leak de|tection |
|00002540| 70 61 63 6b 61 67 65 2e | 0a 58 0a 58 2a 2a 2a 2f |package.|.X.X***/|
|00002550| 0a 58 0a 58 23 69 6e 63 | 6c 75 64 65 20 22 62 74 |.X.X#inc|lude "bt|
|00002560| 72 65 65 2e 68 22 0a 58 | 0a 58 44 41 54 55 4d 09 |ree.h".X|.XDATUM.|
|00002570| 4e 75 6c 6c 44 61 74 75 | 6d 20 3d 20 7b 0a 58 09 |NullDatu|m = {.X.|
|00002580| 28 63 68 61 72 20 2a 29 | 20 4e 55 4c 4c 2c 0a 58 |(char *)| NULL,.X|
|00002590| 7d 3b 0a 58 0a 58 73 74 | 61 74 69 63 20 42 54 52 |};.X.Xst|atic BTR|
|000025a0| 45 45 09 09 4e 65 77 4e | 6f 64 65 3b 0a 58 0a 58 |EE..NewN|ode;.X.X|
|000025b0| 0c 2f 2a 0a 58 2a 2a 20 | 20 45 52 52 4f 52 20 2d |./*.X** | ERROR -|
|000025c0| 2d 20 50 72 69 6e 74 20 | 61 6e 20 65 72 72 6f 72 |- Print |an error|
|000025d0| 20 6d 65 73 73 61 67 65 | 0a 58 2a 2a 0a 58 2a 2a | message|.X**.X**|
|000025e0| 09 57 72 69 74 65 20 74 | 68 65 20 65 72 72 6f 72 |.Write t|he error|
|000025f0| 20 74 65 78 74 20 74 6f | 20 74 68 65 0a 58 2a 2a | text to| the.X**|
|00002600| 09 73 74 61 6e 64 61 72 | 64 20 65 72 72 6f 72 20 |.standar|d error |
|00002610| 73 74 72 65 61 6d 2e 0a | 58 2a 2a 0a 58 2a 2a 09 |stream..|X**.X**.|
|00002620| 50 61 72 61 6d 65 74 65 | 72 73 3a 0a 58 2a 2a 09 |Paramete|rs:.X**.|
|00002630| 09 66 6d 74 20 20 20 20 | 20 20 20 2d 2d 20 20 50 |.fmt | -- P|
|00002640| 72 69 6e 74 66 2d 73 74 | 79 6c 65 20 66 6f 72 6d |rintf-st|yle form|
|00002650| 61 74 20 73 74 72 69 6e | 67 0a 58 2a 2a 09 09 61 |at strin|g.X**..a|
|00002660| 72 67 5b 31 2d 33 5d 20 | 20 2d 2d 20 20 41 72 67 |rg[1-3] | -- Arg|
|00002670| 75 6d 65 6e 74 73 20 61 | 73 20 6e 65 65 64 65 64 |uments a|s needed|
|00002680| 2e 0a 58 2a 2a 0a 58 2a | 2a 09 52 65 74 75 72 6e |..X**.X*|*.Return|
|00002690| 73 3a 0a 58 2a 2a 09 09 | 4e 6f 6e 65 2e 0a 58 2a |s:.X**..|None..X*|
|000026a0| 2a 0a 58 2a 2f 0a 58 0a | 58 2f 2a 20 41 52 47 53 |*.X*/.X.|X/* ARGS|
|000026b0| 55 53 45 44 20 2a 2f 0a | 58 0a 58 45 72 72 6f 72 |USED */.|X.XError|
|000026c0| 28 66 6d 74 2c 20 61 72 | 67 31 2c 20 61 72 67 32 |(fmt, ar|g1, arg2|
|000026d0| 2c 20 61 72 67 33 29 0a | 58 63 68 61 72 09 2a 66 |, arg3).|Xchar.*f|
|000026e0| 6d 74 3b 7b 0a 58 09 66 | 70 72 69 6e 74 66 28 73 |mt;{.X.f|printf(s|
|000026f0| 74 64 65 72 72 2c 20 66 | 6d 74 2c 20 61 72 67 31 |tderr, f|mt, arg1|
|00002700| 2c 20 61 72 67 32 2c 20 | 61 72 67 33 29 3b 0a 58 |, arg2, |arg3);.X|
|00002710| 7d 0a 58 0a 58 0c 2f 2a | 0a 58 2a 2a 20 20 4b 45 |}.X.X./*|.X** KE|
|00002720| 59 43 4d 50 20 2d 2d 20 | 43 6f 6d 70 61 72 65 20 |YCMP -- |Compare |
|00002730| 74 77 6f 20 6b 65 79 20 | 76 61 6c 75 65 73 0a 58 |two key |values.X|
|00002740| 2a 2a 0a 58 2a 2a 09 4c | 69 6b 65 20 22 73 74 72 |**.X**.L|ike "str|
|00002750| 63 6d 70 22 20 62 75 74 | 20 75 73 65 20 6b 65 79 |cmp" but| use key|
|00002760| 0a 58 2a 2a 09 76 61 6c | 75 65 73 20 72 61 74 68 |.X**.val|ues rath|
|00002770| 65 72 20 74 68 61 6e 20 | 73 74 72 69 6e 67 73 2e |er than |strings.|
|00002780| 0a 58 2a 2a 0a 58 2a 2a | 09 50 61 72 61 6d 65 74 |.X**.X**|.Paramet|
|00002790| 65 72 73 3a 0a 58 2a 2a | 09 09 6b 65 79 31 20 20 |ers:.X**|..key1 |
|000027a0| 2d 2d 20 20 46 69 72 73 | 74 20 6b 65 79 2c 0a 58 |-- Firs|t key,.X|
|000027b0| 2a 2a 09 09 6b 65 79 32 | 20 20 2d 2d 20 20 53 65 |**..key2| -- Se|
|000027c0| 63 6f 6e 64 20 6b 65 79 | 2e 0a 58 2a 2a 0a 58 2a |cond key|..X**.X*|
|000027d0| 2a 09 52 65 74 75 72 6e | 73 3a 0a 58 2a 2a 09 09 |*.Return|s:.X**..|
|000027e0| 2d 31 20 69 66 20 6b 65 | 79 31 20 3c 20 6b 65 79 |-1 if ke|y1 < key|
|000027f0| 32 3b 0a 58 2a 2a 09 09 | 30 20 20 69 66 20 6b 65 |2;.X**..|0 if ke|
|00002800| 79 31 20 3d 20 6b 65 79 | 32 3b 0a 58 2a 2a 09 09 |y1 = key|2;.X**..|
|00002810| 31 20 20 69 66 20 6b 65 | 79 31 20 3e 20 6b 65 79 |1 if ke|y1 > key|
|00002820| 32 3b 0a 58 2a 2a 0a 58 | 2a 2f 0a 58 0a 58 4b 65 |2;.X**.X|*/.X.XKe|
|00002830| 79 43 6d 70 28 6b 65 79 | 31 2c 20 6b 65 79 32 29 |yCmp(key|1, key2)|
|00002840| 0a 58 4b 45 59 09 6b 65 | 79 31 2c 0a 58 09 6b 65 |.XKEY.ke|y1,.X.ke|
|00002850| 79 32 3b 7b 0a 58 0a 58 | 09 72 65 74 75 72 6e 20 |y2;{.X.X|.return |
|00002860| 6b 65 79 31 20 3c 20 6b | 65 79 32 20 3f 20 2d 31 |key1 < k|ey2 ? -1|
|00002870| 20 3a 20 6b 65 79 31 20 | 3d 3d 20 6b 65 79 32 20 | : key1 |== key2 |
|00002880| 3f 20 30 20 3a 20 31 3b | 0a 58 7d 0a 58 0a 58 0c |? 0 : 1;|.X}.X.X.|
|00002890| 2f 2a 0a 58 2a 2a 20 20 | 53 48 4f 57 44 41 54 55 |/*.X** |SHOWDATU|
|000028a0| 4d 20 2d 2d 20 44 69 73 | 70 6c 61 79 20 61 20 64 |M -- Dis|play a d|
|000028b0| 61 74 75 6d 0a 58 2a 2a | 0a 58 2a 2a 09 41 74 6f |atum.X**|.X**.Ato|
|000028c0| 6d 69 63 20 72 6f 75 74 | 69 6e 65 20 75 73 65 64 |mic rout|ine used|
|000028d0| 20 74 6f 20 64 69 73 70 | 6c 61 79 0a 58 2a 2a 09 | to disp|lay.X**.|
|000028e0| 74 68 65 20 63 6f 6e 74 | 65 6e 74 73 20 6f 66 20 |the cont|ents of |
|000028f0| 61 20 64 61 74 75 6d 2e | 0a 58 2a 2a 0a 58 2a 2a |a datum.|.X**.X**|
|00002900| 09 50 61 72 61 6d 65 74 | 65 72 73 3a 0a 58 2a 2a |.Paramet|ers:.X**|
|00002910| 09 09 64 61 74 75 6d 20 | 20 2d 2d 20 20 44 61 74 |..datum | -- Dat|
|00002920| 75 6d 20 74 6f 20 70 72 | 69 6e 74 2e 0a 58 2a 2a |um to pr|int..X**|
|00002930| 0a 58 2a 2a 09 52 65 74 | 75 72 6e 73 3a 0a 58 2a |.X**.Ret|urns:.X*|
|00002940| 2a 09 09 4e 6f 6e 65 2e | 0a 58 2a 2a 0a 58 2a 2f |*..None.|.X**.X*/|
|00002950| 0a 58 0a 58 53 68 6f 77 | 44 61 74 75 6d 28 64 74 |.X.XShow|Datum(dt|
|00002960| 6d 29 0a 58 44 41 54 55 | 4d 09 64 74 6d 3b 7b 0a |m).XDATU|M.dtm;{.|
|00002970| 58 09 70 72 69 6e 74 66 | 28 22 5c 74 6b 65 79 20 |X.printf|("\tkey |
|00002980| 78 25 78 3a 20 63 61 6c | 6c 6e 75 6d 20 25 64 2c |x%x: cal|lnum %d,|
|00002990| 20 73 69 7a 65 20 25 64 | 5c 6e 22 2c 20 64 74 6d | size %d|\n", dtm|
|000029a0| 2e 6b 65 79 2c 20 64 74 | 6d 2e 69 6e 66 2e 4d 61 |.key, dt|m.inf.Ma|
|000029b0| 6c 43 61 6c 6c 4e 75 6d | 2c 0a 58 09 09 64 74 6d |lCallNum|,.X..dtm|
|000029c0| 2e 69 6e 66 2e 4d 61 6c | 53 69 7a 65 29 3b 0a 58 |.inf.Mal|Size);.X|
|000029d0| 7d 0a 58 0a 58 0c 2f 2a | 0a 58 2a 2a 20 20 4d 4b |}.X.X./*|.X** MK|
|000029e0| 4e 4f 44 45 20 2d 2d 20 | 4d 61 6b 65 20 61 20 6e |NODE -- |Make a n|
|000029f0| 65 77 20 42 2d 74 72 65 | 65 20 6e 6f 64 65 0a 58 |ew B-tre|e node.X|
|00002a00| 2a 2a 0a 58 2a 2a 09 41 | 6c 6c 6f 63 61 74 65 20 |**.X**.A|llocate |
|00002a10| 73 74 6f 72 61 67 65 20 | 66 6f 72 20 61 20 6e 65 |storage |for a ne|
|00002a20| 77 20 42 2d 74 72 65 65 | 20 6e 6f 64 65 0a 58 2a |w B-tree| node.X*|
|00002a30| 2a 09 61 6e 64 20 63 6f | 70 79 20 69 6e 20 73 6f |*.and co|py in so|
|00002a40| 6d 65 20 70 6f 69 6e 74 | 65 72 73 2e 0a 58 2a 2a |me point|ers..X**|
|00002a50| 0a 58 2a 2a 09 50 61 72 | 61 6d 65 74 65 72 73 3a |.X**.Par|ameters:|
|00002a60| 0a 58 2a 2a 09 09 6b 31 | 20 20 2d 2d 20 20 46 69 |.X**..k1| -- Fi|
|00002a70| 72 73 74 20 6b 65 79 20 | 76 61 6c 75 65 2c 0a 58 |rst key |value,.X|
|00002a80| 2a 2a 09 09 70 30 20 20 | 2d 2d 20 20 46 69 72 73 |**..p0 |-- Firs|
|00002a90| 74 20 70 74 72 2c 0a 58 | 2a 2a 09 09 70 31 20 20 |t ptr,.X|**..p1 |
|00002aa0| 2d 2d 20 20 53 65 63 6f | 6e 64 20 70 74 72 2e 0a |-- Seco|nd ptr..|
|00002ab0| 58 2a 2a 0a 58 2a 2a 09 | 52 65 74 75 72 6e 73 3a |X**.X**.|Returns:|
|00002ac0| 0a 58 2a 2a 09 09 52 65 | 66 65 72 65 6e 63 65 20 |.X**..Re|ference |
|00002ad0| 74 6f 20 74 68 65 20 6e | 65 77 20 6e 6f 64 65 2e |to the n|ew node.|
|00002ae0| 0a 58 2a 2a 0a 58 2a 2f | 0a 58 0a 58 42 54 52 45 |.X**.X*/|.X.XBTRE|
|00002af0| 45 0a 58 4d 6b 4e 6f 64 | 65 28 64 74 6d 2c 20 70 |E.XMkNod|e(dtm, p|
|00002b00| 30 2c 20 70 31 29 0a 58 | 44 41 54 55 4d 09 64 74 |0, p1).X|DATUM.dt|
|00002b10| 6d 3b 0a 58 42 54 52 45 | 45 09 70 30 2c 0a 58 09 |m;.XBTRE|E.p0,.X.|
|00002b20| 70 31 3b 7b 0a 58 09 63 | 68 61 72 09 2a 6d 6d 61 |p1;{.X.c|har.*mma|
|00002b30| 6c 6c 6f 63 28 29 3b 0a | 58 09 42 54 52 45 45 09 |lloc();.|X.BTREE.|
|00002b40| 74 3b 0a 58 0a 58 09 74 | 20 3d 20 28 42 54 52 45 |t;.X.X.t| = (BTRE|
|00002b50| 45 29 20 6d 6d 61 6c 6c | 6f 63 28 73 69 7a 65 6f |E) mmall|oc(sizeo|
|00002b60| 66 28 4e 4f 44 45 29 29 | 3b 0a 58 0a 58 09 74 20 |f(NODE))|;.X.X.t |
|00002b70| 2d 3e 20 74 5f 70 74 72 | 20 5b 30 5d 20 3d 20 70 |-> t_ptr| [0] = p|
|00002b80| 30 3b 0a 58 09 74 20 2d | 3e 20 74 5f 70 74 72 20 |0;.X.t -|> t_ptr |
|00002b90| 5b 31 5d 20 3d 20 70 31 | 3b 0a 58 09 74 20 2d 3e |[1] = p1|;.X.t ->|
|00002ba0| 20 74 5f 64 61 74 20 5b | 30 5d 20 3d 20 64 74 6d | t_dat [|0] = dtm|
|00002bb0| 3b 0a 58 09 74 20 2d 3e | 20 74 5f 61 63 74 69 76 |;.X.t ->| t_activ|
|00002bc0| 65 20 20 3d 20 31 3b 0a | 58 0a 58 09 72 65 74 75 |e = 1;.|X.X.retu|
|00002bd0| 72 6e 20 74 3b 0a 58 7d | 0a 58 0c 2f 2a 0a 58 2a |rn t;.X}|.X./*.X*|
|00002be0| 2a 20 20 44 49 53 50 4f | 53 45 20 2d 2d 20 44 69 |* DISPO|SE -- Di|
|00002bf0| 73 70 6f 73 65 20 6f 66 | 20 61 20 74 72 65 65 20 |spose of| a tree |
|00002c00| 6e 6f 64 65 0a 58 2a 2a | 0a 58 2a 2a 09 52 65 74 |node.X**|.X**.Ret|
|00002c10| 75 72 6e 20 74 68 65 20 | 73 74 6f 72 61 67 65 20 |urn the |storage |
|00002c20| 6f 63 63 75 70 69 65 64 | 20 62 79 20 74 68 65 0a |occupied| by the.|
|00002c30| 58 2a 2a 09 74 72 65 65 | 20 6e 6f 64 65 20 74 6f |X**.tree| node to|
|00002c40| 20 74 68 65 20 70 6f 6f | 6c 2e 0a 58 2a 2a 0a 58 | the poo|l..X**.X|
|00002c50| 2a 2a 09 50 61 72 61 6d | 65 74 65 72 73 3a 0a 58 |**.Param|eters:.X|
|00002c60| 2a 2a 09 09 74 20 20 2d | 2d 20 20 50 74 72 20 74 |**..t -|- Ptr t|
|00002c70| 6f 20 74 68 65 20 74 72 | 65 65 20 6e 6f 64 65 2e |o the tr|ee node.|
|00002c80| 0a 58 2a 2a 0a 58 2a 2a | 09 52 65 74 75 72 6e 73 |.X**.X**|.Returns|
|00002c90| 3a 0a 58 2a 2a 09 09 4e | 6f 6e 65 2e 0a 58 2a 2a |:.X**..N|one..X**|
|00002ca0| 0a 58 2a 2f 0a 58 0a 58 | 44 69 73 70 6f 73 65 28 |.X*/.X.X|Dispose(|
|00002cb0| 74 29 0a 58 42 54 52 45 | 45 09 74 3b 7b 0a 58 09 |t).XBTRE|E.t;{.X.|
|00002cc0| 66 66 72 65 65 28 28 63 | 68 61 72 20 2a 29 20 74 |ffree((c|har *) t|
|00002cd0| 29 3b 0a 58 7d 0a 58 0a | 58 0c 2f 2a 0a 58 2a 2a |);.X}.X.|X./*.X**|
|00002ce0| 20 20 49 4e 53 49 4e 4e | 4f 44 45 20 2d 2d 20 41 | INSINN|ODE -- A|
|00002cf0| 64 64 20 61 20 6b 65 79 | 20 74 6f 20 61 20 6e 6f |dd a key| to a no|
|00002d00| 64 65 0a 58 2a 2a 0a 58 | 2a 2a 09 41 64 64 20 61 |de.X**.X|**.Add a|
|00002d10| 20 6b 65 79 20 76 61 6c | 75 65 20 69 6e 74 6f 20 | key val|ue into |
|00002d20| 61 0a 58 2a 2a 09 42 2d | 74 72 65 65 20 6e 6f 64 |a.X**.B-|tree nod|
|00002d30| 65 2e 20 20 53 70 6c 69 | 74 74 69 6e 67 20 6f 66 |e. Spli|tting of|
|00002d40| 0a 58 2a 2a 09 6e 6f 64 | 65 73 20 69 73 20 68 61 |.X**.nod|es is ha|
|00002d50| 6e 64 6c 65 64 20 65 6c | 73 65 77 68 65 72 65 2e |ndled el|sewhere.|
|00002d60| 0a 58 2a 2a 0a 58 2a 2a | 09 50 61 72 61 6d 65 74 |.X**.X**|.Paramet|
|00002d70| 65 72 73 3a 0a 58 2a 2a | 09 09 74 20 20 20 2d 2d |ers:.X**|..t --|
|00002d80| 20 20 50 74 72 20 74 6f | 20 74 68 65 20 6e 6f 64 | Ptr to| the nod|
|00002d90| 65 2c 0a 58 2a 2a 09 09 | 6b 65 79 20 2d 2d 20 20 |e,.X**..|key -- |
|00002da0| 4b 65 79 20 76 61 6c 75 | 65 20 74 6f 20 65 6e 74 |Key valu|e to ent|
|00002db0| 65 72 2c 0a 58 2a 2a 09 | 09 70 74 72 20 2d 2d 20 |er,.X**.|.ptr -- |
|00002dc0| 20 4c 69 6e 6b 20 74 6f | 20 73 75 62 6f 72 64 69 | Link to| subordi|
|00002dd0| 6e 61 74 65 20 6e 6f 64 | 65 2e 0a 58 2a 2a 0a 58 |nate nod|e..X**.X|
|00002de0| 2a 2a 09 52 65 74 75 72 | 6e 73 3a 0a 58 2a 2a 09 |**.Retur|ns:.X**.|
|00002df0| 09 4e 6f 6e 65 2e 0a 58 | 2a 2a 0a 58 2a 2f 0a 58 |.None..X|**.X*/.X|
|00002e00| 0a 58 49 6e 73 49 6e 4e | 6f 64 65 28 74 2c 20 64 |.XInsInN|ode(t, d|
|00002e10| 2c 20 70 74 72 29 0a 58 | 42 54 52 45 45 09 74 2c |, ptr).X|BTREE.t,|
|00002e20| 0a 58 09 70 74 72 3b 0a | 58 44 41 54 55 4d 09 64 |.X.ptr;.|XDATUM.d|
|00002e30| 3b 7b 0a 58 09 69 6e 74 | 09 69 3b 0a 58 0a 58 09 |;{.X.int|.i;.X.X.|
|00002e40| 66 6f 72 20 28 20 69 20 | 3d 20 74 20 2d 3e 20 74 |for ( i |= t -> t|
|00002e50| 5f 61 63 74 69 76 65 3b | 20 69 20 3e 20 30 20 26 |_active;| i > 0 &|
|00002e60| 26 20 4b 65 79 43 6d 70 | 28 64 20 2e 20 6b 65 79 |& KeyCmp|(d . key|
|00002e70| 2c 20 74 20 2d 3e 20 74 | 5f 64 61 74 20 5b 69 2d |, t -> t|_dat [i-|
|00002e80| 31 5d 20 2e 20 6b 65 79 | 29 20 3c 20 30 3b 20 69 |1] . key|) < 0; i|
|00002e90| 2d 2d 29 20 7b 0a 58 09 | 09 74 20 2d 3e 20 74 5f |--) {.X.|.t -> t_|
|00002ea0| 64 61 74 20 5b 69 5d 20 | 20 20 20 20 3d 20 74 20 |dat [i] | = t |
|00002eb0| 2d 3e 20 74 5f 64 61 74 | 20 5b 69 20 2d 20 31 5d |-> t_dat| [i - 1]|
|00002ec0| 3b 0a 58 09 09 74 20 2d | 3e 20 74 5f 70 74 72 20 |;.X..t -|> t_ptr |
|00002ed0| 5b 69 20 2b 20 31 5d 20 | 3d 20 74 20 2d 3e 20 74 |[i + 1] |= t -> t|
|00002ee0| 5f 70 74 72 20 5b 69 5d | 3b 0a 58 09 7d 0a 58 0a |_ptr [i]|;.X.}.X.|
|00002ef0| 58 09 74 20 2d 3e 20 74 | 5f 61 63 74 69 76 65 2b |X.t -> t|_active+|
|00002f00| 2b 3b 0a 58 09 74 20 2d | 3e 20 74 5f 64 61 74 20 |+;.X.t -|> t_dat |
|00002f10| 5b 69 5d 20 20 20 3d 20 | 64 3b 0a 58 09 74 20 2d |[i] = |d;.X.t -|
|00002f20| 3e 20 74 5f 70 74 72 20 | 5b 69 2b 31 5d 20 3d 20 |> t_ptr |[i+1] = |
|00002f30| 70 74 72 3b 0a 58 7d 0a | 58 0a 58 0c 2f 2a 0a 58 |ptr;.X}.|X.X./*.X|
|00002f40| 2a 2a 20 20 49 4e 54 45 | 52 4e 41 4c 49 4e 53 45 |** INTE|RNALINSE|
|00002f50| 52 54 20 2d 2d 20 4b 65 | 79 20 69 6e 73 65 72 74 |RT -- Ke|y insert|
|00002f60| 20 72 6f 75 74 69 6e 65 | 20 70 72 6f 70 65 72 0a | routine| proper.|
|00002f70| 58 2a 2a 0a 58 2a 2a 09 | 54 68 65 20 62 75 73 69 |X**.X**.|The busi|
|00002f80| 6e 65 73 73 20 65 6e 64 | 20 6f 66 20 74 68 65 20 |ness end| of the |
|00002f90| 6b 65 79 20 69 6e 73 65 | 72 74 69 6f 6e 0a 58 2a |key inse|rtion.X*|
|00002fa0| 2a 09 72 6f 75 74 69 6e | 65 2e 0a 58 2a 2a 0a 58 |*.routin|e..X**.X|
|00002fb0| 2a 2a 09 50 61 72 61 6d | 65 74 65 72 73 3a 0a 58 |**.Param|eters:.X|
|00002fc0| 2a 2a 09 09 6b 65 79 20 | 20 2d 2d 20 20 4b 65 79 |**..key | -- Key|
|00002fd0| 20 74 6f 20 69 6e 73 65 | 72 74 2c 0a 58 2a 2a 09 | to inse|rt,.X**.|
|00002fe0| 09 74 20 20 20 20 2d 2d | 20 20 54 72 65 65 20 74 |.t --| Tree t|
|00002ff0| 6f 20 75 73 65 2e 0a 58 | 2a 2a 0a 58 2a 2a 09 52 |o use..X|**.X**.R|
|00003000| 65 74 75 72 6e 73 3a 0a | 58 2a 2a 09 09 56 61 6c |eturns:.|X**..Val|
|00003010| 75 65 20 6f 66 20 74 68 | 65 20 6b 65 79 20 69 6e |ue of th|e key in|
|00003020| 73 65 72 74 65 64 2e 0a | 58 2a 2a 0a 58 2a 2f 0a |serted..|X**.X*/.|
|00003030| 58 0a 58 44 41 54 55 4d | 0a 58 49 6e 74 65 72 6e |X.XDATUM|.XIntern|
|00003040| 61 6c 49 6e 73 65 72 74 | 28 64 74 6d 2c 20 74 29 |alInsert|(dtm, t)|
|00003050| 0a 58 44 41 54 55 4d 09 | 64 74 6d 3b 0a 58 42 54 |.XDATUM.|dtm;.XBT|
|00003060| 52 45 45 09 74 3b 7b 0a | 58 09 69 6e 74 09 69 2c |REE.t;{.|X.int.i,|
|00003070| 0a 58 09 09 6a 3b 0a 58 | 09 44 41 54 55 4d 09 69 |.X..j;.X|.DATUM.i|
|00003080| 6e 73 3b 0a 58 09 42 54 | 52 45 45 09 74 6d 70 3b |ns;.X.BT|REE.tmp;|
|00003090| 0a 58 0a 58 09 69 66 20 | 28 74 20 3d 3d 20 4e 55 |.X.X.if |(t == NU|
|000030a0| 4c 4c 29 20 7b 0a 58 09 | 09 4e 65 77 4e 6f 64 65 |LL) {.X.|.NewNode|
|000030b0| 20 3d 20 4e 55 4c 4c 3b | 0a 58 09 09 72 65 74 75 | = NULL;|.X..retu|
|000030c0| 72 6e 20 64 74 6d 3b 0a | 58 09 7d 20 65 6c 73 65 |rn dtm;.|X.} else|
|000030d0| 20 7b 0a 58 09 09 66 6f | 72 20 28 69 20 3d 20 30 | {.X..fo|r (i = 0|
|000030e0| 3b 20 69 20 3c 20 74 20 | 2d 3e 20 74 5f 61 63 74 |; i < t |-> t_act|
|000030f0| 69 76 65 20 26 26 20 4b | 65 79 43 6d 70 28 74 20 |ive && K|eyCmp(t |
|00003100| 2d 3e 20 74 5f 64 61 74 | 20 5b 69 5d 20 2e 20 6b |-> t_dat| [i] . k|
|00003110| 65 79 2c 20 64 74 6d 20 | 2e 20 6b 65 79 29 20 3c |ey, dtm |. key) <|
|00003120| 20 30 3b 20 2b 2b 69 29 | 0a 58 09 09 09 3b 09 09 | 0; ++i)|.X...;..|
|00003130| 2f 2a 20 4e 55 4c 4c 20 | 42 4f 44 59 20 2a 2f 0a |/* NULL |BODY */.|
|00003140| 58 09 09 69 66 20 28 69 | 20 3c 20 74 20 2d 3e 20 |X..if (i| < t -> |
|00003150| 74 5f 61 63 74 69 76 65 | 20 26 26 20 4b 65 79 43 |t_active| && KeyC|
|00003160| 6d 70 28 64 74 6d 20 2e | 20 6b 65 79 2c 20 74 20 |mp(dtm .| key, t |
|00003170| 2d 3e 20 74 5f 64 61 74 | 20 5b 69 5d 20 2e 20 6b |-> t_dat| [i] . k|
|00003180| 65 79 29 20 3d 3d 20 30 | 29 0a 58 09 09 09 66 70 |ey) == 0|).X...fp|
|00003190| 72 69 6e 74 66 28 73 74 | 64 65 72 72 2c 20 22 41 |rintf(st|derr, "A|
|000031a0| 6c 72 65 61 64 79 20 68 | 61 64 20 69 74 21 5c 6e |lready h|ad it!\n|
|000031b0| 22 29 3b 0a 58 09 09 65 | 6c 73 65 20 7b 0a 58 09 |");.X..e|lse {.X.|
|000031c0| 09 09 69 6e 73 20 3d 20 | 49 6e 74 65 72 6e 61 6c |..ins = |Internal|
|000031d0| 49 6e 73 65 72 74 28 64 | 74 6d 2c 20 74 20 2d 3e |Insert(d|tm, t ->|
|000031e0| 20 74 5f 70 74 72 20 5b | 69 5d 29 3b 0a 58 0a 58 | t_ptr [|i]);.X.X|
|000031f0| 09 09 09 69 66 20 28 4b | 65 79 43 6d 70 28 69 6e |...if (K|eyCmp(in|
|00003200| 73 20 2e 20 6b 65 79 2c | 20 4e 75 6c 6c 44 61 74 |s . key,| NullDat|
|00003210| 75 6d 20 2e 20 6b 65 79 | 29 20 21 3d 20 30 29 0a |um . key|) != 0).|
|00003220| 58 09 09 09 09 69 66 20 | 28 74 20 2d 3e 20 74 5f |X....if |(t -> t_|
|00003230| 61 63 74 69 76 65 20 3c | 20 32 20 2a 20 4d 29 0a |active <| 2 * M).|
|00003240| 58 09 09 09 09 09 49 6e | 73 49 6e 4e 6f 64 65 28 |X.....In|sInNode(|
|00003250| 74 2c 20 69 6e 73 2c 20 | 4e 65 77 4e 6f 64 65 29 |t, ins, |NewNode)|
|00003260| 3b 0a 58 09 09 09 09 65 | 6c 73 65 20 7b 0a 58 09 |;.X....e|lse {.X.|
|00003270| 09 09 09 09 69 66 20 28 | 69 20 3c 3d 20 4d 29 20 |....if (|i <= M) |
|00003280| 7b 0a 58 09 09 09 09 09 | 09 74 6d 70 20 3d 20 4d |{.X.....|.tmp = M|
|00003290| 6b 4e 6f 64 65 28 74 20 | 2d 3e 20 74 5f 64 61 74 |kNode(t |-> t_dat|
|000032a0| 20 5b 32 20 2a 20 4d 20 | 2d 20 31 5d 2c 20 28 42 | [2 * M |- 1], (B|
|000032b0| 54 52 45 45 29 20 4e 55 | 4c 4c 2c 20 74 20 2d 3e |TREE) NU|LL, t ->|
|000032c0| 20 74 5f 70 74 72 20 5b | 32 20 2a 20 4d 5d 29 3b | t_ptr [|2 * M]);|
|000032d0| 0a 58 09 09 09 09 09 09 | 74 20 2d 3e 20 74 5f 61 |.X......|t -> t_a|
|000032e0| 63 74 69 76 65 2d 2d 3b | 0a 58 09 09 09 09 09 09 |ctive--;|.X......|
|000032f0| 49 6e 73 49 6e 4e 6f 64 | 65 28 74 2c 20 69 6e 73 |InsInNod|e(t, ins|
|00003300| 2c 20 4e 65 77 4e 6f 64 | 65 29 3b 0a 58 09 09 09 |, NewNod|e);.X...|
|00003310| 09 09 7d 20 65 6c 73 65 | 0a 58 09 09 09 09 09 09 |..} else|.X......|
|00003320| 74 6d 70 20 3d 20 4d 6b | 4e 6f 64 65 28 69 6e 73 |tmp = Mk|Node(ins|
|00003330| 2c 20 28 42 54 52 45 45 | 29 20 4e 55 4c 4c 2c 20 |, (BTREE|) NULL, |
|00003340| 4e 65 77 4e 6f 64 65 29 | 3b 0a 58 09 09 09 09 09 |NewNode)|;.X.....|
|00003350| 2f 2a 0a 58 09 09 09 09 | 09 20 2a 09 4d 6f 76 65 |/*.X....|. *.Move|
|00003360| 20 6b 65 79 73 20 61 6e | 64 20 70 6f 69 6e 74 65 | keys an|d pointe|
|00003370| 72 73 20 2e 2e 2e 0a 58 | 09 09 09 09 09 20 2a 2f |rs ....X|..... */|
|00003380| 0a 58 0a 58 09 09 09 09 | 09 66 6f 72 20 28 6a 20 |.X.X....|.for (j |
|00003390| 3d 20 4d 20 2b 20 32 3b | 20 6a 20 3c 3d 20 32 20 |= M + 2;| j <= 2 |
|000033a0| 2a 20 4d 3b 20 2b 2b 6a | 29 0a 58 09 09 09 09 09 |* M; ++j|).X.....|
|000033b0| 09 49 6e 73 49 6e 4e 6f | 64 65 28 74 6d 70 2c 20 |.InsInNo|de(tmp, |
|000033c0| 74 20 2d 3e 20 74 5f 64 | 61 74 20 5b 6a 2d 31 5d |t -> t_d|at [j-1]|
|000033d0| 2c 20 74 20 2d 3e 20 74 | 5f 70 74 72 20 5b 6a 5d |, t -> t|_ptr [j]|
|000033e0| 29 3b 0a 58 0a 58 09 09 | 09 09 09 74 20 2d 3e 20 |);.X.X..|...t -> |
|000033f0| 74 5f 61 63 74 69 76 65 | 20 3d 20 4d 3b 0a 58 09 |t_active| = M;.X.|
|00003400| 09 09 09 09 74 6d 70 20 | 2d 3e 20 74 5f 70 74 72 |....tmp |-> t_ptr|
|00003410| 20 5b 30 5d 20 3d 20 74 | 20 2d 3e 20 74 5f 70 74 | [0] = t| -> t_pt|
|00003420| 72 20 5b 4d 2b 31 5d 3b | 0a 58 09 09 09 09 09 4e |r [M+1];|.X.....N|
|00003430| 65 77 4e 6f 64 65 20 3d | 20 74 6d 70 3b 0a 58 0a |ewNode =| tmp;.X.|
|00003440| 58 09 09 09 09 09 72 65 | 74 75 72 6e 20 74 20 2d |X.....re|turn t -|
|00003450| 3e 20 74 5f 64 61 74 20 | 5b 4d 5d 3b 0a 58 09 09 |> t_dat |[M];.X..|
|00003460| 09 09 7d 0a 58 09 09 7d | 0a 58 09 09 72 65 74 75 |..}.X..}|.X..retu|
|00003470| 72 6e 20 4e 75 6c 6c 44 | 61 74 75 6d 3b 0a 58 09 |rn NullD|atum;.X.|
|00003480| 7d 0a 58 7d 0a 58 0c 2f | 2a 0a 58 2a 2a 20 20 49 |}.X}.X./|*.X** I|
|00003490| 4e 53 45 52 54 20 2d 2d | 20 50 75 74 20 61 20 6b |NSERT --| Put a k|
|000034a0| 65 79 20 69 6e 74 6f 20 | 74 68 65 20 42 2d 74 72 |ey into |the B-tr|
|000034b0| 65 65 0a 58 2a 2a 0a 58 | 2a 2a 09 45 6e 74 65 72 |ee.X**.X|**.Enter|
|000034c0| 20 74 68 65 20 67 69 76 | 65 6e 20 6b 65 79 20 69 | the giv|en key i|
|000034d0| 6e 74 6f 20 74 68 65 0a | 58 2a 2a 09 42 2d 74 72 |nto the.|X**.B-tr|
|000034e0| 65 65 2e 0a 58 2a 2a 0a | 58 2a 2a 09 50 61 72 61 |ee..X**.|X**.Para|
|000034f0| 6d 65 74 65 72 73 3a 0a | 58 2a 2a 09 09 6b 65 79 |meters:.|X**..key|
|00003500| 20 20 2d 2d 20 20 4b 65 | 79 20 76 61 6c 75 65 20 | -- Ke|y value |
|00003510| 74 6f 20 65 6e 74 65 72 | 2e 0a 58 2a 2a 0a 58 2a |to enter|..X**.X*|
|00003520| 2a 09 52 65 74 75 72 6e | 73 3a 0a 58 2a 2a 09 09 |*.Return|s:.X**..|
|00003530| 52 65 66 65 72 65 6e 63 | 65 20 74 6f 20 74 68 65 |Referenc|e to the|
|00003540| 20 6e 65 77 20 42 2d 74 | 72 65 65 2e 0a 58 2a 2a | new B-t|ree..X**|
|00003550| 0a 58 2a 2f 0a 58 0a 58 | 42 54 52 45 45 0a 58 49 |.X*/.X.X|BTREE.XI|
|00003560| 6e 73 65 72 74 28 64 74 | 6d 2c 20 74 29 0a 58 44 |nsert(dt|m, t).XD|
|00003570| 41 54 55 4d 09 64 74 6d | 3b 0a 58 42 54 52 45 45 |ATUM.dtm|;.XBTREE|
|00003580| 09 74 3b 7b 0a 58 09 44 | 41 54 55 4d 09 69 6e 73 |.t;{.X.D|ATUM.ins|
|00003590| 3b 0a 58 0a 58 09 69 6e | 73 20 3d 20 49 6e 74 65 |;.X.X.in|s = Inte|
|000035a0| 72 6e 61 6c 49 6e 73 65 | 72 74 28 64 74 6d 2c 20 |rnalInse|rt(dtm, |
|000035b0| 74 29 3b 0a 58 0a 58 09 | 2f 2a 0a 58 09 20 2a 09 |t);.X.X.|/*.X. *.|
|000035c0| 44 69 64 20 74 68 65 20 | 72 6f 6f 74 20 67 72 6f |Did the |root gro|
|000035d0| 77 20 3f 0a 58 09 20 2a | 2f 0a 58 0a 58 09 72 65 |w ?.X. *|/.X.X.re|
|000035e0| 74 75 72 6e 20 4b 65 79 | 43 6d 70 28 69 6e 73 20 |turn Key|Cmp(ins |
|000035f0| 2e 20 6b 65 79 2c 20 4e | 75 6c 6c 44 61 74 75 6d |. key, N|ullDatum|
|00003600| 20 2e 20 6b 65 79 29 20 | 21 3d 20 30 20 3f 20 4d | . key) |!= 0 ? M|
|00003610| 6b 4e 6f 64 65 28 69 6e | 73 2c 20 74 2c 20 4e 65 |kNode(in|s, t, Ne|
|00003620| 77 4e 6f 64 65 29 20 3a | 20 74 3b 0a 58 7d 0a 58 |wNode) :| t;.X}.X|
|00003630| 0c 2f 2a 0a 58 2a 2a 20 | 20 44 45 4c 45 54 45 20 |./*.X** | DELETE |
|00003640| 2d 2d 20 52 65 6d 6f 76 | 65 20 61 20 6b 65 79 20 |-- Remov|e a key |
|00003650| 66 72 6f 6d 20 61 20 42 | 2d 74 72 65 65 0a 58 2a |from a B|-tree.X*|
|00003660| 2a 0a 58 2a 2a 09 52 65 | 6d 6f 76 65 20 74 68 65 |*.X**.Re|move the|
|00003670| 20 64 61 74 61 20 61 73 | 73 6f 63 69 61 74 65 64 | data as|sociated|
|00003680| 20 77 69 74 68 20 61 0a | 58 2a 2a 09 67 69 76 65 | with a.|X**.give|
|00003690| 6e 20 6b 65 79 20 66 72 | 6f 6d 20 61 20 42 2d 74 |n key fr|om a B-t|
|000036a0| 72 65 65 2e 0a 58 2a 2a | 0a 58 2a 2a 09 50 61 72 |ree..X**|.X**.Par|
|000036b0| 61 6d 65 74 65 72 73 3a | 0a 58 2a 2a 09 09 6b 65 |ameters:|.X**..ke|
|000036c0| 79 20 20 2d 2d 20 20 4b | 65 79 20 74 6f 20 75 73 |y -- K|ey to us|
|000036d0| 65 2c 0a 58 2a 2a 09 09 | 74 20 20 20 20 2d 2d 20 |e,.X**..|t -- |
|000036e0| 20 42 2d 74 72 65 65 20 | 74 6f 20 75 70 64 61 74 | B-tree |to updat|
|000036f0| 65 2e 0a 58 2a 2a 0a 58 | 2a 2a 09 52 65 74 75 72 |e..X**.X|**.Retur|
|00003700| 6e 73 3a 0a 58 2a 2a 09 | 09 52 65 66 65 72 65 6e |ns:.X**.|.Referen|
|00003710| 63 65 20 74 6f 20 74 68 | 65 20 75 70 64 61 74 65 |ce to th|e update|
|00003720| 64 20 42 2d 74 72 65 65 | 2e 0a 58 2a 2a 0a 58 2a |d B-tree|..X**.X*|
|00003730| 2a 09 4e 6f 74 65 73 3a | 0a 58 2a 2a 09 09 52 65 |*.Notes:|.X**..Re|
|00003740| 61 6c 20 77 6f 72 6b 20 | 69 73 20 64 6f 6e 65 20 |al work |is done |
|00003750| 62 79 20 52 65 61 6c 44 | 65 6c 65 74 65 28 29 20 |by RealD|elete() |
|00003760| 71 2e 76 2e 0a 58 2a 2a | 0a 58 2a 2f 0a 58 0a 58 |q.v..X**|.X*/.X.X|
|00003770| 73 74 61 74 69 63 20 69 | 6e 74 09 68 61 64 69 74 |static i|nt.hadit|
|00003780| 20 3d 20 46 41 4c 53 45 | 3b 0a 58 0a 58 42 54 52 | = FALSE|;.X.XBTR|
|00003790| 45 45 0a 58 44 65 6c 65 | 74 65 28 6b 65 79 2c 20 |EE.XDele|te(key, |
|000037a0| 74 29 0a 58 4b 45 59 09 | 6b 65 79 3b 0a 58 42 54 |t).XKEY.|key;.XBT|
|000037b0| 52 45 45 09 74 3b 7b 0a | 58 09 42 54 52 45 45 09 |REE.t;{.|X.BTREE.|
|000037c0| 73 61 76 65 74 3b 0a 58 | 0a 58 09 52 65 61 6c 44 |savet;.X|.X.RealD|
|000037d0| 65 6c 65 74 65 28 6b 65 | 79 2c 20 74 29 3b 0a 58 |elete(ke|y, t);.X|
|000037e0| 0a 58 09 69 66 20 28 21 | 68 61 64 69 74 29 20 7b |.X.if (!|hadit) {|
|000037f0| 0a 58 09 09 45 72 72 6f | 72 28 22 4e 6f 20 73 75 |.X..Erro|r("No su|
|00003800| 63 68 20 6b 65 79 5c 6e | 22 29 3b 0a 58 09 09 72 |ch key\n|");.X..r|
|00003810| 65 74 75 72 6e 20 4e 55 | 4c 4c 3b 0a 58 09 7d 20 |eturn NU|LL;.X.} |
|00003820| 65 6c 73 65 20 69 66 20 | 28 74 20 2d 3e 20 74 5f |else if |(t -> t_|
|00003830| 61 63 74 69 76 65 20 3d | 3d 20 30 29 20 7b 09 2f |active =|= 0) {./|
|00003840| 2a 20 52 6f 6f 74 20 69 | 73 20 6e 6f 77 20 65 6d |* Root i|s now em|
|00003850| 70 74 79 20 2a 2f 0a 58 | 09 09 73 61 76 65 74 20 |pty */.X|..savet |
|00003860| 3d 20 74 20 2d 3e 20 74 | 5f 70 74 72 20 5b 30 5d |= t -> t|_ptr [0]|
|00003870| 3b 0a 58 09 09 44 69 73 | 70 6f 73 65 28 74 29 3b |;.X..Dis|pose(t);|
|00003880| 0a 58 09 09 72 65 74 75 | 72 6e 20 73 61 76 65 74 |.X..retu|rn savet|
|00003890| 3b 0a 58 09 7d 20 65 6c | 73 65 0a 58 09 09 72 65 |;.X.} el|se.X..re|
|000038a0| 74 75 72 6e 20 74 3b 0a | 58 7d 0a 58 0a 58 0c 2f |turn t;.|X}.X.X./|
|000038b0| 2a 0a 58 2a 2a 20 20 53 | 45 41 52 43 48 4e 4f 44 |*.X** S|EARCHNOD|
|000038c0| 45 20 2d 2d 20 46 69 6e | 64 20 61 20 6b 65 79 20 |E -- Fin|d a key |
|000038d0| 69 6e 20 61 20 6e 6f 64 | 65 0a 58 2a 2a 0a 58 2a |in a nod|e.X**.X*|
|000038e0| 2a 09 4c 6f 6f 6b 20 66 | 6f 72 20 61 20 6b 65 79 |*.Look f|or a key|
|000038f0| 20 69 6e 20 61 20 73 69 | 6e 67 6c 65 20 42 2d 74 | in a si|ngle B-t|
|00003900| 72 65 65 0a 58 2a 2a 09 | 6e 6f 64 65 2e 0a 58 2a |ree.X**.|node..X*|
|00003910| 2a 0a 58 2a 2a 09 50 61 | 72 61 6d 65 74 65 72 73 |*.X**.Pa|rameters|
|00003920| 3a 0a 58 2a 2a 09 09 6b | 65 79 20 20 2d 2d 20 20 |:.X**..k|ey -- |
|00003930| 4b 65 79 20 74 6f 20 6c | 6f 6f 6b 20 66 6f 72 2c |Key to l|ook for,|
|00003940| 0a 58 2a 2a 09 09 74 20 | 20 20 20 2d 2d 20 20 50 |.X**..t | -- P|
|00003950| 74 72 20 74 6f 20 42 2d | 74 72 65 65 20 6e 6f 64 |tr to B-|tree nod|
|00003960| 65 2e 0a 58 2a 2a 0a 58 | 2a 2a 09 52 65 74 75 72 |e..X**.X|**.Retur|
|00003970| 6e 73 3a 0a 58 2a 2a 09 | 09 49 6e 64 65 78 20 6f |ns:.X**.|.Index o|
|00003980| 66 20 6d 61 74 63 68 69 | 6e 67 20 6b 65 79 2e 0a |f matchi|ng key..|
|00003990| 58 2a 2a 0a 58 2a 2f 0a | 58 0a 58 69 6e 74 0a 58 |X**.X*/.|X.Xint.X|
|000039a0| 53 65 61 72 63 68 4e 6f | 64 65 28 6b 65 79 2c 20 |SearchNo|de(key, |
|000039b0| 74 29 0a 58 4b 45 59 09 | 6b 65 79 3b 0a 58 42 54 |t).XKEY.|key;.XBT|
|000039c0| 52 45 45 09 74 3b 7b 0a | 58 09 69 6e 74 09 69 3b |REE.t;{.|X.int.i;|
|000039d0| 0a 58 0a 58 09 69 66 20 | 28 4b 65 79 43 6d 70 28 |.X.X.if |(KeyCmp(|
|000039e0| 6b 65 79 2c 20 74 20 2d | 3e 20 74 5f 64 61 74 20 |key, t -|> t_dat |
|000039f0| 5b 30 5d 20 2e 20 6b 65 | 79 29 20 3c 20 30 29 20 |[0] . ke|y) < 0) |
|00003a00| 7b 0a 58 09 09 68 61 64 | 69 74 20 3d 20 46 41 4c |{.X..had|it = FAL|
|00003a10| 53 45 3b 0a 58 09 09 72 | 65 74 75 72 6e 20 30 3b |SE;.X..r|eturn 0;|
|00003a20| 0a 58 09 7d 20 65 6c 73 | 65 20 7b 0a 58 09 09 66 |.X.} els|e {.X..f|
|00003a30| 6f 72 20 28 69 20 3d 20 | 74 20 2d 3e 20 74 5f 61 |or (i = |t -> t_a|
|00003a40| 63 74 69 76 65 3b 20 4b | 65 79 43 6d 70 28 6b 65 |ctive; K|eyCmp(ke|
|00003a50| 79 2c 20 74 20 2d 3e 20 | 74 5f 64 61 74 20 5b 69 |y, t -> |t_dat [i|
|00003a60| 2d 31 5d 20 2e 20 6b 65 | 79 29 20 3c 20 30 20 26 |-1] . ke|y) < 0 &|
|00003a70| 26 20 69 20 3e 20 31 3b | 20 2d 2d 69 29 0a 58 09 |& i > 1;| --i).X.|
|00003a80| 09 09 3b 09 09 2f 2a 20 | 4e 55 4c 4c 20 42 4f 44 |..;../* |NULL BOD|
|00003a90| 59 20 2a 2f 0a 58 09 09 | 68 61 64 69 74 20 3d 20 |Y */.X..|hadit = |
|00003aa0| 28 4b 65 79 43 6d 70 28 | 6b 65 79 2c 20 74 20 2d |(KeyCmp(|key, t -|
|00003ab0| 3e 20 74 5f 64 61 74 20 | 5b 69 2d 31 5d 20 2e 20 |> t_dat |[i-1] . |
|00003ac0| 6b 65 79 29 20 3d 3d 20 | 30 29 3b 0a 58 0a 58 09 |key) == |0);.X.X.|
|00003ad0| 09 72 65 74 75 72 6e 20 | 69 3b 0a 58 09 7d 0a 58 |.return |i;.X.}.X|
|00003ae0| 7d 0a 58 0c 2f 2a 0a 58 | 2a 2a 20 20 52 45 41 4c |}.X./*.X|** REAL|
|00003af0| 44 45 4c 45 54 45 20 2d | 2d 20 52 65 6d 6f 76 65 |DELETE -|- Remove|
|00003b00| 20 61 20 6b 65 79 20 66 | 72 6f 6d 20 61 20 74 72 | a key f|rom a tr|
|00003b10| 65 65 0a 58 2a 2a 0a 58 | 2a 2a 09 54 68 65 20 62 |ee.X**.X|**.The b|
|00003b20| 75 73 69 6e 65 73 73 20 | 65 6e 64 20 6f 66 20 74 |usiness |end of t|
|00003b30| 68 65 20 44 65 6c 65 74 | 65 28 29 20 66 75 6e 63 |he Delet|e() func|
|00003b40| 74 69 6f 6e 2e 0a 58 2a | 2a 0a 58 2a 2a 09 50 61 |tion..X*|*.X**.Pa|
|00003b50| 72 61 6d 65 74 65 72 73 | 3a 0a 58 2a 2a 09 09 6b |rameters|:.X**..k|
|00003b60| 65 79 20 20 2d 2d 20 20 | 4b 65 79 20 74 6f 20 75 |ey -- |Key to u|
|00003b70| 73 65 2c 0a 58 2a 2a 09 | 09 74 20 20 20 20 2d 2d |se,.X**.|.t --|
|00003b80| 20 20 54 72 65 65 20 74 | 6f 20 75 70 64 61 74 65 | Tree t|o update|
|00003b90| 2e 0a 58 2a 2a 0a 58 2a | 2a 09 52 65 74 75 72 6e |..X**.X*|*.Return|
|00003ba0| 73 3a 0a 58 2a 2a 09 09 | 4e 6f 6e 65 2e 0a 58 2a |s:.X**..|None..X*|
|00003bb0| 2a 0a 58 2a 2f 0a 58 0a | 58 52 65 61 6c 44 65 6c |*.X*/.X.|XRealDel|
|00003bc0| 65 74 65 28 6b 65 79 2c | 20 74 29 0a 58 4b 45 59 |ete(key,| t).XKEY|
|00003bd0| 09 6b 65 79 3b 0a 58 42 | 54 52 45 45 09 74 3b 7b |.key;.XB|TREE.t;{|
|00003be0| 0a 58 09 69 6e 74 09 6b | 3b 0a 58 0a 58 09 69 66 |.X.int.k|;.X.X.if|
|00003bf0| 20 28 74 20 3d 3d 20 4e | 55 4c 4c 29 0a 58 09 09 | (t == N|ULL).X..|
|00003c00| 68 61 64 69 74 20 3d 20 | 46 41 4c 53 45 3b 0a 58 |hadit = |FALSE;.X|
|00003c10| 09 65 6c 73 65 20 7b 0a | 58 09 09 6b 20 3d 20 53 |.else {.|X..k = S|
|00003c20| 65 61 72 63 68 4e 6f 64 | 65 28 6b 65 79 2c 20 74 |earchNod|e(key, t|
|00003c30| 29 3b 0a 58 0a 58 09 09 | 69 66 20 28 68 61 64 69 |);.X.X..|if (hadi|
|00003c40| 74 29 20 7b 0a 58 09 09 | 09 69 66 20 28 74 20 2d |t) {.X..|.if (t -|
|00003c50| 3e 20 74 5f 70 74 72 20 | 5b 6b 2d 31 5d 20 3d 3d |> t_ptr |[k-1] ==|
|00003c60| 20 4e 55 4c 4c 29 09 09 | 2f 2a 20 41 20 6c 65 61 | NULL)..|/* A lea|
|00003c70| 66 20 2a 2f 0a 58 09 09 | 09 09 52 65 6d 6f 76 65 |f */.X..|..Remove|
|00003c80| 28 74 2c 20 6b 29 3b 0a | 58 09 09 09 65 6c 73 65 |(t, k);.|X...else|
|00003c90| 20 7b 0a 58 09 09 09 09 | 53 75 63 63 28 74 2c 20 | {.X....|Succ(t, |
|00003ca0| 6b 29 3b 0a 58 09 09 09 | 09 52 65 61 6c 44 65 6c |k);.X...|.RealDel|
|00003cb0| 65 74 65 28 74 20 2d 3e | 20 74 5f 64 61 74 20 5b |ete(t ->| t_dat [|
|00003cc0| 6b 2d 31 5d 20 2e 20 6b | 65 79 2c 20 74 20 2d 3e |k-1] . k|ey, t ->|
|00003cd0| 20 74 5f 70 74 72 20 5b | 6b 5d 29 3b 0a 58 09 09 | t_ptr [|k]);.X..|
|00003ce0| 09 09 69 66 20 28 21 68 | 61 64 69 74 29 0a 58 09 |..if (!h|adit).X.|
|00003cf0| 09 09 09 09 45 72 72 6f | 72 28 22 48 6d 6d 20 3f |....Erro|r("Hmm ?|
|00003d00| 3f 3f 22 29 3b 0a 58 09 | 09 09 7d 0a 58 09 09 7d |??");.X.|..}.X..}|
|00003d10| 20 65 6c 73 65 20 7b 0a | 58 09 09 09 52 65 61 6c | else {.|X...Real|
|00003d20| 44 65 6c 65 74 65 28 6b | 65 79 2c 20 74 20 2d 3e |Delete(k|ey, t ->|
|00003d30| 20 74 5f 70 74 72 20 5b | 6b 5d 29 3b 0a 58 0a 58 | t_ptr [|k]);.X.X|
|00003d40| 09 09 09 69 66 20 28 74 | 20 2d 3e 20 74 5f 70 74 |...if (t| -> t_pt|
|00003d50| 72 20 5b 6b 5d 20 21 3d | 20 4e 55 4c 4c 20 26 26 |r [k] !=| NULL &&|
|00003d60| 20 74 20 2d 3e 20 74 5f | 70 74 72 20 5b 6b 5d 20 | t -> t_|ptr [k] |
|00003d70| 2d 3e 20 74 5f 61 63 74 | 69 76 65 20 3c 20 4d 29 |-> t_act|ive < M)|
|00003d80| 0a 58 09 09 09 09 52 65 | 73 74 6f 72 65 28 74 2c |.X....Re|store(t,|
|00003d90| 20 6b 29 3b 0a 58 09 09 | 7d 0a 58 09 7d 0a 58 7d | k);.X..|}.X.}.X}|
|00003da0| 0a 58 0a 58 0c 2f 2a 0a | 58 2a 2a 20 20 52 45 4d |.X.X./*.|X** REM|
|00003db0| 4f 56 45 20 2d 2d 20 52 | 65 6d 6f 76 65 20 61 20 |OVE -- R|emove a |
|00003dc0| 73 69 6e 67 6c 65 20 64 | 61 74 75 6d 0a 58 2a 2a |single d|atum.X**|
|00003dd0| 0a 58 2a 2a 09 52 65 6d | 6f 76 65 20 61 20 64 61 |.X**.Rem|ove a da|
|00003de0| 74 75 6d 20 66 72 6f 6d | 20 61 20 42 2d 74 72 65 |tum from| a B-tre|
|00003df0| 65 20 6e 6f 64 65 0a 58 | 2a 2a 09 62 79 20 73 68 |e node.X|**.by sh|
|00003e00| 75 66 66 6c 69 6e 67 20 | 64 6f 77 6e 20 74 68 65 |uffling |down the|
|00003e10| 20 70 6f 69 6e 74 65 72 | 73 20 61 6e 64 0a 58 2a | pointer|s and.X*|
|00003e20| 2a 09 64 61 74 61 20 61 | 62 6f 76 65 20 69 74 2e |*.data a|bove it.|
|00003e30| 0a 58 2a 2a 0a 58 2a 2a | 09 50 61 72 61 6d 65 74 |.X**.X**|.Paramet|
|00003e40| 65 72 73 3a 0a 58 2a 2a | 09 09 74 20 20 20 2d 2d |ers:.X**|..t --|
|00003e50| 20 20 50 74 72 20 74 6f | 20 74 68 65 20 42 2d 74 | Ptr to| the B-t|
|00003e60| 72 65 65 20 6e 6f 64 65 | 2c 0a 58 2a 2a 09 09 70 |ree node|,.X**..p|
|00003e70| 6f 73 20 2d 2d 20 20 49 | 6e 64 65 78 20 6f 66 20 |os -- I|ndex of |
|00003e80| 74 68 65 20 6b 65 79 20 | 74 6f 20 62 65 20 72 65 |the key |to be re|
|00003e90| 6d 6f 76 65 64 2e 0a 58 | 2a 2a 0a 58 2a 2a 09 52 |moved..X|**.X**.R|
|00003ea0| 65 74 75 72 6e 73 3a 0a | 58 2a 2a 09 09 4e 6f 6e |eturns:.|X**..Non|
|00003eb0| 65 2e 0a 58 2a 2a 0a 58 | 2a 2f 0a 58 0a 58 52 65 |e..X**.X|*/.X.XRe|
|00003ec0| 6d 6f 76 65 28 74 2c 20 | 70 6f 73 29 0a 58 42 54 |move(t, |pos).XBT|
|00003ed0| 52 45 45 09 74 3b 0a 58 | 69 6e 74 09 70 6f 73 3b |REE.t;.X|int.pos;|
|00003ee0| 7b 0a 58 09 69 6e 74 09 | 69 3b 0a 58 0a 58 09 66 |{.X.int.|i;.X.X.f|
|00003ef0| 6f 72 20 28 69 20 3d 20 | 70 6f 73 20 2b 20 31 3b |or (i = |pos + 1;|
|00003f00| 20 69 20 3c 3d 20 74 20 | 2d 3e 20 74 5f 61 63 74 | i <= t |-> t_act|
|00003f10| 69 76 65 3b 20 2b 2b 69 | 29 20 7b 0a 58 09 09 74 |ive; ++i|) {.X..t|
|00003f20| 20 2d 3e 20 74 5f 64 61 | 74 20 5b 69 2d 32 5d 20 | -> t_da|t [i-2] |
|00003f30| 3d 20 74 20 2d 3e 20 74 | 5f 64 61 74 20 5b 69 2d |= t -> t|_dat [i-|
|00003f40| 31 5d 3b 0a 58 09 09 74 | 20 2d 3e 20 74 5f 70 74 |1];.X..t| -> t_pt|
|00003f50| 72 20 5b 69 2d 31 5d 20 | 3d 20 74 20 2d 3e 20 74 |r [i-1] |= t -> t|
|00003f60| 5f 70 74 72 20 5b 69 5d | 3b 0a 58 09 7d 0a 58 09 |_ptr [i]|;.X.}.X.|
|00003f70| 74 20 2d 3e 20 74 5f 61 | 63 74 69 76 65 2d 2d 3b |t -> t_a|ctive--;|
|00003f80| 0a 58 7d 0a 58 0a 58 0c | 2f 2a 0a 58 2a 2a 20 20 |.X}.X.X.|/*.X** |
|00003f90| 53 55 43 43 20 2d 2d 20 | 52 65 70 6c 61 63 65 20 |SUCC -- |Replace |
|00003fa0| 61 20 6b 65 79 20 62 79 | 20 69 74 73 20 73 75 63 |a key by| its suc|
|00003fb0| 63 65 73 73 6f 72 0a 58 | 2a 2a 0a 58 2a 2a 09 55 |cessor.X|**.X**.U|
|00003fc0| 73 69 6e 67 20 74 68 65 | 20 6e 61 74 75 72 61 6c |sing the| natural|
|00003fd0| 20 6f 72 64 65 72 69 6e | 67 2c 20 72 65 70 6c 61 | orderin|g, repla|
|00003fe0| 63 65 0a 58 2a 2a 09 61 | 20 6b 65 79 20 77 69 74 |ce.X**.a| key wit|
|00003ff0| 68 20 69 74 73 20 73 75 | 63 63 65 73 73 6f 72 2e |h its su|ccessor.|
|00004000| 0a 58 2a 2a 0a 58 2a 2a | 09 50 61 72 61 6d 65 74 |.X**.X**|.Paramet|
|00004010| 65 72 73 3a 0a 58 2a 2a | 09 09 74 20 20 20 2d 2d |ers:.X**|..t --|
|00004020| 20 20 50 74 72 20 74 6f | 20 61 20 42 2d 74 72 65 | Ptr to| a B-tre|
|00004030| 65 20 6e 6f 64 65 2c 0a | 58 2a 2a 09 09 70 6f 73 |e node,.|X**..pos|
|00004040| 20 2d 2d 20 20 49 6e 64 | 65 78 20 6f 66 20 74 68 | -- Ind|ex of th|
|00004050| 65 20 6b 65 79 20 74 6f | 20 62 65 20 73 75 63 63 |e key to| be succ|
|00004060| 27 65 64 2e 0a 58 2a 2a | 0a 58 2a 2a 09 52 65 74 |'ed..X**|.X**.Ret|
|00004070| 75 72 6e 73 3a 0a 58 2a | 2a 09 09 4e 6f 6e 65 2e |urns:.X*|*..None.|
|00004080| 0a 58 2a 2a 0a 58 2a 2a | 09 4e 6f 74 65 73 3a 0a |.X**.X**|.Notes:.|
|00004090| 58 2a 2a 09 09 54 68 69 | 73 20 72 6f 75 74 69 6e |X**..Thi|s routin|
|000040a0| 65 20 72 65 6c 69 65 73 | 20 6f 6e 20 74 68 65 20 |e relies| on the |
|000040b0| 66 61 63 74 0a 58 2a 2a | 09 09 74 68 61 74 20 69 |fact.X**|..that i|
|000040c0| 66 20 74 68 65 20 6b 65 | 79 20 74 6f 20 62 65 20 |f the ke|y to be |
|000040d0| 64 65 6c 65 74 65 64 20 | 69 73 0a 58 2a 2a 09 09 |deleted |is.X**..|
|000040e0| 6e 6f 74 20 69 6e 20 61 | 20 6c 65 61 66 20 6e 6f |not in a| leaf no|
|000040f0| 64 65 2c 20 74 68 65 6e | 20 69 74 73 0a 58 2a 2a |de, then| its.X**|
|00004100| 09 09 69 6d 6d 65 64 69 | 61 74 65 20 73 75 63 63 |..immedi|ate succ|
|00004110| 65 73 73 6f 72 20 77 69 | 6c 6c 20 62 65 2e 0a 58 |essor wi|ll be..X|
|00004120| 2a 2f 0a 58 0a 58 53 75 | 63 63 28 74 2c 20 70 6f |*/.X.XSu|cc(t, po|
|00004130| 73 29 0a 58 42 54 52 45 | 45 09 74 3b 0a 58 69 6e |s).XBTRE|E.t;.Xin|
|00004140| 74 09 70 6f 73 3b 7b 0a | 58 09 42 54 52 45 45 09 |t.pos;{.|X.BTREE.|
|00004150| 74 73 75 63 63 3b 0a 58 | 0a 58 09 2f 2a 0a 58 09 |tsucc;.X|.X./*.X.|
|00004160| 20 2a 09 55 73 69 6e 67 | 20 74 68 65 20 62 72 61 | *.Using| the bra|
|00004170| 6e 63 68 20 2a 61 62 6f | 76 65 2a 20 74 68 65 20 |nch *abo|ve* the |
|00004180| 6b 65 79 0a 58 09 20 2a | 09 63 68 61 69 6e 20 64 |key.X. *|.chain d|
|00004190| 6f 77 6e 20 74 6f 20 6c | 65 66 74 6d 6f 73 74 20 |own to l|eftmost |
|000041a0| 6e 6f 64 65 20 62 65 6c | 6f 77 0a 58 09 20 2a 09 |node bel|ow.X. *.|
|000041b0| 69 74 2e 0a 58 09 20 2a | 2f 0a 58 0a 58 09 66 6f |it..X. *|/.X.X.fo|
|000041c0| 72 20 28 74 73 75 63 63 | 20 3d 20 74 20 2d 3e 20 |r (tsucc| = t -> |
|000041d0| 74 5f 70 74 72 20 5b 70 | 6f 73 5d 3b 20 74 73 75 |t_ptr [p|os]; tsu|
|000041e0| 63 63 20 2d 3e 20 74 5f | 70 74 72 20 5b 30 5d 20 |cc -> t_|ptr [0] |
|000041f0| 21 3d 20 4e 55 4c 4c 3b | 20 74 73 75 63 63 20 3d |!= NULL;| tsucc =|
|00004200| 20 74 73 75 63 63 20 2d | 3e 20 74 5f 70 74 72 20 | tsucc -|> t_ptr |
|00004210| 5b 30 5d 29 0a 58 09 09 | 3b 09 09 2f 2a 20 4e 55 |[0]).X..|;../* NU|
|00004220| 4c 4c 20 42 4f 44 59 20 | 2a 2f 0a 58 0a 58 09 74 |LL BODY |*/.X.X.t|
|00004230| 20 2d 3e 20 74 5f 64 61 | 74 20 5b 70 6f 73 2d 31 | -> t_da|t [pos-1|
|00004240| 5d 20 3d 20 74 73 75 63 | 63 20 2d 3e 20 74 5f 64 |] = tsuc|c -> t_d|
|00004250| 61 74 20 5b 30 5d 3b 0a | 58 7d 0a 58 0c 2f 2a 0a |at [0];.|X}.X./*.|
|00004260| 58 2a 2a 20 20 52 45 53 | 54 4f 52 45 20 2d 2d 20 |X** RES|TORE -- |
|00004270| 52 65 73 74 6f 72 65 20 | 62 61 6c 61 6e 63 65 20 |Restore |balance |
|00004280| 74 6f 20 61 20 42 2d 74 | 72 65 65 0a 58 2a 2a 0a |to a B-t|ree.X**.|
|00004290| 58 2a 2a 09 41 66 74 65 | 72 20 72 65 6d 6f 76 69 |X**.Afte|r removi|
|000042a0| 6e 67 20 61 6e 20 69 74 | 65 6d 20 66 72 6f 6d 20 |ng an it|em from |
|000042b0| 61 20 42 2d 74 72 65 65 | 0a 58 2a 2a 09 77 65 20 |a B-tree|.X**.we |
|000042c0| 6d 75 73 74 20 72 65 73 | 74 6f 72 65 20 74 68 65 |must res|tore the|
|000042d0| 20 62 61 6c 61 6e 63 65 | 2e 0a 58 2a 2a 0a 58 2a | balance|..X**.X*|
|000042e0| 2a 09 50 61 72 61 6d 65 | 74 65 72 73 3a 0a 58 2a |*.Parame|ters:.X*|
|000042f0| 2a 09 09 74 20 20 20 2d | 2d 20 20 50 74 72 20 74 |*..t -|- Ptr t|
|00004300| 6f 20 74 68 65 20 42 2d | 74 72 65 65 20 6e 6f 64 |o the B-|tree nod|
|00004310| 65 2c 0a 58 2a 2a 09 09 | 70 6f 73 20 2d 2d 20 20 |e,.X**..|pos -- |
|00004320| 49 6e 64 65 78 20 6f 66 | 20 74 68 65 20 6f 75 74 |Index of| the out|
|00004330| 2d 6f 66 2d 62 61 6c 61 | 6e 63 65 20 70 6f 69 6e |-of-bala|nce poin|
|00004340| 74 2e 0a 58 2a 2a 0a 58 | 2a 2a 09 52 65 74 75 72 |t..X**.X|**.Retur|
|00004350| 6e 73 3a 0a 58 2a 2a 09 | 09 4e 6f 6e 65 2e 0a 58 |ns:.X**.|.None..X|
|00004360| 2a 2a 0a 58 2a 2f 0a 58 | 0a 58 52 65 73 74 6f 72 |**.X*/.X|.XRestor|
|00004370| 65 28 74 2c 20 70 6f 73 | 29 0a 58 42 54 52 45 45 |e(t, pos|).XBTREE|
|00004380| 09 74 3b 0a 58 69 6e 74 | 09 70 6f 73 3b 7b 0a 58 |.t;.Xint|.pos;{.X|
|00004390| 09 69 66 20 28 70 6f 73 | 20 3e 20 30 29 20 7b 0a |.if (pos| > 0) {.|
|000043a0| 58 09 09 69 66 20 28 74 | 20 2d 3e 20 74 5f 70 74 |X..if (t| -> t_pt|
|000043b0| 72 20 5b 70 6f 73 20 2d | 20 31 5d 20 2d 3e 20 74 |r [pos -| 1] -> t|
|000043c0| 5f 61 63 74 69 76 65 20 | 3e 20 4d 29 0a 58 09 09 |_active |> M).X..|
|000043d0| 09 4d 6f 76 65 52 69 67 | 68 74 28 74 2c 20 70 6f |.MoveRig|ht(t, po|
|000043e0| 73 29 3b 0a 58 09 09 65 | 6c 73 65 0a 58 09 09 09 |s);.X..e|lse.X...|
|000043f0| 43 6f 6d 62 69 6e 65 28 | 74 2c 20 70 6f 73 29 3b |Combine(|t, pos);|
|00004400| 0a 58 09 7d 20 65 6c 73 | 65 20 7b 0a 58 09 09 69 |.X.} els|e {.X..i|
|00004410| 66 20 28 74 20 2d 3e 20 | 74 5f 70 74 72 20 5b 31 |f (t -> |t_ptr [1|
|00004420| 5d 20 2d 3e 20 74 5f 61 | 63 74 69 76 65 20 3e 20 |] -> t_a|ctive > |
|00004430| 4d 29 0a 58 09 09 09 4d | 6f 76 65 4c 65 66 74 28 |M).X...M|oveLeft(|
|00004440| 74 2c 20 31 29 3b 0a 58 | 09 09 65 6c 73 65 0a 58 |t, 1);.X|..else.X|
|00004450| 09 09 09 43 6f 6d 62 69 | 6e 65 28 74 2c 20 31 29 |...Combi|ne(t, 1)|
|00004460| 3b 0a 58 09 7d 0a 58 7d | 0a 58 0a 58 0c 2f 2a 0a |;.X.}.X}|.X.X./*.|
|00004470| 58 2a 2a 20 20 4d 4f 56 | 45 52 49 47 48 54 20 2d |X** MOV|ERIGHT -|
|00004480| 2d 20 53 68 75 66 66 6c | 65 20 6b 65 79 73 20 75 |- Shuffl|e keys u|
|00004490| 70 0a 58 2a 2a 0a 58 2a | 2a 09 4d 61 6b 65 20 72 |p.X**.X*|*.Make r|
|000044a0| 6f 6f 6d 20 66 6f 72 20 | 61 20 6b 65 79 20 69 6e |oom for |a key in|
|000044b0| 20 61 20 42 2d 74 72 65 | 65 0a 58 2a 2a 09 6e 6f | a B-tre|e.X**.no|
|000044c0| 64 65 2e 0a 58 2a 2a 0a | 58 2a 2a 09 50 61 72 61 |de..X**.|X**.Para|
|000044d0| 6d 65 74 65 72 73 3a 0a | 58 2a 2a 09 09 74 20 20 |meters:.|X**..t |
|000044e0| 20 2d 2d 20 20 50 74 72 | 20 74 6f 20 74 68 65 20 | -- Ptr| to the |
|000044f0| 42 2d 74 72 65 65 20 6e | 6f 64 65 2c 0a 58 2a 2a |B-tree n|ode,.X**|
|00004500| 09 09 70 6f 73 20 2d 2d | 20 20 49 6e 64 65 78 20 |..pos --| Index |
|00004510| 6f 66 20 74 68 65 20 66 | 69 72 73 74 20 6b 65 79 |of the f|irst key|
|00004520| 0a 58 2a 2a 09 09 09 74 | 6f 20 62 65 20 6d 6f 76 |.X**...t|o be mov|
|00004530| 65 64 2e 0a 58 2a 2a 0a | 58 2a 2a 09 52 65 74 75 |ed..X**.|X**.Retu|
|00004540| 72 6e 73 3a 0a 58 2a 2a | 09 09 4e 6f 6e 65 2e 0a |rns:.X**|..None..|
|00004550| 58 2a 2a 0a 58 2a 2f 0a | 58 0a 58 4d 6f 76 65 52 |X**.X*/.|X.XMoveR|
|00004560| 69 67 68 74 28 74 2c 20 | 70 6f 73 29 0a 58 42 54 |ight(t, |pos).XBT|
|00004570| 52 45 45 09 74 3b 0a 58 | 69 6e 74 09 70 6f 73 3b |REE.t;.X|int.pos;|
|00004580| 7b 0a 58 09 69 6e 74 09 | 69 3b 0a 58 09 42 54 52 |{.X.int.|i;.X.BTR|
|00004590| 45 45 09 74 70 6f 73 3b | 0a 58 0a 58 09 74 70 6f |EE.tpos;|.X.X.tpo|
|000045a0| 73 20 3d 20 74 20 2d 3e | 20 74 5f 70 74 72 20 5b |s = t ->| t_ptr [|
|000045b0| 70 6f 73 5d 3b 0a 58 0a | 58 09 66 6f 72 20 28 69 |pos];.X.|X.for (i|
|000045c0| 20 3d 20 74 70 6f 73 20 | 2d 3e 20 74 5f 61 63 74 | = tpos |-> t_act|
|000045d0| 69 76 65 3b 20 69 20 3e | 3d 20 31 3b 20 69 2d 2d |ive; i >|= 1; i--|
|000045e0| 29 20 7b 0a 58 09 09 74 | 70 6f 73 20 2d 3e 20 74 |) {.X..t|pos -> t|
|000045f0| 5f 64 61 74 20 5b 69 5d | 20 20 20 3d 20 74 70 6f |_dat [i]| = tpo|
|00004600| 73 20 2d 3e 20 74 5f 64 | 61 74 20 5b 69 2d 31 5d |s -> t_d|at [i-1]|
|00004610| 3b 0a 58 09 09 74 70 6f | 73 20 2d 3e 20 74 5f 70 |;.X..tpo|s -> t_p|
|00004620| 74 72 20 5b 69 2b 31 5d | 20 3d 20 74 70 6f 73 20 |tr [i+1]| = tpos |
|00004630| 2d 3e 20 74 5f 70 74 72 | 20 5b 69 5d 3b 0a 58 09 |-> t_ptr| [i];.X.|
|00004640| 7d 0a 58 0a 58 09 74 70 | 6f 73 20 2d 3e 20 74 5f |}.X.X.tp|os -> t_|
|00004650| 70 74 72 20 5b 31 5d 20 | 3d 20 74 70 6f 73 20 2d |ptr [1] |= tpos -|
|00004660| 3e 20 74 5f 70 74 72 20 | 5b 30 5d 3b 0a 58 09 74 |> t_ptr |[0];.X.t|
|00004670| 70 6f 73 20 2d 3e 20 74 | 5f 61 63 74 69 76 65 2b |pos -> t|_active+|
|00004680| 2b 3b 0a 58 09 74 70 6f | 73 20 2d 3e 20 74 5f 64 |+;.X.tpo|s -> t_d|
|00004690| 61 74 20 5b 30 5d 20 3d | 20 74 20 2d 3e 20 74 5f |at [0] =| t -> t_|
|000046a0| 64 61 74 20 5b 70 6f 73 | 2d 31 5d 3b 0a 58 0a 58 |dat [pos|-1];.X.X|
|000046b0| 09 74 70 6f 73 20 3d 20 | 74 20 2d 3e 20 74 5f 70 |.tpos = |t -> t_p|
|000046c0| 74 72 20 5b 70 6f 73 2d | 31 5d 3b 0a 58 0a 58 09 |tr [pos-|1];.X.X.|
|000046d0| 74 20 2d 3e 20 74 5f 64 | 61 74 20 5b 70 6f 73 2d |t -> t_d|at [pos-|
|000046e0| 31 5d 20 20 20 20 20 20 | 20 20 20 20 20 20 3d 20 |1] | = |
|000046f0| 74 70 6f 73 20 2d 3e 20 | 74 5f 64 61 74 20 5b 74 |tpos -> |t_dat [t|
|00004700| 70 6f 73 20 2d 3e 20 74 | 5f 61 63 74 69 76 65 2d |pos -> t|_active-|
|00004710| 31 5d 3b 0a 58 09 74 20 | 2d 3e 20 74 5f 70 74 72 |1];.X.t |-> t_ptr|
|00004720| 20 5b 70 6f 73 5d 20 2d | 3e 20 74 5f 70 74 72 20 | [pos] -|> t_ptr |
|00004730| 5b 30 5d 20 3d 20 74 70 | 6f 73 20 2d 3e 20 74 5f |[0] = tp|os -> t_|
|00004740| 70 74 72 20 5b 74 70 6f | 73 20 2d 3e 20 74 5f 61 |ptr [tpo|s -> t_a|
|00004750| 63 74 69 76 65 5d 3b 0a | 58 09 74 70 6f 73 20 2d |ctive];.|X.tpos -|
|00004760| 3e 20 74 5f 61 63 74 69 | 76 65 2d 2d 3b 0a 58 7d |> t_acti|ve--;.X}|
|00004770| 0a 58 0c 2f 2a 0a 58 2a | 2a 20 20 4d 4f 56 45 4c |.X./*.X*|* MOVEL|
|00004780| 45 46 54 20 2d 2d 20 53 | 68 75 66 66 6c 65 20 6b |EFT -- S|huffle k|
|00004790| 65 79 73 20 64 6f 77 6e | 0a 58 2a 2a 0a 58 2a 2a |eys down|.X**.X**|
|000047a0| 09 53 68 75 66 66 6c 65 | 20 6b 65 79 73 20 64 6f |.Shuffle| keys do|
|000047b0| 77 6e 20 61 66 74 65 72 | 20 61 20 72 65 6d 6f 76 |wn after| a remov|
|000047c0| 61 6c 0a 58 2a 2a 09 66 | 72 6f 6d 20 61 20 42 2d |al.X**.f|rom a B-|
|000047d0| 74 72 65 65 20 6e 6f 64 | 65 2e 0a 58 2a 2a 0a 58 |tree nod|e..X**.X|
|000047e0| 2a 2a 09 50 61 72 61 6d | 65 74 65 72 73 3a 0a 58 |**.Param|eters:.X|
|000047f0| 2a 2a 09 09 74 20 20 20 | 2d 2d 20 20 50 74 72 20 |**..t |-- Ptr |
|00004800| 74 6f 20 74 68 65 20 42 | 2d 74 72 65 65 20 6e 6f |to the B|-tree no|
|00004810| 64 65 2c 0a 58 2a 2a 09 | 09 70 6f 73 20 2d 2d 20 |de,.X**.|.pos -- |
|00004820| 20 49 6e 64 65 78 20 6f | 66 20 74 68 65 20 66 69 | Index o|f the fi|
|00004830| 72 73 74 20 6b 65 79 0a | 58 2a 2a 09 09 09 74 6f |rst key.|X**...to|
|00004840| 20 62 65 20 6d 6f 76 65 | 64 2e 0a 58 2a 2a 0a 58 | be move|d..X**.X|
|00004850| 2a 2a 09 52 65 74 75 72 | 6e 73 3a 0a 58 2a 2a 09 |**.Retur|ns:.X**.|
|00004860| 09 4e 6f 6e 65 2e 0a 58 | 2a 2a 0a 58 2a 2f 0a 58 |.None..X|**.X*/.X|
|00004870| 0a 58 4d 6f 76 65 4c 65 | 66 74 28 74 2c 20 70 6f |.XMoveLe|ft(t, po|
|00004880| 73 29 0a 58 42 54 52 45 | 45 09 74 3b 0a 58 69 6e |s).XBTRE|E.t;.Xin|
|00004890| 74 09 70 6f 73 3b 7b 0a | 58 09 69 6e 74 09 69 3b |t.pos;{.|X.int.i;|
|000048a0| 0a 58 09 42 54 52 45 45 | 09 74 70 6f 73 3b 0a 58 |.X.BTREE|.tpos;.X|
|000048b0| 0a 58 09 74 70 6f 73 20 | 3d 20 74 20 2d 3e 20 74 |.X.tpos |= t -> t|
|000048c0| 5f 70 74 72 20 5b 70 6f | 73 2d 31 5d 3b 0a 58 0a |_ptr [po|s-1];.X.|
|000048d0| 58 09 74 70 6f 73 20 2d | 3e 20 74 5f 61 63 74 69 |X.tpos -|> t_acti|
|000048e0| 76 65 2b 2b 3b 0a 58 09 | 74 70 6f 73 20 2d 3e 20 |ve++;.X.|tpos -> |
|000048f0| 74 5f 64 61 74 20 5b 74 | 70 6f 73 20 2d 3e 20 74 |t_dat [t|pos -> t|
|00004900| 5f 61 63 74 69 76 65 2d | 31 5d 20 3d 20 74 20 2d |_active-|1] = t -|
|00004910| 3e 20 74 5f 64 61 74 20 | 5b 70 6f 73 2d 31 5d 3b |> t_dat |[pos-1];|
|00004920| 0a 58 09 74 70 6f 73 20 | 2d 3e 20 74 5f 70 74 72 |.X.tpos |-> t_ptr|
|00004930| 20 5b 74 70 6f 73 20 2d | 3e 20 74 5f 61 63 74 69 | [tpos -|> t_acti|
|00004940| 76 65 5d 20 20 20 3d 20 | 74 20 2d 3e 20 74 5f 70 |ve] = |t -> t_p|
|00004950| 74 72 20 5b 70 6f 73 5d | 20 2d 3e 20 74 5f 70 74 |tr [pos]| -> t_pt|
|00004960| 72 20 5b 30 5d 3b 0a 58 | 0a 58 09 74 70 6f 73 20 |r [0];.X|.X.tpos |
|00004970| 3d 20 74 20 2d 3e 20 74 | 5f 70 74 72 20 5b 70 6f |= t -> t|_ptr [po|
|00004980| 73 5d 3b 0a 58 0a 58 09 | 74 20 2d 3e 20 74 5f 64 |s];.X.X.|t -> t_d|
|00004990| 61 74 20 5b 70 6f 73 2d | 31 5d 20 20 3d 20 74 70 |at [pos-|1] = tp|
|000049a0| 6f 73 20 2d 3e 20 74 5f | 64 61 74 20 5b 30 5d 3b |os -> t_|dat [0];|
|000049b0| 0a 58 09 74 70 6f 73 20 | 2d 3e 20 74 5f 70 74 72 |.X.tpos |-> t_ptr|
|000049c0| 20 5b 30 5d 20 20 20 3d | 20 74 70 6f 73 20 2d 3e | [0] =| tpos ->|
|000049d0| 20 74 5f 70 74 72 20 5b | 31 5d 3b 0a 58 09 74 70 | t_ptr [|1];.X.tp|
|000049e0| 6f 73 20 2d 3e 20 74 5f | 61 63 74 69 76 65 2d 2d |os -> t_|active--|
|000049f0| 3b 0a 58 0a 58 09 66 6f | 72 20 28 69 20 3d 20 31 |;.X.X.fo|r (i = 1|
|00004a00| 3b 20 69 20 3c 3d 20 74 | 70 6f 73 20 2d 3e 20 74 |; i <= t|pos -> t|
|00004a10| 5f 61 63 74 69 76 65 3b | 20 2b 2b 69 29 20 7b 0a |_active;| ++i) {.|
|00004a20| 58 09 09 74 70 6f 73 20 | 2d 3e 20 74 5f 64 61 74 |X..tpos |-> t_dat|
|00004a30| 20 5b 69 2d 31 5d 20 3d | 20 74 70 6f 73 20 2d 3e | [i-1] =| tpos ->|
|00004a40| 20 74 5f 64 61 74 20 5b | 69 5d 3b 0a 58 09 09 74 | t_dat [|i];.X..t|
|00004a50| 70 6f 73 20 2d 3e 20 74 | 5f 70 74 72 20 5b 69 5d |pos -> t|_ptr [i]|
|00004a60| 20 20 20 3d 20 74 70 6f | 73 20 2d 3e 20 74 5f 70 | = tpo|s -> t_p|
|00004a70| 74 72 20 5b 69 2b 31 5d | 3b 0a 58 09 7d 0a 58 7d |tr [i+1]|;.X.}.X}|
|00004a80| 0a 58 0c 2f 2a 0a 58 2a | 2a 20 20 43 4f 4d 42 49 |.X./*.X*|* COMBI|
|00004a90| 4e 45 20 2d 2d 20 43 6f | 6d 62 69 6e 65 20 74 77 |NE -- Co|mbine tw|
|00004aa0| 6f 20 6e 6f 64 65 73 2e | 0a 58 2a 2a 0a 58 2a 2a |o nodes.|.X**.X**|
|00004ab0| 09 43 6f 61 6c 65 73 63 | 65 20 74 77 6f 20 6e 6f |.Coalesc|e two no|
|00004ac0| 64 65 73 20 6f 66 20 61 | 0a 58 2a 2a 09 42 2d 74 |des of a|.X**.B-t|
|00004ad0| 72 65 65 20 77 68 65 6e | 20 74 68 65 79 20 68 61 |ree when| they ha|
|00004ae0| 76 65 20 74 6f 6f 20 66 | 65 77 20 6e 6f 64 65 73 |ve too f|ew nodes|
|00004af0| 2e 0a 58 2a 2a 0a 58 2a | 2a 09 50 61 72 61 6d 65 |..X**.X*|*.Parame|
|00004b00| 74 65 72 73 3a 0a 58 2a | 2a 09 09 74 20 20 20 2d |ters:.X*|*..t -|
|00004b10| 2d 20 20 50 74 72 20 74 | 6f 20 42 2d 74 72 65 65 |- Ptr t|o B-tree|
|00004b20| 20 6e 6f 64 65 2c 0a 58 | 2a 2a 09 09 70 6f 73 20 | node,.X|**..pos |
|00004b30| 2d 2d 20 20 49 6e 64 65 | 78 20 6f 66 20 74 68 65 |-- Inde|x of the|
|00004b40| 20 73 70 6c 69 74 20 70 | 6f 69 6e 74 2e 0a 58 2a | split p|oint..X*|
|00004b50| 2a 0a 58 2a 2a 09 52 65 | 74 75 72 6e 73 3a 0a 58 |*.X**.Re|turns:.X|
|00004b60| 2a 2a 09 09 4e 6f 6e 65 | 2e 0a 58 2a 2a 0a 58 2a |**..None|..X**.X*|
|00004b70| 2f 0a 58 0a 58 43 6f 6d | 62 69 6e 65 28 74 2c 20 |/.X.XCom|bine(t, |
|00004b80| 6b 29 0a 58 42 54 52 45 | 45 09 74 3b 0a 58 69 6e |k).XBTRE|E.t;.Xin|
|00004b90| 74 09 6b 3b 7b 0a 58 09 | 69 6e 74 09 69 3b 0a 58 |t.k;{.X.|int.i;.X|
|00004ba0| 09 42 54 52 45 45 09 70 | 2c 0a 58 09 09 71 3b 0a |.BTREE.p|,.X..q;.|
|00004bb0| 58 0a 58 09 70 20 3d 20 | 74 20 2d 3e 20 74 5f 70 |X.X.p = |t -> t_p|
|00004bc0| 74 72 20 5b 6b 2d 31 5d | 3b 0a 58 09 71 20 3d 20 |tr [k-1]|;.X.q = |
|00004bd0| 74 20 2d 3e 20 74 5f 70 | 74 72 20 5b 6b 5d 3b 0a |t -> t_p|tr [k];.|
|00004be0| 58 0a 58 09 70 20 2d 3e | 20 74 5f 61 63 74 69 76 |X.X.p ->| t_activ|
|00004bf0| 65 2b 2b 3b 0a 58 09 70 | 20 2d 3e 20 74 5f 64 61 |e++;.X.p| -> t_da|
|00004c00| 74 20 5b 70 20 2d 3e 20 | 74 5f 61 63 74 69 76 65 |t [p -> |t_active|
|00004c10| 2d 31 5d 20 3d 20 74 20 | 2d 3e 20 74 5f 64 61 74 |-1] = t |-> t_dat|
|00004c20| 20 5b 6b 2d 31 5d 3b 0a | 58 09 70 20 2d 3e 20 74 | [k-1];.|X.p -> t|
|00004c30| 5f 70 74 72 20 5b 70 20 | 2d 3e 20 74 5f 61 63 74 |_ptr [p |-> t_act|
|00004c40| 69 76 65 5d 20 20 20 3d | 20 71 20 2d 3e 20 74 5f |ive] =| q -> t_|
|00004c50| 70 74 72 20 5b 30 5d 3b | 0a 58 0a 58 09 66 6f 72 |ptr [0];|.X.X.for|
|00004c60| 20 28 69 20 3d 20 31 3b | 20 69 20 3c 3d 20 71 20 | (i = 1;| i <= q |
|00004c70| 2d 3e 20 74 5f 61 63 74 | 69 76 65 3b 20 2b 2b 69 |-> t_act|ive; ++i|
|00004c80| 29 20 7b 0a 58 09 09 70 | 20 2d 3e 20 74 5f 61 63 |) {.X..p| -> t_ac|
|00004c90| 74 69 76 65 2b 2b 3b 0a | 58 09 09 70 20 2d 3e 20 |tive++;.|X..p -> |
|00004ca0| 74 5f 64 61 74 20 5b 70 | 20 2d 3e 20 74 5f 61 63 |t_dat [p| -> t_ac|
|00004cb0| 74 69 76 65 2d 31 5d 20 | 3d 20 71 20 2d 3e 20 74 |tive-1] |= q -> t|
|00004cc0| 5f 64 61 74 20 5b 69 2d | 31 5d 3b 0a 58 09 09 70 |_dat [i-|1];.X..p|
|00004cd0| 20 2d 3e 20 74 5f 70 74 | 72 20 5b 70 20 2d 3e 20 | -> t_pt|r [p -> |
|00004ce0| 74 5f 61 63 74 69 76 65 | 5d 20 20 20 3d 20 71 20 |t_active|] = q |
|00004cf0| 2d 3e 20 74 5f 70 74 72 | 20 5b 69 5d 3b 0a 58 09 |-> t_ptr| [i];.X.|
|00004d00| 7d 0a 58 0a 58 09 66 6f | 72 20 28 69 20 3d 20 6b |}.X.X.fo|r (i = k|
|00004d10| 3b 20 69 20 3c 3d 20 74 | 20 2d 3e 20 74 5f 61 63 |; i <= t| -> t_ac|
|00004d20| 74 69 76 65 20 2d 20 31 | 3b 20 2b 2b 69 29 20 7b |tive - 1|; ++i) {|
|00004d30| 0a 58 09 09 74 20 2d 3e | 20 74 5f 64 61 74 20 5b |.X..t ->| t_dat [|
|00004d40| 69 2d 31 5d 20 3d 20 74 | 20 2d 3e 20 74 5f 64 61 |i-1] = t| -> t_da|
|00004d50| 74 20 5b 69 5d 3b 0a 58 | 09 09 74 20 2d 3e 20 74 |t [i];.X|..t -> t|
|00004d60| 5f 70 74 72 20 5b 69 5d | 20 20 20 3d 20 74 20 2d |_ptr [i]| = t -|
|00004d70| 3e 20 74 5f 70 74 72 20 | 5b 69 2b 31 5d 3b 0a 58 |> t_ptr |[i+1];.X|
|00004d80| 09 7d 0a 58 09 74 20 2d | 3e 20 74 5f 61 63 74 69 |.}.X.t -|> t_acti|
|00004d90| 76 65 2d 2d 3b 0a 58 0a | 58 09 44 69 73 70 6f 73 |ve--;.X.|X.Dispos|
|00004da0| 65 28 71 29 3b 0a 58 7d | 0a 58 0a 58 0c 2f 2a 0a |e(q);.X}|.X.X./*.|
|00004db0| 58 2a 2a 20 20 53 45 41 | 52 43 48 20 2d 2d 20 46 |X** SEA|RCH -- F|
|00004dc0| 65 74 63 68 20 61 20 6b | 65 79 20 66 72 6f 6d 20 |etch a k|ey from |
|00004dd0| 61 20 74 72 65 65 0a 58 | 2a 2a 0a 58 2a 2a 09 4c |a tree.X|**.X**.L|
|00004de0| 6f 6f 6b 20 66 6f 72 20 | 61 20 6b 65 79 20 69 6e |ook for |a key in|
|00004df0| 20 61 20 74 72 65 65 2e | 0a 58 2a 2a 0a 58 2a 2a | a tree.|.X**.X**|
|00004e00| 09 50 61 72 61 6d 65 74 | 65 72 73 3a 0a 58 2a 2a |.Paramet|ers:.X**|
|00004e10| 09 09 6b 65 79 20 20 2d | 2d 20 20 4b 65 79 20 76 |..key -|- Key v|
|00004e20| 61 6c 75 65 20 74 6f 20 | 6c 6f 6f 6b 20 66 6f 72 |alue to |look for|
|00004e30| 2c 0a 58 2a 2a 09 09 74 | 20 20 20 20 2d 2d 20 20 |,.X**..t| -- |
|00004e40| 54 72 65 65 20 74 6f 20 | 6c 6f 6f 6b 20 69 6e 2e |Tree to |look in.|
|00004e50| 0a 58 2a 2a 0a 58 2a 2a | 09 52 65 74 75 72 6e 73 |.X**.X**|.Returns|
|00004e60| 3a 0a 58 2a 2a 09 09 4e | 6f 6e 65 2e 0a 58 2a 2a |:.X**..N|one..X**|
|00004e70| 0a 58 2a 2f 0a 58 0a 58 | 44 41 54 55 4d 20 2a 0a |.X*/.X.X|DATUM *.|
|00004e80| 58 53 65 61 72 63 68 28 | 6b 65 79 2c 20 74 29 0a |XSearch(|key, t).|
|00004e90| 58 4b 45 59 09 6b 65 79 | 3b 0a 58 42 54 52 45 45 |XKEY.key|;.XBTREE|
|00004ea0| 09 74 3b 7b 0a 58 09 69 | 6e 74 09 69 3b 0a 58 0a |.t;{.X.i|nt.i;.X.|
|00004eb0| 58 09 77 68 69 6c 65 20 | 28 74 20 21 3d 20 4e 55 |X.while |(t != NU|
|00004ec0| 4c 4c 29 20 7b 0a 58 09 | 09 66 6f 72 20 28 69 20 |LL) {.X.|.for (i |
|00004ed0| 3d 20 30 3b 20 69 20 3c | 20 74 20 2d 3e 20 74 5f |= 0; i <| t -> t_|
|00004ee0| 61 63 74 69 76 65 20 26 | 26 20 4b 65 79 43 6d 70 |active &|& KeyCmp|
|00004ef0| 28 74 20 2d 3e 20 74 5f | 64 61 74 20 5b 69 5d 20 |(t -> t_|dat [i] |
|00004f00| 2e 20 6b 65 79 2c 20 6b | 65 79 29 20 3c 20 30 3b |. key, k|ey) < 0;|
|00004f10| 20 2b 2b 69 29 0a 58 09 | 09 09 3b 09 09 2f 2a 20 | ++i).X.|..;../* |
|00004f20| 4e 55 4c 4c 20 42 4f 44 | 59 20 2a 2f 0a 58 0a 58 |NULL BOD|Y */.X.X|
|00004f30| 09 09 69 66 20 28 69 20 | 3c 20 74 20 2d 3e 20 74 |..if (i |< t -> t|
|00004f40| 5f 61 63 74 69 76 65 20 | 26 26 20 4b 65 79 43 6d |_active |&& KeyCm|
|00004f50| 70 28 6b 65 79 2c 20 74 | 20 2d 3e 20 74 5f 64 61 |p(key, t| -> t_da|
|00004f60| 74 20 5b 69 5d 20 2e 20 | 6b 65 79 29 20 3d 3d 20 |t [i] . |key) == |
|00004f70| 30 29 20 7b 0a 58 09 09 | 09 2f 2a 20 46 4f 55 4e |0) {.X..|./* FOUN|
|00004f80| 44 20 49 54 20 2a 2f 0a | 58 09 09 09 72 65 74 75 |D IT */.|X...retu|
|00004f90| 72 6e 20 26 74 20 2d 3e | 20 74 5f 64 61 74 20 5b |rn &t ->| t_dat [|
|00004fa0| 69 5d 3b 0a 58 09 09 7d | 0a 58 09 09 74 20 3d 20 |i];.X..}|.X..t = |
|00004fb0| 74 20 2d 3e 20 74 5f 70 | 74 72 20 5b 69 5d 3b 0a |t -> t_p|tr [i];.|
|00004fc0| 58 09 7d 0a 58 09 72 65 | 74 75 72 6e 20 4e 55 4c |X.}.X.re|turn NUL|
|00004fd0| 4c 3b 0a 58 7d 0a 58 0c | 2f 2a 0a 58 2a 2a 20 20 |L;.X}.X.|/*.X** |
|00004fe0| 53 48 4f 57 54 52 45 45 | 20 2d 2d 20 44 69 73 70 |SHOWTREE| -- Disp|
|00004ff0| 6c 61 79 20 61 20 74 72 | 65 65 0a 58 2a 2a 0a 58 |lay a tr|ee.X**.X|
|00005000| 2a 2a 09 50 72 69 6e 74 | 20 74 68 65 20 63 6f 6e |**.Print| the con|
|00005010| 74 65 6e 74 73 20 6f 66 | 0a 58 2a 2a 09 61 20 74 |tents of|.X**.a t|
|00005020| 72 65 65 2c 20 73 68 6f | 77 69 6e 67 20 74 68 65 |ree, sho|wing the|
|00005030| 20 6c 65 76 65 6c 0a 58 | 2a 2a 09 6f 66 20 65 61 | level.X|**.of ea|
|00005040| 63 68 20 6e 6f 64 65 2e | 0a 58 2a 2a 0a 58 2a 2a |ch node.|.X**.X**|
|00005050| 09 50 61 72 61 6d 65 74 | 65 72 73 3a 0a 58 2a 2a |.Paramet|ers:.X**|
|00005060| 09 09 74 20 20 20 20 20 | 2d 2d 20 20 54 72 65 65 |..t |-- Tree|
|00005070| 20 74 6f 20 70 72 69 6e | 74 2c 0a 58 2a 2a 09 09 | to prin|t,.X**..|
|00005080| 6c 65 76 65 6c 20 2d 2d | 20 20 44 65 70 74 68 20 |level --| Depth |
|00005090| 69 6e 20 74 72 65 65 2e | 0a 58 2a 2a 0a 58 2a 2a |in tree.|.X**.X**|
|000050a0| 09 52 65 74 75 72 6e 73 | 3a 0a 58 2a 2a 09 09 4e |.Returns|:.X**..N|
|000050b0| 6f 6e 65 2e 0a 58 2a 2a | 0a 58 2a 2f 0a 58 0a 58 |one..X**|.X*/.X.X|
|000050c0| 53 68 6f 77 54 72 65 65 | 28 74 2c 20 6c 65 76 65 |ShowTree|(t, leve|
|000050d0| 6c 29 0a 58 42 54 52 45 | 45 09 74 3b 0a 58 69 6e |l).XBTRE|E.t;.Xin|
|000050e0| 74 09 6c 65 76 65 6c 3b | 7b 0a 58 09 69 6e 74 09 |t.level;|{.X.int.|
|000050f0| 69 3b 0a 58 0a 58 09 69 | 66 20 28 74 20 21 3d 20 |i;.X.X.i|f (t != |
|00005100| 4e 55 4c 4c 29 20 7b 0a | 58 09 09 66 6f 72 20 28 |NULL) {.|X..for (|
|00005110| 69 20 3d 20 30 3b 20 69 | 20 3c 20 6c 65 76 65 6c |i = 0; i| < level|
|00005120| 3b 20 2b 2b 69 29 0a 58 | 09 09 09 70 75 74 63 68 |; ++i).X|...putch|
|00005130| 61 72 28 27 20 27 29 3b | 0a 58 09 09 66 6f 72 20 |ar(' ');|.X..for |
|00005140| 28 69 20 3d 20 30 3b 20 | 69 20 3c 20 74 20 2d 3e |(i = 0; |i < t ->|
|00005150| 20 74 5f 61 63 74 69 76 | 65 3b 20 2b 2b 69 29 0a | t_activ|e; ++i).|
|00005160| 58 09 09 09 53 68 6f 77 | 44 61 74 75 6d 28 74 20 |X...Show|Datum(t |
|00005170| 2d 3e 20 74 5f 64 61 74 | 20 5b 69 5d 29 3b 0a 58 |-> t_dat| [i]);.X|
|00005180| 09 09 70 75 74 63 68 61 | 72 28 27 5c 6e 27 29 3b |..putcha|r('\n');|
|00005190| 0a 58 09 09 66 6f 72 20 | 28 69 20 3d 20 30 3b 20 |.X..for |(i = 0; |
|000051a0| 69 20 3c 3d 20 74 20 2d | 3e 20 74 5f 61 63 74 69 |i <= t -|> t_acti|
|000051b0| 76 65 3b 20 2b 2b 69 29 | 0a 58 09 09 09 53 68 6f |ve; ++i)|.X...Sho|
|000051c0| 77 54 72 65 65 28 74 20 | 2d 3e 20 74 5f 70 74 72 |wTree(t |-> t_ptr|
|000051d0| 20 5b 69 5d 2c 20 31 20 | 2b 20 6c 65 76 65 6c 29 | [i], 1 |+ level)|
|000051e0| 3b 0a 58 09 7d 0a 58 7d | 0a 58 0a 58 0c 2f 2a 0a |;.X.}.X}|.X.X./*.|
|000051f0| 58 2a 2a 20 20 41 50 50 | 4c 59 20 2d 2d 20 41 70 |X** APP|LY -- Ap|
|00005200| 70 6c 79 20 61 20 66 75 | 6e 63 74 69 6f 6e 20 74 |ply a fu|nction t|
|00005210| 6f 20 61 20 62 2d 74 72 | 65 65 0a 58 2a 2a 0a 58 |o a b-tr|ee.X**.X|
|00005220| 2a 2a 09 54 72 61 76 65 | 72 73 65 20 61 20 42 2d |**.Trave|rse a B-|
|00005230| 74 72 65 65 2c 20 61 70 | 70 6c 79 69 6e 67 20 74 |tree, ap|plying t|
|00005240| 68 65 20 66 75 6e 63 74 | 69 6f 6e 0a 58 2a 2a 09 |he funct|ion.X**.|
|00005250| 74 6f 20 65 61 63 68 20 | 6b 65 79 20 77 65 20 66 |to each |key we f|
|00005260| 69 6e 64 2e 0a 58 2a 2a | 0a 58 2a 2a 09 50 61 72 |ind..X**|.X**.Par|
|00005270| 61 6d 65 74 65 72 73 3a | 0a 58 2a 2a 09 09 74 20 |ameters:|.X**..t |
|00005280| 20 20 20 2d 2d 20 20 54 | 68 65 20 74 72 65 65 20 | -- T|he tree |
|00005290| 74 6f 20 64 69 73 70 6c | 61 79 2c 0a 58 2a 2a 09 |to displ|ay,.X**.|
|000052a0| 09 66 75 6e 63 20 2d 2d | 20 20 54 68 65 20 66 75 |.func --| The fu|
|000052b0| 6e 63 74 69 6f 6e 20 74 | 6f 20 61 70 70 6c 79 2e |nction t|o apply.|
|000052c0| 0a 58 2a 2a 0a 58 2a 2a | 09 52 65 74 75 72 6e 73 |.X**.X**|.Returns|
|000052d0| 3a 0a 58 2a 2a 09 09 4e | 6f 6e 65 2e 0a 58 2a 2a |:.X**..N|one..X**|
|000052e0| 0a 58 2a 2f 0a 58 0a 58 | 41 70 70 6c 79 28 74 2c |.X*/.X.X|Apply(t,|
|000052f0| 20 66 75 6e 63 29 0a 58 | 42 54 52 45 45 09 74 3b | func).X|BTREE.t;|
|00005300| 0a 58 69 6e 74 09 28 2a | 66 75 6e 63 29 28 29 3b |.Xint.(*|func)();|
|00005310| 7b 0a 58 09 69 6e 74 09 | 69 3b 0a 58 0a 58 09 69 |{.X.int.|i;.X.X.i|
|00005320| 66 20 28 74 20 21 3d 20 | 4e 55 4c 4c 29 20 7b 0a |f (t != |NULL) {.|
|00005330| 58 09 09 66 6f 72 20 28 | 69 20 3d 20 30 3b 20 69 |X..for (|i = 0; i|
|00005340| 20 3c 20 74 20 2d 3e 20 | 74 5f 61 63 74 69 76 65 | < t -> |t_active|
|00005350| 3b 20 2b 2b 69 29 20 7b | 0a 58 09 09 09 41 70 70 |; ++i) {|.X...App|
|00005360| 6c 79 28 74 20 2d 3e 20 | 74 5f 70 74 72 20 5b 69 |ly(t -> |t_ptr [i|
|00005370| 5d 2c 20 66 75 6e 63 29 | 3b 0a 58 09 09 09 28 2a |], func)|;.X...(*|
|00005380| 66 75 6e 63 29 20 28 74 | 20 2d 3e 20 74 5f 64 61 |func) (t| -> t_da|
|00005390| 74 20 5b 69 5d 29 3b 0a | 58 09 09 7d 0a 58 09 09 |t [i]);.|X..}.X..|
|000053a0| 41 70 70 6c 79 28 74 20 | 2d 3e 20 74 5f 70 74 72 |Apply(t |-> t_ptr|
|000053b0| 20 5b 74 20 2d 3e 20 74 | 5f 61 63 74 69 76 65 5d | [t -> t|_active]|
|000053c0| 2c 20 66 75 6e 63 29 3b | 0a 58 09 7d 0a 58 7d 0a |, func);|.X.}.X}.|
|000053d0| 58 23 69 66 64 65 66 20 | 53 54 41 4e 44 5f 41 4c |X#ifdef |STAND_AL|
|000053e0| 4f 4e 45 0a 58 6d 61 69 | 6e 28 29 7b 0a 58 09 42 |ONE.Xmai|n(){.X.B|
|000053f0| 54 52 45 45 09 74 2c 0a | 58 09 09 6f 6c 64 74 3b |TREE.t,.|X..oldt;|
|00005400| 0a 58 09 44 41 54 55 4d | 09 64 2c 0a 58 09 09 2a |.X.DATUM|.d,.X..*|
|00005410| 64 70 3b 0a 58 09 4b 45 | 59 09 6b 3b 0a 58 09 63 |dp;.X.KE|Y.k;.X.c|
|00005420| 68 61 72 09 62 75 66 20 | 5b 42 55 46 53 49 5a 5d |har.buf |[BUFSIZ]|
|00005430| 3b 0a 58 0a 58 09 74 20 | 3d 20 4e 55 4c 4c 3b 0a |;.X.X.t |= NULL;.|
|00005440| 58 0a 58 09 70 72 69 6e | 74 66 28 22 43 6f 6d 6d |X.X.prin|tf("Comm|
|00005450| 61 6e 64 3a 20 22 29 3b | 20 66 66 6c 75 73 68 28 |and: ");| fflush(|
|00005460| 73 74 64 6f 75 74 29 3b | 0a 58 09 77 68 69 6c 65 |stdout);|.X.while|
|00005470| 20 28 66 67 65 74 73 28 | 62 75 66 2c 20 73 69 7a | (fgets(|buf, siz|
|00005480| 65 6f 66 20 62 75 66 2c | 20 73 74 64 69 6e 29 20 |eof buf,| stdin) |
|00005490| 21 3d 20 4e 55 4c 4c 29 | 20 7b 0a 58 09 09 62 75 |!= NULL)| {.X..bu|
|000054a0| 66 20 5b 73 74 72 6c 65 | 6e 28 62 75 66 29 20 2d |f [strle|n(buf) -|
|000054b0| 20 31 5d 20 3d 20 27 5c | 30 27 3b 0a 58 0a 58 09 | 1] = '\|0';.X.X.|
|000054c0| 09 2f 2a 0a 58 09 09 20 | 2a 09 47 65 74 20 74 68 |./*.X.. |*.Get th|
|000054d0| 65 20 63 6f 6d 6d 61 6e | 64 0a 58 09 09 20 2a 2f |e comman|d.X.. */|
|000054e0| 0a 58 0a 58 09 09 73 77 | 69 74 63 68 20 28 62 75 |.X.X..sw|itch (bu|
|000054f0| 66 20 5b 30 5d 29 20 7b | 0a 58 09 09 09 64 65 66 |f [0]) {|.X...def|
|00005500| 61 75 6c 74 3a 09 09 2f | 2a 20 45 72 72 6f 72 20 |ault:../|* Error |
|00005510| 63 61 73 65 20 2a 2f 0a | 58 09 09 09 09 66 70 72 |case */.|X....fpr|
|00005520| 69 6e 74 66 28 73 74 64 | 65 72 72 2c 20 22 49 2c |intf(std|err, "I,|
|00005530| 20 44 2c 20 4c 2c 20 50 | 20 6f 72 20 53 20 70 6c | D, L, P| or S pl|
|00005540| 65 61 73 65 21 5c 6e 22 | 29 3b 0a 58 09 09 09 09 |ease!\n"|);.X....|
|00005550| 62 72 65 61 6b 3b 0a 58 | 0a 58 09 09 09 63 61 73 |break;.X|.X...cas|
|00005560| 65 20 27 30 27 3a 0a 58 | 09 09 09 63 61 73 65 20 |e '0':.X|...case |
|00005570| 27 31 27 3a 0a 58 09 09 | 09 63 61 73 65 20 27 32 |'1':.X..|.case '2|
|00005580| 27 3a 0a 58 09 09 09 63 | 61 73 65 20 27 33 27 3a |':.X...c|ase '3':|
|00005590| 0a 58 09 09 09 63 61 73 | 65 20 27 34 27 3a 0a 58 |.X...cas|e '4':.X|
|000055a0| 09 09 09 63 61 73 65 20 | 27 35 27 3a 0a 58 09 09 |...case |'5':.X..|
|000055b0| 09 63 61 73 65 20 27 36 | 27 3a 0a 58 09 09 09 63 |.case '6|':.X...c|
|000055c0| 61 73 65 20 27 37 27 3a | 0a 58 09 09 09 63 61 73 |ase '7':|.X...cas|
|000055d0| 65 20 27 38 27 3a 0a 58 | 09 09 09 63 61 73 65 20 |e '8':.X|...case |
|000055e0| 27 39 27 3a 0a 58 09 09 | 09 09 73 73 63 61 6e 66 |'9':.X..|..sscanf|
|000055f0| 28 62 75 66 2c 20 22 25 | 64 22 2c 20 26 64 20 2e |(buf, "%|d", &d .|
|00005600| 20 6b 65 79 29 3b 0a 58 | 09 09 09 09 74 20 3d 20 | key);.X|....t = |
|00005610| 49 6e 73 65 72 74 28 64 | 2c 20 74 29 3b 0a 58 09 |Insert(d|, t);.X.|
|00005620| 09 09 09 62 72 65 61 6b | 3b 0a 58 0a 58 09 09 09 |...break|;.X.X...|
|00005630| 63 61 73 65 20 27 53 27 | 3a 09 09 2f 2a 20 53 65 |case 'S'|:../* Se|
|00005640| 74 20 75 70 20 64 65 66 | 61 75 6c 74 20 74 72 65 |t up def|ault tre|
|00005650| 65 20 2a 2f 0a 58 09 09 | 09 09 74 20 3d 20 4e 55 |e */.X..|..t = NU|
|00005660| 4c 4c 3b 0a 58 09 09 09 | 09 64 20 2e 20 6b 65 79 |LL;.X...|.d . key|
|00005670| 20 3d 20 32 30 3b 0a 58 | 09 09 09 09 74 20 3d 20 | = 20;.X|....t = |
|00005680| 49 6e 73 65 72 74 28 64 | 2c 20 74 29 3b 0a 58 09 |Insert(d|, t);.X.|
|00005690| 09 09 09 64 20 2e 20 6b | 65 79 20 3d 20 31 30 3b |...d . k|ey = 10;|
|000056a0| 0a 58 09 09 09 09 74 20 | 3d 20 49 6e 73 65 72 74 |.X....t |= Insert|
|000056b0| 28 64 2c 20 74 29 3b 0a | 58 09 09 09 09 64 20 2e |(d, t);.|X....d .|
|000056c0| 20 6b 65 79 20 3d 20 31 | 35 3b 0a 58 09 09 09 09 | key = 1|5;.X....|
|000056d0| 74 20 3d 20 49 6e 73 65 | 72 74 28 64 2c 20 74 29 |t = Inse|rt(d, t)|
|000056e0| 3b 0a 58 09 09 09 09 64 | 20 2e 20 6b 65 79 20 3d |;.X....d| . key =|
|000056f0| 20 33 30 3b 0a 58 09 09 | 09 09 74 20 3d 20 49 6e | 30;.X..|..t = In|
|00005700| 73 65 72 74 28 64 2c 20 | 74 29 3b 0a 58 09 09 09 |sert(d, |t);.X...|
|00005710| 09 64 20 2e 20 6b 65 79 | 20 3d 20 34 30 3b 0a 58 |.d . key| = 40;.X|
|00005720| 09 09 09 09 74 20 3d 20 | 49 6e 73 65 72 74 28 64 |....t = |Insert(d|
|00005730| 2c 20 74 29 3b 0a 58 09 | 09 09 09 64 20 2e 20 6b |, t);.X.|...d . k|
|00005740| 65 79 20 3d 20 37 3b 0a | 58 09 09 09 09 74 20 3d |ey = 7;.|X....t =|
|00005750| 20 49 6e 73 65 72 74 28 | 64 2c 20 74 29 3b 0a 58 | Insert(|d, t);.X|
|00005760| 09 09 09 09 64 20 2e 20 | 6b 65 79 20 3d 20 31 38 |....d . |key = 18|
|00005770| 3b 0a 58 09 09 09 09 74 | 20 3d 20 49 6e 73 65 72 |;.X....t| = Inser|
|00005780| 74 28 64 2c 20 74 29 3b | 0a 58 09 09 09 09 64 20 |t(d, t);|.X....d |
|00005790| 2e 20 6b 65 79 20 3d 20 | 32 32 3b 0a 58 09 09 09 |. key = |22;.X...|
|000057a0| 09 74 20 3d 20 49 6e 73 | 65 72 74 28 64 2c 20 74 |.t = Ins|ert(d, t|
|000057b0| 29 3b 0a 58 09 09 09 09 | 64 20 2e 20 6b 65 79 20 |);.X....|d . key |
|000057c0| 3d 20 32 36 3b 0a 58 09 | 09 09 09 74 20 3d 20 49 |= 26;.X.|...t = I|
|000057d0| 6e 73 65 72 74 28 64 2c | 20 74 29 3b 0a 58 09 09 |nsert(d,| t);.X..|
|000057e0| 09 09 64 20 2e 20 6b 65 | 79 20 3d 20 35 3b 0a 58 |..d . ke|y = 5;.X|
|000057f0| 09 09 09 09 74 20 3d 20 | 49 6e 73 65 72 74 28 64 |....t = |Insert(d|
|00005800| 2c 20 74 29 3b 0a 58 09 | 09 09 09 64 20 2e 20 6b |, t);.X.|...d . k|
|00005810| 65 79 20 3d 20 33 35 3b | 0a 58 09 09 09 09 74 20 |ey = 35;|.X....t |
|00005820| 3d 20 49 6e 73 65 72 74 | 28 64 2c 20 74 29 3b 0a |= Insert|(d, t);.|
|00005830| 58 09 09 09 09 64 20 2e | 20 6b 65 79 20 3d 20 31 |X....d .| key = 1|
|00005840| 33 3b 0a 58 09 09 09 09 | 74 20 3d 20 49 6e 73 65 |3;.X....|t = Inse|
|00005850| 72 74 28 64 2c 20 74 29 | 3b 0a 58 09 09 09 09 64 |rt(d, t)|;.X....d|
|00005860| 20 2e 20 6b 65 79 20 3d | 20 32 37 3b 0a 58 09 09 | . key =| 27;.X..|
|00005870| 09 09 74 20 3d 20 49 6e | 73 65 72 74 28 64 2c 20 |..t = In|sert(d, |
|00005880| 74 29 3b 0a 58 09 09 09 | 09 64 20 2e 20 6b 65 79 |t);.X...|.d . key|
|00005890| 20 3d 20 33 32 3b 0a 58 | 09 09 09 09 74 20 3d 20 | = 32;.X|....t = |
|000058a0| 49 6e 73 65 72 74 28 64 | 2c 20 74 29 3b 0a 58 09 |Insert(d|, t);.X.|
|000058b0| 09 09 09 64 20 2e 20 6b | 65 79 20 3d 20 34 32 3b |...d . k|ey = 42;|
|000058c0| 0a 58 09 09 09 09 74 20 | 3d 20 49 6e 73 65 72 74 |.X....t |= Insert|
|000058d0| 28 64 2c 20 74 29 3b 0a | 58 09 09 09 09 64 20 2e |(d, t);.|X....d .|
|000058e0| 20 6b 65 79 20 3d 20 34 | 36 3b 0a 58 09 09 09 09 | key = 4|6;.X....|
|000058f0| 74 20 3d 20 49 6e 73 65 | 72 74 28 64 2c 20 74 29 |t = Inse|rt(d, t)|
|00005900| 3b 0a 58 09 09 09 09 64 | 20 2e 20 6b 65 79 20 3d |;.X....d| . key =|
|00005910| 20 32 34 3b 0a 58 09 09 | 09 09 74 20 3d 20 49 6e | 24;.X..|..t = In|
|00005920| 73 65 72 74 28 64 2c 20 | 74 29 3b 0a 58 09 09 09 |sert(d, |t);.X...|
|00005930| 09 64 20 2e 20 6b 65 79 | 20 3d 20 34 35 3b 0a 58 |.d . key| = 45;.X|
|00005940| 09 09 09 09 74 20 3d 20 | 49 6e 73 65 72 74 28 64 |....t = |Insert(d|
|00005950| 2c 20 74 29 3b 0a 58 09 | 09 09 09 64 20 2e 20 6b |, t);.X.|...d . k|
|00005960| 65 79 20 3d 20 32 35 3b | 0a 58 09 09 09 09 74 20 |ey = 25;|.X....t |
|00005970| 3d 20 49 6e 73 65 72 74 | 28 64 2c 20 74 29 3b 0a |= Insert|(d, t);.|
|00005980| 58 09 09 09 09 53 68 6f | 77 54 72 65 65 28 74 2c |X....Sho|wTree(t,|
|00005990| 20 30 29 3b 0a 58 09 09 | 09 09 62 72 65 61 6b 3b | 0);.X..|..break;|
|000059a0| 0a 58 0a 58 09 09 09 63 | 61 73 65 20 27 49 27 3a |.X.X...c|ase 'I':|
|000059b0| 09 09 2f 2a 20 49 6e 73 | 65 72 74 20 61 20 6b 65 |../* Ins|ert a ke|
|000059c0| 79 20 2a 2f 0a 58 09 09 | 09 09 73 73 63 61 6e 66 |y */.X..|..sscanf|
|000059d0| 28 62 75 66 2b 31 2c 20 | 22 25 64 22 2c 20 26 64 |(buf+1, |"%d", &d|
|000059e0| 20 2e 20 6b 65 79 29 3b | 0a 58 09 09 09 09 74 20 | . key);|.X....t |
|000059f0| 3d 20 49 6e 73 65 72 74 | 28 64 2c 20 74 29 3b 0a |= Insert|(d, t);.|
|00005a00| 58 09 09 09 09 62 72 65 | 61 6b 3b 0a 58 0a 58 09 |X....bre|ak;.X.X.|
|00005a10| 09 09 63 61 73 65 20 27 | 44 27 3a 09 09 2f 2a 20 |..case '|D':../* |
|00005a20| 44 65 6c 65 74 65 20 61 | 20 6b 65 79 20 2a 2f 0a |Delete a| key */.|
|00005a30| 58 09 09 09 09 73 73 63 | 61 6e 66 28 62 75 66 2b |X....ssc|anf(buf+|
|00005a40| 31 2c 20 22 25 64 22 2c | 20 26 64 20 2e 20 6b 65 |1, "%d",| &d . ke|
|00005a50| 79 29 3b 0a 58 09 09 09 | 09 6f 6c 64 74 20 3d 20 |y);.X...|.oldt = |
|00005a60| 74 3b 0a 58 09 09 09 09 | 74 20 3d 20 44 65 6c 65 |t;.X....|t = Dele|
|00005a70| 74 65 28 64 20 2e 20 6b | 65 79 2c 20 74 29 3b 0a |te(d . k|ey, t);.|
|00005a80| 58 09 09 09 09 69 66 20 | 28 74 20 3d 3d 20 4e 55 |X....if |(t == NU|
|00005a90| 4c 4c 29 0a 58 09 09 09 | 09 09 74 20 3d 20 6f 6c |LL).X...|..t = ol|
|00005aa0| 64 74 3b 0a 58 09 09 09 | 09 62 72 65 61 6b 3b 0a |dt;.X...|.break;.|
|00005ab0| 58 0a 58 09 09 09 63 61 | 73 65 20 27 4c 27 3a 09 |X.X...ca|se 'L':.|
|00005ac0| 09 2f 2a 20 4c 6f 6f 6b | 75 70 20 61 20 6b 65 79 |./* Look|up a key|
|00005ad0| 20 2a 2f 0a 58 09 09 09 | 09 73 73 63 61 6e 66 28 | */.X...|.sscanf(|
|00005ae0| 62 75 66 2b 31 2c 20 22 | 25 64 22 2c 20 26 64 20 |buf+1, "|%d", &d |
|00005af0| 2e 20 6b 65 79 29 3b 0a | 58 09 09 09 09 64 70 20 |. key);.|X....dp |
|00005b00| 3d 20 53 65 61 72 63 68 | 28 64 20 2e 20 6b 65 79 |= Search|(d . key|
|00005b10| 2c 20 74 29 3b 0a 58 09 | 09 09 09 70 72 69 6e 74 |, t);.X.|...print|
|00005b20| 66 28 22 25 73 5c 6e 22 | 2c 0a 58 09 09 09 09 09 |f("%s\n"|,.X.....|
|00005b30| 64 70 20 21 3d 20 4e 55 | 4c 4c 20 3f 20 22 46 6f |dp != NU|LL ? "Fo|
|00005b40| 75 6e 64 20 69 74 22 20 | 3a 20 22 4e 6f 20 73 75 |und it" |: "No su|
|00005b50| 63 68 20 6b 65 79 22 29 | 3b 0a 58 09 09 09 09 62 |ch key")|;.X....b|
|00005b60| 72 65 61 6b 3b 0a 58 0a | 58 09 09 09 63 61 73 65 |reak;.X.|X...case|
|00005b70| 20 27 50 27 3a 09 09 2f | 2a 20 53 68 6f 77 20 74 | 'P':../|* Show t|
|00005b80| 68 65 20 74 72 65 65 20 | 2a 2f 0a 58 09 09 09 09 |he tree |*/.X....|
|00005b90| 53 68 6f 77 54 72 65 65 | 28 74 2c 20 30 29 3b 0a |ShowTree|(t, 0);.|
|00005ba0| 58 09 09 09 09 62 72 65 | 61 6b 3b 0a 58 09 09 7d |X....bre|ak;.X..}|
|00005bb0| 0a 58 09 09 70 72 69 6e | 74 66 28 22 43 6f 6d 6d |.X..prin|tf("Comm|
|00005bc0| 61 6e 64 3a 20 22 29 3b | 20 66 66 6c 75 73 68 28 |and: ");| fflush(|
|00005bd0| 73 74 64 6f 75 74 29 3b | 0a 58 09 7d 0a 58 09 41 |stdout);|.X.}.X.A|
|00005be0| 70 70 6c 79 28 74 2c 20 | 53 68 6f 77 44 61 74 75 |pply(t, |ShowDatu|
|00005bf0| 6d 29 3b 0a 58 09 65 78 | 69 74 28 30 29 3b 0a 58 |m);.X.ex|it(0);.X|
|00005c00| 7d 0a 58 23 65 6e 64 69 | 66 20 53 54 41 4e 44 5f |}.X#endi|f STAND_|
|00005c10| 41 4c 4f 4e 45 0a 53 48 | 41 52 5f 45 4f 46 0a 69 |ALONE.SH|AR_EOF.i|
|00005c20| 66 20 74 65 73 74 20 31 | 34 35 37 31 20 2d 6e 65 |f test 1|4571 -ne|
|00005c30| 20 22 60 77 63 20 2d 63 | 20 27 62 74 72 65 65 2e | "`wc -c| 'btree.|
|00005c40| 63 27 60 22 0a 74 68 65 | 6e 0a 09 65 63 68 6f 20 |c'`".the|n..echo |
|00005c50| 73 68 61 72 3a 20 65 72 | 72 6f 72 20 74 72 61 6e |shar: er|ror tran|
|00005c60| 73 6d 69 74 74 69 6e 67 | 20 22 27 62 74 72 65 65 |smitting| "'btree|
|00005c70| 2e 63 27 22 20 27 28 73 | 68 6f 75 6c 64 20 68 61 |.c'" '(s|hould ha|
|00005c80| 76 65 20 62 65 65 6e 20 | 31 34 35 37 31 20 63 68 |ve been |14571 ch|
|00005c90| 61 72 61 63 74 65 72 73 | 29 27 0a 66 69 0a 65 63 |aracters|)'.fi.ec|
|00005ca0| 68 6f 20 73 68 61 72 3a | 20 65 78 74 72 61 63 74 |ho shar:| extract|
|00005cb0| 69 6e 67 20 22 27 62 74 | 72 65 65 2e 68 27 22 20 |ing "'bt|ree.h'" |
|00005cc0| 27 28 38 30 31 20 63 68 | 61 72 61 63 74 65 72 73 |'(801 ch|aracters|
|00005cd0| 29 27 0a 69 66 20 74 65 | 73 74 20 2d 66 20 27 62 |)'.if te|st -f 'b|
|00005ce0| 74 72 65 65 2e 68 27 0a | 74 68 65 6e 0a 09 65 63 |tree.h'.|then..ec|
|00005cf0| 68 6f 20 73 68 61 72 3a | 20 6f 76 65 72 2d 77 72 |ho shar:| over-wr|
|00005d00| 69 74 69 6e 67 20 65 78 | 69 73 74 69 6e 67 20 66 |iting ex|isting f|
|00005d10| 69 6c 65 20 22 27 62 74 | 72 65 65 2e 68 27 22 0a |ile "'bt|ree.h'".|
|00005d20| 66 69 0a 73 65 64 20 27 | 73 2f 5e 58 2f 2f 27 20 |fi.sed '|s/^X//' |
|00005d30| 3c 3c 20 5c 53 48 41 52 | 5f 45 4f 46 20 3e 20 27 |<< \SHAR|_EOF > '|
|00005d40| 62 74 72 65 65 2e 68 27 | 0a 58 23 69 6e 63 6c 75 |btree.h'|.X#inclu|
|00005d50| 64 65 20 3c 73 74 64 69 | 6f 2e 68 3e 0a 58 0a 58 |de <stdi|o.h>.X.X|
|00005d60| 09 09 2f 2a 0a 58 09 09 | 20 2a 09 47 6c 6f 62 61 |../*.X..| *.Globa|
|00005d70| 6c 20 73 74 72 75 63 74 | 75 72 65 73 20 61 6e 64 |l struct|ures and|
|00005d80| 20 64 65 66 69 6e 69 74 | 69 6f 6e 73 0a 58 09 09 | definit|ions.X..|
|00005d90| 20 2a 2f 0a 58 0a 58 23 | 64 65 66 69 6e 65 20 54 | */.X.X#|define T|
|00005da0| 52 55 45 09 31 0a 58 23 | 64 65 66 69 6e 65 20 46 |RUE.1.X#|define F|
|00005db0| 41 4c 53 45 09 30 0a 58 | 0a 58 09 09 2f 2a 0a 58 |ALSE.0.X|.X../*.X|
|00005dc0| 09 09 20 2a 09 44 65 63 | 6c 61 72 65 20 74 68 65 |.. *.Dec|lare the|
|00005dd0| 20 74 79 70 65 20 6f 66 | 20 74 68 65 20 4b 45 59 | type of| the KEY|
|00005de0| 0a 58 09 09 20 2a 2f 0a | 58 0a 58 74 79 70 65 64 |.X.. */.|X.Xtyped|
|00005df0| 65 66 20 63 68 61 72 20 | 2a 20 4b 45 59 3b 09 2f |ef char |* KEY;./|
|00005e00| 2a 20 4b 65 79 20 3d 20 | 61 64 64 72 20 72 65 74 |* Key = |addr ret|
|00005e10| 75 72 6e 65 64 20 66 72 | 6f 6d 20 6d 61 6c 6c 6f |urned fr|om mallo|
|00005e20| 63 20 2a 2f 0a 58 0a 58 | 09 09 2f 2a 0a 58 09 09 |c */.X.X|../*.X..|
|00005e30| 20 2a 09 2e 2e 2e 20 64 | 69 74 74 6f 20 66 6f 72 | *.... d|itto for|
|00005e40| 20 74 68 65 20 49 4e 46 | 4f 20 66 69 65 6c 64 0a | the INF|O field.|
|00005e50| 58 09 09 20 2a 2f 0a 58 | 0a 58 74 79 70 65 64 65 |X.. */.X|.Xtypede|
|00005e60| 66 20 73 74 72 75 63 74 | 20 7b 0a 58 09 69 6e 74 |f struct| {.X.int|
|00005e70| 20 4d 61 6c 43 61 6c 6c | 4e 75 6d 3b 09 2f 2a 20 | MalCall|Num;./* |
|00005e80| 6d 61 6c 6c 6f 63 20 63 | 61 6c 6c 20 6e 75 6d 62 |malloc c|all numb|
|00005e90| 65 72 20 2a 2f 0a 58 09 | 69 6e 74 20 4d 61 6c 53 |er */.X.|int MalS|
|00005ea0| 69 7a 65 3b 09 2f 2a 20 | 6d 61 6c 6c 6f 63 27 64 |ize;./* |malloc'd|
|00005eb0| 20 73 69 7a 65 20 2a 2f | 0a 58 09 63 68 61 72 20 | size */|.X.char |
|00005ec0| 2a 20 4d 61 6c 41 64 64 | 72 3b 09 2f 2a 20 6d 61 |* MalAdd|r;./* ma|
|00005ed0| 6c 6c 6f 63 27 64 20 61 | 64 64 72 65 73 73 20 2a |lloc'd a|ddress *|
|00005ee0| 2f 0a 58 09 73 74 72 75 | 63 74 20 6c 69 73 74 20 |/.X.stru|ct list |
|00005ef0| 2a 6c 70 3b 0a 58 7d 20 | 49 4e 46 4f 3b 0a 58 0a |*lp;.X} |INFO;.X.|
|00005f00| 58 74 79 70 65 64 65 66 | 20 73 74 72 75 63 74 20 |Xtypedef| struct |
|00005f10| 44 61 74 75 6d 20 7b 0a | 58 09 4b 45 59 09 6b 65 |Datum {.|X.KEY.ke|
|00005f20| 79 3b 0a 58 09 49 4e 46 | 4f 09 69 6e 66 3b 0a 58 |y;.X.INF|O.inf;.X|
|00005f30| 7d 20 44 41 54 55 4d 3b | 0a 58 0a 58 09 09 2f 2a |} DATUM;|.X.X../*|
|00005f40| 0a 58 09 09 20 2a 09 54 | 68 69 73 20 69 73 20 74 |.X.. *.T|his is t|
|00005f50| 68 65 20 64 65 66 69 6e | 69 74 69 6f 6e 20 6f 66 |he defin|ition of|
|00005f60| 0a 58 09 09 20 2a 09 74 | 68 65 20 6e 6f 64 65 73 |.X.. *.t|he nodes|
|00005f70| 20 6f 66 20 74 68 65 20 | 42 2d 54 72 65 65 0a 58 | of the |B-Tree.X|
|00005f80| 09 09 20 2a 2f 0a 58 0a | 58 23 64 65 66 69 6e 65 |.. */.X.|X#define|
|00005f90| 09 4d 09 32 0a 58 74 79 | 70 65 64 65 66 20 73 74 |.M.2.Xty|pedef st|
|00005fa0| 72 75 63 74 20 62 74 6e | 6f 64 65 20 7b 0a 58 09 |ruct btn|ode {.X.|
|00005fb0| 69 6e 74 09 09 09 74 5f | 61 63 74 69 76 65 3b 09 |int...t_|active;.|
|00005fc0| 09 2f 2a 20 23 20 6f 66 | 20 61 63 74 69 76 65 20 |./* # of| active |
|00005fd0| 6b 65 79 73 20 2a 2f 0a | 58 09 44 41 54 55 4d 09 |keys */.|X.DATUM.|
|00005fe0| 09 09 74 5f 64 61 74 20 | 20 5b 32 20 2a 20 4d 5d |..t_dat | [2 * M]|
|00005ff0| 3b 09 09 2f 2a 20 4b 65 | 79 73 20 20 2b 20 44 61 |;../* Ke|ys + Da|
|00006000| 74 61 20 2a 2f 0a 58 09 | 73 74 72 75 63 74 20 62 |ta */.X.|struct b|
|00006010| 74 6e 6f 64 65 09 09 2a | 74 5f 70 74 72 20 5b 32 |tnode..*|t_ptr [2|
|00006020| 20 2a 20 4d 20 2b 20 31 | 5d 3b 09 2f 2a 20 53 75 | * M + 1|];./* Su|
|00006030| 62 74 72 65 65 20 70 74 | 72 73 20 2a 2f 0a 58 7d |btree pt|rs */.X}|
|00006040| 20 4e 4f 44 45 2c 20 2a | 42 54 52 45 45 3b 0a 58 | NODE, *|BTREE;.X|
|00006050| 0a 58 42 54 52 45 45 20 | 49 6e 73 65 72 74 28 29 |.XBTREE |Insert()|
|00006060| 3b 0a 58 0a 58 42 54 52 | 45 45 20 44 65 6c 65 74 |;.X.XBTR|EE Delet|
|00006070| 65 28 29 3b 0a 58 0a 58 | 44 41 54 55 4d 20 2a 53 |e();.X.X|DATUM *S|
|00006080| 65 61 72 63 68 28 29 3b | 0a 58 0a 58 69 6e 74 20 |earch();|.X.Xint |
|00006090| 41 70 70 6c 79 28 29 3b | 0a 53 48 41 52 5f 45 4f |Apply();|.SHAR_EO|
|000060a0| 46 0a 69 66 20 74 65 73 | 74 20 38 30 31 20 2d 6e |F.if tes|t 801 -n|
|000060b0| 65 20 22 60 77 63 20 2d | 63 20 27 62 74 72 65 65 |e "`wc -|c 'btree|
|000060c0| 2e 68 27 60 22 0a 74 68 | 65 6e 0a 09 65 63 68 6f |.h'`".th|en..echo|
|000060d0| 20 73 68 61 72 3a 20 65 | 72 72 6f 72 20 74 72 61 | shar: e|rror tra|
|000060e0| 6e 73 6d 69 74 74 69 6e | 67 20 22 27 62 74 72 65 |nsmittin|g "'btre|
|000060f0| 65 2e 68 27 22 20 27 28 | 73 68 6f 75 6c 64 20 68 |e.h'" '(|should h|
|00006100| 61 76 65 20 62 65 65 6e | 20 38 30 31 20 63 68 61 |ave been| 801 cha|
|00006110| 72 61 63 74 65 72 73 29 | 27 0a 66 69 0a 65 63 68 |racters)|'.fi.ech|
|00006120| 6f 20 73 68 61 72 3a 20 | 65 78 74 72 61 63 74 69 |o shar: |extracti|
|00006130| 6e 67 20 22 27 6d 61 6b | 65 66 69 6c 65 27 22 20 |ng "'mak|efile'" |
|00006140| 27 28 31 37 37 20 63 68 | 61 72 61 63 74 65 72 73 |'(177 ch|aracters|
|00006150| 29 27 0a 69 66 20 74 65 | 73 74 20 2d 66 20 27 6d |)'.if te|st -f 'm|
|00006160| 61 6b 65 66 69 6c 65 27 | 0a 74 68 65 6e 0a 09 65 |akefile'|.then..e|
|00006170| 63 68 6f 20 73 68 61 72 | 3a 20 6f 76 65 72 2d 77 |cho shar|: over-w|
|00006180| 72 69 74 69 6e 67 20 65 | 78 69 73 74 69 6e 67 20 |riting e|xisting |
|00006190| 66 69 6c 65 20 22 27 6d | 61 6b 65 66 69 6c 65 27 |file "'m|akefile'|
|000061a0| 22 0a 66 69 0a 73 65 64 | 20 27 73 2f 5e 58 2f 2f |".fi.sed| 's/^X//|
|000061b0| 27 20 3c 3c 20 5c 53 48 | 41 52 5f 45 4f 46 20 3e |' << \SH|AR_EOF >|
|000061c0| 20 27 6d 61 6b 65 66 69 | 6c 65 27 0a 58 43 46 4c | 'makefi|le'.XCFL|
|000061d0| 41 47 53 20 3d 20 2d 67 | 0a 58 0a 58 6d 61 6c 74 |AGS = -g|.X.Xmalt|
|000061e0| 72 61 63 65 2e 61 3a 09 | 6d 61 6c 74 72 61 63 65 |race.a:.|maltrace|
|000061f0| 2e 6f 20 6d 61 6c 6c 6f | 63 2e 6f 20 62 74 72 65 |.o mallo|c.o btre|
|00006200| 65 2e 6f 0a 58 09 61 72 | 20 72 76 75 20 6d 61 6c |e.o.X.ar| rvu mal|
|00006210| 74 72 61 63 65 2e 61 20 | 6d 61 6c 74 72 61 63 65 |trace.a |maltrace|
|00006220| 2e 6f 20 6d 61 6c 6c 6f | 63 2e 6f 20 62 74 72 65 |.o mallo|c.o btre|
|00006230| 65 2e 6f 0a 58 09 72 61 | 6e 6c 69 62 20 6d 61 6c |e.o.X.ra|nlib mal|
|00006240| 74 72 61 63 65 2e 61 0a | 58 0a 58 74 65 73 74 3a |trace.a.|X.Xtest:|
|00006250| 09 74 65 73 74 2e 6f 20 | 6d 61 6c 74 72 61 63 65 |.test.o |maltrace|
|00006260| 2e 61 0a 58 09 63 63 20 | 2d 67 20 2d 6f 20 74 65 |.a.X.cc |-g -o te|
|00006270| 73 74 20 74 65 73 74 2e | 6f 20 6d 61 6c 74 72 61 |st test.|o maltra|
|00006280| 63 65 2e 61 0a 53 48 41 | 52 5f 45 4f 46 0a 69 66 |ce.a.SHA|R_EOF.if|
|00006290| 20 74 65 73 74 20 31 37 | 37 20 2d 6e 65 20 22 60 | test 17|7 -ne "`|
|000062a0| 77 63 20 2d 63 20 27 6d | 61 6b 65 66 69 6c 65 27 |wc -c 'm|akefile'|
|000062b0| 60 22 0a 74 68 65 6e 0a | 09 65 63 68 6f 20 73 68 |`".then.|.echo sh|
|000062c0| 61 72 3a 20 65 72 72 6f | 72 20 74 72 61 6e 73 6d |ar: erro|r transm|
|000062d0| 69 74 74 69 6e 67 20 22 | 27 6d 61 6b 65 66 69 6c |itting "|'makefil|
|000062e0| 65 27 22 20 27 28 73 68 | 6f 75 6c 64 20 68 61 76 |e'" '(sh|ould hav|
|000062f0| 65 20 62 65 65 6e 20 31 | 37 37 20 63 68 61 72 61 |e been 1|77 chara|
|00006300| 63 74 65 72 73 29 27 0a | 66 69 0a 65 63 68 6f 20 |cters)'.|fi.echo |
|00006310| 73 68 61 72 3a 20 65 78 | 74 72 61 63 74 69 6e 67 |shar: ex|tracting|
|00006320| 20 22 27 6d 61 6c 74 72 | 61 63 65 2e 63 27 22 20 | "'maltr|ace.c'" |
|00006330| 27 28 35 33 34 39 20 63 | 68 61 72 61 63 74 65 72 |'(5349 c|haracter|
|00006340| 73 29 27 0a 69 66 20 74 | 65 73 74 20 2d 66 20 27 |s)'.if t|est -f '|
|00006350| 6d 61 6c 74 72 61 63 65 | 2e 63 27 0a 74 68 65 6e |maltrace|.c'.then|
|00006360| 0a 09 65 63 68 6f 20 73 | 68 61 72 3a 20 6f 76 65 |..echo s|har: ove|
|00006370| 72 2d 77 72 69 74 69 6e | 67 20 65 78 69 73 74 69 |r-writin|g existi|
|00006380| 6e 67 20 66 69 6c 65 20 | 22 27 6d 61 6c 74 72 61 |ng file |"'maltra|
|00006390| 63 65 2e 63 27 22 0a 66 | 69 0a 73 65 64 20 27 73 |ce.c'".f|i.sed 's|
|000063a0| 2f 5e 58 2f 2f 27 20 3c | 3c 20 5c 53 48 41 52 5f |/^X//' <|< \SHAR_|
|000063b0| 45 4f 46 20 3e 20 27 6d | 61 6c 74 72 61 63 65 2e |EOF > 'm|altrace.|
|000063c0| 63 27 0a 58 2f 2a 20 43 | 6f 64 65 20 66 6f 72 20 |c'.X/* C|ode for |
|000063d0| 64 79 6e 61 6d 69 63 20 | 6d 65 6d 6f 72 79 20 61 |dynamic |memory a|
|000063e0| 6c 6c 6f 63 61 74 69 6f | 6e 20 6c 65 61 6b 20 74 |llocatio|n leak t|
|000063f0| 72 61 63 65 20 74 6f 6f | 6c 2e 20 20 42 79 20 4d |race too|l. By M|
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.
