|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
 |
 |
HP OpenVMS systems documentation |
|
| Previous | Contents | Index |
Therefore, any node you declare that LIB$INSERT_TREE_64 manipulates must contain 18 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_64 specifies the allocate routine. This argument is required. LIB$INSERT_TREE_64 always calls the allocate routine.
This 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;
__int64 Alloc_size = sizeof(struct Full_node);
extern long LIB$GET_VM_64();
/*
** Allocate node: size of header, plus the length of our data.
*/
Status_code = LIB$GET_VM_64 (&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 procedure 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_64, LIB$LOOKUP_TREE_64, and LIB$TRAVERSE_TREE_64.
/*
** 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_64,
** LIB$LOOKUP_TREE_64 and LIB$TRAVERSE_TREE_64.
*/
#pragma pointer_size long
#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_64(); /* Function to insert node */
extern long lib$traverse_tree_64(); /* Function to walk tree */
extern long lib$lookup_tree_64(); /* 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_64 ( /* 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_64 (&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_64(&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;
__int64 Alloc_size = sizeof(struct Full_node);
extern long lib$get_vm_64();
/*
** Allocate node: size of header, plus the length of our data.
*/
Status_code = lib$get_vm_64 (&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 at Head of Queue routine inserts a queue entry at the head of the specified self-relative longword interlocked queue. LIB$INSQHI makes the INSQHI instruction available as a callable routine.
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$INSQHI entry ,header [,retry-count]
OpenVMS usage: cond_value type: longword (unsigned) access: write only mechanism: by value
entry
OpenVMS usage: unspecified type: unspecified access: modify mechanism: by reference, array reference
Entry to be inserted by LIB$INSQHI. The entry argument contains the address of this signed quadword-aligned array that must be at least 8 bytes long. Bytes following the first 8 bytes can be used for any purpose by the calling program.For Alpha and I64 systems, the entry argument must contain a 32-bit sign-extended address. An illegal operand exception occurs for any other form of address.
header
OpenVMS usage: quadword_signed type: quadword integer (signed) access: modify mechanism: by reference
Queue header specifying the queue into which entry is to be inserted. The header argument contains the address of this signed aligned quadword integer. The header argument must be initialized to zero before first use of the queue; zero means an empty queue.For Alpha systems, the header argument must contain a 32-bit sign-extended address. An illegal operand exception occurs for any other form of address.
retry-count
OpenVMS usage: longword_unsigned type: longword (unsigned) access: read only mechanism: by reference
The number of times the insertion is to be retried in case of secondary-interlock failure of the queue instruction in a processor-shared memory application. The retry-count argument is the address of an unsigned longword that contains the retry count value. A value of 1 causes no retries. The default value is 10.
The queue into which LIB$INSQHI inserts an entry can be in process-private, processor-private, or processor-shareable memory to implement per-process, per-processor, or across-processor queues.A queue is a doubly linked list. A Run-Time Library routine specifies a queue entry by its address.
A self-relative queue is a queue in which the links between entries are the displacements of the current entry's predecessor and successor. If these links are longwords, the queue is referred to as a self-relative longword queue.
You can use the LIB$INSQHI, LIB$INSQTI, LIB$REMQHI, and LIB$REMQTI routines to manage your self-relative longword queue on a VAX or an Alpha or I64 system. These routines implement the INSQHI, INSQTI, REMQHI, and REMQTI instructions that allow you to insert and remove an entry at the head or tail of a self-relative longword queue.
When you insert or remove a queue entry using the self-relative queue routines, the queue pointers are changed as an atomic operation. This ensures that no other process can interrupt the operation to insert or remove a queue entry of its own.
When you use these routines, cooperating processes can communicate without further synchronization and without danger of being interrupted, either on a single processor or in a multiprocessor environment. The queue access routines are also useful in an AST environment; they allow you to add or remove an entry from a queue without being interrupted by an AST.
If you do not use the self-relative queue routines to insert or remove a queue entry, you must ensure that the operation cannot be interrupted.
Use of the self-relative longword queue routines requires that the queue header and each of the queue entries be quadword aligned. You can use the Run-Time Library routine LIB$GET_VM on a VAX, Alpha, or I64 system to allocate quadword-aligned virtual memory for a queue.
SS$_NORMAL Routine successfully completed. The entry was added to the front of the queue, and the resulting queue contains more than one entry. SS$_ROPRAND Reserved operand fault. Either the entry or the header is at an address that is not quadword aligned, or the header address equals the entry address. LIB$_ONEENTQUE Routine successfully completed. The entry was added to the front of the queue, and the resulting queue contains one entry. LIB$_SECINTFAI A secondary interlock failure occurred; the insertion was attempted the number of times specified by retry-count. This is a severe error. The queue is not modified. This condition can occur only when the queue is in memory being shared between two or more processors.
| #1 |
|---|
INTEGER*4 FUNCTION INSERT_Q (QENTRY)
COMMON/QUEUES/QHEADER
INTEGER*4 QENTRY(10), QHEADER(2)
INSERT_Q = LIB$INSQHI (QENTRY, QHEADER)
RETURN
END
|
This is a Fortran application using processor-shared memory.
| #2 |
|---|
COM (QUEUES) QENTRY%(9), QHEADER%(1)
EXTERNAL INTEGER FUNCTION LIB$INSQHI
IF LIB$INSQHI (QENTRY%() BY REF, QHEADER%() BY REF) AND 1%
THEN GOTO 1000
.
.
.
1000 REM INSERTED OK
|
In BASIC and Fortran, queues can be quadword aligned in a named COMMON block by using a linker option file to specify PSECT alignment. For instance, to create a COMMON block called QUEUES, use the LINK command with the FILE/OPTIONS qualifier, where FILE.OPT is a linker option file containing the following line:
PSECT = QUEUES, QUAD
The Insert Entry at Head of Queue routine inserts a queue entry at the head of the specified self-relative quadword interlocked queue. LIB$INSQHIQ makes the INSQHIQ instruction available as a callable routine.
LIB$INSQHIQ entry ,header [,retry-count]
OpenVMS usage: cond_value type: longword (unsigned) access: write only mechanism: by value
entry
OpenVMS usage: unspecified type: unspecified access: modify mechanism: by reference, array reference
Entry to be inserted by LIB$INSQHIQ. The entry argument contains the address of this signed octaword-aligned array that must be at least 16 bytes long. Bytes following the first 16 bytes can be used for any purpose by the calling program.header
OpenVMS usage: octaword_signed type: octaword integer (signed) access: modify mechanism: by reference
Queue header specifying the queue into which entry is to be inserted. The header argument contains the address of this signed aligned octaword integer. The header argument must be initialized to zero before first use of the queue; zero means an empty queue.retry-count
OpenVMS usage: longword_unsigned type: longword (unsigned) access: read only mechanism: by reference
The number of times the insertion is to be retried in case of secondary-interlock failure of the queue instruction in a processor-shared memory application. The retry-count argument is the address of an unsigned longword that contains the retry count value. A value of 1 causes no retries. The default value is 10.
The queue into which LIB$INSQHIQ inserts an entry can be in process-private, processor-private, or processor-shareable memory to implement per-process, per-processor, or cross-processor queues.A queue is a doubly linked list. A Run-Time Library routine specifies a queue entry by its address.
A self-relative queue is a queue in which the links between entries are the displacements of the current entry's predecessor and successor. If these links are quadwords, the queue is referred to as a self-relative quadword queue.
You can use the LIB$INSQHIQ, LIB$INSQTIQ, LIB$REMQHIQ, and LIB$REMQTIQ routines to manage your self-relative quadword queue on an Alpha or I64 system. These routines implement the INSQHIQ, INSQTIQ, REMQHIQ, and REMQTIQ instructions that allow you to insert and remove an entry at the head or tail of a self-relative quadword queue.
When you insert or remove a queue entry using the self-relative queue routines, the queue pointers are changed as an atomic operation. This ensures that no other process can interrupt the operation to insert or remove a queue entry of its own.
When you use these routines, cooperating processes can communicate without further synchronization and without danger of being interrupted, either on a single processor or in a multiprocessor environment. The queue access routines are also useful in an AST environment; they allow you to add or remove an entry from a queue without being interrupted by an AST.
If you do not use the self-relative queue routines to insert or remove a queue entry, you must ensure that the operation cannot be interrupted.
Use of the self-relative quadword queue routines requires that the queue header and each of the queue entries be octaword aligned. You can use the Run-Time Library routine LIB$GET_VM_64 to allocate octaword aligned virtual memory for a queue.
SS$_NORMAL Routine successfully completed. The entry was added to the front of the queue, and the resulting queue contains more than one entry. SS$_ROPRAND Reserved operand fault. Either the entry or the header is at an address that is not octaword aligned, or the header address equals the entry address. LIB$_ONEENTQUE Routine successfully completed. The entry was added to the front of the queue, and the resulting queue contains one entry. LIB$_SECINTFAI A secondary interlock failure occurred; the insertion was attempted the number of times specified by retry-count. This is a severe error. The queue is not modified. This condition can occur only when the queue is in memory being shared between two or more processors.
The following Fortran application uses processor-shared memory:
INTEGER*4 FUNCTION INSERT_Q (QENTRY)
COMMON/QUEUES/QHEADER
INTEGER*8 QENTRY(10), QHEADER(2)
INSERT_Q = LIB$INSQHIQ (QENTRY, QHEADER)
RETURN
END
|
In Fortran, queues can be octaword aligned in a named COMMON block by using a linker option file to specify PSECT alignment. For instance, to create a COMMON block called QUEUES, use the LINK command with the FILE/OPTIONS qualifier, where FILE.OPT is a linker option file containing the following line:
PSECT = QUEUES, OCTA
| Previous | Next | Contents | Index |