hp.com home products and services support and drivers solutions how to buy
cd-rom home
End of Jump to page title
HP OpenVMS systems
documentation

Jump to content


HP OpenVMS RTL Library (LIB$) Manual

HP OpenVMS RTL Library (LIB$) Manual


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:

  1. 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.
  2. 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:


PSECT = QUEUES, QUAD 


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:


PSECT = QUEUES, OCTA 


Previous Next Contents Index