$ od -c -N 50000 [Indigo]<AltoSource>BTREE.DM!3 0000000 377 \0 \0 B T r e e . d e c l \0 373 231 0000020 005 230 g \0 \0 376 001 \0 017 032 / / \t B - T 0000040 r e e M a i n t e n a n c e 0000060 R o u t i n e s \r / / C o p y 0000100 r i g h t X e r o x C o r p 0000120 o r a t i o n 1 9 7 9 , 1 9 0000140 8 1 \r \r / / \t B T R E E . D E C 0000160 L - - S t r u c t u r e d 0000200 e f i n i t i o n s \r \r / / \t l 0000220 a s t m o d i f i e d M a y 0000240 9 , 1 9 8 2 1 : 4 0 P 0000260 M b y T a f t \r \r \r s t r u 0000300 c t u r e T S : \t / / T r e 0000320 e S t a t e \r \r \t [ L o g P 0000340 a g e L e n g t h w o r d \t / 0000360 / l o g 2 o f p a g e l 0000400 e n g t h i n w o r d s \r \t 0000420 R o o t P a g e w 376 001 \0 277 D o 0000440 r d \t \t / / B - P a g e c o 0000460 n t a i n i n g t h e r o o 0000500 t \r \t G r e a t e s t P a g e 0000520 w o r d \t / / G r e a t e s t 0000540 k n o w n B - p a g e i n 0000560 t h e t r e e \r \t F i r s t 0000600 F r e e P a g e w o r d \t / / 0000620 H e a d o f l i s t o f 0000640 f r e e B - p a g e s l e 0000660 \r \t \t \t \t / / G r e a t e s t 0000700 P a g e , 0 i f e m p t y 0000720 \r \t R e c o r d C o u n t w o 0000740 r d \t / / R e c o r d c o u 0000760 n t m o d 2 ^ 1 6 f o r 0001000 c h e c k i n g \r \t ] \r \r m a n 0001020 i f e s t [ l T S = s 376 0001040 001 \0 030 \a i z e T S / 1 6 ] \r 0001060 \r s t r u c t u r e T R E E : 0001100 \t / / T r e e D e s c r i p 0001120 t o r \r \r \t [ B V R R P w o 0001140 r d \t \t / / P r o c e d u r e 0001160 w h i c h r e a d s a B 0001200 - T r e e p a g e \r \t B V W R 0001220 P w o r d \t \t / / P r o c e 0001240 d u r e w h i c h r e a d s 0001260 a B - T r e e p a g e \r \t 0001300 \t \t \t / / b u t s e t s i 0001320 t s d i r t y b i t o n \r 0001340 \t B L o c k C e l l w o r d \t 0001360 \t / / P r o c e d u r e w h 0001400 i c h l o c k s a c e l l 0001420 \r \t B U n l o c k C e l l w o 0001440 r d \t / 376 001 \0 S & / P r o c e 0001460 d u r e w h i c h u n l o c 0001500 k s a p r e v i o u s l y - 0001520 l o c k e d c e l l \r \t B V A 0001540 P w o r d \t \t / / P r o c e 0001560 d u r e w h i c h a l l o c 0001600 a t e s a n e w B - T r e 0001620 e p a g e \r \t B V F P w o r 0001640 d \t \t / / P r o c e d u r e 0001660 w h i c h a c c e p t s b a 0001700 c k a \r \t \t \t \t / / p r e v 0001720 i o u s l y - a l l o c a t e d 0001740 B - T r e e p a g e \r \t B T 0001760 B u g w o r d \t \t / / E r r 0002000 o r - h a n d l i n g p r o c 0002020 e d u r e \r \t B T C l o s e w 0002040 o r d \t \t / / P 376 001 \0 304 4 r o 0002060 c e d u r e t o c l o s e 0002100 t h i s t r e e \r \r \t C o m p 0002120 a r e K e y R t n w o r d \t / 0002140 / P r o c e d u r e w h i c 0002160 h c o m p a r e s t h e k 0002200 e y i n a \r \t \t \t \t / / r 0002220 e c o r d w i t h a n i s 0002240 o l a t e d k e y \r \t L e n g 0002260 t h R t n w o r d \t \t / / P 0002300 r o c e d u r e w h i c h r 0002320 e t u r n s t h e l e n g t 0002340 h o f a \r \t \t \t \t / / r e 0002360 c o r d i n w o r d s \r \r \t 0002400 P a g e L e n g t h w o r d \t 0002420 \t / / B - P a g e l e n g t 0002440 h i n w o r d s ( s h 376 001 0002460 \0 C h o u l d b e p o w e r 0002500 o f 2 ) \r \r \t Z o n e w o 0002520 r d \t \t / / P o i n t e r t 0002540 o a f r e e s t o r a g e 0002560 z o n e o b j e c t \r \r \t S 0002600 t a t e D i r t y w o r d \t \t 0002620 / / T r u e i f s t a t e 0002640 i n c o r e n e s t a t 0002660 e o n d i s k \r \t V e r s i 0002700 o n w o r d \t \t / / N u m b 0002720 e r o f u p d a t e s t o 0002740 t h e t r e e \r \r \r \t T S 0002760 @ T S \t \t \t / / P e r m a n e 0003000 n t t r e e s t a t e \r \t = 0003020 \r \t @ T S \r \r \t v m d w o r d 0003040 \t \t / / v i r t u a l m e m 0003060 o r y 376 001 \0 C 354 d e s c r i p 0003100 t o r ( f o r I F S e n v 0003120 i r o n m e n t ) \r \t ] \r \r \r m 0003140 a n i f e s t [ \r \t E m p t y 0003160 = 0 \r \t m a x R e c o r d s 0003200 P e r P a g e = 1 0 2 2 / 8 0003220 / / a s s u m i n g 8 - 0003240 w o r d e n t r i e s i n 0003260 1 0 2 4 - w o r d p a g e \r \t 0003300 m a x L e v e l s I n T r e e 0003320 = 6 \t / / m a x i m u m d 0003340 e p t h o f t r e e \r \t ] \r 0003360 \r \r s t r u c t u r e B T E : 0003400 \t / / B - T r e e E n t r y 0003420 \r \r \t [ G r P t r w o r d \t 0003440 \t / / P a g e c o n t a i n 0003460 i n g s o n s 376 001 \0 t 351 g r 0003500 e a t e r \r \t \t \t \t / / \t t h a 0003520 n t h i s e n t r y b u t 0003540 l e s s \r \t \t \t \t / / \t t h a 0003560 n t h e n e x t \r \t R e c o 0003600 r d w o r d 1 0 \t \t / / T 0003620 h e r e c o r d c o r r e s 0003640 p o n d i n g t o t h i s \r 0003660 \t \t \t \t / / \t e n t r y , c o 0003700 n t a i n i n g a k e y \r \t 0003720 ] \r \r \r s t r u c t u r e E S 0003740 L E : \t / / E n t r y S e q 0003760 u e n c e L i s t E n t r y 0004000 \r \r \t [ F w d P w o r d \r \t 0004020 E n t S e q P w o r d \t \t / / 0004040 P o i n t e r t o a s e 0004060 q u e n c e o f e n t 376 001 \0 0004100 V 312 r i e s \r \t E n t S e q L e 0004120 n w o r d \t \t / / L e n g t 0004140 h o f s e q u e n c e i n 0004160 w o r d s \r \t E n t S e q w 0004200 o r d 1 0 \t \t / / S e q u e 0004220 n c e g o e s h e r e \r \t ] 0004240 \r \r \r s t r u c t u r e E L E 0004260 : \t / / E n t r y L i s t 0004300 E l e m e n t \r \t \t / / G i v 0004320 e s c u m u l a t i v e l e 0004340 n g t h a n d p o i n t e r 0004360 t o h e a p e n t r y \r \t 0004400 [ C u m E n t L e n w o r d 0004420 \r \t H e a p P o s w o r d \r \t 0004440 ] \r \r \r s t r u c t u r e E L 0004460 L : / / B l o c k o f E 0004500 n t 376 001 \0 257 322 r y L i s t E 0004520 l e m e n t s \r \r \t [ [ E L 0004540 E ^ 0 , 3 * m a x R e c o r d s 0004560 P e r P a g e + 2 @ E L E 0004600 ] = \r \t @ E L E ^ 0 , 3 * m 0004620 a x R e c o r d s P e r P a g e 0004640 + 2 \r \t ] \r \r \r \r s t r u c 0004660 t u r e H P : \t / / H e a p 0004700 o f e n t r i e s c o n t 0004720 e n d i n g f o r f a t h e 0004740 r b l o c k \r \r \t [ H e a p 0004760 E n t ^ 1 , 2 5 6 w o r d \r \t 0005000 ] \r \r \r s t r u c t u r e B T 0005020 P : \t / / B - T r e e P a g 0005040 e \r \r \t [ F r e e W o r d s 0005060 w o r d \t / / N u m b e r o 0005100 f f r e e 376 001 \0 \v 375 w o r d 0005120 s t h i s p a g e \r \t M i n 0005140 P t r w o r d \t \t / / P a g 0005160 e c o n t a i n i n g s m a 0005200 l l e s t s o n o f t h i 0005220 s p a g e \r \t B T E B l o c k 0005240 w o r d 1 \t \t / / T h e 0005260 B T E e n t r i e s o n t 0005300 h i s p a g e \r \t ] \r \r \r m a 0005320 n i f e s t [ \r \t P a g e O v 0005340 e r h e a d = o f f s e t 0005360 B T P . B T E B l o c k / 1 6 \r 0005400 \t R e c 0 O f f s e t = o f 0005420 f s e t B T P . M i n P t r / 0005440 1 6 \r \t R e c 1 O f f s e t = 0005460 o f f s e t B T P . B T E B 0005500 l o c k / 1 6 \r \t ] \r \r 376 001 \0 356 0005520 R \r s t r u c t u r e P S E : 0005540 \t / / P a t h S t a c k E 0005560 n t r y \r \r \t [ P a g e N o 0005600 w o r d \t \t / / a l s o a 0005620 p p e a r s a s G r P t r 0005640 f i e l d o f B T E i n d 0005660 e x e d \r \t \t \t \t / / b y L 0005700 a s t O f f s e t i n p r e 0005720 v i o u s s t a c k l e v e 0005740 l \r \r \t O f f s e t w o r d \r 0005760 \t L a s t O f f s e t w o r d 0006000 \r \t N e x t T o L a s t O f f s 0006020 e t w o r d \r \r \t E S L F r o 0006040 n t w o r d \t \t / / A d d e 0006060 d b l o c k s o f e n t r 0006100 i e s t h a t g o b e t w 0006120 e 376 001 \0 344 335 e n \r \t \t \t \t / / 0006140 L a s t O f f s e t a n d O 0006160 f f s e t \r \t E S L R e a r w 0006200 o r d \r \r \t L e a s t S o n w 0006220 o r d \r \t ] \r \r \r / / P a t h 0006240 S t k s t r u c t u r e \r / / 0006260 N o t e t h a t l e v e l 0006300 0 i s d u m m y ; i t 0006320 i s u s e d o n l y w h e 0006340 n t h e r o o t p a g e 0006360 s p l i t s \r / / a n d a 0006400 n e w r o o t p a g e m u 0006420 s t b e c r e a t e d . \r s 0006440 t r u c t u r e P S : \r \t [ 0006460 V e r s i o n w o r d \t \t / / 0006500 v a l u e o f T R E E . V 0006520 e r s i o n 376 001 \0 r 352 f o r 0006540 w h i c h t h i s P S i s 0006560 v a l i d \r \t P a t h S t k T 0006600 o p w o r d \r \t P S E ^ 0 , m 0006620 a x L e v e l s I n T r e e : 0006640 @ P S E \r \t ] \r \r s t r u c t 0006660 u r e I S : \t / / I n s e r 0006700 t i o n / d e l e t i o n a l 0006720 g o r i t h m a u x i l i a r 0006740 y s t a t e \r \t [ T r e e 0006760 w o r d \t \t / / P t r t o 0007000 t r e e h a n d l e \r \r \t M a 0007020 x F r e e W o r d s w o r d \t 0007040 / / n o n - o v e r h e a d 0007060 w o r d s p e r p a g e \r \t 0007100 A w f u l l y F u l l w o r d 0007120 \t / / w o r d s i 376 001 \0 t 031 0007140 n 9 / 1 0 f u l l p a g e 0007160 \r \t P r e t t y F u l l w o r 0007200 d \t \t / / w o r d s i n 2 0007220 / 3 f u l l p a g e \r \t F a 0007240 i r l y F u l l w o r d \t \t / 0007260 / w o r d s i n 1 / 2 f 0007300 u l l p a g e \r \t B r e a t h 0007320 i n g S p a c e w o r d \t / / 0007340 w o r d s i n 1 / 1 0 p 0007360 a g e \r \r \t P a t h S t k w o 0007400 r d \r \r \t E L L P t r w o r d 0007420 \t \t / / P t r t o v e c t 0007440 o r o f c u m u l a t i v e 0007460 l e n g t h s o f \r \t \t \t \t 0007500 / / E S L e n t r i e s \r \t 0007520 E L L L e n w o r d \t \t / / 0007540 376 001 \0 035 232 N u m b e r o f E 0007560 S L e n t r i e s \r \r \t H e a 0007600 p P t r w o r d \r \t H e a p S 0007620 i z e w o r d \r \t ] \r \r \r m a 0007640 n i f e s t [ / / e r r 0007660 o r c o d e s , k e y i n g 0007700 m e s s a g e s i n S y s 0007720 . e r r o r s \r \t e c R e c G e 0007740 n R e t u r n e d W r o n g K e 0007760 y = 2 1 0 0 \r \t e c M c C r 0010000 e i g h t W a s W r o n g = 0010020 2 1 0 1 \r \t e c D e p o s i t E 0010040 S L W r o n g = 2 1 0 2 \r \t 0010060 e c E n t r y L i s t T o o S h 0010100 o r t = 2 1 0 3 \r \t e c W r 0010120 i t e P a g e W r o n g = 2 0010140 1 0 4 \r \t 376 \0 w 035 _ e c T w o B 0010160 r o t h e r s N o t E n o u g h 0010200 = 2 1 0 5 \r \t e c N e w R o 0010220 o t O v e r f l o w = 2 1 0 0010240 6 \r \t e c R e c o r d C o u n t 0010260 s D i s a g r e e = 2 1 0 7 0010300 \r \t e c R e c o r d s O u t O f 0010320 O r d e r = 2 1 0 8 \r \t ] \r 0010340 \r 377 \0 \0 B T r e e R e a d . b c 0010360 p l \0 373 231 005 302 r \0 \0 376 001 \0 207 030 / 0010400 / \t B - T r e e M a i n t e n 0010420 a n c e R o u t i n e s \r / / 0010440 C o p y r i g h t X e r o x 0010460 C o r p o r a t i o n 1 9 7 0010500 9 , 1 9 8 1 , 1 9 8 2 \r \r / 0010520 / \t B T r e e R e a d . b c p l 0010540 - - R o u t i n e s f o 0010560 r r e a d i n g B - T r e e 0010600 s \r \r / / \t l a s t e d i t e 0010620 d M a y 9 , 1 9 8 2 5 0010640 : 2 5 P M b y T a f t \r \r 0010660 g e t " B T r e e . d e c l " 0010700 \r \r e x t e r n a l \r \t [ M o 0010720 v e B l o c k \r \t A l l o c a t 0010740 e \r \t F r e e \r \t D e f a u l t 0010760 A r g s \r \t Z e r o \r \t D v e 376 0011000 001 \0 216 305 c \r \r \t R e a d B T r e 0011020 e P a g e \t / / d e f i n e d 0011040 i n O p e n B T r e e \r \t W 0011060 r i t e B T r e e P a g e \r \t L 0011100 o c k B T r e e P t r \r \t U n l 0011120 o c k B T r e e P t r \r \t ] \r \r 0011140 \r e x t e r n a l \r \t [ \r \t R e 0011160 a d R e c L E \t / / o u t g o 0011200 i n g p r o c e d u e s \r \t M 0011220 a p T r e e \r \t P a t h R e c L 0011240 E \r \t B a c k U p O n e R e c o 0011260 r d \r \t R e p a i r O f f s e t 0011300 s \r \t R e a d S t a c k A n d L 0011320 o c k B T r e e P t r \r \t R e a 0011340 d P a g e A n d L o c k B T r e 0011360 e P t r \r \t R e a d S t a c k \r 0011400 \t P o p 376 001 \0 217 s S t a c k \r \t 0011420 G e t R e c o r d \r \t ] \r \r \r / 0011440 / F o r t h e e x t e r n 0011460 a l l y - c a l l e d p r o c 0011500 e d u r e s ( R e a d R e c L 0011520 E , M a p T r e e , U p d a 0011540 t e R e c o r d , \r / / a n d 0011560 D e l e t e K e y ) , i f 0011600 c a l l e r s u p p l i e s 0011620 a P a t h S t k a n d U s 0011640 e E x i s t i n g P a t h \r / / 0011660 i s t r u e , t h e n t 0011700 h e c a l l e r a s s e r t 0011720 s t h a t t h e s u p p l 0011740 i e d P a t h S t k w a s 0011760 t h e r e s u l t \r / / o f 0012000 a p r e v i o 376 001 \0 001 + u s 0012020 c a l l w i t h t h e s 0012040 a m e K e y . ( N o t e 0012060 t h a t t h e B - T r e e 0012100 p a c k a g e i s \r / / r e 0012120 s p o n s i b l e f o r d e 0012140 t e r m i n i n g w h e t h e 0012160 r o r n o t t h e t r e 0012200 e h a s c h a n g e d s i 0012220 n c e \r / / t h e P a t h S 0012240 t k w a s c o m p u t e d , 0012260 s o t h e c a l l e r n 0012300 e e d n o t w o r r y a b 0012320 o u t t h a t . ) \r / / I n 0012340 a n y e v e n t , i f c 0012360 a l l e r s u p p l i e s a 0012400 P a t h S t k t h e n 376 001 0012420 \0 ; 8 i t i s f i l l e d 0012440 i n w i t h \r / / t h e p 0012460 a t h t o t h e e n t r y 0012500 r e t u r n e d b y R e a 0012520 d R e c L E o r t h e l a 0012540 s t e n t r y e n u m e r a 0012560 t e d \r / / b y M a p T r e 0012600 e ; U p d a t e R e c o r d 0012620 a n d D e l e t e K e y i n 0012640 v a l i d a t e t h e s u p 0012660 p l i e d P a t h S t k . \r \r 0012700 \r l e t R e a d R e c L E ( T 0012720 r e e , K e y , C K R t n , 0012740 d o n t C o p y , P a t h S 0012760 t k , U s e E x i s t i n g P 0013000 a t h ; \r \t n u m a r g s n a 0013020 ) = 376 001 \0 360 226 v a l o f \r \r 0013040 \t [ \r \t D e f a u l t A r g s ( 0013060 l v n a , - 2 , T r e e > 0013100 > T R E E . C o m p a r e K e y 0013120 R t n , f a l s e , \r \t \t s i 0013140 z e P S / 1 6 , f a l s e ) 0013160 \r \t i f P a t h S t k e q 0013200 s i z e P S / 1 6 t h e n \r 0013220 \t \t [ D v e c ( R e a d R e c 0013240 L E , l v P a t h S t k ) ; 0013260 U s e E x i s t i n g P a t h 0013300 = f a l s e ] \r \r \t P a t 0013320 h R e c L E ( T r e e , P a t 0013340 h S t k , U s e E x i s t i n 0013360 g P a t h , K e y , C K R t 0013400 n ) \r \t r e s u l t i s G e t 0013420 R e c o r d ( T 376 001 \0 372 9 r e e 0013440 , P a t h S t k , d o n t C 0013460 o p y ) \r \t ] \r \r \r a n d M a 0013500 p T r e e ( T r e e , S t a r 0013520 t K e y , F u n c t i o n , 0013540 P a r a m , C K R t n , d o 0013560 n t C o p y , P a t h S t k , 0013600 U s e E x i s t i n g P a t h 0013620 ; \r \t n u m a r g s n a ) = 0013640 v a l o f \r \r \t [ D e f a u 0013660 l t A r g s ( l v n a , - 3 0013700 , 0 , T r e e > > T R E E . 0013720 C o m p a r e K e y R t n , f 0013740 a l s e , \r \t \t s i z e P S / 0013760 1 6 , f a l s e ) \r \t i f P 0014000 a t h S t k e q s i z e P 0014020 S / 1 6 t h e n \r \t \t [ 376 001 \0 0014040 c 373 D v e c ( M a p T r e e , 0014060 l v P a t h S t k ) ; U s 0014100 e E x i s t i n g P a t h = 0014120 f a l s e ] \r \r \t l e t L e 0014140 a f S t k T o p = P a t h R 0014160 e c L E ( T r e e , P a t h S 0014200 t k , U s e E x i s t i n g P 0014220 a t h , S t a r t K e y , C 0014240 K R t n ) \r \r \t i f P a t h S 0014260 t k > > P S . P a t h S t k T o 0014300 p e q 0 t h e n \r \r \t \t / 0014320 / K e y i s l e s s t h 0014340 a n a n y e x i s t i n g 0014360 r e c o r d i n t h e t r 0014400 e e . \r \t \t / / S e t P a t 0014420 h S t k t o f i r s t r e 0014440 c o 376 001 \0 017 330 r d i n l e f 0014460 t m o s t l e a f p a g e . 0014500 \r \r \t \t [ i f L e a f S t k 0014520 T o p e q 0 t h e n r e 0014540 s u l t i s t r u e / / 0014560 e m p t y t r e e \r \t \t P a t 0014600 h S t k > > P S . P a t h S t k 0014620 T o p = L e a f S t k T o p 0014640 \r \t \t P a t h S t k > > P S . P 0014660 S E ^ L e a f S t k T o p . L a 0014700 s t O f f s e t = R e c 1 O 0014720 f f s e t \r \t \t ] \r \r \t l e t 0014740 S P = l v P a t h S t k > 0014760 > P S . P S E ^ ( P a t h S t k 0015000 > > P S . P a t h S t k T o p ) 0015020 \r \r \t l e t P a g e P t r = 0015040 0 \r \t L o c 376 001 \0 305 257 k B T r 0015060 e e P t r ( T r e e , l v P 0015100 a g e P t r ) \r \r \t [ / / r 0015120 e p e a t \r \t l e t O f f s e 0015140 t = S P > > P S E . L a s t 0015160 O f f s e t \r \r \t i f P a g e 0015200 P t r e q 0 t h e n \r \t \t 0015220 P a g e P t r = R e a d B T 0015240 r e e P a g e ( T r e e , S P 0015260 > > P S E . P a g e N o ) \r \r \t 0015300 t e s t O f f s e t g e T 0015320 r e e > > T R E E . P a g e L e 0015340 n g t h - P a g e P t r > > 0015360 B T P . F r e e W o r d s \r \r \t 0015400 i f s o \t / / R a n o f f 0015420 e n d o f p a g e . P o 0015440 p u p a l e v e l 376 001 \0 245 0015460 345 a n d d o t h e n e x 0015500 t \r \t \t / / e n t r y i n 0015520 t h e f a t h e r p a g e . 0015540 \r \r \t \t [ P a g e P t r = 0015560 0 \r \t \t P a t h S t k > > P S . 0015600 P a t h S t k T o p = P a t 0015620 h S t k > > P S . P a t h S t k 0015640 T o p - 1 \r \t \t i f P a t h S 0015660 t k > > P S . P a t h S t k T o 0015700 p l e 0 t h e n \r \t \t \t / 0015720 / R a n o f f e n d o f 0015740 t r e e . P a t h S t k 0015760 i s n o l o n g e r v a l 0016000 i d . \r \t \t \t [ U n l o c k B 0016020 T r e e P t r ( T r e e , l v 0016040 P a g e P t r ) \r \t \t \t P a t 0016060 h 376 001 \0 224 b S t k > > P S . V e 0016100 r s i o n = T r e e > > T R 0016120 E E . V e r s i o n - 1 \r \t \t \t 0016140 r e s u l t i s t r u e \r \t \t 0016160 \t ] \r \t \t S P = S P - s 0016200 i z e P S E / 1 6 \r \t \t ] \r \r 0016220 \t i f n o t \t / / D o n e x 0016240 t e n t r y i n c u r r e 0016260 n t p a g e . \r \r \t \t [ l e 0016300 t N x t P g N o = ( P a g 0016320 e P t r + O f f s e t ) > > B T 0016340 E . G r P t r \r \t \t l e t R e 0016360 c P t r = l v ( P a g e P 0016400 t r + O f f s e t ) > > B T E . 0016420 R e c o r d \r \t \t l e t R e c 0016440 L e n = ( T r e e > > T R E 0016460 E . L e n g 376 001 \0 362 207 t h R t n 0016500 ) ( R e c P t r ) \r \t \t S P > > 0016520 P S E . O f f s e t = O f f 0016540 s e t + ( o f f s e t B T E . 0016560 R e c o r d / 1 6 ) + R e c L e 0016600 n \r \t \r \t \t u n l e s s d o n 0016620 t C o p y d o \r \t \t \t [ l e 0016640 t C o p y R e c = A l l o 0016660 c a t e ( T r e e > > T R E E . 0016700 Z o n e , R e c L e n ) \r \t \t 0016720 \t M o v e B l o c k ( C o p y R 0016740 e c , R e c P t r , R e c L 0016760 e n ) \r \t \t \t R e c P t r = 0017000 C o p y R e c \r \t \t \t P a g e P 0017020 t r = 0 \t / / u n l o c k 0017040 t h e B - T r e e p a g e 0017060 \r \t \t \t ] \r \r \t \t u n 376 001 \0 201 b 0017100 l e s s F u n c t i o n ( R e 0017120 c P t r , P a r a m , P a t 0017140 h S t k ) d o \r \t \t \t [ U n 0017160 l o c k B T r e e P t r ( T r e 0017200 e , l v P a g e P t r ) \r \t 0017220 \t \t r e s u l t i s f a l s e 0017240 \r \t \t \t ] \r \r \t \t / / I f w 0017260 e a r e i n a n o n - l 0017300 e a f p a g e , f i n d t 0017320 h e l e f t m o s t \r \t \t / / 0017340 r i g h t d e s c e n d a n 0017360 t o f t h e e n t r y w 0017400 e j u s t d i d . \r \t \t w h 0017420 i l e N x t P g N o n e E 0017440 m p t y d o \r \t \t \t [ P a t 0017460 h S t k > > P S . P a t h S t k 0017500 376 001 \0 \n 240 T o p = P a t h S 0017520 t k > > P S . P a t h S t k T o 0017540 p + 1 \r \t \t \t S P = S P + 0017560 s i z e P S E / 1 6 \r \t \t \t 0017600 S P > > P S E . P a g e N o = 0017620 N x t P g N o \r \t \t \t S P > > 0017640 P S E . N e x t T o L a s t O f 0017660 f s e t = E m p t y \r \t \t \t 0017700 S P > > P S E . L a s t O f f s 0017720 e t = R e c 0 O f f s e t \r 0017740 \t \t \t S P > > P S E . O f f s e 0017760 t = R e c 1 O f f s e t \r \t 0020000 \t \t P a g e P t r = R e a d 0020020 B T r e e P a g e ( T r e e , 0020040 N x t P g N o ) \r \t \t \t N x t P 0020060 g N o = P a g e P t r > > B 0020100 T P . M i 376 001 \0 202 n P t r \r \t 0020120 \t \t ] \r \t \t ] \r \r \t S P > > P S 0020140 E . N e x t T o L a s t O f f s 0020160 e t = S P > > P S E . L a s 0020200 t O f f s e t \r \t S P > > P S E 0020220 . L a s t O f f s e t = S P 0020240 > > P S E . O f f s e t \r \r \t ] 0020260 r e p e a t \r \r \t ] \r \r \r a n 0020300 d P a t h R e c L E ( T r e e 0020320 , P a t h S t k , U s e E x 0020340 i s t i n g P a t h , K e y , 0020360 C K R ) = v a l o f \r \r / 0020400 / C o m p u t e s a P a t 0020420 h S t k f o r t h e s u p 0020440 p l i e d K e y s u c h t 0020460 h a t a t e a c h l e v e 0020500 l \r / / P S E . L 376 001 \0 c K a 0020520 s t O f f s e t r e f e r s 0020540 t o a n e n t r y l e s s 0020560 t h a n o r e q u a l t 0020600 o K e y a n d \r / / P S E 0020620 . O f f s e t r e f e r s t 0020640 o a n e n t r y s t r i c 0020660 t l y g r e a t e r t h a n 0020700 K e y , i f a n y \r / / 0020720 s u c h e n t r i e s e x i 0020740 s t . S e t s P a t h S t 0020760 k > > P S . P a t h S t k T o p 0021000 t o t h e d e e p e s t 0021020 l e v e l \r / / i n w h i c 0021040 h P S E . L a s t O f f s e t 0021060 r e f e r s t o a r e a 0021100 l e n t r y ( i . e . , 376 0021120 001 \0 341 T n o t R e c 0 O f f s 0021140 e t ) , \r / / u n l e s s n 0021160 o s u c h e n t r y e x i 0021200 s t s i n t h e e n t i r 0021220 e t r e e , i n w h i c h 0021240 c a s e s e t s \r / / P a 0021260 t h S t k T o p t o z e r o 0021300 . R e t u r n s t h e d 0021320 e p t h o f t h e t r e e 0021340 , i . e . , t h e \r / / P 0021360 a t h S t k T o p f o r t h 0021400 e l e a f p a g e ( w h i 0021420 c h i s e i t h e r t h e 0021440 p a g e c o n t a i n i n g 0021460 \r / / t h e L E e n t r y 0021500 o r i t s l e f t m o s t 0021520 r i g 376 001 \0 217 B h t d e s c 0021540 e n d a n t p a g e ) . \r \r \t 0021560 [ i f U s e E x i s t i n g 0021600 P a t h & \r \t \t P a t h S t k 0021620 > > P S . V e r s i o n e q 0021640 T r e e > > T R E E . V e r s i 0021660 o n t h e n \r \r \t \t / / S u 0021700 p p l i e d P a t h S t k s 0021720 t i l l v a l i d ; n o n 0021740 e e d t o s e a r c h t r 0021760 e e . \r \r \t \t [ l e t P a t 0022000 h S t k T o p = P a t h S t 0022020 k > > P S . P a t h S t k T o p 0022040 \r \t \t w h i l e P a t h S t k 0022060 > > P S . P S E ^ P a t h S t k 0022100 T o p . L e a s t S o n n e 0022120 E m p t y d o \r 376 001 \0 324 332 \t \t 0022140 \t P a t h S t k T o p = P a 0022160 t h S t k T o p + 1 \r \t \t r e s 0022200 u l t i s P a t h S t k T o p 0022220 \r \t \t ] \r \r \t Z e r o ( P a t h 0022240 S t k , ( o f f s e t P S . 0022260 P S E ^ 1 ) / 1 6 ) / / o 0022300 v e r h e a d a n d d u m m 0022320 y P S E \r \t P a t h S t k > > 0022340 P S . V e r s i o n = T r e 0022360 e > > T R E E . V e r s i o n \r 0022400 \r \t l e t o f f s e t T a b l 0022420 e = A l l o c a t e ( T r e 0022440 e > > T R E E . Z o n e , m a 0022460 x R e c o r d s P e r P a g e + 0022500 3 ) \r \t M o v e B l o c k ( o f 0022520 f s e t T a b l e , t a b 376 001 0022540 \0 006 321 l e [ E m p t y ; R 0022560 e c 0 O f f s e t ; R e c 1 O 0022600 f f s e t ] , 3 ) \r \r \t l e 0022620 t P a t h S t k T o p = 0 0022640 \r \t l e t S P = l v P a 0022660 t h S t k > > P S . P S E ^ 0 \r 0022700 \r \t l e t C u r P t r = 0 0022720 \r \t L o c k B T r e e P t r ( T 0022740 r e e , l v C u r P t r ) \r 0022760 \r \t l e t C u r P a g e = 0023000 T r e e > > T R E E . R o o t P 0023020 a g e \r \t w h i l e C u r P a 0023040 g e n e E m p t y d o \r \r 0023060 \t \t [ P a t h S t k T o p = 0023100 P a t h S t k T o p + 1 \r \t \t 0023120 S P = S P + s i z e P 0023140 S E / 376 001 \0 o c 1 6 \r \t \t S P > 0023160 > P S E . P a g e N o = C u 0023200 r P a g e \r \r \t \t C u r P t r 0023220 = 0 \r \t \t C u r P t r = R 0023240 e a d B T r e e P a g e ( T r e 0023260 e , C u r P a g e ) \r \r \t \t l 0023300 e t f i r s t G r = B i n 0023320 S e a r c h P a g e ( T r e e , 0023340 C u r P t r , o f f s e t T 0023360 a b l e , C K R , K e y ) \r 0023400 \t \t S P > > P S E . O f f s e t 0023420 = o f f s e t T a b l e ! f 0023440 i r s t G r \r \t \t S P > > P S E 0023460 . L a s t O f f s e t = o f 0023500 f s e t T a b l e ! ( f i r s t 0023520 G r - 1 ) \r \t \t S P > > P S E . 0023540 N e x t T o L a 376 001 \0 h 237 s t O 0023560 f f s e t = o f f s e t T a 0023600 b l e ! ( f i r s t G r - 2 ) \r 0023620 \t \t S P > > P S E . L e a s t S 0023640 o n = C u r P t r > > B T P 0023660 . M i n P t r \r \t \t i f f i r 0023700 s t G r g r 2 t h e n P 0023720 a t h S t k > > P S . P a t h S 0023740 t k T o p = P a t h S t k T 0023760 o p \r \r \t \t S P > > P S E . E S 0024000 L F r o n t = 0 \r \t \t S P > 0024020 > P S E . E S L R e a r = 0 0024040 \r \r \t \t C u r P a g e = ( C 0024060 u r P t r + ( S P > > P S E . L 0024100 a s t O f f s e t ) ) > > B T E 0024120 . G r P t r \r \t \t ] \r \r \t U n l 0024140 o c k B T r e e P t r ( T 376 001 \0 0024160 K 231 r e e , l v C u r P t r 0024200 ) \r \t F r e e ( T r e e > > T R 0024220 E E . Z o n e , o f f s e t T 0024240 a b l e ) \r \t r e s u l t i s 0024260 P a t h S t k T o p \r \t ] \r \r \r 0024300 a n d B i n S e a r c h P a g 0024320 e ( T r e e , c u r P t r , 0024340 o f f s e t T a b l e , C K R 0024360 , K e y ) = v a l o f \r \r 0024400 / / \t R e t u r n s a n i n 0024420 d e x r s u c h t h a t 0024440 o f f s e t T a b l e ! r i s 0024460 t h e o f f s e t o f \r / 0024500 / \t t h e f i r s t r e c o 0024520 r d s t r i c t l y g r e a 0024540 t e r t h a n K e y , a n 0024560 d 376 001 \0 s \ f i l l s i n \r 0024600 / / \t o f f s e t T a b l e ! 2 0024620 t h r o u g h o f f s e t T 0024640 a b l e ! r w i t h t h e 0024660 o f f s e t s o f \r / / \t a l 0024700 l r e c o r d s u p t o 0024720 a n d i n c l u d i n g t h 0024740 a t o n e . \r \r \t [ l e t 0024760 L R = T r e e > > T R E E . 0025000 L e n g t h R t n \r \t l e t f 0025020 i r s t B a d O f f s e t = 0025040 T r e e > > T R E E . P a g e L 0025060 e n g t h - c u r P t r > > B T 0025100 P . F r e e W o r d s \r \t l e t 0025120 m i d O f f s e t = f i r 0025140 s t B a d O f f s e t r s h i 0025160 f t 1 \r \t l 376 001 \0 240 ; e t c 0025200 u r O f f s e t = R e c 1 O 0025220 f f s e t \r \t l e t l = 2 0025240 \r \t l e t r = 2 \r \r / / \t 0025260 S c a n r e c o r d s l i n 0025300 e a r l y a n d b u i l d 0025320 o f f s e t T a b l e u n t i 0025340 l h a l f t h e i n - u s 0025360 e \r / / \t p o r t i o n o f 0025400 t h e B - T r e e p a g e 0025420 h a s b e e n e x a m i n e 0025440 d . T h e n d o o n e \r 0025460 / / \t k e y c o m p a r i s o 0025500 n t o d e t e r m i n e w 0025520 h i c h h a l f o f t h e 0025540 p a g e t o d i r e c t 0025560 o u r \r / / \t a t t e n 376 001 \0 d 0025600 230 t i o n t o , a n d b u 0025620 i l d t h e r e s t o f 0025640 o f f s e t T a b l e o n l y 0025660 i f n e c e s s a r y . \r / 0025700 / \t O n t h e a v e r a g e 0025720 t h i s s a v e s 2 5 % 0025740 o f t h e w o r k o f b 0025760 u i l d i n g o f f s e t T a 0026000 b l e s , \r / / \t a n d c o s 0026020 t s n o e x t r a c o m p 0026040 a r i s o n s s i n c e t h 0026060 e f i r s t c o m p a r i s 0026100 o n w o u l d \r / / \t e x a m 0026120 i n e a m i d d l e r e c 0026140 o r d a n y w a y ( n o t 0026160 n e c e s s a r i l y t h e 0026200 s 376 001 \0 340 ; a m e o n e ) . \r 0026220 \r \t [ / / r e p e a t \r \t i 0026240 f c u r O f f s e t g e m 0026260 i d O f f s e t t h e n \r \t \t 0026300 [ \r \t \t i f c u r O f f s e t 0026320 g e f i r s t B a d O f f s 0026340 e t % \r \t \t C K R ( K e y , 0026360 l v ( c u r P t r + c u r O 0026400 f f s e t ) > > B T E . R e c o 0026420 r d ) l s 0 t h e n \r \t \t 0026440 \t b r e a k \r \t \t m i d O f f s 0026460 e t = f i r s t B a d O f f 0026500 s e t \r \t \t l = r \r \t \t ] \r 0026520 \r \t c u r O f f s e t = c u 0026540 r O f f s e t + o f f s e t 0026560 B T E . R e c o r d / 1 6 \r \t 0026600 c u r O f f 376 001 \0 227 367 s e t = 0026620 c u r O f f s e t + L R ( 0026640 c u r P t r + c u r O f f s e t 0026660 ) \r \t r = r + 1 \r \t o f 0026700 f s e t T a b l e ! r = c u 0026720 r O f f s e t \r \t ] r e p e a 0026740 t \r \r / / \t A t t h i s p o 0026760 i n t , o f f s e t T a b l e 0027000 ! r i s t h e o f f s e t 0027020 o f t h e f i r s t n o 0027040 n - r e c o r d , \r / / \t w h i 0027060 c h w e a s s u m e t o 0027100 h a v e a n i n f i n i t e 0027120 k e y ( t h a t w e s h 0027140 a l l n e v e r t e s t ) . 0027160 \r / / \t W e s h a l l l e a 0027200 v e r p o i n t i 376 001 \0 353 034 0027220 n g a t t h e o f f s e t 0027240 o f t h e f i r s t r e 0027260 c o r d w h o s e \r / / \t k e 0027300 y i s g r e a t e r t h a 0027320 n K e y . \r \r \t w h i l e l 0027340 l s r d o \r \t \t [ l e t 0027360 m = ( l + r ) r s h i f 0027400 t 1 \r \t \t s w i t c h o n C 0027420 K R ( K e y , l v ( c u r P 0027440 t r + o f f s e t T a b l e ! m 0027460 ) > > B T E . R e c o r d ) i 0027500 n t o \r \t \t \t [ \r \t \t \t c a s e 0027520 1 : l = m + 1 ; l o o 0027540 p \t / / K e y > r e c o r 0027560 d \r \t \t \t c a s e 0 : r e s 0027600 u l t i s m + 1 \t / / K e y 0027620 376 001 \0 263 320 = r e c o r d \r \t 0027640 \t \t c a s e - 1 : r = m 0027660 ; l o o p \t / / K e y < 0027700 r e c o r d \r \t \t \t ] \r \t \t ] \r 0027720 \r \t r e s u l t i s r \r \t ] \r 0027740 \r \r a n d G e t R e c o r d ( 0027760 T r e e , P a t h S t k , d 0030000 o n t C o p y ) = v a l o f 0030020 \r \r \t [ l e t P a t h S t k 0030040 T o p = P a t h S t k > > P 0030060 S . P a t h S t k T o p \r \r \t i 0030100 f P a t h S t k T o p e q 0030120 0 t h e n r e s u l t i s 0030140 E m p t y \r \r \t l e t S P = 0030160 l v ( P a t h S t k > > P S 0030200 . P S E ^ P a t h S t k T o p ) 0030220 \r \t l e t 376 001 \0 f 313 P a g e P 0030240 t r = 0 \r \t R e a d S t a c 0030260 k A n d L o c k B T r e e P t r 0030300 ( T r e e , P a t h S t k , 0030320 l v P a g e P t r ) \r \t l e t 0030340 B e s t R e c P t r = l v 0030360 ( ( P a g e P t r + S P > > P 0030400 S E . L a s t O f f s e t ) > > 0030420 \r \t \t \t \t B T E . R e c o r d ) 0030440 \r \r \t u n l e s s d o n t C o 0030460 p y d o \r \t \t [ l e t B e 0030500 s t R e c L e n = ( T r e e 0030520 > > T R E E . L e n g t h R t n 0030540 ) ( B e s t R e c P t r ) \r \t \t 0030560 l e t B e s t R e c = A l 0030600 l o c a t e ( T r e e > > T R E 0030620 E . Z o n e , B e 376 001 \0 z d s 0030640 t R e c L e n ) \r \t \t M o v e B 0030660 l o c k ( B e s t R e c , B e 0030700 s t R e c P t r , B e s t R e 0030720 c L e n ) \r \t \t B e s t R e c P 0030740 t r = B e s t R e c \r \t \t ] 0030760 \r \r \t U n l o c k B T r e e P t 0031000 r ( T r e e , l v P a g e P 0031020 t r ) \r \r \t r e s u l t i s B 0031040 e s t R e c P t r \t / / r e c 0031060 i p i e n t r e s p o n s i b 0031100 l e f o r l o c k i n g \r \t 0031120 ] \r \r \r a n d B a c k U p O n 0031140 e R e c o r d ( T r e e , P a 0031160 t h S t k E n t ) b e \r \r \t [ 0031200 R e p a i r O f f s e t s ( T 0031220 r e e , P a t h S t k E n t 376 0031240 001 \0 e q ) \r \t P a t h S t k E n 0031260 t > > P S E . O f f s e t = 0031300 P a t h S t k E n t > > P S E . 0031320 L a s t O f f s e t \r \t R e p a 0031340 i r O f f s e t s ( T r e e , 0031360 P a t h S t k E n t ) \r \t ] \r \r 0031400 \r a n d R e p a i r O f f s e 0031420 t s ( T r e e , P a t h S t k 0031440 E n t ) b e \r \r \t [ l e t 0031460 P t r = n i l \r \t R e a d P 0031500 a g e A n d L o c k B T r e e P 0031520 t r ( T r e e , P a t h S t k 0031540 E n t > > P S E . P a g e N o , 0031560 l v P t r ) \r \t l e t O f 0031600 f s e t = P a t h S t k E n 0031620 t > > P S E . O f f s e t \r \t l 0031640 e t L 376 001 \0 & E a s t O f f s 0031660 e t = P a t h S t k E n t > 0031700 > P S E . L a s t O f f s e t \r 0031720 \t l e t N e x t T o L a s t O 0031740 f f s e t = P a t h S t k E 0031760 n t > > P S E . N e x t T o L a 0032000 s t O f f s e t \r \r \t u n l e s 0032020 s C h e c k P r o g r e s s i 0032040 o n ( T r e e , P t r , L a 0032060 s t O f f s e t , O f f s e t 0032100 ) & \r \t \t C h e c k P r o g r 0032120 e s s i o n ( T r e e , P t r 0032140 , N e x t T o L a s t O f f s 0032160 e t , L a s t O f f s e t ) 0032200 d o \r \r \t \t [ l e t n e w O 0032220 f f s e t = R e c 1 O f f s 0032240 e t \r \t \t L a s t 376 001 \0 034 367 O f 0032260 f s e t = R e c 0 O f f s e 0032300 t \r \t \t N e x t T o L a s t O f 0032320 f s e t = E m p t y \r \r \t \t 0032340 w h i l e n e w O f f s e t 0032360 n e O f f s e t d o \r \t \t \t 0032400 [ N e x t T o L a s t O f f s 0032420 e t = L a s t O f f s e t \r 0032440 \t \t \t L a s t O f f s e t = 0032460 n e w O f f s e t \r \t \t \t n e w 0032500 O f f s e t = n e w O f f s 0032520 e t + \r \t \t \t \t ( o f f s e t 0032540 B T E . R e c o r d / 1 6 ) + \r 0032560 \t \t \t \t ( T r e e > > T R E E . 0032600 L e n g t h R t n ) ( l v ( ( 0032620 P t r + n e w O f f s e t ) > > 0032640 \r \t \t \t \t \t B T E . R e c o 376 001 0032660 \0 301 243 r d ) ) \r \t \t \t ] \r \r \t \t 0032700 P a t h S t k E n t > > P S E . 0032720 L a s t O f f s e t = L a s 0032740 t O f f s e t \r \t \t P a t h S t 0032760 k E n t > > P S E . N e x t T o 0033000 L a s t O f f s e t = N e x 0033020 t T o L a s t O f f s e t \r \t \t 0033040 ] \r \r \t U n l o c k B T r e e P 0033060 t r ( T r e e , l v P t r ) 0033100 \r \t ] \r \r \r a n d C h e c k P 0033120 r o g r e s s i o n ( T r e e , 0033140 P t r , O f f s e t 1 , O 0033160 f f s e t 2 ) = \r \r \t s e l 0033200 e c t o n O f f s e t 2 i n 0033220 t o \r \t \t [ c a s e R e c 0 0033240 O f f s e t : O f f s e t 1 0033260 e q 376 001 \0 o [ E m p t y \r \t \t 0033300 c a s e R e c 1 O f f s e t : 0033320 O f f s e t 1 e q R e c 0 0033340 O f f s e t \r \t \t d e f a u l t 0033360 : ( O f f s e t 1 g e O f 0033400 f s e t 2 ) ? f a l s e , \r \t 0033420 \t \t ( O f f s e t 1 + ( o f f s 0033440 e t B T E . R e c o r d / 1 6 0033460 ) + \r \t \t \t ( T r e e > > T R E 0033500 E . L e n g t h R t n ) ( \r \t \t 0033520 \t l v ( P t r + O f f s e t 0033540 1 ) > > B T E . R e c o r d ) ) 0033560 \r \t \t \t e q O f f s e t 2 \r \t 0033600 \t ] \r \r \r a n d R e a d S t a 0033620 c k ( T r e e , P a t h S t k 0033640 ) = \r \t R e a d B T r e e P a 0033660 g e ( T r e e , 376 001 \0 331 005 \r \t \t 0033700 P a t h S t k > > P S . P S E ^ 0033720 ( P a t h S t k > > P S . P a t 0033740 h S t k T o p ) . P a g e N o ) 0033760 \r \r \r a n d R e a d P a g e A 0034000 n d L o c k B T r e e P t r ( T 0034020 r e e , p a g e N o , p P t 0034040 r ) b e \r \r \t [ @ p P t r 0034060 = R e a d B T r e e P a g e ( 0034100 T r e e , p a g e N o ) \r \t L 0034120 o c k B T r e e P t r ( T r e e 0034140 , p P t r ) \r \t ] \r \r \r a n d 0034160 R e a d S t a c k A n d L o c 0034200 k B T r e e P t r ( T r e e , 0034220 P a t h S t k , p P t r ) b 0034240 e \r \r \t [ @ p P t r = R e 0034260 a d S t a c k ( T r e e , 376 \0 v 0034300 253 p P a t h S t k ) \r \t L o c 0034320 k B T r e e P t r ( T r e e , 0034340 p P t r ) \r \t ] \r \r \r a n d P 0034360 o p S t a c k ( P a t h S t k ) 0034400 b e \r \r \t P a t h S t k > > P 0034420 S . P a t h S t k T o p = P 0034440 a t h S t k > > P S . P a t h S 0034460 t k T o p - 1 \r 377 \0 \0 B T r e e 0034500 W r t M S 0 . b c p l \0 373 231 005 300 0034520 365 \0 \0 376 001 \0 324 353 / / \t B - T r e 0034540 e M a i n t e n a n c e R o 0034560 u t i n e s \r / / C o p y r i 0034600 g h t X e r o x C o r p o r 0034620 a t i o n 1 9 7 9 , 1 9 8 0 0034640 , 1 9 8 1 , 1 9 8 2 \r \r \r / 0034660 / \t B T r e e W r t M S 0 . b c 0034700 p l - - R o u t i n e s 0034720 f o r w r i t i n g i n B 0034740 - T r e e s \r / / \t \t U s e s 0034760 p a g i n a t i o n s t r a t 0035000 e g y M S t o m i n i m i 0035020 z e t h e s u m o f l e 0035040 n g t h s \r / / \t \t o f r e c 0035060 o r d s p o s t e d t o t 0035100 h e f a t h e r p a g e . \r 0035120 \r / / \t l a s t 376 001 \0 316 317 e d 0035140 i t e d M a y 9 , 1 9 8 2 0035160 5 : 2 4 P M b y T a f 0035200 t \r \r g e t " b t r e e . d e 0035220 c l " \r \r \r e x t e r n a l \r \t 0035240 [ A l l o c a t e \t / / D e 0035260 f i n e d b y O S \r \t F r e 0035300 e \r \t M o v e B l o c k \r \t D e 0035320 f a u l t A r g s \r \t D v e c \r 0035340 \r \t R e a d B T r e e P a g e \t 0035360 / / d e f i n e d b y O p 0035400 e n B T r e e \r \t W r i t e B T 0035420 r e e P a g e \r \t L o c k B T r 0035440 e e P t r \r \t U n l o c k B T r 0035460 e e P t r \r \t B T r e e B u g \r 0035500 \r \t P a t h R e c L E \t \t / / 0035520 D e f i n e d i n B T 376 001 \0 0035540 275 324 r e e R e a d . b c p l \r \t 0035560 B a c k U p O n e R e c o r d \r 0035600 \t P o p S t a c k \r \t R e a d S 0035620 t a c k \r \t R e a d S t a c k A 0035640 n d L o c k B T r e e P t r \r \t 0035660 G e t R e c o r d \r \t ] \r \r \r e 0035700 x t e r n a l \r \t [ U p d a t 0035720 e R e c o r d \t / / D e f i n 0035740 e d i n B T r e e W r t M S 0035760 . b c p l \r \t I n s e r t R e c 0036000 o r d s \r \t C o m p l e x I n s 0036020 e r t R e c o r d s \r \t H a i r 0036040 y I n s e r t R e c o r d s \r \t 0036060 M a k e N e w R o o t \r \t P a g 0036100 e L e n g t h \r \t E n t r y L e 0036120 n g t h \r \t F i l l L e f t P a 0036140 g e 376 001 \0 357 226 \r \t F i l l R i g 0036160 h t P a g e \r \t A p p e n d E n 0036200 t S e q E n t \r \t P u s h E n t 0036220 S e q E n t \r \t M a k e E n t S 0036240 e q E n t \r \t C o m p u t e E n 0036260 t L e n s \r \t P u s h E n t S e 0036300 q E n t L e n s \r \t A p p e n d 0036320 E n t S e q E n t L e n s \r \t D 0036340 e p o s i t E S L \r \t F i n d R 0036360 i g h t B r o t h e r \r \t F i n 0036400 d L e f t B r o t h e r \r \t R e 0036420 m o v e E n t r y \r \t W r i t e 0036440 R i g h t B r o t h e r \r \t W r 0036460 i t e P a g e \r \t A d d T o H e 0036500 a p \r \t T r i c k l e D o w n \r 0036520 \t R e m o v e F r o m H e a p \r 0036540 \t S i f t U p 376 001 \0 247 201 \r \t F a 0036560 b r i c a t e I S \r \t F r e e I 0036600 S \r \t ] \r \r \r l e t U p d a t 0036620 e R e c o r d ( T r e e , K e 0036640 y , R e c o r d G e n e r a t 0036660 o r , P a r a m , C K R , 0036700 P a t h S t k , U s e E x i s 0036720 t i n g P a t h ; \r \t n u m a r 0036740 g s n a ) b e \r \r \t [ D e 0036760 f a u l t A r g s ( l v n a , 0037000 - 3 , 0 , T r e e > > T R 0037020 E E . C o m p a r e K e y R t n 0037040 , s i z e P S / 1 6 , f a 0037060 l s e ) \r \t i f P a t h S t k 0037100 e q s i z e P S / 1 6 t 0037120 h e n \r \t \t [ D v e c ( U p d 0037140 a t e R e c o r d , l 376 001 \0 246 0037160 303 v P a t h S t k ) ; U s e 0037200 E x i s t i n g P a t h = f 0037220 a l s e ] \r \r \t l e t L R 0037240 = T r e e > > T R E E . L e n 0037260 g t h R t n \r \t l e t Z o n e 0037300 = T r e e > > T R E E . Z o 0037320 n e \r \r \t l e t O r i g S T 0037340 = P a t h R e c L E ( T r e e 0037360 , P a t h S t k , U s e E x 0037400 i s t i n g P a t h , K e y , 0037420 C K R ) \r \r \t l e t F o u n 0037440 d R e c o r d = E m p t y \r 0037460 \t l e t F o u n d R e c L e n 0037500 = n i l \r \t i f P a t h S 0037520 t k > > P S . P a t h S t k T o 0037540 p g e 1 t h e n \r \t \t [ 0037560 F 376 001 \0 317 _ o u n d R e c o r d 0037600 = G e t R e c o r d ( T r e 0037620 e , P a t h S t k , f a l s 0037640 e ) \r \t \t F o u n d R e c L e n 0037660 = L R ( F o u n d R e c o r 0037700 d ) \r \t \t u n l e s s C K R ( 0037720 K e y , F o u n d R e c o r d 0037740 ) e q 0 d o \r \t \t \t [ F 0037760 r e e ( Z o n e , F o u n d R 0040000 e c o r d ) ; F o u n d R e c 0040020 o r d = E m p t y ] \r \t \t 0040040 ] \r \r \t l e t R e c o r d = 0040060 R e c o r d G e n e r a t o r 0040100 ( F o u n d R e c o r d , P a 0040120 r a m ) \r \t l e t R e c L e n 0040140 = L R ( R e c o r d ) \r \r \t 0040160 u n l e s s 376 001 \0 003 D C K R ( 0040200 K e y , R e c o r d ) e q 0040220 0 d o \r \t \t B T r e e B u g ( 0040240 T r e e , e c R e c G e n R e 0040260 t u r n e d W r o n g K e y ) \r 0040300 \r \t / / T h i s u p d a t e 0040320 m a y c h a n g e t h e 0040340 t r e e i n w a y s t h a 0040360 t i n v a l i d a t e a n y 0040400 \r \t / / e x i s t i n g P a 0040420 t h S t k . \r \t T r e e > > T R 0040440 E E . V e r s i o n = T r e 0040460 e > > T R E E . V e r s i o n + 0040500 1 \r \r \t / / T o m i n i m i 0040520 z e a v e r a g e i n s e r 0040540 t i o n t i m e , p e r f o 0040560 r m t h e u p d a 376 001 \0 \a 3 0040600 t e i n o n e o f \r \t / / 0040620 t h r e e w a y s ( i n 0040640 i n c r e a s i n g o r d e r 0040660 o f d i f f i c u l t y , 0040700 a s m e a s u r e d b y a 0040720 m o u n t \r \t / / o f t e m 0040740 p o r a r y s t o r a g e a 0040760 l l o c a t e d a n d a m o 0041000 u n t o f d a t a c o p i 0041020 e d ) : \r \t / / ( 1 ) I f 0041040 r e p l a c i n g a n e x i 0041060 s t i n g r e c o r d o f 0041100 t h e s a m e s i z e , j 0041120 u s t o v e r w r i t e i t 0041140 . \r \t / / ( 2 ) I f t h e 0041160 n e w r e c o r d f i t s 0041200 376 001 \0 315 i o n t h e p a g 0041220 e ( a f t e r r e m o v i n 0041240 g t h e o l d r e c o r d 0041260 \r \t / / i f a n y ) 0041300 , j u s t s l i d e u p 0041320 t h e r e c o r d s b e y o 0041340 n d t h e i n s e r t i o n 0041360 p o i n t a n d \r \t / / 0041400 i n s e r t t h e n e 0041420 w r e c o r d . \r \t / / ( 3 0041440 ) O t h e r w i s e , l e a 0041460 v e t h e n e w r e c o r 0041500 d a s a n E S E a t t 0041520 h e a p p r o p r i a t e \r \t 0041540 / / s t a c k l e v 0041560 e l , a n d l e t I n s e 0041600 r t R e c 376 001 \0 241 231 o r d s c 0041620 o p e w i t h t h e p r o 0041640 b l e m . \r \r \t l e t P S E 0041660 = l v ( P a t h S t k > > P 0041700 S . P S E ^ ( P a t h S t k > > 0041720 P S . P a t h S t k T o p ) ) \r 0041740 \t i f F o u n d R e c o r d 0041760 n e E m p t y & R e c L e 0042000 n e q F o u n d R e c L e n 0042020 t h e n \r \t \t [ / / N e w 0042040 r e c o r d s a m e l e n 0042060 g t h a s o l d , j u s t 0042100 c o p y i t o v e r \r \t \t 0042120 l e t P a g e P t r = W r 0042140 i t e B T r e e P a g e ( T r e 0042160 e , P S E > > P S E . P a g e 0042200 N o ) \r \t \t L o c k 376 001 \0 273 360 B 0042220 T r e e P t r ( T r e e , l v 0042240 P a g e P t r ) \r \t \t M o v e 0042260 B l o c k ( l v ( P a g e P t 0042300 r + P S E > > P S E . L a s t O 0042320 f f s e t ) > > B T E . R e c o 0042340 r d , \r \t \t \t R e c o r d , R 0042360 e c L e n ) \r \t \t U n l o c k B 0042400 T r e e P t r ( T r e e , l v 0042420 P a g e P t r ) \r \t \t F r e e 0042440 ( Z o n e , R e c o r d ) \r \t 0042460 \t r e t u r n \r \t \t ] \r \r \t l e 0042500 t O l d R e c G r P t r = 0042520 E m p t y \r \t t e s t F o u n 0042540 d R e c o r d e q E m p t y 0042560 \r \t i f s o \t [ P a t h S t k 0042600 > > P S . P a t h S t k T o p 376 0042620 001 \0 341 [ = O r i g S T \r \t \t 0042640 P S E = l v ( P a t h S t 0042660 k > > P S . P S E ^ ( P a t h S 0042700 t k > > P S . P a t h S t k T o 0042720 p ) ) \r \t \t T r e e > > T R E E 0042740 . R e c o r d C o u n t = T 0042760 r e e > > T R E E . R e c o r d 0043000 C o u n t + 1 \r \t \t T r e e > > 0043020 T R E E . S t a t e D i r t y 0043040 = t r u e \r \t \t ] \r \r \t i f n 0043060 o t \t [ B a c k U p O n e R e 0043100 c o r d ( T r e e , P S E ) \r 0043120 \t \t F r e e ( Z o n e , R e m 0043140 o v e E n t r y ( T r e e , P 0043160 S E , l v O l d R e c G r P 0043200 t r ) ) \r \t \t ] \r \r \r \t l e t 0043220 E n t L 376 001 \0 311 331 e n = R e 0043240 c L e n + ( o f f s e t B T E 0043260 . R e c o r d / 1 6 ) \r \r \t i f 0043300 E n t L e n l e R e a d S 0043320 t a c k ( T r e e , P a t h S 0043340 t k ) > > B T P . F r e e W o r 0043360 d s t h e n \r \t \t [ / / N 0043400 e w r e c o r d f i t s o 0043420 n t h e p a g e - - i n 0043440 s e r t i t t h e e a s y 0043460 w a y \r \t \t l e t P a g e P 0043500 t r = W r i t e B T r e e P 0043520 a g e ( T r e e , P S E > > P 0043540 S E . P a g e N o ) \r \t \t L o c 0043560 k B T r e e P t r ( T r e e , 0043600 l v P a g e P t r ) \r \t \t l e 0043620 t N e w E n t 376 001 \0 % 254 = 0043640 P a g e P t r + P S E > > P 0043660 S E . O f f s e t \r \t \t l e t 0043700 F r e e E n t = P a g e P t 0043720 r + T r e e > > T R E E . P 0043740 a g e L e n g t h - \r \t \t \t P 0043760 a g e P t r > > B T P . F r e e 0044000 W o r d s \r \t \t w h i l e F r 0044020 e e E n t g r N e w E n t 0044040 d o \r \t \t \t [ / / s l i d e 0044060 u p i n c h u n k s - - 0044100 M o v e B l o c k g o e s 0044120 t h e w r o n g w a y \r \t \t 0044140 \t M o v e B l o c k ( F r e e E 0044160 n t , F r e e E n t - E n t L 0044200 e n , E n t L e n ) \r \t \t \t F 0044220 r e e E n t = F r e e E 376 001 0044240 \0 342 215 n t - E n t L e n \r \t 0044260 \t \t ] \r \t \t M o v e B l o c k ( 0044300 l v N e w E n t > > B T E . R 0044320 e c o r d , R e c o r d , R 0044340 e c L e n ) \r \t \t N e w E n t > 0044360 > B T E . G r P t r = O l d 0044400 R e c G r P t r \r \t \t P a g e P 0044420 t r > > B T P . F r e e W o r d 0044440 s = P a g e P t r > > B T P 0044460 . F r e e W o r d s - E n t 0044500 L e n \r \t \t U n l o c k B T r e 0044520 e P t r ( T r e e , l v P a 0044540 g e P t r ) \r \t \t F r e e ( Z o 0044560 n e , R e c o r d ) \r \t \t r e 0044600 t u r n \r \t \t ] \r \r \t l e t R 0044620 e c P t r = A l l o c a t e 0044640 ( Z o 376 001 \0 , 274 n e , E n t L 0044660 e n ) \r \t M o v e B l o c k ( l 0044700 v ( R e c P t r > > B T E . R 0044720 e c o r d ) , R e c o r d , 0044740 R e c L e n ) \r \t R e c P t r > 0044760 > B T E . G r P t r = O l d 0045000 R e c G r P t r \r \t F r e e ( Z 0045020 o n e , R e c o r d ) \r \t A p 0045040 p e n d E n t S e q E n t ( P S 0045060 E , M a k e E n t S e q E n t 0045100 ( Z o n e , R e c P t r , E 0045120 n t L e n ) ) \r \r \t F r e e ( Z 0045140 o n e , R e c P t r ) \r \r \t l 0045160 e t I S = F a b r i c a t 0045200 e I S ( T r e e , P a t h S t 0045220 k ) \r \r \t w h i l e ( P a t h 0045240 S t k > > P S . 376 001 \0 - 247 P a t 0045260 h S t k T o p g e 0 ) & \r 0045300 \t \t ( P a t h S t k > > P S . P 0045320 S E ^ ( P a t h S t k > > P S . 0045340 P a t h S t k T o p ) . E S L F 0045360 r o n t \r \t \t \t n e E m p t y 0045400 ) d o \r \t \t [ I n s e r t R 0045420 e c o r d s ( T r e e , P a t 0045440 h S t k , I S ) \r \t \t P o p S 0045460 t a c k ( P a t h S t k ) \r \t \t 0045500 ] \r \r \t F r e e I S ( I S ) \r \t 0045520 ] \r \r \r a n d M a k e E n t S 0045540 e q E n t ( Z o n e , E n t S 0045560 e q , L e n g t h ) = v a 0045600 l o f \r \r \t [ l e t E = 0045620 A l l o c a t e ( Z o n e , ( 0045640 o f f s e t E S L E . E 376 001 \0 0045660 224 252 n t S e q / 1 6 ) + L e n g 0045700 t h ) \r \t E > > E S L E . E n t 0045720 S e q P = l v E > > E S L 0045740 E . E n t S e q \r \t E > > E S L 0045760 E . E n t S e q L e n = L e 0046000 n g t h \r \t M o v e B l o c k ( 0046020 l v E > > E S L E . E n t S e 0046040 q , E n t S e q , L e n g t 0046060 h ) \r \t r e s u l t i s E \r \t 0046100 ] \r \r \r a n d A p p e n d E n 0046120 t S e q E n t ( P a t h S t k E 0046140 n t r y , E n t r y ) b e \r 0046160 \r \t [ E n t r y > > E S L E . 0046200 F w d P = E m p t y \r \r \t t 0046220 e s t P a t h S t k E n t r y 0046240 > > P S E . E S L R e a r e q 0046260 E 376 001 \0 \a 364 m p t y \r \t i f s 0046300 o \t P a t h S t k E n t r y > > 0046320 P S E . E S L F r o n t = E 0046340 n t r y \r \t i f n o t \t ( P a t 0046360 h S t k E n t r y > > P S E . E 0046400 S L R e a r ) > > E S L E . F w 0046420 d P = E n t r y \r \r \t P a t 0046440 h S t k E n t r y > > P S E . E 0046460 S L R e a r = E n t r y \r \t 0046500 ] \r \r \r a n d F a b r i c a t 0046520 e I S ( T r e e , P a t h S t 0046540 k ) = v a l o f \r \r \t [ l 0046560 e t Z o n e = T r e e > > 0046600 T R E E . Z o n e \r \t l e t I 0046620 S = A l l o c a t e ( Z o n 0046640 e , s i z e I S / 1 6 ) \r \t 0046660 I S > > I S . 376 001 \0 006 250 T r e e 0046700 = T r e e \r \r \t l e t M a 0046720 x F r e e W o r d s = T r e 0046740 e > > T R E E . P a g e L e n g 0046760 t h - P a g e O v e r h e a d \r 0047000 \t I S > > I S . M a x F r e e W 0047020 o r d s = M a x F r e e W o 0047040 r d s \r \t I S > > I S . A w f u 0047060 l l y F u l l = ( 9 * M a x 0047100 F r e e W o r d s ) / 1 0 \r \t I 0047120 S > > I S . P r e t t y F u l l 0047140 = ( 2 * M a x F r e e W o r 0047160 d s ) / 3 \r \t I S > > I S . F a 0047200 i r l y F u l l = M a x F r 0047220 e e W o r d s / 2 \r \t I S > > I 0047240 S . B r e a t h i n g S p a c e 0047260 = M a x F r e e W o 376 001 \0 006 0047300 C r d s - I S > > I S . A w f u 0047320 l l y F u l l \r \r \t I S > > I S 0047340 . P a t h S t k = P a t h S 0047360 t k \r \t I S > > I S . H e a p P 0047400 t r = A l l o c a t e ( Z o 0047420 n e , s i z e H P / 1 6 ) \r 0047440 \t I S > > I S . E L L P t r = 0047460 A l l o c a t e ( Z o n e , 0047500 s i z e E L L / 1 6 ) \r \t r e 0047520 s u l t i s I S \r \t ] \r \r \r a 0047540 n d F r e e I S ( I S ) b e 0047560 \r \r \t [ l e t Z o n e = 0047600 ( I S > > I S . T r e e ) > > T 0047620 R E E . Z o n e \r \t F r e e ( Z 0047640 o n e , I S > > I S . H e a p 0047660 P t r ) \r \t F r e e ( Z o n e , 0047700 376 001 \0 334 : I S > > I S . E L L 0047720 P t r ) \r \t F r e e ( Z o n e , 0047740 I S ) \r \t ] \r \f \r a n d I n 0047760 s e r t R e c o r d s ( T r e e 0050000 , P a t h S t k , I S ) b 0050020 e \r \r \t [ l e t P a t h S t 0050040 k T o p = P a t h S t k > > 0050060 P S . P a t h S t k T o p \r \t l 0050100 e t S P = l v P a t h S 0050120 t k > > P S . P S E ^ P a t h S 0050140 t k T o p \r \t i f S P > > P S 0050160 E . E S L F r o n t e q E m 0050200 p t y t h e n r e t u r n \r 0050220 \r \t l e t Z o n e = T r e 0050240 e > > T R E E . Z o n e \r \r \t C 0050260 o m p u t e E n t L e n s ( I S 0050300 , S P ) \r 376 001 \0 235 a \r \t i f 0050320 P a t h S t k T o p l e 0 0050340 t h e n \r \r \t \t [ M a k e N e 0050360 w R o o t ( I S , S P , T r 0050400 e e ) \r \t \t r e t u r n \r \t \t ] 0050420 \r \r \t l e t C u r P t r = 0050440 W r i t e B T r e e P a g e ( T 0050460 r e e , S P > > P S E . P a g 0050500 e N o ) \r \t L o c k B T r e e P 0050520 t r ( T r e e , l v C u r P 0050540 t r ) \r \r \t l e t F r e e W o 0050560 r d s = C u r P t r > > B T 0050600 P . F r e e W o r d s \r \t l e t 0050620 O f f s e t = S P > > P S 0050640 E . O f f s e t \r \t l e t T a 0050660 i l B l k P t r = C u r P t 0050700 r + O f f s e t \r \t l 376 001 \0 253 260 0050720 e t T a i l B l k L e n = 0050740 ( I S > > I S . M a x F r e e W 0050760 o r d s - F r e e W o r d s ) - 0051000 \r \t \t ( O f f s e t - R e c 1 O 0051020 f f s e t ) \r \r \t l e t N e w 0051040 W o r d s = P a g e L e n g 0051060 t h ( I S , 0 ) \r \t i f N e 0051100 w W o r d s l e F r e e W o 0051120 r d s t h e n \r \r \t \t / / A 0051140 l l e n t r i e s f i t t 0051160 h e c u r r e n t p a g e . 0051200 H u r r a h ! \r \r \t \t [ l e 0051220 t T = A l l o c a t e ( Z 0051240 o n e , I S > > I S . M a x F 0051260 r e e W o r d s ) \r \t \t M o v e 0051300 B l o c k ( T , T a i l B l k 0051320 376 001 \0 < \b P t r , T a i l B l 0051340 k L e n ) \r \r \t \t u n l e s s 0051360 D e p o s i t E S L ( T r e e , 0051400 S P , T a i l B l k P t r , 0051420 \r \t \t \t \t N e w W o r d s ) 0051440 e q N e w W o r d s \r \t \t \t d 0051460 o B T r e e B u g ( T r e e , 0051500 e c D e p o s i t E S L W r o 0051520 n g ) \r \r \t \t M o v e B l o c k 0051540 ( T a i l B l k P t r + N e w W 0051560 o r d s , T , T a i l B l k 0051600 L e n ) \r \t \t F r e e ( Z o n e 0051620 , T ) \r \r \t \t C u r P t r > > 0051640 B T P . F r e e W o r d s = 0051660 F r e e W o r d s - N e w W o r 0051700 d s \r \t \t U n l o c k B T r e e 0051720 P t r ( T 376 001 \0 302 312 r e e , l 0051740 v C u r P t r ) \r \t \t r e t u 0051760 r n \r \t \t ] \r \r / / \t N o t a 0052000 l l t h e e n t r i e s w 0052020 i l l f i t o n t h e c 0052040 u r r e n t p a g e . T h i 0052060 s i s \r / / \t g e t t i n g 0052100 c o m p l e x . \r \r \t l e t L 0052120 e f t E S E n t = M a k e E 0052140 n t S e q E n t ( Z o n e , \r \t 0052160 \t C u r P t r + R e c 1 O f f 0052200 s e t , O f f s e t - R e c 1 0052220 O f f s e t ) \r \t P u s h E n t 0052240 S e q E n t ( S P , L e f t E 0052260 S E n t ) \r \t P u s h E n t S e 0052300 q E n t L e n s ( I S , L e f 0052320 t E S E n t ) \r \r \t 376 001 \0 301 226 l 0052340 e t R i g h t E S E n t = 0052360 M a k e E n t S e q E n t ( Z o 0052400 n e , T a i l B l k P t r , 0052420 T a i l B l k L e n ) \r \t A p p 0052440 e n d E n t S e q E n t ( S P , 0052460 R i g h t E S E n t ) \r \t A p 0052500 p e n d E n t S e q E n t L e n 0052520 s ( I S , R i g h t E S E n t 0052540 ) \r \r \t U n l o c k B T r e e P 0052560 t r ( T r e e , l v C u r P 0052600 t r ) \r \r \t l e t R t B r o P 0052620 g 1 = C o m p l e x I n s e 0052640 r t R e c o r d s ( T r e e , 0052660 P a t h S t k , I S ) \r \r \t i 0052700 f R t B r o P g 1 n e E m 0052720 p t y t h e n H a i r y I 376 0052740 001 \0 [ 204 n s e r t R e c o r d s 0052760 ( T r e e , P a t h S t k , 0053000 I S , \r \t \t R t B r o P g 1 ) \r 0053020 \t ] \r \r \r a n d C o m p u t e 0053040 E n t L e n s ( I S , P S E ) 0053060 b e \r \r \t [ I S > > I S . E 0053100 L L L e n = 0 \r \t ( I S > > 0053120 I S . E L L P t r ) > > E L L . 0053140 C u m E n t L e n ^ 0 = 0 \r 0053160 \t l e t N e x t T o S c a n 0053200 = P S E > > P S E . E S L F r 0053220 o n t \r \r \t w h i l e N e x t 0053240 T o S c a n n e E m p t y 0053260 d o \r \t \t [ A p p e n d E n t 0053300 S e q E n t L e n s ( I S , N 0053320 e x t T o S c a n ) \r \t \t N e x 0053340 t T o S 376 001 \0 357 ; c a n = N 0053360 e x t T o S c a n > > E S L E . 0053400 F w d P \r \t \t ] \r \t ] \r \r \r a n 0053420 d A p p e n d E n t S e q E n 0053440 t L e n s ( I S , E n t S e q 0053460 E n t ) b e \r \r \t [ l e t 0053500 L R = ( I S > > I S . T r e 0053520 e ) > > T R E E . L e n g t h R 0053540 t n \r \t l e t C u r S i z e 0053560 = I S > > I S . E L L L e n \r 0053600 \t l e t E n t L e n s = I 0053620 S > > I S . E L L P t r \r \r \t l 0053640 e t C u m L e n = E n t L 0053660 e n s > > E L L . C u m E n t L 0053700 e n ^ C u r S i z e \r \t l e t 0053720 W o r d s L e f t = E n t S 0053740 e q E n t > > E S 376 001 \0 367 243 L E 0053760 . E n t S e q L e n \r \t l e t 0054000 B T E n t r y = E n t S e q 0054020 E n t > > E S L E . E n t S e q 0054040 P \r \r \t w h i l e W o r d s L 0054060 e f t g r 0 d o \r \t \t [ 0054100 C u r S i z e = C u r S i z 0054120 e + 1 \r \r \t \t l e t L e n g t 0054140 h T h i s E n t r y = \r \t \t \t 0054160 ( o f f s e t B T E . R e c o 0054200 r d / 1 6 ) + \r \t \t \t L R ( B T 0054220 E n t r y + ( o f f s e t B T 0054240 E . R e c o r d / 1 6 ) ) \r \t \t 0054260 C u m L e n = C u m L e n + 0054300 L e n g t h T h i s E n t r y \r 0054320 \t \t E n t L e n s > > E L L . C 0054340 u m E n t L e n ^ C u r S i 376 001 0054360 \0 334 206 z e = C u m L e n \r \r 0054400 \t \t B T E n t r y = B T E n 0054420 t r y + L e n g t h T h i s E n 0054440 t r y \r \t \t W o r d s L e f t 0054460 = W o r d s L e f t - L e n g 0054500 t h T h i s E n t r y \r \t \t ] \r 0054520 \r \t I S > > I S . E L L L e n 0054540 = C u r S i z e \r \t ] \r \r \r a 0054560 n d P a g e L e n g t h ( I S 0054600 , L e f t F a t h e r , R i 0054620 g h t F a t h e r ; n u m a r 0054640 g s n a ) = v a l o f \r \r 0054660 \t [ i f n a l s 3 t h 0054700 e n R i g h t F a t h e r = 0054720 I S > > I S . E L L L e n + 1 0054740 \r \t l e t E n t L e n s = 0054760 I S > 376 001 \0 0 216 > I S . E L L P 0055000 t r \r \t r e s u l t i s ( E n 0055020 t L e n s > > E L L . C u m E n 0055040 t L e n ^ ( R i g h t F a t h e 0055060 r - 1 ) - \r \t \t E n t L e n s > 0055100 > E L L . C u m E n t L e n ^ L 0055120 e f t F a t h e r ) \r \t ] \r \r \r 0055140 a n d D e p o s i t E S L ( T 0055160 r e e , P S E , B l o c k , 0055200 L e n g t h ) = v a l o f 0055220 \r \r \t [ l e t L R = T r 0055240 e e > > T R E E . L e n g t h R 0055260 t n \r \r \t l e t O r i g L e n 0055300 g t h = L e n g t h \r \r \t w 0055320 h i l e P S E > > P S E . E S 0055340 L F r o n t n e E m p t y 0055360 d o \r \r \t \t [ 376 001 \0 S 033 l e t 0055400 E S L F r o n t = P S E > 0055420 > P S E . E S L F r o n t \r \t \t 0055440 l e t E S P = E S L F r o 0055460 n t > > E S L E . E n t S e q P 0055500 \r \t \t l e t E S L e n = E 0055520 S L F r o n t > > E S L E . E n 0055540 t S e q L e n \r \r \t \t t e s t 0055560 E S L e n l e L e n g t h \r 0055600 \r \t \t i f s o \t [ M o v e B l 0055620 o c k ( B l o c k , E S P , 0055640 E S L e n ) \r \t \t \t B l o c k 0055660 = B l o c k + E S L e n \r \t \t 0055700 \t L e n g t h = L e n g t h 0055720 - E S L e n \r \r \t \t \t P S E > > 0055740 P S E . E S L F r o n t = E 0055760 S L F r o n t > > E S L E 376 001 \0 0056000 f 022 . F w d P \r \t \t \t F r e e ( 0056020 T r e e > > T R E E . Z o n e , 0056040 E S L F r o n t ) \r \t \t \t ] \r 0056060 \r \t \t i f n o t \t [ l e t F 0056100 i r s t R e c P = l v ( E 0056120 S P > > B T E . R e c o r d ) \r 0056140 \t \t \t l e t F i r s t E n t L 0056160 e n = L R ( F i r s t R e c 0056200 P ) + \r \t \t \t \t \t ( o f f s e t 0056220 B T E . R e c o r d / 1 6 ) \r 0056240 \r \t \t \t t e s t F i r s t E n 0056260 t L e n l e L e n g t h \r \r 0056300 \t \t \t i f s o \t [ M o v e B l 0056320 o c k ( B l o c k , E S P , 0056340 F i r s t E n t L e n ) \r \t \t \t 0056360 \t B l o c k = B l o c k + F 0056400 i r 376 001 \0 375 U s t E n t L e n \r 0056420 \t \t \t \t L e n g t h = L e n 0056440 g t h - F i r s t E n t L e n \r 0056460 \r \t \t \t \t E S L F r o n t > > E 0056500 S L E . E n t S e q P = \r \t \t 0056520 \t \t \t E S P + F i r s t E n t L 0056540 e n \r \t \t \t \t E S L F r o n t > 0056560 > E S L E . E n t S e q L e n 0056600 = \r \t \t \t \t \t E S L e n - F i r 0056620 s t E n t L e n \r \t \t \t \t ] \r \r 0056640 \t \t \t i f n o t \t r e s u l t i 0056660 s O r i g L e n g t h - L e n 0056700 g t h \r \t \t \t ] \r \t \t ] \r \r \t P 0056720 S E > > P S E . E S L R e a r 0056740 = E m p t y \r \t r e s u l t i 0056760 s O r i g L e n g t h - L e n 0057000 g t h \r \t ] \r 377 \0 \0 B T r e e W 0057020 r t M S 1 . b c p l \0 373 230 - W 323 0057040 \0 \0 376 001 \0 314 376 / / \t B - T r e e 0057060 M a i n t e n a n c e R o u 0057100 t i n e s \r / / C o p y r i g 0057120 h t X e r o x C o r p o r a 0057140 t i o n 1 9 7 9 , 1 9 8 1 \r 0057160 \r \r / / \t B T r e e W r t M S 1 0057200 . b c p l - - R o u t i n 0057220 e s f o r w r i t i n g i 0057240 n B - T r e e s \r / / \t \t U s 0057260 e s p a g i n a t i o n s t 0057300 r a t e g y M S t o m i n 0057320 i m i z e t h e s u m o f 0057340 l e n g t h s \r / / \t \t o f 0057360 r e c o r d s p o s t e d t 0057400 o t h e f a t h e r p a g 0057420 e . \r \r / / \t l a s t e d i t 0057440 e d N o v e 376 001 \0 d 347 m b e r 0057460 2 6 , 1 9 8 1 1 2 : 3 8 0057500 P M b y T a f t \r \r g e t 0057520 " b t r e e . d e c l " \r \r \r 0057540 e x t e r n a l \r \t [ A l l o 0057560 c a t e \t / / D e f i n e d 0057600 b y O S \r \t F r e e \r \t M o v 0057620 e B l o c k \r \r \t R e a d B T r 0057640 e e P a g e \t / / d e f i n e 0057660 d b y O p e n B T r e e \r \t 0057700 W r i t e B T r e e P a g e \r \t 0057720 L o c k B T r e e P t r \r \t U n 0057740 l o c k B T r e e P t r \r \t A l 0057760 l o c a t e B T r e e P a g e \r 0060000 \t B T r e e B u g \r \r \t P a t h 0060020 R e c L E \t \t / / D e f i n e 0060040 d i n B T r e e R e 376 001 \0 M 0060060 303 a d . b c p l \r \t B a c k U p 0060100 O n e R e c o r d \r \t R e a d P 0060120 a g e A n d L o c k B T r e e P 0060140 t r \r \t ] \r \r \r e x t e r n a l 0060160 \r \t [ U p d a t e R e c o r d 0060200 \t / / D e f i n e d i n B 0060220 T r e e W r t M S . b c p l \r \t 0060240 I n s e r t R e c o r d s \r \t C 0060260 o m p l e x I n s e r t R e c o 0060300 r d s \r \t M a k e N e w R o o t 0060320 \r \t P a g e L e n g t h \r \t E n 0060340 t r y L e n g t h \r \t F i l l L 0060360 e f t P a g e \r \t F i l l R i g 0060400 h t P a g e \r \t A p p e n d E n 0060420 t S e q E n t \r \t P u s h E n t 0060440 S e q E n t \r \t M a k e E n t S 0060460 e 376 001 \0 L [ q E n t \r \t C o m p 0060500 u t e E n t L e n s \r \t P u s h 0060520 E n t S e q E n t L e n s \r \t A 0060540 p p e n d E n t S e q E n t L e 0060560 n s \r \t D e p o s i t E S L \r \t 0060600 F i n d R i g h t B r o t h e r 0060620 \r \t F i n d L e f t B r o t h e 0060640 r \r \t R e m o v e E n t r y \r \t 0060660 B a s i c R e m o v e E n t r y 0060700 \r \t W r i t e R i g h t B r o t 0060720 h e r \r \t W r i t e P a g e \r \t 0060740 A d d T o H e a p \r \t T r i c k 0060760 l e D o w n \r \t R e m o v e F r 0061000 o m H e a p \r \t S i f t U p \r \t 0061020 ] \r \r \r l e t C o m p l e x I 0061040 n s e r t R e c o r d s ( T r e 0061060 e , P a t 376 001 \0 8 034 h S t k , 0061100 I S ) = v a l o f \r \r \t [ 0061120 \r \t l e t P a t h S t k T o p 0061140 = P a t h S t k > > P S . P 0061160 a t h S t k T o p \r \t l e t S 0061200 P = l v P a t h S t k > > 0061220 P S . P S E ^ P a t h S t k T o 0061240 p \r \t l e t S F P = S P 0061260 - s i z e P S E / 1 6 \r \t l 0061300 e t M a x F r e e W o r d s 0061320 = I S > > I S . M a x F r e e 0061340 W o r d s \r \r / / \t N o t a l 0061360 l t h e e n t r i e s w i 0061400 l l f i t o n t h e c u 0061420 r r e n t p a g e . T r y \r 0061440 / / \t s p i l l i n g o v e r 0061460 o n t o t h e r 376 001 \0 271 211 0061500 i g h t b r o t h e r p a g 0061520 e , o r o n t o t h e \r / 0061540 / \t l e f t b r o t h e r p 0061560 a g e i f t h e r e i s n 0061600 ' t a r i g h t b r o t h 0061620 e r . \r \r \t S F P > > P S E . L 0061640 e a s t S o n = S P > > P S 0061660 E . P a g e N o / / I n 0061700 c a s e t h i s i s t h e 0061720 \r \t \t \t \t \t / / r o o t 0061740 p a g e s p l i t t i n g \r 0061760 \r \t l e t R t B r o P g 1 = 0062000 E m p t y \r \t i f P a t h S 0062020 t k T o p g r 1 t h e n \r 0062040 \t \t [ R t B r o P g 1 = F 0062060 i n d R i g h t B r o t h e r ( 0062100 376 001 \0 274 331 I S , S F P , - M 0062120 a x F r e e W o r d s , S P ) 0062140 \r \t \t i f R t B r o P g 1 e 0062160 q E m p t y t h e n \r \t \t \t 0062200 R t B r o P g 1 = F i n d L 0062220 e f t B r o t h e r ( I S , S 0062240 F P , - M a x F r e e W o r d 0062260 s , S P ) \r \t \t ] \r \r \t i f 0062300 R t B r o P g 1 e q E m p t 0062320 y t h e n \r \t \t R t B r o P g 0062340 1 = A l l o c a t e B T r e 0062360 e P a g e ( T r e e ) \r \r \t l e 0062400 t O n e B r o t h e r E n o u 0062420 g h = f a l s e \r \t i f I 0062440 S > > I S . E L L L e n l s 0062460 3 t h e n \r \t \t B T r e e B u 0062500 g ( T r e 376 001 \0 R ( e , e c E 0062520 n t r y L i s t T o o S h o r t 0062540 ) \r \r \t l e t F a t h e r E n 0062560 t = F i l l L e f t P a g e 0062600 ( I S , 0 ) \r \r \t l e t B e 0062620 s t F a t h e r E n t = n i 0062640 l \r \t l e t B e s t F a t h e 0062660 r L e n = M a x F r e e W o 0062700 r d s + 1 / / C a u s e s 0062720 B e s t F a t h e r E n t \r \t \t 0062740 \t \t \t / / t o b e u p 0062760 d a t e d t h e \r \t \t \t \t \t / 0063000 / f i r s t t i m e a 0063020 r o u n d . \r \r / / \t T h e i 0063040 d e a n e x t i s t o s 0063060 e n d t h e s h o r t e s t 0063100 e n t r y i n t 376 001 \0 241 205 o 0063120 \r / / \t t h e f a t h e r p 0063140 a g e s u c h t h a t t h 0063160 e c u r r e n t p a g e i 0063200 s a t l e a s t \r / / \t " p 0063220 r e t t y " f u l l ( i f 0063240 w e h a v e s u c h a c 0063260 h o i c e ) . \r \r \t w h i l e 0063300 v a l o f \r \t \t [ l e t P L 0063320 1 = P a g e L e n g t h ( I 0063340 S , F a t h e r E n t ) \r \t \t 0063360 i f P L 1 g r M a x F r e 0063400 e W o r d s t h e n r e s u 0063420 l t i s f a l s e \r \t \t l e t 0063440 P L 0 = P a g e L e n g t 0063460 h ( I S , 0 , F a t h e r E 0063500 n t ) \r \t \t r e s u l t i s 376 0063520 001 \0 205 200 ( P L 0 g r 0 ) & 0063540 ( P L 0 + P L 1 l e \r \t \t \t 0063560 \t \t M a x F r e e W o r d s + I 0063600 S > > I S . A w f u l l y F u l 0063620 l ) \r \t \t ] \r \t d o \r 0063640 \t \t / / S t i l l e n o u g 0063660 h r o o m i n b r o t h e 0063700 r p a g e . S e e i f t 0063720 h i s \r \t \t / / i s s h o r 0063740 t e s t f a t h e r e n t r 0063760 y , a n d t r y m o v i n 0064000 g o n e \r \t \t / / m o r e 0064020 e n t r y i n t o b r o t h 0064040 e r p a g e . \r \r \t \t [ l e 0064060 t F a t h e r L e n = E n 0064100 t r y L e n g t h ( I S , F a 0064120 t h e r 376 001 \0 9 254 E n t ) \r \t \t 0064140 i f F a t h e r L e n l s 0064160 B e s t F a t h e r L e n t h 0064200 e n \r \t \t \t [ B e s t F a t h 0064220 e r E n t = F a t h e r E n 0064240 t \r \t \t \t B e s t F a t h e r L 0064260 e n = F a t h e r L e n \r \t 0064300 \t \t O n e B r o t h e r E n o u 0064320 g h = t r u e \r \t \t \t ] \r \t 0064340 \t F a t h e r E n t = F a t 0064360 h e r E n t - 1 \r \t \t ] \r \r \t i 0064400 f O n e B r o t h e r E n o u 0064420 g h t h e n \r \t \t [ l e t 0064440 B r e a k L e n = P a g e L 0064460 e n g t h ( I S , 0 , B e s 0064500 t F a t h e r E n t ) \r \t \t l e 0064520 t T o t L e n 376 001 \0 217 F = 0064540 P a g e L e n g t h ( I S , 0 0064560 ) \r \r \t \t W r i t e P a g e ( I 0064600 S , S P , S P > > P S E . P 0064620 a g e N o , B r e a k L e n ) 0064640 \r \r \t \t P u s h E n t S e q E n 0064660 t ( S F P , \r \t \t \t W r i t e R 0064700 i g h t B r o t h e r ( I S , 0064720 S P , S F P , R t B r o P g 0064740 1 , \r \t \t \t \t T o t L e n - B r 0064760 e a k L e n ) ) \r \t \t r e s u l 0065000 t i s E m p t y \r \t \t ] \r \r / 0065020 / \t A t t h i s p o i n t 0065040 w e k n o w t h a t a t 0065060 l e a s t t h e c u r r e n 0065100 t p a g e a n d \r / / \t t w 0065120 o b r o t h e r p a g e 376 001 0065140 \0 357 250 s a r e i n v o l v e 0065160 d . \r \r \t r e s u l t i s R t 0065200 B r o P g 1 \r \t ] \r \r \r a n d 0065220 F i n d R i g h t B r o t h e 0065240 r ( I S , S t k F a t h e r P 0065260 t r , S p a c e N e e d e d , 0065300 P a t h S t k E n t r y ) \r \t 0065320 \t = v a l o f \r \r \t [ l e t 0065340 T r e e = I S > > I S . T 0065360 r e e \r \t l e t L R = T r 0065400 e e > > T R E E . L e n g t h R 0065420 t n \r \t l e t F a t h e r E n 0065440 t = n i l \r \t l e t F a t 0065460 h e r P t r = 0 \r \t L o c k 0065500 B T r e e P t r ( T r e e , l 0065520 v F a t h e r P t r ) \r \r \t t 0065540 e s t 376 001 \0 355 $ S t k F a t h 0065560 e r P t r > > P S E . E S L F r 0065600 o n t e q E m p t y \r \t i f 0065620 s o \r \t \t [ F a t h e r P t r 0065640 = R e a d B T r e e P a g e 0065660 ( T r e e , S t k F a t h e r 0065700 P t r > > P S E . P a g e N o ) 0065720 \r \t \t l e t F a t h e r F r e 0065740 e W o r d s = F a t h e r P 0065760 t r > > B T P . F r e e W o r d 0066000 s \r \t \t l e t F a t h e r O f 0066020 f s e t = S t k F a t h e r 0066040 P t r > > P S E . O f f s e t \r 0066060 \t \t F a t h e r E n t = F a 0066100 t h e r P t r + F a t h e r O f 0066120 f s e t \r \r \t \t i f ( ( F a t 0066140 h e r O f f s e 376 001 \0 252 K t - R 0066160 e c 1 O f f s e t ) g e \r \t \t 0066200 \t ( I S > > I S . M a x F r e e 0066220 W o r d s - F a t h e r F r e e 0066240 W o r d s ) ) t h e n \r \t \t \t 0066260 \t [ U n l o c k B T r e e P t 0066300 r ( T r e e , l v F a t h e 0066320 r P t r ) \r \t \t \t \t r e s u l t 0066340 i s E m p t y \r \t \t \t \t ] \r \t 0066360 \t ] \r \t i f n o t F a t h e r 0066400 E n t = ( S t k F a t h e r 0066420 P t r > > P S E . E S L F r o n 0066440 t ) > > E S L E . E n t S e q P 0066460 \r \r \t l e t F a t h e r E n 0066500 t L e n = ( o f f s e t B 0066520 T E . R e c o r d / 1 6 ) + \r \t 0066540 \t L R ( l v F a t h e r 376 001 \0 0066560 o 311 E n t > > B T E . R e c o r 0066600 d ) \r \t l e t R t B r o P g 0066620 = F a t h e r E n t > > B T E 0066640 . G r P t r \r \r \t l e t R t B 0066660 r o P t r = R e a d B T r e 0066700 e P a g e ( T r e e , R t B r 0066720 o P g ) \r \t u n l e s s R t B 0066740 r o P t r > > B T P . F r e e W 0066760 o r d s - F a t h e r E n t L e 0067000 n g e S p a c e N e e d e d 0067020 \r \t \t d o \r \t \t [ U n l o c k 0067040 B T r e e P t r ( T r e e , l 0067060 v F a t h e r P t r ) \r \t \t r 0067100 e s u l t i s E m p t y \r \t \t 0067120 ] \r \r \r \t L o c k B T r e e P t 0067140 r ( T r e e , l v R t B r o 0067160 P t 376 001 \0 001 _ r ) \r \r \t l e t 0067200 R t B r o L e n = I S > > I 0067220 S . M a x F r e e W o r d s - ( 0067240 R t B r o P t r > > B T P . \r \t 0067260 \t \t F r e e W o r d s ) \r \r \t l 0067300 e t N e w E S E = M a k e 0067320 E n t S e q E n t ( T r e e > > 0067340 T R E E . Z o n e , l v ( R 0067360 t B r o P t r > > B T P . B T E 0067400 B l o c k ) , \r \t \t \t \t R t B r 0067420 o L e n ) \r \r \t l e t E S E 0067440 = R e m o v e E n t r y ( T r 0067460 e e , S t k F a t h e r P t r 0067500 ) \r \t A p p e n d E n t S e q E 0067520 n t L e n s ( I S , E S E ) \r 0067540 \t A p p e n d E n t S e q E n t 0067560 ( P a t h S t 376 001 \0 211 376 k E n t 0067600 r y , E S E ) \r \t A p p e n d 0067620 E n t S e q E n t L e n s ( I S 0067640 , N e w E S E ) \r \t A p p e n 0067660 d E n t S e q E n t ( P a t h S 0067700 t k E n t r y , N e w E S E ) 0067720 \r \r \t W r i t e B T r e e P a g 0067740 e ( T r e e , R t B r o P g ) 0067760 \r \t U n l o c k B T r e e P t r 0070000 ( T r e e , l v F a t h e r 0070020 P t r ) \r \t U n l o c k B T r e 0070040 e P t r ( T r e e , l v R t 0070060 B r o P t r ) \r \t r e s u l t i 0070100 s R t B r o P g \r \t ] \r \r \r a 0070120 n d R e m o v e E n t r y ( T 0070140 r e e , S t k P t r , l v O 0070160 l d G r P t r ; n u m 376 001 \0 x 0070200 y a r g s n a ) = v a l o 0070220 f \r \r \t [ l e t R e s u l t 0070240 E S E = ( S t k P t r > > P 0070260 S E . E S L F r o n t e q E 0070300 m p t y ) ? \r \t \t B a s i c R e 0070320 m o v e E n t r y ( T r e e , 0070340 S t k P t r ) , \r \t \t R e m o v 0070360 e E S E ( T r e e , S t k P t 0070400 r ) \r \t l e t G r e a t e r S 0070420 o n P g = ( R e s u l t E S 0070440 E > > E S L E . E n t S e q P ) 0070460 > > B T E . G r P t r \r \t i f 0070500 n a e q 3 t h e n @ l v 0070520 O l d G r P t r = G r e a t 0070540 e r S o n P g \r \t ( R e s u l t 0070560 E S E > > E S L E . E n t S e q 0070600 P 376 001 \0 K 346 ) > > B T E . G r P 0070620 t r = \r \t \t ( G r e a t e r S 0070640 o n P g e q E m p t y ) ? \r 0070660 \t \t \t E m p t y , \r \t \t \t ( R e 0070700 a d B T r e e P a g e ( T r e e 0070720 , G r e a t e r S o n P g ) ) 0070740 > > B T P . M i n P t r \r \t \t \t 0070760 \t / / n o n e e d t o l 0071000 o c k t r a n s i e n t r e 0071020 f e r e n c e \r \t r e s u l t i 0071040 s R e s u l t E S E \r \t ] \r \r 0071060 \r a n d B a s i c R e m o v e 0071100 E n t r y ( T r e e , S t k P 0071120 t r ) = v a l o f \r \r \t [ 0071140 l e t P t r = W r i t e B 0071160 T r e e P a g e ( T r e e , S 0071200 t k P t r > 376 001 \0 275 j > P S E . 0071220 P a g e N o ) \r \t L o c k B T r 0071240 e e P t r ( T r e e , l v P 0071260 t r ) \r \r \t l e t O f f s e t 0071300 = S t k P t r > > P S E . O 0071320 f f s e t \r \t l e t E n t r y 0071340 = P t r + O f f s e t \r \t l 0071360 e t E n t L e n = ( o f f 0071400 s e t B T E . R e c o r d / 1 0071420 6 ) + \r \t \t ( T r e e > > T R E 0071440 E . L e n g t h R t n ) ( l v 0071460 ( E n t r y > > B T E . R e c o 0071500 r d ) ) \r \r \t l e t R e s u l 0071520 t E S E = M a k e E n t S e 0071540 q E n t ( T r e e > > T R E E . 0071560 Z o n e , E n t r y , E n t 0071600 L e n ) \r \r \t P t r > 376 001 \0 d 200 0071620 > B T P . F r e e W o r d s = 0071640 P t r > > B T P . F r e e W o 0071660 r d s + E n t L e n \r \t l e t 0071700 T a i l B l k L e n = \r \t \t ( 0071720 T r e e > > T R E E . P a g e L 0071740 e n g t h - P t r > > B T P . F 0071760 r e e W o r d s ) - O f f s e t 0072000 \r \t M o v e B l o c k ( E n t r 0072020 y , E n t r y + E n t L e n , 0072040 T a i l B l k L e n ) \r \r \t U 0072060 n l o c k B T r e e P t r ( T r 0072100 e e , l v P t r ) \r \t r e s 0072120 u l t i s R e s u l t E S E \r 0072140 \t ] \r \r \r a n d R e m o v e E 0072160 S E ( T r e e , S t k P t r ) 0072200 = v a l o f \r \r \t [ l e t 0072220 376 001 \0 \f 273 E n t = ( S t k 0072240 P t r > > P S E . E S L F r o n 0072260 t ) > > \r \t \t \t E S L E . E n t 0072300 S e q P \r \t l e t E n t L e n 0072320 = ( o f f s e t B T E . R 0072340 e c o r d / 1 6 ) + \r \t \t ( T r 0072360 e e > > T R E E . L e n g t h R 0072400 t n ) ( l v ( E n t > > B T E 0072420 . R e c o r d ) ) \r \r \t l e t 0072440 E S E = A l l o c a t e ( T 0072460 r e e > > T R E E . Z o n e , \r 0072500 \t \t ( o f f s e t E S L E . E 0072520 n t S e q / 1 6 ) + E n t L e n 0072540 ) \r \t E S E > > E S L E . E n t 0072560 S e q P = l v ( E S E > > 0072600 E S L E . E n t S e q ) \r \t E S 0072620 E > > E S 376 001 \0 034 267 L E . E n t 0072640 S e q L e n = E n t L e n \r 0072660 \t D e p o s i t E S L ( T r e e 0072700 , S t k P t r , l v ( E S 0072720 E > > E S L E . E n t S e q ) , 0072740 E n t L e n ) \r \t r e s u l t 0072760 i s E S E \r \t ] \r \r \r a n d 0073000 W r i t e R i g h t B r o t h e 0073020 r ( I S , S t k P t r , S t 0073040 k F a t h e r P t r , R t B r 0073060 o P g , \r \t \t \t \t \t N W o r d s 0073100 ) = v a l o f \r \r \t [ l e 0073120 t T r e e = I S > > I S . 0073140 T r e e \r \r \t l e t E S E = 0073160 R e m o v e E S E ( T r e e , 0073200 S t k P t r ) \r \t l e t W o 0073220 r d s L e f t = 376 001 \0 214 210 N 0073240 W o r d s - E S E > > E S L E . 0073260 E n t S e q L e n \r \t l e t M 0073300 i n P t r = ( E S E > > E S 0073320 L E . E n t S e q P ) > > B T E 0073340 . G r P t r \r \t ( E S E > > E S 0073360 L E . E n t S e q P ) > > B T E 0073400 . G r P t r = R t B r o P g 0073420 \r \r \r \t W r i t e B T r e e P a 0073440 g e ( T r e e , R t B r o P g 0073460 ) > > B T P . M i n P t r = 0073500 M i n P t r \r \t u n l e s s W 0073520 r i t e P a g e ( I S , S t k 0073540 P t r , R t B r o P g , W o 0073560 r d s L e f t ) e q \r \t \t W o 0073600 r d s L e f t d o B T r e e 0073620 B u g ( T r e e , e c W r i 376 0073640 001 \0 y 252 t e P a g e W r o n g ) 0073660 \r \t r e s u l t i s E S E / 0073700 / f o r f a t h e r p a g 0073720 e \r \t ] \r \r \r a n d W r i t e 0073740 P a g e ( I S , P S E , P a 0073760 g e N o , N W o r d s ) = 0074000 v a l o f \r \r \t [ l e t T r 0074020 e e = I S > > I S . T r e e 0074040 \r \t l e t P a g e P t r = 0074060 W r i t e B T r e e P a g e ( T 0074100 r e e , P a g e N o ) \r \t L o 0074120 c k B T r e e P t r ( T r e e , 0074140 l v P a g e P t r ) \r \t l e 0074160 t S e n t W o r d s = D e 0074200 p o s i t E S L ( T r e e , P 0074220 S E , l v ( P a g e P t r > 0074240 > B T P 376 001 \0 X P . B T E B l o 0074260 c k ) , \r \t \t N W o r d s ) \r \t 0074300 P a g e P t r > > B T P . F r e 0074320 e W o r d s = I S > > I S . 0074340 M a x F r e e W o r d s - S e n 0074360 t W o r d s \r \t U n l o c k B T 0074400 r e e P t r ( T r e e , l v 0074420 P a g e P t r ) \r \t r e s u l t 0074440 i s S e n t W o r d s \r \t ] \r 0074460 \r \r a n d E n t r y L e n g t 0074500 h ( I S , E n t r y ) = P 0074520 a g e L e n g t h ( I S , E n 0074540 t r y - 1 , E n t r y + 1 ) \r 0074560 \r \r a n d F i l l L e f t P a 0074600 g e ( I S , L e f t F a t h e 0074620 r , R i g h t F a t h e r ; 0074640 n u m a r g s n 376 001 \0 230 226 a ) 0074660 = v a l o f \r \r \t [ i f 0074700 n a l s 3 t h e n R i g 0074720 h t F a t h e r = I S > > I 0074740 S . E L L L e n + 1 \r \r \t l e t 0074760 M i d F a t h e r = L e f 0075000 t F a t h e r + 2 \r \t w h i l e 0075020 M i d F a t h e r l s R i 0075040 g h t F a t h e r - 2 & \r \t \t 0075060 P a g e L e n g t h ( I S , L 0075100 e f t F a t h e r , M i d F a 0075120 t h e r + 1 ) l e I S > > I 0075140 S . M a x F r e e W o r d s \r \t 0075160 \t d o M i d F a t h e r = 0075200 M i d F a t h e r + 1 \r \t r e s 0075220 u l t i s M i d F a t h e r \r 0075240 \t ] \r \r \r a n d F i l l R 376 001 0075260 \0 B 352 i g h t P a g e ( I S , 0075300 L e f t F a t h e r , R i g h 0075320 t F a t h e r ; n u m a r g s 0075340 n a ) = v a l o f \r \r \t [ 0075360 i f n a l s 3 t h e n 0075400 R i g h t F a t h e r = I 0075420 S > > I S . E L L L e n + 1 \r \r 0075440 \t l e t M i d F a t h e r = 0075460 R i g h t F a t h e r - 2 \r \t 0075500 w h i l e M i d F a t h e r 0075520 g r L e f t F a t h e r + 2 0075540 & \r \t \t P a g e L e n g t h ( I 0075560 S , M i d F a t h e r - 1 , 0075600 R i g h t F a t h e r ) l e 0075620 I S > > I S . M a x F r e e W o 0075640 r d s \r \t \t d o M i d F a t h 0075660 e r 376 001 \0 5 215 = M i d F a t 0075700 h e r - 1 \r \t r e s u l t i s 0075720 M i d F a t h e r \r \t ] \r \r \r a 0075740 n d P u s h E n t S e q E n t 0075760 ( P a t h S t k E n t r y , E 0076000 n t r y ) b e \r \r \t [ E n t 0076020 r y > > E S L E . F w d P = 0076040 P a t h S t k E n t r y > > P S 0076060 E . E S L F r o n t \r \t P a t h 0076100 S t k E n t r y > > P S E . E S 0076120 L F r o n t = E n t r y \r \r 0076140 \t i f P a t h S t k E n t r y 0076160 > > P S E . E S L R e a r e q 0076200 E m p t y t h e n \r \t \t P a 0076220 t h S t k E n t r y > > P S E . 0076240 E S L R e a r = E n t r y \r 0076260 \t ] \r \r \r a n d 376 001 \0 377 242 P u 0076300 s h E n t S e q E n t L e n s ( 0076320 I S , E n t S e q E n t ) b 0076340 e \r \r \t [ / / \t T h e i d e 0076360 a i s t o a d d t h e 0076400 e n t r i e s o n t h e t 0076420 a i l e n d a n d \r \t / / 0076440 t h e n t o t a k e t h e 0076460 a d d e d b u n c h o f 0076500 e n t r i e s a n d m o v e 0076520 t h e m \r \t / / t o t h e 0076540 h e a d e n d , a d j u s 0076560 t i n g c u m u l a t i v e 0076600 l e n g t h s \r \t / / a p p r 0076620 o p r i a t e l y . \r \r \t / / 0076640 N . B . T h i s m u s t n 0076660 e v e r b e d o n e 376 001 \0 0076700 o 267 w h i l e w e h a v e 0076720 a n \r \t / / a c t i v e h e 0076740 a p , o r d i s a s t e r 0076760 w i l l e n s u e . \r \r \t l e 0077000 t O l d E n d = I S > > I 0077020 S . E L L L e n \r \t A p p e n d 0077040 E n t S e q E n t L e n s ( I S 0077060 , E n t S e q E n t ) \r \t l e 0077100 t N e w E n d = I S > > I 0077120 S . E L L L e n \r \r \t l e t E 0077140 L L = I S > > I S . E L L P 0077160 t r \r \t l e t O l d L e n = 0077200 E L L > > E L L . C u m E n t 0077220 L e n ^ O l d E n d \r \t l e t 0077240 N e w L e n = E L L > > E L 0077260 L . C u m E n t L e n ^ N e w E 0077300 n d 376 001 \0 364 275 \r \t l e t O l d 0077320 B a s e = E L L > > E L L . 0077340 C u m E n t L e n ^ 0 \r \r \t l e 0077360 t Z o n e = ( I S > > I S 0077400 . T r e e ) > > T R E E . Z o n 0077420 e \r \t l e t T S i z e = O 0077440 l d E n d * ( s i z e E L E / 0077460 1 6 ) \r \t l e t T = A l l 0077500 o c a t e ( Z o n e , T S i z 0077520 e ) \r \t M o v e B l o c k ( T , 0077540 l v E L L > > E L L . E L E 0077560 ^ 1 , T S i z e ) \r \t M o v e 0077600 B l o c k ( l v E L L > > E L 0077620 L . E L E ^ 1 , l v E L L > 0077640 > E L L . E L E ^ ( O l d E n d 0077660 + 1 ) , \r \t \t ( ( N e w E n d - 0077700 O l d E n d ) 376 \0 371 c 274 * ( s i 0077720 z e E L E / 1 6 ) ) ) \r \t M o 0077740 v e B l o c k ( l v E L L > > 0077760 E L L . E L E ^ ( 1 + N e w E n 0100000 d - O l d E n d ) , T , T S 0100020 i z e ) \r \t F r e e ( Z o n e , 0100040 T ) \r \r \t E L L > > E L L . C 0100060 u m E n t L e n ^ 0 = O l d 0100100 B a s e - ( N e w L e n - O l d 0100120 L e n ) \r \t l e t D e l t a 0100140 = O l d B a s e - N e w L e n 0100160 \r \t f o r i = 1 t o N e w 0100200 E n d - O l d E n d d o \r \t \t 0100220 E L L > > E L L . C u m E n t L 0100240 e n ^ i = E L L > > E L L . 0100260 C u m E n t L e n ^ i + D e l t 0100300 a \r \t ] \r 377 \0 \0 B T r e e W r t 0100320 M S 2 . b c p l \0 373 230 - W 213 \0 \0 0100340 376 001 \0 315 376 / / \t B - T r e e M 0100360 a i n t e n a n c e R o u t i 0100400 n e s \r / / C o p y r i g h t 0100420 X e r o x C o r p o r a t i 0100440 o n 1 9 7 9 , 1 9 8 1 \r \r \r 0100460 / / \t B T r e e W r t M S 2 . b 0100500 c p l - - R o u t i n e s 0100520 f o r w r i t i n g i n 0100540 B - T r e e s \r / / \t \t U s e s 0100560 p a g i n a t i o n s t r a 0100600 t e g y M S t o m i n i m 0100620 i z e t h e s u m o f l 0100640 e n g t h s \r / / \t \t o f r e 0100660 c o r d s p o s t e d t o 0100700 t h e f a t h e r p a g e . 0100720 \r \r / / \t l a s t e d i t e d 0100740 N o v e 376 001 \0 e 342 m b e r 2 0100760 6 , 1 9 8 1 1 2 : 4 3 P 0101000 M b y T a f t \r \r g e t " 0101020 b t r e e . d e c l " \r \r \r e x 0101040 t e r n a l \r \t [ A l l o c a 0101060 t e \t / / D e f i n e d b y 0101100 O S \r \t F r e e \r \t M o v e B 0101120 l o c k \r \r \t R e a d B T r e e 0101140 P a g e \t / / d e f i n e d 0101160 b y O p e n B T r e e \r \t W r 0101200 i t e B T r e e P a g e \r \t L o 0101220 c k B T r e e P t r \r \t U n l o 0101240 c k B T r e e P t r \r \t A l l o 0101260 c a t e B T r e e P a g e \r \t B 0101300 T r e e B u g \r \r \t P a t h R e 0101320 c L E \t \t / / D e f i n e d 0101340 i n B T r e e R e 376 001 \0 \t 235 a 0101360 d . b c p l \r \t R e a d P a g e 0101400 A n d L o c k B T r e e P t r \r 0101420 \t B a c k U p O n e R e c o r d 0101440 \r \t R e p a i r O f f s e t s \r 0101460 \t ] \r \r \r e x t e r n a l \r \t [ 0101500 U p d a t e R e c o r d \t / / 0101520 D e f i n e d i n B T r e 0101540 e W r t M S . b c p l \r \t I n s 0101560 e r t R e c o r d s \r \t C o m p 0101600 l e x I n s e r t R e c o r d s 0101620 \r \t H a i r y I n s e r t R e c 0101640 o r d s \r \t M a k e N e w R o o 0101660 t \r \t P a g e L e n g t h \r \t E 0101700 n t r y L e n g t h \r \t F i l l 0101720 L e f t P a g e \r \t F i l l R i 0101740 g h t P a g e \r \t A p p e n d 376 0101760 001 \0 200 203 E n t S e q E n t \r \t P 0102000 u s h E n t S e q E n t \r \t M a 0102020 k e E n t S e q E n t \r \t C o m 0102040 p u t e E n t L e n s \r \t P u s 0102060 h E n t S e q E n t L e n s \r \t 0102100 A p p e n d E n t S e q E n t L 0102120 e n s \r \t D e p o s i t E S L \r 0102140 \t F i n d R i g h t B r o t h e 0102160 r \r \t F i n d L e f t B r o t h 0102200 e r \r \t R e m o v e E n t r y \r 0102220 \t B a s i c R e m o v e E n t r 0102240 y \r \t W r i t e R i g h t B r o 0102260 t h e r \r \t W r i t e P a g e \r 0102300 \t A d d T o H e a p \r \t T r i c 0102320 k l e D o w n \r \t R e m o v e F 0102340 r o m H e a p \r \t S i f t U p \r 0102360 \t ] \r \r 376 001 \0 243 027 \r l e t H a 0102400 i r y I n s e r t R e c o r d s 0102420 ( T r e e , P a t h S t k , 0102440 I S , R t B r o P g 1 ) b e 0102460 \r \r \t [ \r / / \t F r o m t h i 0102500 s p o i n t o n , w e k 0102520 n o w t h a t a t l e a s 0102540 t t h e c u r r e n t p a 0102560 g e \r / / \t a n d t w o r i 0102600 g h t b r o t h e r p a g e 0102620 s a r e i n v o l v e d . 0102640 F i r s t w e \r / / \t c a l c 0102660 u l a t e t h e m i n i m u 0102700 m s p a c e r e q u i r e d 0102720 i n t h e s e c o n d r 0102740 i g h t \r / / \t b r o t h e r 0102760 i n o r d e r 376 001 \0 i 223 t h 0103000 a t h e c a n h a n d l e 0103020 o u r o v e r f l o w . T 0103040 h e n \r / / \t w e s e e i f 0103060 o u r s e c o n d b r o t 0103100 h e r e x i s t s a n d h 0103120 a s t h a t \r / / \t m u c h 0103140 s p a c e . \r \r \t l e t S P 0103160 = l v P a t h S t k > > P S 0103200 . P S E ^ ( P a t h S t k > > P 0103220 S . P a t h S t k T o p ) \r \t l 0103240 e t S F P = S P - s i 0103260 z e P S E / 1 6 \r \t l e t M 0103300 a x F r e e W o r d s = I S 0103320 > > I S . M a x F r e e W o r d 0103340 s \r \r \t i f I S > > I S . E L 0103360 L L e n l s 5 t h e n 376 001 0103400 \0 177 331 \r \t \t B T r e e B u g ( T 0103420 r e e , e c E n t r y L i s t 0103440 T o o S h o r t ) \r \r / / \t S e 0103460 e h o w m u c h s p a c e 0103500 o u r s e c o n d b r o t 0103520 h e r p a g e w o u l d h 0103540 a v e t o \r / / \t c o n t a i 0103560 n i n o r d e r t o h a 0103600 n d l e t h e o v e r f l o 0103620 w . T h i s i s d o n e \r 0103640 / / \t b y p r e t e n d i n g 0103660 t o f i l l u p t h i s 0103700 p a g e a n d t h e f i 0103720 r s t r i g h t b r o t h e 0103740 r \r / / \t p a g e a n d s e 0103760 e i n g w h a t i s l e f 0104000 t o 376 001 \0 s 346 v e r . \r \r \t l 0104020 e t F a t h e r E n t = F 0104040 i l l L e f t P a g e ( I S , 0104060 0 ) \r \t l e t F a t h e r E n 0104100 t 2 = F i l l L e f t P a g 0104120 e ( I S , F a t h e r E n t ) 0104140 \r \r / / \t C u r P a g e c a n 0104160 ' t b e t h e r o o t , 0104200 b e c a u s e \r / / \t o n e b 0104220 r o t h e r w o u l d s u r 0104240 e l y h a v e b e e n e n 0104260 o u g h i n t h a t \r / / \t 0104300 c a s e , s o w e d o n ' 0104320 t h a v e t o p u s s y f 0104340 o o t w h e n c a l l i n g 0104360 \r / / \t F i n d R i g h t B r 0104400 o t h e r . \r \r 376 001 \0 337 8 \t l e 0104420 t R t B r o P g 2 = F i n 0104440 d R i g h t B r o t h e r ( I S 0104460 , S F P , \r \t \t P a g e L e n 0104500 g t h ( I S , F a t h e r E n 0104520 t 2 ) + \r \t \t \t 2 * ( I S > > I 0104540 S . B r e a t h i n g S p a c e 0104560 ) , S P ) \r \r \t i f R t B r 0104600 o P g 2 e q E m p t y t h 0104620 e n \r \t \t / / N o l u c k . 0104640 T r y t h e l e f t b r 0104660 o t h e r . \r \t \t [ l e t F 0104700 E 2 = F i l l R i g h t P a 0104720 g e ( I S , 0 ) \r \t \t l e t 0104740 F E = F i l l R i g h t P a 0104760 g e ( I S , 0 , F E 2 ) \r \t 0105000 \t R t B r o P g 2 = F 376 001 \0 0105020 035 345 i n d L e f t B r o t h e r 0105040 ( I S , S F P , P a g e L e 0105060 n g t h ( I S , 0 , F E ) + 0105100 \r \t \t \t \t \t \t 2 * ( I S > > I S 0105120 . B r e a t h i n g S p a c e ) 0105140 , \r \t \t \t \t \t \t S P ) \r \r \t \t t 0105160 e s t R t B r o P g 2 e q 0105200 E m p t y \r \r \t \t i f s o \t / / 0105220 S t i l l n o l u c k , 0105240 g e t e m p t y p a g e \r \t 0105260 \t \t R t B r o P g 2 = A l l 0105300 o c a t e B T r e e P a g e ( T 0105320 r e e ) \r \r \t \t i f n o t \t / / 0105340 L e f t b r o t h e r h a 0105360 d s p a c e , b u t \r \t \t \t 0105400 / / \t F a t h e r E n t ' s a 0105420 r e 376 001 \0 277 272 n o w i n v a 0105440 l i d \r \t \t \t [ F a t h e r E 0105460 n t = F i l l L e f t P a g 0105500 e ( I S , 0 ) \r \t \t \t F a t h 0105520 e r E n t 2 = F i l l L e f 0105540 t P a g e ( I S , F a t h e r 0105560 E n t ) \r \t \t \t ] \r \t \t ] \r \r \t 0105600 l e t M a x F e a s E n t = 0105620 F a t h e r E n t 2 \r \t w h i 0105640 l e P a g e L e n g t h ( I S 0105660 , M a x F e a s E n t ) l e 0105700 I S > > I S . F a i r l y F u 0105720 l l d o \r \t \t M a x F e a s E 0105740 n t = M a x F e a s E n t - 0105760 1 \r \t l e t M i n F e a s E n 0106000 t = M a x F e a s E n t + 1 0106020 \r \r \t l e t 376 001 \0 017 026 T w o B 0106040 r o t h e r s E n o u g h = 0106060 f a l s e \r \t l e t B e s t F 0106100 a t h e r E n t = n i l \r \t 0106120 l e t B e s t F a t h e r E n 0106140 t 2 = n i l \r \t l e t B e 0106160 s t F a t h e r L e n S u m = 0106200 M a x F r e e W o r d s + 1 \r 0106220 \t I S > > I S . H e a p S i z e 0106240 = 0 \r \r \t w h i l e ( P a 0106260 g e L e n g t h ( I S , 0 , 0106300 F a t h e r E n t ) g e I S 0106320 > > I S . P r e t t y F u l l ) 0106340 % \r \t \t ( n o t T w o B r o 0106360 t h e r s E n o u g h & \r \t \t 0106400 \t ( P a g e L e n g t h ( I S , 0106420 0 , F a t h e r E n 376 001 \0 204 0106440 302 t ) g r 0 ) ) \r \t \t d o \r 0106460 \r \t \t [ w h i l e ( P a g e 0106500 L e n g t h ( I S , F a t h e 0106520 r E n t , M i n F e a s E n t 0106540 - 1 ) g r 0 ) & \r \t \t \t ( 0106560 P a g e L e n g t h ( I S , M 0106600 i n F e a s E n t - 1 ) l e \r 0106620 \t \t \t M a x F r e e W o r d s ) 0106640 d o \r \r \t \t \t \t [ M i n F e 0106660 a s E n t = M i n F e a s E 0106700 n t - 1 \r \t \t \t \t i f M i n F 0106720 e a s E n t l e M a x F e a 0106740 s E n t t h e n \r \t \t \t \t \t A 0106760 d d T o H e a p ( I S , M i n 0107000 F e a s E n t ) \r \t \t \t \t ] \r \r 0107020 \t \t w h i l e P a g e L e n g 0107040 t 376 001 \0 241 210 h ( I S , F a t h 0107060 e r E n t , M a x F e a s E n 0107100 t ) g r \r \t \t \t M a x F r e e 0107120 W o r d s d o \r \r \t \t \t \t [ 0107140 i f M a x F e a s E n t g e 0107160 M i n F e a s E n t t h e n 0107200 \r \t \t \t \t \t R e m o v e F r o m 0107220 H e a p ( I S , M a x F e a s 0107240 E n t ) \r \t \t \t \t M a x F e a s 0107260 E n t = M a x F e a s E n t 0107300 - 1 \r \t \t \t \t ] \r \r \r \t \t i f 0107320 I S > > I S . H e a p S i z e 0107340 g r 0 t h e n \r \t \t \t [ F 0107360 a t h e r E n t 2 = ( I S > 0107400 > I S . H e a p P t r ) > > H P 0107420 . H e a p E n t ^ 1 \r \t \t \t l e 0107440 t S L = 376 001 \0 206 027 E n t r 0107460 y L e n g t h ( I S , F a t h 0107500 e r E n t ) + \r \t \t \t \t \t E n t 0107520 r y L e n g t h ( I S , F a t 0107540 h e r E n t 2 ) \r \r \t \t \t i f 0107560 S L l s B e s t F a t h e r 0107600 L e n S u m t h e n \r \t \t \t \t 0107620 [ T w o B r o t h e r s E n o 0107640 u g h = t r u e \r \t \t \t \t B 0107660 e s t F a t h e r L e n S u m 0107700 = S L \r \t \t \t \t B e s t F a t 0107720 h e r E n t = F a t h e r E 0107740 n t \r \t \t \t \t B e s t F a t h e 0107760 r E n t 2 = F a t h e r E n 0110000 t 2 \r \t \t \t \t ] \r \t \t \t ] \r \r \t 0110020 \t F a t h e r E n t = F a t 0110040 h e r E n t - 1 \r \t \t 376 001 \0 Y ` 0110060 ] \r \r \t u n l e s s T w o B r 0110100 o t h e r s E n o u g h d o \r 0110120 \t \t B T r e e B u g ( T r e e , 0110140 e c T w o B r o t h e r s N o 0110160 t E n o u g h ) \r \r \t l e t B 0110200 r e a k L e n 1 = P a g e L 0110220 e n g t h ( I S , 0 , B e s 0110240 t F a t h e r E n t ) \r \t l e t 0110260 B r e a k L e n 2 = P a g 0110300 e L e n g t h ( I S , 0 , B 0110320 e s t F a t h e r E n t 2 ) \r \t 0110340 l e t T o t L e n = P a g 0110360 e L e n g t h ( I S , 0 ) \r \r 0110400 \t W r i t e P a g e ( I S , S 0110420 P , S P > > P S E . P a g e N 0110440 o , B r e a k L e n 1 ) \r \r \t 0110460 376 001 \0 377 \n l e t t = W r i 0110500 t e R i g h t B r o t h e r ( I 0110520 S , S P , S F P , R t B r 0110540 o P g 1 , \r \t \t \t \t B r e a k L 0110560 e n 2 - B r e a k L e n 1 ) \r \r 0110600 \t P u s h E n t S e q E n t ( S 0110620 F P , \r \t \t W r i t e R i g h t 0110640 B r o t h e r ( I S , S P , 0110660 S F P , R t B r o P g 2 , \r \t 0110700 \t \t \t T o t L e n - B r e a k L 0110720 e n 2 ) ) \r \t P u s h E n t S e 0110740 q E n t ( S F P , t ) \r \t ] \r 0110760 \r \r a n d M a k e N e w R o o 0111000 t ( I S , S P , T r e e ) 0111020 b e \r \r \t [ l e t N e w W o 0111040 r d s = P a g e L e n g t h 0111060 ( I S , 376 001 \0 T L 0 ) \r \r \t i 0111100 f N e w W o r d s g r I S 0111120 > > I S . M a x F r e e W o r d 0111140 s t h e n \r \t \t B T r e e B u 0111160 g ( T r e e , e c N e w R o o 0111200 t O v e r f l o w ) \r \r \t l e t 0111220 N e w R o o t P a g e = A 0111240 l l o c a t e B T r e e P a g e 0111260 ( T r e e ) \r \r \t W r i t e B T 0111300 r e e P a g e ( T r e e , N e 0111320 w R o o t P a g e ) > > B T P . 0111340 M i n P t r = S P > > P S E 0111360 . L e a s t S o n \r \r \t u n l e 0111400 s s W r i t e P a g e ( I S , 0111420 S P , N e w R o o t P a g e 0111440 , N e w W o r d s ) e q N 0111460 e w W o r d s \r \t \t 376 001 \0 b G d 0111500 o B T r e e B u g ( T r e e , 0111520 e c W r i t e P a g e W r o n 0111540 g ) \r \r \t T r e e > > T R E E . 0111560 R o o t P a g e = N e w R o 0111600 o t P a g e \r \t T r e e > > T R 0111620 E E . S t a t e D i r t y = 0111640 t r u e \r \t ] \r \r \r a n d F i 0111660 n d L e f t B r o t h e r ( I S 0111700 , S t k F a t h e r P t r , 0111720 S p a c e N e e d e d , P a t 0111740 h S t k E n t r y ) \r \t \t = v 0111760 a l o f \r \r \t [ l e t T r e 0112000 e = I S > > I S . T r e e \r 0112020 \t l e t F a t h e r P g = 0112040 S t k F a t h e r P t r > > P S 0112060 E . P a g e N o \r \t l e t F 376 0112100 001 \0 X 267 a t h e r P t r = n 0112120 i l \r \t R e a d P a g e A n d L 0112140 o c k B T r e e P t r ( T r e e 0112160 , F a t h e r P g , l v F 0112200 a t h e r P t r ) \r \t l e t F 0112220 a t h e r F r e e W o r d s = 0112240 F a t h e r P t r > > B T P . 0112260 F r e e W o r d s \r \t l e t F 0112300 a t h e r O f f s e t = S t 0112320 k F a t h e r P t r > > P S E . 0112340 O f f s e t \r \t l e t F a t h 0112360 e r L O f f s e t = S t k F 0112400 a t h e r P t r > > P S E . L a 0112420 s t O f f s e t \r \t l e t F a 0112440 t h e r N T L O f f s e t = 0112460 S t k F a t h e r P t r > > P S 0112500 E . N e 376 001 \0 \0 206 x t T o L a s 0112520 t O f f s e t \r \r \t i f ( F a 0112540 t h e r O f f s e t l e R e 0112560 c 1 O f f s e t ) t h e n \r \t 0112600 \t [ U n l o c k B T r e e P t 0112620 r ( T r e e , l v F a t h e 0112640 r P t r ) \r \t \t r e s u l t i s 0112660 E m p t y \r \t \t ] \r \r \t l e t 0112700 F a t h e r E n t = F a t 0112720 h e r P t r + F a t h e r L O f 0112740 f s e t \r \t l e t F a t h e r 0112760 E n t L e n = ( T r e e > > 0113000 T R E E . L e n g t h R t n ) ( 0113020 l v F a t h e r E n t > > B T 0113040 E . R e c o r d ) + \r \t \t o f f 0113060 s e t B T E . R e c o r d / 1 0113100 6 \r \t l e t L F 376 001 \0 4 260 a t 0113120 h e r E n t = F a t h e r P 0113140 t r + F a t h e r N T L O f f s 0113160 e t \r \t l e t L e f t B r o P 0113200 g = L F a t h e r E n t > > 0113220 B T E . G r P t r \r \t l e t L 0113240 e f t B r o P t r = R e a d 0113260 B T r e e P a g e ( T r e e , 0113300 L e f t B r o P g ) \r \t u n l e 0113320 s s L e f t B r o P t r > > B 0113340 T P . F r e e W o r d s - F a t 0113360 h e r E n t L e n g e \r \t \t S 0113400 p a c e N e e d e d d o \r \t \t 0113420 [ U n l o c k B T r e e P t r 0113440 ( T r e e , l v F a t h e r 0113460 P t r ) \r \t \t r e s u l t i s 0113500 E m p t y \r \t \t ] \r \r \t L o 376 001 0113520 \0 Y 2 c k B T r e e P t r ( T r 0113540 e e , l v L e f t B r o P t 0113560 r ) \r \t W r i t e B T r e e P a 0113600 g e ( T r e e , F a t h e r P 0113620 g ) \r \t W r i t e B T r e e P a 0113640 g e ( T r e e , L e f t B r o 0113660 P g ) \r \r \t l e t L e f t B r 0113700 o L e n = I S > > I S . M a 0113720 x F r e e W o r d s - ( L e f t 0113740 B r o P t r > > B T P . \r \t \t \t 0113760 F r e e W o r d s ) \r \r \t l e t 0114000 N e w E S E = M a k e E n 0114020 t S e q E n t ( T r e e > > T R 0114040 E E . Z o n e , \r \t \t l v ( L 0114060 e f t B r o P t r > > B T P . B 0114100 T E B l o c k ) , L e f t B r 0114120 o L e 376 001 \0 F < n ) \r \r \t l e t 0114140 R i g h t B r o P g = F a 0114160 t h e r E n t > > B T E . G r P 0114200 t r \r \t L F a t h e r E n t > > 0114220 B T E . G r P t r = R i g h 0114240 t B r o P g \r \r \t B a c k U p O 0114260 n e R e c o r d ( T r e e , S 0114300 t k F a t h e r P t r ) \r \t l e 0114320 t E S E = B a s i c R e m 0114340 o v e E n t r y ( T r e e , S 0114360 t k F a t h e r P t r ) \r \t l e 0114400 t R i g h t B r o P t r = 0114420 W r i t e B T r e e P a g e ( T 0114440 r e e , R i g h t B r o P g ) 0114460 \r \t ( E S E > > E S L E . E n t 0114500 S e q P ) > > B T E . G r P t r 0114520 = R i g h t 376 001 \0 213 242 B r o 0114540 P t r > > B T P . M i n P t r \r 0114560 \t R i g h t B r o P t r > > B T 0114600 P . M i n P t r = L e f t B 0114620 r o P t r > > B T P . M i n P t 0114640 r \r \r \t P u s h E n t S e q E n 0114660 t L e n s ( I S , E S E ) \r \t 0114700 P u s h E n t S e q E n t ( P a 0114720 t h S t k E n t r y , E S E ) 0114740 \r \t P u s h E n t S e q E n t L 0114760 e n s ( I S , N e w E S E ) \r 0115000 \t P u s h E n t S e q E n t ( P 0115020 a t h S t k E n t r y , N e w 0115040 E S E ) \r \r \t U n l o c k B T r 0115060 e e P t r ( T r e e , l v L 0115100 e f t B r o P t r ) \r \t U n l o 0115120 c k B T r e e P t r ( T r 376 001 \0 0115140 023 & e e , l v F a t h e r P 0115160 t r ) \r \t r e s u l t i s L e 0115200 f t B r o P g \r \t ] \r \r \r a n d 0115220 A d d T o H e a p ( I S , E 0115240 n t r y ) b e \r \r \t [ I S > 0115260 > I S . H e a p S i z e = I 0115300 S > > I S . H e a p S i z e + 1 0115320 \r \t T r i c k l e D o w n ( I S 0115340 , I S > > I S . H e a p S i z 0115360 e , E n t r y ) \r \t ] \r \r \r a 0115400 n d T r i c k l e D o w n ( I 0115420 S , E m p t y L o c , E n t 0115440 r y ) b e \r \r \t [ l e t H 0115460 e a p = I S > > I S . H e a 0115500 p P t r \r \t l e t E n t L e n 0115520 s = I S > > I S . E L L P t 0115540 r \r 376 001 \0 347 360 \r \t l e t S o n 0115560 L e n = E n t r y L e n g t 0115600 h ( I S , E n t r y ) \r \r \t l 0115620 e t S o n = E m p t y L o 0115640 c \r \t l e t F a t h e r = 0115660 n i l \r \t l e t F E = n i 0115700 l \r \r \t w h i l e v a l o f \r 0115720 \t \t [ F a t h e r = S o n 0115740 r s h i f t 1 \t / / S o n 0115760 / 2 \r \t \t i f F a t h e r l 0116000 e 0 t h e n r e s u l t i 0116020 s f a l s e \r \t \t F E = H 0116040 e a p > > H P . H e a p E n t ^ 0116060 F a t h e r \r \t \t r e s u l t i 0116100 s ( E n t r y L e n g t h ( I 0116120 S , F E ) g r S o n L e n 0116140 ) \r \t \t ] \r \t 376 001 \0 233 343 0116160 d o \r \t \t [ H e a p > > H P . 0116200 H e a p E n t ^ S o n = F E 0116220 \r \t \t E n t L e n s > > E L L . 0116240 H e a p P o s ^ F E = S o n 0116260 \r \t \t S o n = F a t h e r \r 0116300 \t \t ] \r \r \t H e a p > > H P . H 0116320 e a p E n t ^ S o n = E n t 0116340 r y \r \t E n t L e n s > > E L L 0116360 . H e a p P o s ^ E n t r y = 0116400 S o n \r \t ] \r \r \r a n d R e 0116420 m o v e F r o m H e a p ( I S , 0116440 E n t r y ) b e \r \r \t [ l 0116460 e t H e a p = I S > > I S 0116500 . H e a p P t r \r \t l e t E n 0116520 t L e n s = I S > > I S . E 0116540 L L P t r \r \r \t l e t 376 001 \0 342 0116560 H H e a p P o s = E n t L e 0116600 n s > > E L L . H e a p P o s ^ 0116620 E n t r y \r \t I S > > I S . H e 0116640 a p S i z e = I S > > I S . 0116660 H e a p S i z e - 1 \r \t i f H 0116700 e a p P o s g r I S > > I S 0116720 . H e a p S i z e t h e n r 0116740 e t u r n \t / / O u r g u y 0116760 w a s l a s t \r \r \t l e t 0117000 R e p l a c e m e n t E n t r y 0117020 = H e a p > > H P . H e a p 0117040 E n t ^ ( I S > > I S . H e a p 0117060 S i z e + 1 ) \r \t t e s t E n 0117100 t r y L e n g t h ( I S , R e 0117120 p l a c e m e n t E n t r y ) 0117140 l e \r \t \t E n t r y L e n g t h 0117160 ( 376 001 \0 \b 210 I S , E n t r y ) 0117200 \r \r \t i f s o \t T r i c k l e D 0117220 o w n ( I S , H e a p P o s , 0117240 R e p l a c e m e n t E n t r 0117260 y ) \r \t i f n o t \t S i f t U p 0117300 ( I S , H e a p P o s , R e 0117320 p l a c e m e n t E n t r y ) \r 0117340 \t ] \r \r \r a n d S i f t U p ( 0117360 I S , E m p t y L o c , E n 0117400 t r y ) b e \r \r \t [ l e t 0117420 H e a p = I S > > I S . H e 0117440 a p P t r \r \t l e t H e a p S 0117460 i z e = I S > > I S . H e a 0117500 p S i z e \r \t l e t E n t L e 0117520 n s = I S > > I S . E L L P 0117540 t r \r \r \t l e t E E L e n = 0117560 E n t r y 376 001 \0 k 206 L e n g t 0117600 h ( I S , E n t r y ) \r \r \t w 0117620 h i l e t r u e d o \r \t \t [ 0117640 l e t S o n = E m p t y 0117660 L o c + E m p t y L o c \r \t \t l 0117700 e t E R S o n = n i l \r \r 0117720 \t \t i f S o n g r H e a p 0117740 S i z e t h e n b r e a k \r 0117760 \r \t \t l e t E S o n = H e 0120000 a p > > H P . H e a p E n t ^ S 0120020 o n \r \t \t i f S o n l s H 0120040 e a p S i z e t h e n \r \t \t \t 0120060 [ l e t E R S o n = H e 0120100 a p > > H P . H e a p E n t ^ ( 0120120 S o n + 1 ) \r \t \t \t i f E n t 0120140 r y L e n g t h ( I S , E R S 0120160 o n ) l s \r \t \t \t \t 376 001 \0 231 255 0120200 E n t r y L e n g t h ( I S , 0120220 E S o n ) d o \r \t \t \t \t \t [ 0120240 S o n = S o n + 1 \r \t \t \t \t 0120260 \t E S o n = E R S o n \r \t \t 0120300 \t \t \t ] \r \t \t \t ] \r \r \t \t i f 0120320 E n t r y L e n g t h ( I S , 0120340 H e a p > > H P . H e a p E n t 0120360 ^ S o n ) g e E E L e n t 0120400 h e n \r \t \t \t b r e a k \r \r \t \t 0120420 H e a p > > H P . H e a p E n t 0120440 ^ E m p t y L o c = E S o n 0120460 \r \t \t E n t L e n s > > E L L . 0120500 H e a p P o s ^ E S o n = E 0120520 m p t y L o c \r \r \t \t E m p t y 0120540 L o c = S o n \r \t \t ] \r \r \t 0120560 H e a p > > H P . H e a p E n t 0120600 376 \0 < H 267 ^ E m p t y L o c = 0120620 E n t r y \r \t E n t L e n s > 0120640 > E L L . H e a p P o s ^ E n t 0120660 r y = E m p t y L o c \r \t ] 0120700 \r 377 \0 \0 B T r e e D e l . b c p 0120720 l \0 373 231 005 303 + \0 \0 376 001 \0 [ F / / 0120740 \t B - T r e e M a i n t e n a 0120760 n c e R o u t i n e s \r / / 0121000 C o p y r i g h t X e r o x 0121020 C o r p o r a t i o n 1 9 7 9 0121040 , 1 9 8 1 , 1 9 8 2 \r \r \r / 0121060 / \t B T R E E D E L . B C P L 0121100 - - R o u t i n e s f o r 0121120 d e l e t i n g f r o m B 0121140 - T r e e s \r \r / / \t l a s t 0121160 e d i t e d M a y 9 , 1 9 0121200 8 2 5 : 1 0 P M b y T 0121220 a f t \r \r g e t " b t r e e . 0121240 d e c l " \r \r e x t e r n a l \r 0121260 \t [ A l l o c a t e \t / / D 0121300 e f i n e d b y O S \r \t F r 0121320 e e \r \t D e f a u l t A r g 376 001 0121340 \0 002 221 s \r \t D v e c \r \r \t R e a 0121360 d B T r e e P a g e \t / / d e 0121400 f i n e d b y O p e n B T r 0121420 e e \r \t W r i t e B T r e e P a 0121440 g e \r \t L o c k B T r e e P t r 0121460 \r \t U n l o c k B T r e e P t r 0121500 \r \t F r e e B T r e e P a g e \r 0121520 \t B T r e e B u g \r \r \t P a t h 0121540 R e c L E \t / / D e f i n e d 0121560 b y B T r e e R e a d . b c 0121600 p l \r \t R e a d P a g e A n d L 0121620 o c k B T r e e P t r \r \t P o p 0121640 S t a c k \r \t R e p a i r O f f 0121660 s e t s \r \t B a c k U p O n e R 0121700 e c o r d \r \r \t R e m o v e E n 0121720 t r y \t / / D e f i n e d b 0121740 y B 376 001 \0 201 S T r e e W r t . 0121760 b c p l \r \t M a k e E n t S e q 0122000 E n t \r \t A p p e n d E n t S e 0122020 q E n t \r \t P u s h E n t S e q 0122040 E n t \r \t I n s e r t R e c o r 0122060 d s \r \t F a b r i c a t e I S \r 0122100 \t F r e e I S \r \t ] \r \r e x t e 0122120 r n a l \r \t [ D e l e t e K e 0122140 y \t / / D e f i n e d i n 0122160 B T R E E D E L . B C P L \r \t ] 0122200 \r \r \r l e t D e l e t e K e y 0122220 ( T r e e , K e y , C K R t 0122240 n , P a t h S t k , U s e E 0122260 x i s t i n g P a t h ; n u m 0122300 a r g s n a ) = v a l o f 0122320 \r \r \t [ D e f a u l t A r g s 0122340 ( l v n a , 376 001 \0 D 016 - 2 , 0122360 T r e e > > T R E E . C o m p 0122400 a r e K e y R t n , s i z e 0122420 P S / 1 6 , f a l s e ) \r \t i 0122440 f P a t h S t k e q s i z 0122460 e P S / 1 6 t h e n \r \t \t [ 0122500 D v e c ( D e l e t e K e y , 0122520 l v P a t h S t k ) ; U s 0122540 e E x i s t i n g P a t h = 0122560 f a l s e ] \r \r \t P a t h R e 0122600 c L E ( T r e e , P a t h S t 0122620 k , U s e E x i s t i n g P a 0122640 t h , K e y , C K R t n ) \r 0122660 \r \t l e t O r i g P a t h S t 0122700 k T o p = P a t h S t k > > 0122720 P S . P a t h S t k T o p \r \t i 0122740 f O r i g P a t h S t k 376 001 \0 0122760 d ] T o p e q 0 t h e n 0123000 r e s u l t i s f a l s e \r \r 0123020 \t l e t S P = l v ( P a 0123040 t h S t k > > P S . P S E ^ O r 0123060 i g P a t h S t k T o p ) \r \r \t 0123100 l e t P a g e P t r = n i 0123120 l \r \t R e a d P a g e A n d L o 0123140 c k B T r e e P t r ( T r e e , 0123160 S P > > P S E . P a g e N o , 0123200 l v P a g e P t r ) \r \t i f 0123220 C K R t n ( K e y , l v ( 0123240 ( P a g e P t r + S P > > P S E 0123260 . L a s t O f f s e t ) \r \t \t \t 0123300 > > B T E . R e c o r d ) ) n 0123320 e 0 t h e n \r \t \t [ U n l 0123340 o c k B T r e e P t r ( T r e e 0123360 , 376 001 \0 y 362 l v P a g e P t 0123400 r ) \r \t \t r e s u l t i s f a 0123420 l s e \r \t \t ] \r \r \t T r e e > > 0123440 T R E E . R e c o r d C o u n t 0123460 = T r e e > > T R E E . R e 0123500 c o r d C o u n t - 1 \r \t T r e 0123520 e > > T R E E . S t a t e D i r 0123540 t y = t r u e \r \t T r e e > 0123560 > T R E E . V e r s i o n = 0123600 T r e e > > T R E E . V e r s i 0123620 o n + 1 \r \r \t B a c k U p O n e 0123640 R e c o r d ( T r e e , S P ) 0123660 / / o f f s e t s h o u l 0123700 d i n d e x d e l e t i o n 0123720 v i c t i m \r \t l e t D e s 0123740 c e n d a n t P g = ( P a g 0123760 e P t r + S P 376 001 \0 032 304 > > P S 0124000 E . L a s t O f f s e t ) > > B 0124020 T E . G r P t r \r \t l e t D S 0124040 P = S P \r \r \t w h i l e D 0124060 e s c e n d a n t P g n e E 0124100 m p t y d o \r \t \t [ / / d 0124120 e l e t i o n s u r r o g a t 0124140 e i s g r e a t e s t k e 0124160 y l e s s t h a n v i c t 0124200 i m ' s \r \t \t P a t h S t k > > 0124220 P S . P a t h S t k T o p = 0124240 P a t h S t k > > P S . P a t h 0124260 S t k T o p + 1 \r \t \t D S P = 0124300 l v ( P a t h S t k > > P S 0124320 . P S E ^ ( P a t h S t k > > P 0124340 S . P a t h S t k T o p ) ) \r \t 0124360 \t D S P > > P S E . P a 376 001 \0 Q 0124400 364 g e N o = D e s c e n d a 0124420 n t P g \r \t \t P a g e P t r = 0124440 0 \r \t \t P a g e P t r = R 0124460 e a d B T r e e P a g e ( T r e 0124500 e , D e s c e n d a n t P g ) 0124520 \r \t \t D S P > > P S E . O f f s 0124540 e t = ( T r e e > > T R E E 0124560 . P a g e L e n g t h ) - \r \t \t 0124600 \t ( P a g e P t r > > B T P . F 0124620 r e e W o r d s ) \r \t \t D S P > 0124640 > P S E . L a s t O f f s e t 0124660 = R e c 1 O f f s e t \r \t \t D 0124700 S P > > P S E . N e x t T o L a 0124720 s t O f f s e t = R e c 0 O 0124740 f f s e t \r \t \t R e p a i r O f 0124760 f s e t s ( T r e e , D S P ) 0125000 \r 376 001 \0 \t Z \t \t D S P > > P S E 0125020 . E S L F r o n t = E m p t 0125040 y \r \t \t D S P > > P S E . E S L 0125060 R e a r = E m p t y \r \t \t D 0125100 S P > > P S E . L e a s t S o n 0125120 = E m p t y \r \r \t \t D e s c 0125140 e n d a n t P g = ( P a g e 0125160 P t r + D S P > > P S E . L a s 0125200 t O f f s e t ) > > B T E . G r 0125220 P t r \r \t \t ] \r \r \t U n l o c k 0125240 B T r e e P t r ( T r e e , l 0125260 v P a g e P t r ) \r \r \t t e s 0125300 t P a t h S t k > > P S . P a 0125320 t h S t k T o p g r O r i g 0125340 P a t h S t k T o p \r \t i f s o 0125360 \t [ B a c k U p O n e R e c o 0125400 r d ( T r e 376 001 \0 226 254 e , D S 0125420 P ) / / o f f s e t s h o 0125440 u l d i n d e x s u r r o g 0125460 a t e \r \t \t l e t L e a f P a 0125500 g e E S E = R e m o v e E n 0125520 t r y ( T r e e , D S P ) \r \t 0125540 \t l e t N o n L e a f P a g e 0125560 E S E = R e m o v e E n t r 0125600 y ( T r e e , S P , \r \t \t \t l 0125620 v ( L e a f P a g e E S E > > 0125640 E S L E . E n t S e q P ) > > B 0125660 T E . G r P t r ) \r \t \t A p p e 0125700 n d E n t S e q E n t ( S P , 0125720 L e a f P a g e E S E ) \r \t \t F 0125740 r e e ( T r e e > > T R E E . Z 0125760 o n e , N o n L e a f P a g e 0126000 E S E ) \r \t \t ] \r \t i 376 001 \0 326 334 0126020 f n o t \t [ F r e e ( T r e e 0126040 > > T R E E . Z o n e , R e m 0126060 o v e E n t r y ( T r e e , S 0126100 P ) ) \r \t \t ] \r \r \t l e t I S 0126120 = F a b r i c a t e I S ( T 0126140 r e e , P a t h S t k ) \r \r \t 0126160 w h i l e P a t h S t k > > P 0126200 S . P a t h S t k T o p g e 0126220 0 & \r \t \t ( F a t h e r M a y 0126240 N e e d W o r k ( T r e e , P 0126260 a t h S t k , I S ) ? \r \t \t \t 0126300 t r u e , \r \t \t \t P a t h S t k 0126320 > > P S . P a t h S t k T o p 0126340 g r O r i g P a t h S t k T o 0126360 p ) \r \t \t d o \r \t \t [ P o p S 0126400 t a c k ( P a t h S t k ) \r \t \t 0126420 376 001 \0 n 257 ] \r \r \t F r e e I S ( 0126440 I S ) \r \t P a t h S t k > > P S 0126460 . P a t h S t k T o p = 0 \r 0126500 \t r e s u l t i s t r u e \r \t 0126520 ] \r \r \r a n d F a t h e r M a 0126540 y N e e d W o r k ( T r e e , 0126560 P a t h S t k , I S ) = v 0126600 a l o f \r \r \t [ / / T h i s 0126620 c o d e a s s u m e s t h 0126640 a t \r \t / / t h e s o n p 0126660 a g e i s p o i n t e d t 0126700 o b y t h e f a t h e r 0126720 p a g e ' s \r \t / / L a s t O 0126740 f f s e t i n d e x ' s G r 0126760 P t r , a n d t h a t t h 0127000 i s c o n d i t i o n i s \r 0127020 \t / / p 376 001 \0 347 D r e s e r v 0127040 e d b y I n s e r t R e c o 0127060 r d s . \r \t \r \r \t l e t N e e 0127100 d s W o r k = C h a n g e I 0127120 n F a t h e r ( T r e e , P a 0127140 t h S t k , I S ) \r \r \t l e t 0127160 P a t h S t k T o p = P a 0127200 t h S t k > > P S . P a t h S t 0127220 k T o p \r \t l e t S P = l 0127240 v ( P a t h S t k > > P S . P 0127260 S E ^ P a t h S t k T o p ) \r \t 0127300 l e t C u r P a g e = S P 0127320 > > P S E . P a g e N o \r \t l e 0127340 t C u r P t r = n i l \r \t 0127360 R e a d P a g e A n d L o c k B 0127400 T r e e P t r ( T r e e , S P 0127420 > > P S E . P a g e 376 001 \0 360 016 N 0127440 o , l v C u r P t r ) \r \t l 0127460 e t F r e e W o r d s = C 0127500 u r P t r > > B T P . F r e e W 0127520 o r d s \r \r \t i f P a t h S t 0127540 k T o p e q 1 & F r e e 0127560 W o r d s e q I S > > I S . 0127600 M a x F r e e W o r d s t h e 0127620 n \r \t \t / / B y e - b y e , 0127640 o l d r o o t p a g e ! \r \t 0127660 \t [ T r e e > > T R E E . R o 0127700 o t P a g e = C u r P t r > 0127720 > B T P . M i n P t r \r \t \t T r 0127740 e e > > T R E E . S t a t e D i 0127760 r t y = t r u e \r \t \t U n l 0130000 o c k B T r e e P t r ( T r e e 0130020 , l v C u r P t r ) \r \t \t 376 0130040 001 \0 207 ` F r e e B T r e e P a g 0130060 e ( T r e e , S P > > P S E . 0130100 P a g e N o ) \r \t \t r e s u l t 0130120 i s f a l s e \r \t \t ] \r \r \t i 0130140 f P a t h S t k T o p e q 0130160 1 % \r \t \t ( I S > > I S . M a 0130200 x F r e e W o r d s - F r e e W 0130220 o r d s ) g e I S > > I S . 0130240 P r e t t y F u l l t h e n \r 0130260 \t \t \t [ U n l o c k B T r e e 0130300 P t r ( T r e e , l v C u r 0130320 P t r ) \r \t \t \t r e s u l t i s 0130340 N e e d s W o r k \r \t \t \t ] \r 0130360 \r \t A p p e n d E n t S e q E n 0130400 t ( S P , \r \t \t \t M a k e E n t 0130420 S e q E n t ( T r e e > > T R E 0130440 E . Z o 376 001 \0 351 Y n e , C u r 0130460 P t r + R e c 1 O f f s e t , \r 0130500 \t \t \t \t I S > > I S . M a x F r 0130520 e e W o r d s - F r e e W o r d 0130540 s ) ) \r \r \t l e t S F P = 0130560 l v ( P a t h S t k > > P S . 0130600 P S E ^ ( P a t h S t k T o p - 0130620 1 ) ) \r \t l e t O t h e r P t 0130640 r = n i l \r \t R e a d P a g 0130660 e A n d L o c k B T r e e P t r 0130700 ( T r e e , S F P > > P S E . 0130720 P a g e N o , l v O t h e r 0130740 P t r ) \r \t l e t F a t h e r 0130760 O f f s e t = S F P > > P S 0131000 E . O f f s e t \r \t l e t F a 0131020 t h e r F r e e W o r d s = 0131040 O t h e r P t r > 376 001 \0 221 r > B 0131060 T P . F r e e W o r d s \r \r \t t 0131100 e s t ( ( F a t h e r O f f s 0131120 e t - R e c 1 O f f s e t ) l 0131140 s ( I S > > I S . M a x F r e 0131160 e W o r d s - \r \t \t F a t h e r 0131200 F r e e W o r d s ) ) % ( S 0131220 F P > > P S E . E S L F r o n t 0131240 n e E m p t y ) \r \r \t i f s 0131260 o \t / / T h e c u r r e n t 0131300 p a g e h a s a r i g h 0131320 t b r o t h e r \r \t \t [ l e 0131340 t R t B r o P g = n i l \r 0131360 \t \t A p p e n d E n t S e q E n 0131400 t ( S P , R e m o v e E n t r 0131420 y ( T r e e , S F P , l v 0131440 R t B r o P g ) ) \r \r \t \t i 376 001 0131460 \0 201 \f f ( O t h e r P t r + S 0131500 F P > > P S E . L a s t O f f s 0131520 e t ) > > B T E . G r P t r n 0131540 e C u r P a g e t h e n \r \t 0131560 \t \t B T r e e B u g ( T r e e , 0131600 e c M c C r e i g h t W a s W 0131620 r o n g ) \r \t \t ( O t h e r P t 0131640 r + S F P > > P S E . L a s t O 0131660 f f s e t ) > > B T E . G r P t 0131700 r = R t B r o P g \r \r \t \t O 0131720 t h e r P t r = 0 \r \t \t O t 0131740 h e r P t r = W r i t e B T 0131760 r e e P a g e ( T r e e , R t 0132000 B r o P g ) \r \t \t O t h e r P t 0132020 r > > B T P . M i n P t r = 0132040 C u r P t r > > B T P . M i n P 0132060 t r \r 376 001 \0 276 342 \r \t \t S P > > P 0132100 S E . P a g e N o = R t B r 0132120 o P g \r \t \t S P > > P S E . O f 0132140 f s e t = R e c 1 O f f s e 0132160 t \r \t \t S P > > P S E . L a s t 0132200 O f f s e t = R e c 0 O f f 0132220 s e t \r \t \t S P > > P S E . N e 0132240 x t T o L a s t O f f s e t = 0132260 E m p t y \r \r \t \t C u r P t r 0132300 = 0 \r \t \t F r e e B T r e e 0132320 P a g e ( T r e e , C u r P a 0132340 g e ) \r \t \t ] \r \r \t i f n o t \t 0132360 / / T h e c u r r e n t p 0132400 a g e s u r e l y h a s a 0132420 l e f t b r o t h e r . \r \t 0132440 \t [ B a c k U p O n e R e c o 0132460 r d ( T r e e , 376 001 \0 n 270 S F 0132500 P ) / / o f f s e t s h o 0132520 u l d i n d e x l a s t r 0132540 e c \r \t \t P u s h E n t S e q E 0132560 n t ( S P , R e m o v e E n t 0132600 r y ( T r e e , S F P ) ) \r \r 0132620 \t \t C u r P t r = 0 \r \t \t F 0132640 r e e B T r e e P a g e ( T r e 0132660 e , C u r P a g e ) \r \r \t \t C 0132700 u r P a g e = ( O t h e r P 0132720 t r + S F P > > P S E . L a s t 0132740 O f f s e t ) \r \t \t \t \t \t > > B 0132760 T E . G r P t r \r \t \t S P > > P 0133000 S E . P a g e N o = C u r P 0133020 a g e \r \t \t C u r P t r = R 0133040 e a d B T r e e P a g e ( T r e 0133060 e , C u r P a g e ) \r \t 376 001 \0 0133100 t 207 \t S P > > P S E . O f f s e 0133120 t = R e c 1 O f f s e t + \r 0133140 \t \t \t ( I S > > I S . M a x F r 0133160 e e W o r d s - C u r P t r > > 0133200 B T P . F r e e W o r d s ) \r \t 0133220 \t S P > > P S E . L a s t O f f 0133240 s e t = R e c 1 O f f s e t 0133260 \r \t \t S P > > P S E . N e x t T 0133300 o L a s t O f f s e t = R e 0133320 c 0 O f f s e t \r \t \t R e p a i 0133340 r O f f s e t s ( T r e e , S 0133360 P ) \r \t \t ] \r \r \t U n l o c k B 0133400 T r e e P t r ( T r e e , l v 0133420 O t h e r P t r ) \r \t U n l o 0133440 c k B T r e e P t r ( T r e e , 0133460 l v C u r P t r ) \r \t C h a 0133500 n g 376 001 \0 ] e I n F a t h e r 0133520 ( T r e e , P a t h S t k , 0133540 I S ) \r \t r e s u l t i s t r 0133560 u e \r \t ] \r \r \r a n d C h a n 0133600 g e I n F a t h e r ( T r e e , 0133620 P a t h S t k , I S ) = 0133640 v a l o f \r \r \t [ l e t S P 0133660 = l v ( P a t h S t k > > 0133700 P S . P S E ^ ( P a t h S t k > 0133720 > P S . P a t h S t k T o p ) ) 0133740 \r \t i f S P > > P S E . E S L 0133760 F r o n t e q E m p t y t 0134000 h e n r e s u l t i s f a l 0134020 s e \r \t I n s e r t R e c o r d 0134040 s ( T r e e , P a t h S t k , 0134060 I S ) \r \t i f P a t h S t k 0134100 > > P S . P a 376 \0 m 255 [ t h S t 0134120 k T o p e q 0 t h e n r 0134140 e s u l t i s f a l s e \r \t r 0134160 e s u l t i s P a t h S t k > 0134200 > P S . P S E ^ ( P a t h S t k 0134220 > > P S . P a t h S t k T o p - 0134240 1 ) . E S L F r o n t n e E 0134260 m p t y \r \t ] \r \r 377 \0 \0 B T r e 0134300 e C h e c k . b c p l \0 373 230 - P 0134320 0 \0 \0 376 001 \0 026 313 / / \t B - T r e 0134340 e M a i n t e n a n c e R o 0134360 u t i n e s \r / / C o p y r i 0134400 g h t X e r o x C o r p o r 0134420 a t i o n 1 9 7 9 , 1 9 8 1 0134440 \r \r / / \t B T r e e C h e c k . 0134460 b c p l - - R o u t i n e 0134500 s f o r c h e c k i n g B 0134520 - T r e e s \r \r / / \t l a s t 0134540 e d i t e d N o v e m b e r 0134560 2 6 , 1 9 8 1 1 2 : 0 6 0134600 P M b y T a f t \r \r g e t 0134620 " b t r e e . d e c l " \r \r e x 0134640 t e r n a l \r \t [ D e f a u l 0134660 t A r g s \r \t S y s E r r \r \t T 0134700 r u e P r e d i c a t e \r \r \t L 0134720 o c k B T r e e 376 001 \0 \f Z P t r 0134740 \t / / d e f i n e d i n O 0134760 p e n B T r e e \r \t U n l o c k 0135000 B T r e e P t r \r \r \t M a p T r 0135020 e e \t / / d e f i n e d i n 0135040 B T r e e R e a d \r \t ] \r \r \r 0135060 e x t e r n a l \r \t [ \r \t C h e 0135100 c k T r e e \t / / o u t g o i 0135120 n g p r o c e d u e s \r \r \t G 0135140 a p B e t w e e n C h e c k s 0135160 / / o u t g o i n g s t a t 0135200 i c s \r \t ] \r \r \r s t a t i c \t 0135220 \r \t [ G a p B e t w e e n C h 0135240 e c k s = 0 \r \t G a p T o N 0135260 e x t C h e c k = 0 \r \t ] \r 0135300 \r \r s t r u c t u r e C S : \r 0135320 \t [ l a s t R e c o r d 376 001 \0 0135340 s \0 w o r d \r \t R e c o r d C 0135360 o u n t w o r d \r \t C o m p a 0135400 r e R e c o r d s w o r d \r \t 0135420 E r r o r R t n w o r d \r \t ] 0135440 \r \r \r l e t C h e c k T r e e 0135460 ( T r e e , C K R t n , f o 0135500 r c e C h e c k , E r r o r R 0135520 t n ; n u m a r g s n a ) 0135540 = v a l o f \r \r \t [ D e f a 0135560 u l t A r g s ( l v n a , - 0135600 1 , T r e e > > T R E E . C o 0135620 m p a r e K e y R t n , f a l 0135640 s e , S y s E r r ) \r \r \t u n 0135660 l e s s f o r c e C h e c k 0135700 d o \r \t \t [ i f G a p B e t 0135720 w e e n C h e c k s e q 0 0135740 t h 376 001 \0 365 022 e n r e s u l t 0135760 i s t r u e \r \t \t i f G a p 0136000 T o N e x t C h e c k n e 0 0136020 t h e n \r \t \t \t [ G a p T o 0136040 N e x t C h e c k = G a p T 0136060 o N e x t C h e c k - 1 \r \t \t \t 0136100 r e s u l t i s t r u e \r \t \t 0136120 \t ] \r \t \t G a p T o N e x t C h 0136140 e c k = G a p B e t w e e n 0136160 C h e c k s - 1 \r \t \t ] \r \r \t l 0136200 e t C S = v e c s i z e 0136220 C S / 1 6 \r \t C S > > C S . l 0136240 a s t R e c o r d = E m p t 0136260 y \r \t C S > > C S . R e c o r d 0136300 C o u n t = 0 \r \t C S > > C 0136320 S . C o m p a r e R e c o r d s 0136340 = C K R t 376 001 \0 235 331 n \r \t C 0136360 S > > C S . E r r o r R t n = 0136400 E r r o r R t n \r \r \t L o c k 0136420 B T r e e P t r ( T r e e , l 0136440 v ( C S > > C S . l a s t R e 0136460 c o r d ) ) \r \t l e t r e s u 0136500 l t = M a p T r e e ( T r e 0136520 e , 0 , C h e c k P a i r , 0136540 C S , \r \t \t T r u e P r e d i 0136560 c a t e , t r u e ) / / 0136600 T r u e P r e d i c a t e a l 0136620 w a y s r e t u r n s - 1 \r 0136640 \t U n l o c k B T r e e P t r ( 0136660 T r e e , l v ( C S > > C S 0136700 . l a s t R e c o r d ) ) \r \r \t 0136720 i f T r e e > > T R E E . R e 0136740 c o r d C o u n t n e 376 001 \0 i 0136760 022 C S > > C S . R e c o r d C 0137000 o u n t t h e n \r \t \t [ E r 0137020 r o r R t n ( T r e e , e c R 0137040 e c o r d C o u n t s D i s a g 0137060 r e e ) \r \t \t T r e e > > T R E 0137100 E . R e c o r d C o u n t = 0137120 C S > > C S . R e c o r d C o u 0137140 n t \r \t \t T r e e > > T R E E . 0137160 S t a t e D i r t y = t r u 0137200 e \r \t \t r e s u l t i s f a l 0137220 s e \r \t \t ] \r \r \t r e s u l t i 0137240 s r e s u l t \r \t ] \r \r \r a n 0137260 d C h e c k P a i r ( t h i s 0137300 R e c o r d , C S , P a t h 0137320 S t k ) = v a l o f \r \r \t [ 0137340 C S > > C S . R e c o r d C o 0137360 u 376 001 \0 : 225 n t = C S > > C 0137400 S . R e c o r d C o u n t + 1 \r 0137420 \r \t i f C S > > C S . l a s t 0137440 R e c o r d n e E m p t y 0137460 t h e n \r \t \t i f ( C S > > C 0137500 S . C o m p a r e R e c o r d s 0137520 ) ( C S > > C S . l a s t R e c 0137540 o r d , t h i s R e c o r d ) 0137560 g e 0 t h e n \r \t \t \t [ 0137600 ( C S > > C S . E r r o r R t n 0137620 ) ( P a t h S t k , e c R e c 0137640 o r d s O u t O f O r d e r ) \r 0137660 \t \t \t r e s u l t i s f a l s 0137700 e \r \t \t \t ] \r \t C S > > C S . l 0137720 a s t R e c o r d = t h i s 0137740 R e c o r d \r \t r e s u l t i s 0137760 t r u e \r 376 \0 003 \t ` \t ] \r 377 \0 0140000 \0 I f s B T r e e R e s . b c p 0140020 l \0 373 226 < _ # \0 \0 376 001 \0 362 Y / / 0140040 I f s B T r e e R e s . b c p 0140060 l - - R e s i d e n t p o 0140100 r t i o n o f I F S i n t 0140120 e r f a c e t o t h e B - 0140140 T r e e p a c k a g e \r / / 0140160 C o p y r i g h t X e r o x 0140200 C o r p o r a t i o n 1 9 7 9 0140220 , 1 9 8 0 \r \r / / L a s t 0140240 m o d i f i e d N o v e m b e 0140260 r 1 4 , 1 9 8 0 1 1 : 5 0140300 7 A M b y T a f t \r \r g e 0140320 t " B T r e e . d e c l " \r g 0140340 e t " I f s V M e m . d e c l 0140360 " \r \r e x t e r n a l \r [ \r / / 0140400 O u t g o i n g p r o c e d 0140420 u r e s \r B V W R P ; B V 376 001 0140440 \0 233 243 R R P ; B t L o c k C e 0140460 l l ; B t U n l o c k C e l l 0140500 \r \r / / I n c o m i n g p r 0140520 o c e d u r e s \r @ V R R P ; 0140540 @ V W R P \r L o c k C e l l ; 0140560 U n l o c k C e l l ; Y i e l 0140600 d ; D e f a u l t A r g s ; 0140620 U s c ; I F S E r r o r \r ] \r 0140640 \r s t r u c t u r e F C E : \t 0140660 \t / / F r e e c h a i n e 0140700 n t r y ( d e f s h a r e d 0140720 w i t h I f s B T r e e S w 0140740 a p ) \r [ \r F r e e M a r k e r 0140760 w o r d \r n e x t w o r d \r 0141000 ] \r \r m a n i f e s t e c B t 0141020 O u t O f V M e m = 2 8 \r m 0141040 a n i 376 001 \0 z 336 f e s t e c B 0141060 t R e f F r e e P a g e = 3 0141100 0 \r \r / / P r o c e d u r e s 0141120 t o a c c e s s a s p e 0141140 c i f i e d p a g e o f t 0141160 h e B - T r e e . \r / / T h 0141200 e f i r s t 1 0 2 4 w o r 0141220 d s o f t h e f i l e a 0141240 r e r e s e r v e d f o r 0141260 t h e f i l e m a p , r e 0141300 g a r d l e s s \r / / o f t 0141320 h e p h y s i c a l p a g e 0141340 s i z e o f t h e d i s 0141360 k o r t h e l o g i c a l 0141400 B - T r e e p a g e s i z 0141420 e . \r / / T h e f i r s t 0141440 v i r t u a l 376 001 \0 \ f p a g 0141460 e i n t h e t r e e ( t 0141500 h e s t a t e p a g e ) i 0141520