COMPILATION LISTING OF SEGMENT mrds_rst_tree_search Compiled by: Multics PL/I Compiler, Release 28e, of February 14, 1985 Compiled at: Honeywell Multics Op. - System M Compiled on: 04/18/85 1105.1 mst Thu Options: optimize map 1 /* *********************************************************** 2* * * 3* * * 4* * Copyright, (C) Honeywell Information Systems Inc., 1981 * 5* * * 6* * * 7* *********************************************************** */ 8 9 /* ****************************************************** 10* * * 11* * * 12* * Copyright (c) 1972 by Massachusetts Institute of * 13* * Technology and Honeywell Information Systems, Inc. * 14* * * 15* * * 16* ****************************************************** */ 17 18 mrds_rst_tree_search: procedure (key, root_ptr, node_ptr, parent_ptr, success); 19 20 21 /* HISTORY: 22* 23* originally written by jim gray - - july 1978 24* 25**/ 26 27 /* DESCRIPTION: 28* Threaded binary tree search 29* Given a pointer to the desired list, do a binary search for the key. 30* Return either a not found indication, 31* or a found indication with a pointer to the key node, 32* and a pointer to it's parent */ 33 34 /* PARAMETERS: 35* 36* key - - (input) word to be searched for as key to tree node 37* 38* root_ptr - - (input) pointer to root node of desired tree 39* 40* node_ptr - - (output) pointer to node containing key when found, 41* else root pointer pointer 42* 43* parent_ptr - - (output) pointer to direct tree parent when key node found, 44* else pointer to prospective parent for insertion of key 45* 46* success - - (output) bit value indicating key was found in tree(on), 47* or that place for it's insertion was found(off) 48* 49**/ 50 51 52 /* Initialize search loop 53* note: parent_ptr is root_ptr when no dummy head exists, 54* or when the dummy head node left link is a thread 55* thus indicating a empty tree */ 56 57 parent_ptr = root_ptr; 58 success = "0"b; 59 60 /* if dummy node at head of tree missing, 61* we fail since tree was never built */ 62 63 if root_ptr = null () then ; 64 else do; 65 node_ptr = root_ptr -> node.left.link; 66 thread = root_ptr -> node.left.thread; 67 68 69 /* Search the tree while the data key is not found, 70* and branches remain to be searched . 71* failure to make even one loop pass means the tree is empty, 72* because the dummy head node left link is a thread to itself */ 73 74 do while (^thread & ^success); 75 76 /* Branch left for smaller or right for larger keys. 77* If key matches, note success and remember pointers. */ 78 79 if key > node_ptr -> node.key then do; 80 thread = node_ptr -> node.right.thread; 81 parent_ptr = node_ptr; 82 node_ptr = node_ptr -> node.right.link; 83 end; 84 85 else if key < node_ptr -> node.key then do; 86 thread = node_ptr -> node.left.thread; 87 parent_ptr = node_ptr; 88 node_ptr = node_ptr -> node.left.link; 89 end; 90 91 else success = "1"b; 92 93 end; 94 95 end; 96 97 dcl null builtin; 98 99 1 1 /* BEGIN INCLUDE FILE mrds_rst_tree.incl.pl1 jeg 7/19/78 */ 1 2 1 3 /* common declarations for threaded binary tree routines 1 4* 1 5* The tree maintains an inorder list of it's keys. 1 6* this means that for a given node, any key in it's left subtree 1 7* is "less" than the given node's key and that any key in it's 1 8* right subtree is "greater" than the given node's key. 1 9* 1 10* Threads are maintained to allow fast and easy traversal of the tree. 1 11* threads occupy the position of null pointers of an straight binary tree, 1 12* thus they only occur in leaf nodes. 1 13* left threads point to that nodes inorder predecessor. 1 14* right threads point to that nodes inorder successor. 1 15* 1 16* note: root_ptr must be passed by reference 1 17* ( not by value ) so it can be changed . 1 18* Also, each parameter must be a different 1 19* variable. The same variable used for two 1 20* or more arguments when any of the tree 1 21* routines are called will produce errors */ 1 22 1 23 1 24 declare key char (32) aligned ; /* data key directing search */ 1 25 1 26 declare root_ptr ptr ; /* pointer to head of desired list */ 1 27 declare node_ptr ptr ; /* pointer to key node, when success */ 1 28 declare parent_ptr ptr ; /* pointer to direct parent of current node */ 1 29 declare data_ptr ptr ; /* pointer from tree node to data structure headed by node */ 1 30 declare successor_ptr ptr ; /* pointer to inorder successor of current node in tree */ 1 31 declare successor_parent_ptr ptr ; /* pointer to immediate tree parent of inorder successor node */ 1 32 declare predecessor_ptr ptr ; /* pointer to inorder predecessor of current node */ 1 33 declare predecessor_parent_ptr ptr ; /* pointer to direct parent of predecessor */ 1 34 declare area_ptr ptr ; /* pointer to based area for node allocation/freeing */ 1 35 1 36 declare work_area area based (area_ptr) ; /* area of storage for tree */ 1 37 1 38 declare success bit (1) ; /* on if operation successful */ 1 39 declare thread bit (1) aligned ; /* current thread indicator, on = thread, off = pointer */ 1 40 1 41 declare 1 node based (node_ptr) aligned, /* tree element */ 1 42 2 data ptr, /* data field link */ 1 43 2 key char (32), /* data key */ 1 44 2 right, /* right branch link */ 1 45 3 thread bit (1), /* indicates whether link is thread or pointer */ 1 46 3 link ptr, /* pointer to right descendent or thread to successor */ 1 47 2 left, /* left branch link */ 1 48 3 thread bit (1), /* indicates whether link is thread or pointer */ 1 49 3 link ptr, /* pointer to left descendent or thread to predecessor */ 1 50 2 pad bit (34) ; /* reserved for future flags */ 1 51 1 52 /* END INCLUDE FILE mrds_rst_tree.incl.pl1 */ 1 53 1 54 1 55 1 56 100 101 102 103 end; SOURCE FILES USED IN THIS COMPILATION. LINE NUMBER DATE MODIFIED NAME PATHNAME 0 04/18/85 0909.3 mrds_rst_tree_search.pl1 >special_ldd>online>mrds.pbf-04/18/85>mrds_rst_tree_search.pl1 100 1 10/14/83 1608.6 mrds_rst_tree.incl.pl1 >ldd>include>mrds_rst_tree.incl.pl1 NAMES DECLARED IN THIS COMPILATION. IDENTIFIER OFFSET LOC STORAGE CLASS DATA TYPE ATTRIBUTES AND REFERENCES (* indicates a set context) NAMES DECLARED BY DECLARE STATEMENT. key parameter char(32) dcl 1-24 in procedure "mrds_rst_tree_search" ref 18 79 85 key 2 based char(32) level 2 in structure "node" dcl 1-41 in procedure "mrds_rst_tree_search" ref 79 85 left 16 based structure level 2 dcl 1-41 link 14 based pointer level 3 in structure "node" dcl 1-41 in procedure "mrds_rst_tree_search" ref 82 link 20 based pointer level 3 in structure "node" dcl 1-41 in procedure "mrds_rst_tree_search" ref 65 88 node based structure level 1 dcl 1-41 node_ptr parameter pointer dcl 1-27 set ref 18 65* 79 80 81 82* 82 85 86 87 88* 88 null builtin function dcl 97 ref 63 parent_ptr parameter pointer dcl 1-28 set ref 18 57* 81* 87* right 12 based structure level 2 dcl 1-41 root_ptr parameter pointer dcl 1-26 ref 18 57 63 65 66 success parameter bit(1) unaligned dcl 1-38 set ref 18 58* 74 91* thread 16 based bit(1) level 3 in structure "node" dcl 1-41 in procedure "mrds_rst_tree_search" ref 66 86 thread 12 based bit(1) level 3 in structure "node" dcl 1-41 in procedure "mrds_rst_tree_search" ref 80 thread 000100 automatic bit(1) dcl 1-39 in procedure "mrds_rst_tree_search" set ref 66* 74 80* 86* NAMES DECLARED BY DECLARE STATEMENT AND NEVER REFERENCED. area_ptr automatic pointer dcl 1-34 data_ptr automatic pointer dcl 1-29 predecessor_parent_ptr automatic pointer dcl 1-33 predecessor_ptr automatic pointer dcl 1-32 successor_parent_ptr automatic pointer dcl 1-31 successor_ptr automatic pointer dcl 1-30 work_area based area(1024) dcl 1-36 NAME DECLARED BY EXPLICIT CONTEXT. mrds_rst_tree_search 000013 constant entry external dcl 18 THERE WERE NO NAMES DECLARED BY CONTEXT OR IMPLICATION. STORAGE REQUIREMENTS FOR THIS PROGRAM. Object Text Link Symbol Defs Static Start 0 0 144 154 114 154 Length 342 114 10 151 27 0 BLOCK NAME STACK SIZE TYPE WHY NONQUICK/WHO SHARES STACK FRAME mrds_rst_tree_search 65 external procedure is an external procedure. STORAGE FOR AUTOMATIC VARIABLES. STACK FRAME LOC IDENTIFIER BLOCK NAME mrds_rst_tree_search 000100 thread mrds_rst_tree_search THE FOLLOWING EXTERNAL OPERATORS ARE USED BY THIS PROGRAM. return ext_entry NO EXTERNAL ENTRIES ARE CALLED BY THIS PROGRAM. NO EXTERNAL VARIABLES ARE USED BY THIS PROGRAM. LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC 18 000006 57 000020 58 000024 63 000030 65 000035 66 000041 74 000045 79 000056 80 000066 81 000070 82 000071 83 000075 85 000076 86 000077 87 000101 88 000102 89 000106 91 000107 93 000112 103 000113 ----------------------------------------------------------- Historical Background This edition of the Multics software materials and documentation is provided and donated to Massachusetts Institute of Technology by Group BULL including BULL HN Information Systems Inc. as a contribution to computer science knowledge. This donation is made also to give evidence of the common contributions of Massachusetts Institute of Technology, Bell Laboratories, General Electric, Honeywell Information Systems Inc., Honeywell BULL Inc., Groupe BULL and BULL HN Information Systems Inc. to the development of this operating system. Multics development was initiated by Massachusetts Institute of Technology Project MAC (1963-1970), renamed the MIT Laboratory for Computer Science and Artificial Intelligence in the mid 1970s, under the leadership of Professor Fernando Jose Corbato. Users consider that Multics provided the best software architecture for managing computer hardware properly and for executing programs. Many subsequent operating systems incorporated Multics principles. Multics was distributed in 1975 to 2000 by Group Bull in Europe , and in the U.S. by Bull HN Information Systems Inc., as successor in interest by change in name only to Honeywell Bull Inc. and Honeywell Information Systems Inc. . ----------------------------------------------------------- Permission to use, copy, modify, and distribute these programs and their documentation for any purpose and without fee is hereby granted,provided that the below copyright notice and historical background appear in all copies and that both the copyright notice and historical background and this permission notice appear in supporting documentation, and that the names of MIT, HIS, BULL or BULL HN not be used in advertising or publicity pertaining to distribution of the programs without specific prior written permission. Copyright 1972 by Massachusetts Institute of Technology and Honeywell Information Systems Inc. Copyright 2006 by BULL HN Information Systems Inc. Copyright 2006 by Bull SAS All Rights Reserved