|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
 |
 |
HP OpenVMS systems documentation |
|
| Previous | Contents | Index |
The Insert Entry in a Balanced Binary Tree routine inserts a node in a balanced binary tree.
Note
No support for arguments passed by 64-bit address reference or for use of 64-bit descriptors, if applicable, is planned for this routine.
LIB$INSERT_TREE treehead ,symbol ,flags ,user-compare-routine ,user-allocation-procedure ,new-node [,user-data]
OpenVMS usage: cond_value type: longword (signed) access: write only mechanism: by value
treehead
OpenVMS usage: address type: address access: modify mechanism: by reference
Tree head for the binary tree. The treehead argument is the address of a longword that is this tree head. The initial value of treehead is 0.symbol
OpenVMS usage: user_arg type: longword (unsigned) access: unspecified mechanism: unspecified
Key to be inserted.flags
OpenVMS usage: mask_longword type: longword (unsigned) access: read only mechanism: by reference
Control flags. The flags argument is the address of the control flags. Currently only bit 0 is used.
Bit Action if Set Action if Clear 0 Duplicate entries are inserted. The address of the existing duplicate entry is returned to the new-node argument.
user-compare-routine
OpenVMS usage: procedure type: procedure value access: function call (before return) mechanism: by value
User-supplied compare routine that LIB$INSERT_TREE calls to compare a symbol with a node. The user-compare-routine argument is required; LIB$INSERT_TREE calls the compare routine for every node except the first node in the tree. The value returned by the compare routine indicates the relationship between the symbol key and the node.For more information on the compare routine, see Call Format for a Compare Routine in the Description section.
user-allocation-procedure
OpenVMS usage: procedure type: procedure value access: function call (before return) mechanism: by value
User-supplied allocate routine that LIB$INSERT_TREE calls to allocate virtual memory for a node. The user-allocation-procedure argument is required; LIB$INSERT_TREE always calls the allocate routine.For more information on the allocate routine, see Call Format for an Allocate Routine in the Description section.
new-node
OpenVMS usage: address type: longword (unsigned) access: write only mechanism: by reference
Location where the new key is inserted. The new-node argument is the address of an unsigned longword that is the address of the new node.user-data
OpenVMS usage: user_arg type: unspecified access: unspecified mechanism: by value
User data that LIB$INSERT_TREE passes to the compare and allocate routines. The user-data argument is optional.
This Description section contains three parts:
- Guidelines for Using LIB$INSERT_TREE
- Call Format for a Compare Routine
- Call Format for an Allocate Routine
Guidelines for Using LIB$INSERT_TREE
LIB$INSERT_TREE inserts a node in a balanced binary tree. You supply two routines: compare and allocate. The compare routine compares the symbol key to the node, and the allocate routine allocates virtual memory for the node to be inserted. LIB$INSERT_TREE first calls the compare routine to find the location at which the new node is inserted. Then LIB$INSERT_TREE calls the allocate routine to allocate memory for the new node. Most programmers insert data in the new node by initializing it within the allocate routine as soon as memory has been allocated.
You may pass the data to be inserted into the tree using either the symbol argument alone or both the symbol and user-data arguments. The symbol argument is required. It may contain all of the data, just the name of the node, or the address of the data. If you decide to use symbol to pass just the name of the node, you must use the user-data argument to pass the rest of the data to be inserted in the new node.
Call Format for a Compare Routine
The call format of a compare routine is as follows:
user-compare-routine symbol ,comparison-node [,user-data]
LIB$INSERT_TREE passes both the symbol and comparison-node arguments to the compare routine, using the same passing mechanism that was used to pass them to LIB$INSERT_TREE. The user-data argument is passed in the same way, but its use is optional.
The user-compare-routine argument in the call to LIB$INSERT_TREE specifies the compare routine. This argument is required. LIB$INSERT_TREE calls the compare routine for every node except the first node in the tree.
The value returned by the compare routine is the result of comparing the symbol key with the current node. The following table interprets the possible values returned by the compare routine:
Return Value Meaning Negative The symbol argument is less than the current node. Zero The symbol argument is equal to the current node. Positive The symbol argument is greater than the current node. This is an example of a user-supplied compare routine, written in C.
struct Full_node { void* left_link; void* right_link; short reserved; char Text[80]; }; static long Compare_node(char* Key_string, struct Full_node* Node, void* Dummy) /* ** This function compares the string described by Key_string with ** the string contained in the data node Node, and returns 0 ** if the strings are equal, -1 if Key_string is < Node, and ** 1 if Key_string > Node. */ { int result; result = strcmp(Key_string, Node->Text); if (result < 0) return -1; else if (result == 0) return 0; else return 1; }Call Format for an Allocate Routine
LIB$INSERT_TREE calls the allocate routine to allocate virtual memory for a node. The allocate routine then stores the value of user-data in the field of the allocated node.
The format of the call is as follows:
user-allocation-procedure symbol ,new-node [,user-data]
LIB$INSERT_TREE passes the symbol, new-node, and user-data arguments to your allocate routine, using the same passing mechanisms that were used to pass them to LIB$INSERT_TREE. Use of user data is optional.
A node header appears at the beginning of each node. The following figure shows the structure of a node header.
Therefore, any node you declare that LIB$INSERT_TREE manipulates must contain 10 bytes of reserved data at the beginning for the node header.
How a node is structured depends on how you allocate your user data. You can allocate data in one of two ways:
The user-allocation-procedure argument in the call to LIB$INSERT_TREE specifies the allocate routine. This argument is required. LIB$INSERT_TREE always calls the allocate routine.
Following is an example of a user-supplied allocate routine written in C.
struct Full_node
{
void* left_link;
void* right_link;
short reserved;
char Text[80];
};
static long Alloc_node(char* Key_string,
struct Full_node** Ret_addr, void* Dummy)
{
/*
** Allocate virtual memory for a new node. Key_string
** is the string to be entered into the newly
** allocated node. RET_ADDR will contain the address
** of the allocated memory.
*/
long Status_code;
long Alloc_size = sizeof(struct Full_node);
extern long lib$get_vm();
/*
** Allocate node: size of header, plus the length of our data.
*/
Status_code = lib$get_vm (&Alloc_size, Ret_addr);
if (!(Status_code & 1))
lib$stop(Status_code);
/*
** Store the data in the newly allocated virtual memory.
*/
strcpy((*Ret_addr)->Text, Key_string);
return (Status_code);
}
|
LIB$_NORMAL Routine successfully completed. LIB$_INSVIRMEM Insufficient virtual memory. The user-supplied allocation routine returned an error. LIB$_KEYALRINS Routine successfully completed, but a key was found in the tree. No new key was inserted.
Any other failure status reported by the user allocation procedure.
The following C program shows the use of LIB$INSERT_TREE, LIB$LOOKUP_TREE, and LIB$TRAVERSE_TREE.
/*
** This program asks the user to enter a series of strings,
** one per line. The user can then query the program to find
** strings that were previously entered. At the end, the entire
** tree is displayed, along with sequence numbers that
** indicate the order in which each element was entered.
**
** This program serves as an example of the use of LIB$INSERT_TREE,
** LIB$LOOKUP_TREE and LIB$TRAVERSE_TREE.
*/
#include <stdio.h>
#include <string.h>
#include <libdef.h>
char Text_line[80];
struct Tree_element /* Define the structure of our */
{ /* record. This record could */
long Seq_num; /* contain many useful data items. */
char Text[80];
};
struct Full_node
{
void* left_link;
void* right_link;
short reserved;
struct Tree_element my_node;
};
struct Tree_element Rec; /* Declare an instance of the record */
extern long lib$insert_tree(); /* Function to insert node */
extern long lib$traverse_tree(); /* Function to walk tree */
extern long lib$lookup_tree(); /* Function to find a node */
extern void lib$stop(); /* Routine to signal fatal error */
static long Compare_node_2(); /* Compare entry (2 arg) */
static long Compare_node_3(); /* Compare entry (3 arg) */
static long Alloc_node(); /* Allocation entry */
static long Print_node(); /* Print entry for walk */
static void Display_Node();
main ()
{
struct Full_node* Tree_head; /* Head for the tree */
struct Full_node* New_node; /* New node after insert */
long Status_code; /* Return status code */
long Counter; /* Sequence number */
long flags = 1;
/*
** Initialize the tree to null
*/
Tree_head = NULL;
printf("Enter one word per line, ^Z to begin searching the tree\n");
/*
** Loop, reading lines of text until the end of the file.
*/
Counter = 0;
printf("> ");
while (gets(Text_line))
{
Counter++;
Rec.Seq_num = Counter;
strcpy(Rec.Text, Text_line);
Status_code = lib$insert_tree ( /* Insert the entry into the tree */
&Tree_head, &Rec, &flags,
Compare_node_3, Alloc_node, &New_node);
if (!(Status_code & 1))
lib$stop(Status_code);
printf("> ");
}
/*
** End of file encountered. Begin searching the tree.
*/
printf("\nYou will now be prompted for words to find. ");
printf("Enter one per line.\n");
Rec.Seq_num = -1;
printf("Word to find? ");
while (gets(Text_line))
{
strcpy(Rec.Text, Text_line);
Status_code = lib$lookup_tree (&Tree_head, &Rec,
Compare_node_2, &New_node);
if (Status_code == LIB$_KEYNOTFOU)
printf("The word you entered does not appear in the tree.\n");
else
Display_Node(New_node);
printf("Word to find? ");
}
/*
** The user has finished searching the tree for specific items. It
** is now time to traverse the entire tree.
*/
printf("\n");
printf("The following is a dump of the tree. Notice that the words\n");
printf("are in alphabetical order\n");
Status_code = lib$traverse_tree(&Tree_head, Print_node, 0);
return(Status_code);
}
static long Print_node(struct Full_node* Node, void* Dummy)
{
/*
** Print the string contained in the current node.
*/
printf("%d\t%s\n", Node->my_node.Seq_num, Node->my_node.Text);
return(LIB$_NORMAL);
}
static long Alloc_node(struct Tree_element* Rec,
struct Full_node** Ret_addr, void* Dummy)
{
/*
** Allocate virtual memory for a new node. Rec is the
** data record to be entered into the newly
** allocated node. RET_ADDR will contain the address
** of the allocated memory.
*/
long Status_code;
long Alloc_size = sizeof(struct Full_node);
extern long lib$get_vm();
/*
** Allocate node: size of header, plus the length of our data.
*/
Status_code = lib$get_vm (&Alloc_size, Ret_addr);
if (!(Status_code & 1))
lib$stop(Status_code);
/*
** Store the data in the newly allocated virtual memory.
*/
(*Ret_addr)->my_node.Seq_num = Rec->Seq_num;
strcpy((*Ret_addr)->my_node.Text, Rec->Text);
return (Status_code);
}
static long Compare_node_3(struct Tree_element* Rec, struct Full_node* Node,
void* Dummy)
{
/*
** Call the 2 argument version of the compare routine
*/
return(Compare_node_2 ( Rec, Node ));
}
static long Compare_node_2(struct Tree_element* Rec, struct Full_node* Node)
{
/*
** This function compares the string described by Key_string with
** the string contained in the data node Node, and returns 0
** if the strings are equal, -1 if Key_string is < Node, and
** 1 if Key_string > Node.
*/
int result;
/*
** Return the result of the comparison.
*/
result = strcmp(Rec->Text, Node->my_node.Text);
if (result < 0)
return -1;
else if (result == 0)
return 0;
else
return 1;
}
static void Display_Node(struct Full_node* Node)
{
/*
** This routine prints the data into the node of the tree
** once LIB$LOOKUP_TREE has been called to find the node.
*/
printf("The sequence number for \"%s\" is %d\n",
Node->my_node.Text, Node->my_node.Seq_num);
}
|
The output generated by this program is as follows:
$ run tree Enter one word per line, ^Z to begin searching the tree > apple > orange > peach > pear > grapefruit > lemon > [Ctrl/Z] You will now be prompted for words to find. Enter one per line. Word to find? lime The word you entered does not appear in the tree Word to find? orange The sequence number for "orange" is 2 Word to find? [Ctrl/Z] The following is a dump of the tree. Notice that the words are in alphabetical order 1 apple 5 grapefruit 6 lemon 2 orange 3 peach 4 pear $
The Insert Entry in a Balanced Binary Tree routine inserts a node in a balanced binary tree.
LIB$INSERT_TREE_64 treehead ,symbol ,flags ,user-compare-routine ,user-allocation-procedure ,new-node [,user-data]
OpenVMS usage: cond_value type: longword (signed) access: write only mechanism: by value
treehead
OpenVMS usage: address type: address access: modify mechanism: by reference
Tree head for the binary tree. The treehead argument is the address of a quadword that is this tree head. The initial value of treehead is 0.symbol
OpenVMS usage: user_arg type: quadword (unsigned) access: unspecified mechanism: unspecified
Key to be inserted.flags
OpenVMS usage: mask_quadword type: quadword (unsigned) access: read only mechanism: by reference
Control flags. The flags argument is the address of the control flags. Currently only bit 0 is used.
Bit Description 0 If clear, the address of the existing duplicate entry is returned to the new-node argument. If set, duplicate entries are inserted.
user-compare-routine
OpenVMS usage: procedure type: procedure value access: function call (before return) mechanism: by value
User-supplied compare routine that LIB$INSERT_TREE_64 calls to compare a symbol with a node. The user-compare-routine argument is required; LIB$INSERT_TREE_64 calls the compare routine for every node except the first node in the tree. The value returned by the compare routine indicates the relationship between the symbol key and the node.For more information on the compare routine, see Call Format for a Compare Routine in the Description section.
user-allocation-procedure
OpenVMS usage: procedure type: procedure value access: function call (before return) mechanism: by value
User-supplied allocate routine that LIB$INSERT_TREE_64 calls to allocate virtual memory for a node. The user-allocation-procedure argument is required; LIB$INSERT_TREE_64 always calls the allocate routine.For more information on the allocate routine, see Call Format for an Allocate Routine in the Description section.
new-node
OpenVMS usage: address type: quadword (unsigned) access: write only mechanism: by reference
Location where the new key is inserted. The new-node argument is the address of an unsigned quadword that is the address of the new node.user-data
OpenVMS usage: user_arg type: unspecified access: unspecified mechanism: by value
User data that LIB$INSERT_TREE_64 passes to the compare and allocate routines. The user-data argument is optional.
This Description section contains three parts:
- Guidelines for Using LIB$INSERT_TREE_64
- Call Format for a Compare Routine
- Call Format for an Allocate Routine
Guidelines for Using LIB$INSERT_TREE_64
LIB$INSERT_TREE_64 inserts a node in a balanced binary tree. You supply two routines: compare and allocate. The compare routine compares the symbol key to the node, and the allocate routine allocates virtual memory for the node to be inserted. LIB$INSERT_TREE_64 first calls the compare routine to find the location at which the new node is inserted. Then LIB$INSERT_TREE_64 calls the allocate routine to allocate memory for the new node. Most programmers insert data in the new node by initializing it within the allocate routine as soon as memory has been allocated.
You may pass the data to be inserted into the tree using either the symbol argument alone or both the symbol and user-data arguments. The symbol argument is required. It may contain all of the data, just the name of the node, or the address of the data. If you decide to use symbol to pass just the name of the node, you must use the user-data argument to pass the rest of the data to be inserted in the new node.
Call Format for a Compare Routine
The call format of a compare routine is as follows:
user-compare-routine symbol ,comparison-node [,user-data]
LIB$INSERT_TREE_64 passes both the symbol and comparison-node arguments to the compare routine, using the same passing mechanism that was used to pass them to LIB$INSERT_TREE_64. The user-data argument is passed in the same way, but its use is optional.
The user-compare-routine argument in the call to LIB$INSERT_TREE_64 specifies the compare routine. This argument is required. LIB$INSERT_TREE_64 calls the compare routine for every node except the first node in the tree.
The value returned by the compare routine is the result of comparing the symbol key with the current node. Following are the possible values returned by the compare routine:
Return Value Meaning Negative The symbol argument is less than the current node. Zero The symbol argument is equal to the current node. Positive The symbol argument is greater than the current node. This is an example of a user-supplied compare routine, written in C.
struct Full_node { void* left_link; void* right_link; short reserved; char Text[80]; }; static long Compare_node(char* Key_string, struct Full_node* Node, void* Dummy) /* ** This function compares the string described by Key_string with ** the string contained in the data node Node, and returns 0 ** if the strings are equal, -1 if Key_string is < Node, and ** 1 if Key_string > Node. */ { int result; result = strcmp(Key_string, Node->Text); if (result < 0) return -1; else if (result == 0) return 0; else return 1; }Call Format for an Allocate Routine
LIB$INSERT_TREE_64 calls the allocate routine to allocate virtual memory for a node. The allocate routine then stores the value of user-data in the field of the allocated node.
The format of the call is as follows:
user-allocation-procedure symbol ,new-node [,user-data]
LIB$INSERT_TREE_64 passes the symbol, new-node, and user-data arguments to your allocate routine, using the same passing mechanisms that were used to pass them to LIB$INSERT_TREE_64. Use of user data is optional.
A node header appears at the beginning of each node. The following figure shows the structure of a node header.
| Previous | Next | Contents | Index |