[OpenVMS documentation]
[Site home] [Send comments] [Help with this site] [How to order documentation] [OpenVMS site] [Compaq site]
Updated: 11 December 1998

OpenVMS RTL Library (LIB$) Manual


Previous Contents Index

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.


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 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 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 or an Alpha 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 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 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

[Site home] [Send comments] [Help with this site] [How to order documentation] [OpenVMS site] [Compaq site]
[OpenVMS documentation]

Copyright © Compaq Computer Corporation 1998. All rights reserved.

Legal
5932PRO_027.HTML