/* BEGIN INCLUDE FILE mrds_rst_tree.incl.pl1   jeg 7/19/78 */

/* common declarations for threaded binary tree routines

   The tree maintains an inorder list of it's keys.
   this means that for a given node, any key in it's left subtree
   is "less" than the given node's key and that any key in it's
   right subtree is "greater" than the given node's key.

   Threads are maintained to allow fast and easy traversal of the tree.
   threads occupy the position of null pointers of an straight binary tree,
   thus they only occur in leaf nodes.
   left threads point to that nodes inorder predecessor.
   right threads point to that nodes inorder successor.

   note: root_ptr must be passed by reference
   ( not by value ) so it can be changed .
   Also, each parameter must be a different
   variable. The same variable used for two
   or more arguments when any of the tree
   routines are called will produce errors */


declare  key char (32) aligned ;			/* data key directing search */

declare  root_ptr ptr ;				/* pointer to head of desired list */
declare  node_ptr ptr ;				/* pointer to key node, when success */
declare  parent_ptr ptr ;				/* pointer to direct parent of current node */
declare  data_ptr ptr ;				/* pointer from tree node to data structure headed by node */
declare  successor_ptr ptr ;				/* pointer to inorder successor of current node in tree */
declare  successor_parent_ptr ptr ;			/* pointer to immediate tree parent of inorder successor node */
declare  predecessor_ptr ptr ;			/* pointer to inorder predecessor of current node */
declare  predecessor_parent_ptr ptr ;			/* pointer to direct parent of predecessor */
declare  area_ptr ptr ;				/* pointer to based area for node allocation/freeing */

declare  work_area area based (area_ptr) ;		/* area of storage for tree */

declare  success bit (1) ;				/* on if operation successful */
declare  thread bit (1) aligned ;			/* current thread indicator, on = thread, off = pointer */

declare 1 node based (node_ptr) aligned,		/* tree element */
        2 data ptr,					/* data field link */
        2 key char (32),				/* data key */
        2 right,					/* right branch link */
	3 thread bit (1),				/* indicates whether link is thread or pointer */
	3 link ptr,				/* pointer to right descendent or thread to successor */
        2 left,					/* left branch link */
	3 thread bit (1),				/* indicates whether link is thread or pointer */
	3 link ptr,				/* pointer to left descendent or thread to predecessor */
        2 pad bit (34) ;				/* reserved for future flags */

/* END INCLUDE FILE mrds_rst_tree.incl.pl1  */






*/
                                          -----------------------------------------------------------


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

*/