 |
HP OpenVMS RTL Library (LIB$) Manual
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:
- Your data immediately follows the node header. In this case, your
allocation routine must allocate a block equal in size to the sum of
your data plus 18 bytes for the node header, as shown in the following
figure.
- The node contains the 18 bytes of header information and a quadword
pointer to the user data as shown in the following figure.
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);
}
|
Condition Values Returned
|
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.
Example
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
$
|
LIB$INSQHI
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.
|
Format
LIB$INSQHI entry ,header [,retry-count]
RETURNS
| OpenVMS usage: |
cond_value |
| type: |
longword (unsigned) |
| access: |
write only |
| mechanism: |
by value |
Arguments
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.
Description
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.
Self-Relative 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.
Synchronization
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.
Alignment
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.
Condition Values Returned
|
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.
|
Examples
| #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:
LIB$INSQHIQ (Alpha and I64 Only)
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.
Format
LIB$INSQHIQ entry ,header [,retry-count]
RETURNS
| OpenVMS usage: |
cond_value |
| type: |
longword (unsigned) |
| access: |
write only |
| mechanism: |
by value |
Arguments
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.
Description
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.
Self-Relative 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.
Synchronization
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.
Alignment
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.
Condition Values Returned
|
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.
|
Example
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:
|
