/*static char *SCCSID = "@(#)ptree.c	6.3 92/01/25";*/
/*
 *      IBM/Microsoft Confidential
 *
 *      Copyright (c) IBM Corporation 1987, 1989
 *      Copyright (c) Microsoft Corporation 1987, 1989
 *
 *      All Rights Reserved
 *
 */
#define SCCSID "@(#)ptree.c	6.3 92/01/25"
#define FNO_NUM FNO_PTREE_C

/*** PTree (Patricia Tree)
 *
 * Implements creating, destroying and walking a PTree, and
 * inserting, searching, and deleting objects from a PTree.
 *
 * PTCreate             - create a PTree
 * PTInsert             - insert an object into a PTree
 * PTFind               - find an object
 * PTFindFromPrefix     - find an object that has the given prefix
 * PTFindMaxPrefix      - find an object that is a prefix of the given key
 * PTDelete             - delete an object from a PTree
 * PTWalk               - walk a PTree calling a specified function
 * PTDestroy            - destroy a PTree
 *
 *
 *
 *
 * The head entry is a special node
 * in the PTree, ala Knuth's description of Patricia Tree's.
 * This is the one area where our Patricia Tree's resemble Knuth's
 * more than SedgeWick's. The special root node has a right pointer
 * which will always be the root.  The search algorithms allways follow
 * the left pointer because the root key string is all nulls.
 *
 * The bit number tested at the root must be lower than any legal bit,
 * so we use bit -1.  The routines are actually structured so that
 * this bit is never tested, but it must be there so that we know
 * when we've reached the bottom of the tree.
 */

#define INCL_TYPES
#define INCL_DOSP
#include <os2p.h>
#include <string.h>

#define INCL_ERRORS
#include <bseerr.h>

#ifdef STANDALONE
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>

    #define KSEMInit(hsem,type,flags)
    #define KSEMRequestExclusive(hsem,timeout)          NO_ERROR
    #define KSEMRequestShared(hsem,timeout)             NO_ERROR
    #define KSEMRequestSharedOwned(hsem,timeout)        NO_ERROR
    #define KSEMUpgrade(hsem,timeout)                   NO_ERROR
    #define KSEMDowngrade(hsem,type)                    NO_ERROR
    #define KSEMRelease(hsem)

    #define SSToDS(foo) (foo)
    #define VMAllocKHB(heap, size, owner, flags, ppfoo) \
                ((*ppfoo = malloc(size)) == NULL)
    #define VMFreeKHB(heap, pfoo)       free(pfoo)

    /* ptAssert for standalone */
    #define ptAssert(e) if (!(e)) ptPanic(__FILE__, __LINE__); else

    void ptPanic(char *pbFile, long iLine )
    {
        fprintf(stderr, "ptPanic: file %s, line %d\n", pbFile, iLine );
        exit( 1 );
    }
#else
    #include <fnomem.h>
    #include <osmac.h>
    #include <basedef.h>
    #include <basemac.h>
    #include <mi.h>
    #include <pgexport.h>
    #include <vmexport.h>
    #include <vmowner.h>
    #include <selxport.h>
    #include <semxport.h>
    #include <tkexport.h>

    #ifdef VMSTRICT
        #define ptAssert(e)     _assert(e)
    #else
        #define ptAssert(e)
    #endif /* VMSTRICT */
#endif

#include <ptree.h>

void ptCheckTree(HPTREE);
void ptCheckNode(HPTREE, P_PTNODE);

/* function prototypes for locals to make C compiler happy with -W3 */

P_PTNODE ptFindNode (HPTREE, uchar_t *, BI);
P_PTNODE ptFindNodeStop(HPTREE, uchar_t *, KEYLEN, BI, P_PTNODE *);
BI ptFirstDiff(uchar_t *, KEYLEN, uchar_t *, KEYLEN, KEYLEN);
long ptWalkWorker(HPTREE, P_PTNODE);
long ptWalkNodeWorker(HPTREE, PF_WALKNODE);


#define BITS_PER_BYTE   8       /* number of bits in a byte */


/* The max bit index (ptn_bi) must fit in a signed short (BI),
 * so the max key length is (max short)/BITS_PER_BYTE == 4095.
 * If 4095 is too small, the bit index can be made a long.
 * Note that the max key length in bytes must fit in ptn_iKeyLen (I_IKEYLEN),
 * so if ptn_bi is made long, then ptn_iKeyLen must be long too,
 * or the max key len limited to 32787 (max short).
 */
#define MAXKEYLEN       (((ushort_t) -1 >> 1) / BITS_PER_BYTE)


/* NOTE: the most significant bit is used first so bit index 0 is 0x80. */

/***LD abBitMask - mask to get a particular bit in a byte given the bit index */
uchar_t abBitMask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };

#define TERMBYTE         0x80


/***LP BitTest - test a bit in a bit string
 *
 * ENTRY:       pb      - pointer to bit (byte) string
 *              bi      - bit index to test
 *                        bi CANNOT be higher that the index
 *                        of the last bit in the string.
 *
 * RETURN:      non-zero if bit is set
 *              zero     if bit is clear
 *
 * BUGBUG - performance - could be a 386 asm function
 */
#define BitTest(pb, bi) ((pb)[(bi) >> 3] & abBitMask[(bi) & 7])


/***LP BitTestCheck - test a bit in a bit string with check for end of string
 *
 * In order to compare bit strings of diferent lengths, we put virtual
 * bits beyond the end of the bit string.  The first bit beyond the
 * end of the bit string is a 1 and all beyond that are 0's.
 * Thus any possible bit pattern of any length is unique.
 *
 * ENTRY:       pb      - pointer to bit (byte) string
 *              bi      - bit index to test
 *                        bi CAN be higher that the index
 *                        of the last bit in the string.
 *              len     - length of bit string in bits
 *
 * RETURN:      non-zero if bit is set
 *              zero     if bit is clear
 *
 * NOTE:        bit indicies less than len are in the bit string,
 *              bit indicies above or equal to len are virtual.
 *
 * BUGBUG - performance - could be a 386 asm function
 */

#define BitTestCheck(pb, bi, len) \
            ( ((bi) < (len))? \
                ((pb)[(bi) >> 3] & abBitMask[(bi) & 7]): \
                ((bi) == (len)) )


/***LD abFirstBit - used to determine the first bit set in a nibble.
 * Note that index 0 is never used.
 *
 * values                0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
 */
uchar_t abFirstBit[] = { 0, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 };


/***LP FirstBit - return the index of the first bit set in the byte
 */
#define FirstBit(x)     ( ((x) & 0xf0)? (BI) (abFirstBit[(x) >> 4]):    \
                                        (BI) (abFirstBit[(x) & 0x0f] + 4) )


/***LP IsRootNode - return boolean indication if this node is the root node
 *
 * The root node is not a real node.
 * It does not have a Key Handle or Bit Index.
 * It's Key Handle (ptn_hKey) is 0 and it's Bit Index (ptn_bi) is -1.
 * It's right pointer is a self pointer.
 * It's left pointer points to the real root of the tree.
 * This is done so that the root of the tree does not move.
 */
#define IsRootNode(x)   ( (x)->ptn_hKey == 0 )


/***LP GetTag   - return boolean indication if this node is tagged (PTWalk)
 ***LP SetTag   - set   tag on this node (PTWalk)
 ***LP ClearTag - clear tag on this node (PTWalk)
 *
 * WARNING - if I_KEYLEN changes to a long, these constants need to change.
 */
#define GetTag(pn)      ((pn)->ptn_iKeyLen &   0x8000)
#define SetTag(pn)      ((pn)->ptn_iKeyLen |=  0x8000)
#define ClearTag(pn)    ((pn)->ptn_iKeyLen &= ~0x8000)


/***EP PTCreate() - Create a PTree and Initialize the Header.
 *
 * ENTRY:
 *      lFlags  - flags
 *          PTF_HEADSWAP        ptree head  is  swappable (heap)
 *          PTF_NODESWAP        ptree nodes are swappable (heap) BUGBUG BMP32?
 *          PTF_PANICINSERT     panic on PTInsert if key already exists
 *          PTF_PANICDELETE     panic on PTDelete if key doesn't exists
 *          PTF_DEBUG           print debugging info while running
 *
 *      owner   - owner from vmowner.h to use in VMAllocKHB
 *
 *      cMaxNodes - maximum number of nodes allowed in the tree
 *
 *              An attempt to insert another node when there are
 *              already cMaxNodes in the tree will return an error.
 *
 *      KeyAlloc - 32 bit flat pointer to function to be called
 *              to allocate and initialize the memory for an object.
 *
 *              Given the pointer to the key, the key's length and
 *              a pointer to the key handle to be filled in, KeyAlloc
 *              should allocate and initialize the object (including
 *              copying the key string into the object) and return
 *              NO_ERROR on success or an error code.
 *              An error here is not fatal, but it will cause the
 *              PTInsert call to fail.
 *
 *              long (*KeyAlloc) (uchar_t *, KEYLEN, HPTKEY *);
 *
 *      KeyFree - 32 bit flat pointer to function to be called
 *              to free the memory for an object.
 *
 *              Given the key handle, KeyFree should free the memory
 *              allocated for the object and return NO_ERROR on
 *              success or an error code.
 *              An error here IS FATAL and will panic.
 *
 *              long (*KeyFree) (HPTKEY);
 *
 *      GetKey  - 32 bit flat pointer to function to be called
 *              to convert a key handle into a pointer the the key.
 *
 *              Given the key handle, GetKey should return the pointer
 *              to the key string.
 *
 *              uchar_t * (*GetKey) (HPTKEY);
 *
 *      phPTree - pointer to handle of the PTree.
 *              To be filled on successful return.
 *
 * RETURN:
 *      NO_ERROR on success.  *phPTree filled in with handle to PTree.
 *      otherwize returns error code (can be ERROR_INTERRUPTED).
 *
 * CALLS:       VMAllocKHB, KSEMInit
 */

long
PTCreate(ulong_t        lFlags,
         VMHOB          owner,
         ulong_t        cMaxNodes,
         PF_KEYALLOC    KeyAlloc,
         PF_KEYFREE     KeyFree,
         PF_GETKEY      GetKey,
         HPTREE         *phPTree)
{
             HPTREE      hPTreeAlloc;
    register HPTREE      hPTree;
             int         rc;

    rc = VMAllocKHB(((lFlags & PTF_HEADSWAP) ? VM_HKH_PUB_SWAPRW :
                                               VM_HKH_PUB_RESRW),
                    sizeof(PTHEAD), owner, 0, (void **) SSToDS(&hPTreeAlloc));

    if (rc != NO_ERROR)
    {
        return(rc);
    }

    hPTree = hPTreeAlloc;

    /* init header node */
    hPTree->pth_nHeader.ptn_bi          = -1;
    hPTree->pth_nHeader.ptn_iKeyLen     = -1;
    hPTree->pth_nHeader.ptn_pnLeft      = &hPTree->pth_nHeader;
    hPTree->pth_nHeader.ptn_pnRight     = &hPTree->pth_nHeader;
    hPTree->pth_nHeader.ptn_hKey        = 0;

    /* init ksem */
    KSEMInit((HKSEM) &hPTree->pth_ksem, KRNL_SHARESEM, 0);

    /* init rest of header */
    hPTree->pth_lFlags          = lFlags;
    hPTree->pth_owner           = owner;
    hPTree->pth_cNodes          = 0;
    hPTree->pth_cMaxNodes       = cMaxNodes;
    hPTree->pth_KeyAlloc        = KeyAlloc;
    hPTree->pth_KeyFree         = KeyFree;
    hPTree->pth_GetKey          = GetKey;
    hPTree->pth_pfWalk          = (PF_WALK) NULL;

    *phPTree = hPTree;          /* fill in users handle to PTree */

    return(NO_ERROR);
}


/***LP ptFindNode() - find closest matching node in ptree
 *
 * Examines a PTree and finds the "closest match" for the given
 * key (the only node which could possibly match the given name).
 *
 * ENTRY:       hPTree  - handle to PTree
 *              pbKey   - pointer to key string
 *              biMax   - number of bits in key (0 to biMax-1)
 *
 * RETURN:      P_PTNODE - pointer to ptree node with closest match
 *
 * CALLS:       BitTestCheck
 */

P_PTNODE
ptFindNode( hPTree, pbKey, biMax )
    HPTREE              hPTree;
    register uchar_t *  pbKey;
    BI                  biMax;
{
    register BI         bi;
    register P_PTNODE   pn;

    pn = hPTree->pth_nHeader.ptn_pnLeft;

    /* go till we follow an up pointer */
    if (!IsRootNode(pn)) /* non-empty tree: walk tree, else just return root */
    do {
        bi = pn->ptn_bi;

        if ( BitTestCheck( pbKey, bi, biMax ) == 0 )
            pn = pn->ptn_pnLeft;
        else
            pn = pn->ptn_pnRight;

    } while ( pn->ptn_bi > bi ) ;

    return pn;
}


/***LP ptFindNodeStop() - find closest matching node in ptree with early out
 *
 * Examines a PTree and finds the "closest match" for the given
 * key (the only node which could possibly match the given name).
 * biMax is the maximum bit offset to examine (for example, the key length).
 * When biMax is reached, the search will stop immediatly.
 *
 * ENTRY:       hPTree          - handle to PTree
 *              pbKey           - pointer to key string
 *              biMax           - number of bits in key (0 to biMax-1)
 *              ppnParent       - pointer to pointer to node to be filled
 *                                in with pointer to parent of node found.
 *                                Can be NULL if not needed.
 *
 * RETURN:      P_PTNODE - pointer to ptree node with closest match
 *
 * CALLS:       BitTest
 */

P_PTNODE
ptFindNodeStop( hPTree, pbKey, iKeyLen, biMax, ppnParent )
    HPTREE              hPTree;
    register uchar_t *  pbKey;
    KEYLEN              iKeyLen;
    BI                  biMax;
    P_PTNODE *          ppnParent;
{
    register BI         bi;
    register P_PTNODE   pn;
    P_PTNODE            pnParent;

    pnParent = &hPTree->pth_nHeader;    /* parent = root */
    pn = pnParent->ptn_pnLeft;

    /*
     * go till we follow an up pointer or go past end of key
     */
    if (!IsRootNode(pn))        /* non-empty tree: walk tree */
    {
        do
        {
            bi = pn->ptn_bi;
            if ( bi >= biMax )      /* early out if past end of key */
            {
                break;
            }

            pnParent = pn;          /* Advance the parent pointer. */

            if (BitTestCheck(pbKey, bi, (BITS_PER_BYTE * iKeyLen)) == 0)
            {
                pn = pn->ptn_pnLeft;
            }
            else
            {
                pn = pn->ptn_pnRight;
            }

        }while ( pn->ptn_bi > bi ) ;
    }

    if ( ppnParent != NULL )
    {
        *ppnParent = pnParent;
    }

    return pn;
}


/***LP CountMatch() - return count of matching bytes in two buffers
 *
 * ENTRY:       pbKey1  - pointer to first  buffer
 *              pbKey2  - pointer to second buffer
 *              cMax - max number of bytes to compare
 *
 * RETURN:      number of matching bytes
 *
 * CALLS:       NONE
 *
 * Compares two buffers returning the number of bytes that matched.
 * If the buffers match exactly for cMax bytes, then cMax is returned.
 *
 * Example:
 *
 * CountMatch( "123456789A", "123456789ABCDEF", 10 ) => 10
 * CountMatch( "123456789A", "12345678 ABCDEF", 10 ) => 8
 * CountMatch( "123456789A", "12345 789ABCDEF", 10 ) => 5
 * CountMatch( "123456789A", "12 456789ABCDEF", 10 ) => 2
 *
 */

KEYLEN
CountMatch( register uchar_t *pbKey1, register uchar_t *pbKey2, KEYLEN cMax )
{
    register KEYLEN c;

    for( c = cMax; c > 0 && *pbKey1++ == *pbKey2++; --c )
        ;
    return cMax - c;
}


/***LP ptFirstDiff - return the bit index where the two keys first differ
 *
 * All normal keys are terminated by a virtual "1000..." bit pattern past
 * the end of the key (TERMBYTE = 0x80).  The root key is all zeros.
 * This guarantees that we can test bits even beyond the end of the key.
 *
 * The key is to first find the right bytes that the first difference is in,
 * whether they be from the key or the virtual byte beyond the end of the key.
 * Then find the first bit on in the xor of the two bytes.
 *
 * There are three possiblities:
 *
 *      If key1 is the root (all zeros),
 *      the differing bit is the first non-zero bit in key2, OR
 *      the virtual bit past the end of key2 if key2 is all null bits.
 *
 *      If the first differing byte is within both keys, then the first
 *      differing bit is simply the first bit on in the xor of the bytes.
 *
 *      If the first differing byte is beyond the end of key1:
 *
 *          key1 is a prefix of key2
 *
 *          key1        = foo
 *          len1        = 3
 *          key2        = foobar
 *          len2        = 6
 *          matchlen    = len1
 *
 *          If Key2[matchlen] != TERMBYTE, then
 *              x = Key2[matchlen] ^ TERMBYTE
 *
 *          If Key2[matchlen] == TERMBYTE, then
 *              matchlen += scan for next non-zero in Key2
 *              If we reach the end of Key2 without finding a non-zero byte,
 *                  x = TERMBYTE
 *              else
 *                  x = Key2[matchlen]
 *
 *          bit index = matchlen * 8 + FirstBit(x)
 *
 *
 * ENTRY:       pbKey1  - pointer to first  key
 *              len1    - length  of first  key in bytes
 *              pbKey2  - pointer to second key
 *              len2    - length  of second key in bytes
 *              MatchLen- number of matching bytes between pbKey1 and pbKey2
 *
 * RETURN:      bit index of first differing bit
 *
 * CALLS:       NONE
 */

BI
ptFirstDiff( pbKey1, len1, pbKey2, len2, matchlen )
    uchar_t *           pbKey1;
    KEYLEN              len1;
    register uchar_t *  pbKey2;
    register KEYLEN     matchlen; /* matching bytes between pbKey1 and pbKey2 */
    register KEYLEN     len2;
{
    long                x;

    /* swap if necessary such that len1 <= len2 */
    if (len2 < len1) {
        uchar_t *       pbKey3  = pbKey1;
        KEYLEN          len3    = len1;

        pbKey1  = pbKey2;
        len1    = len2;

        pbKey2  = pbKey3;
        len2    = len3;
    }

    if (len1 == -1) {                   /* pbKey1 is root */
        ptAssert(matchlen == 0);        /* matchlen must be zero */

        /* find first non-zero byte in key */

        while (matchlen < len2 && *pbKey2 == '\0') {
            pbKey2++;           /* try next byte */
            matchlen++;         /* matchlen = index of non-zero byte */
        }

        if (matchlen == len2)   /* past end of pbKey2? */
            x = TERMBYTE;       /*  yes, use TERMBYTE */
        else
            x = *pbKey2;                /*  no,  use first non-zero byte */

    } else if (matchlen < len1) {       /* differs before end of both keys */
        /* get xor of first byte that differs */
        x = pbKey1[matchlen] ^ pbKey2[matchlen];

    } else {
        /*
         * Matches for full length of pbKey1; pbKey1 is prefix of pbKey2
         * Find next bit that differs.  All keys are terminated by a
         * "1000..." bit pattern past the end of the key.
         *
         * 1. If pbKey2[matchlen] != TERMBYTE, then
         *      x = pbKey2[matchlen] ^ TERMBYTE
         *
         * 2. If pbKey2[matchlen] == TERMBYTE, then
         *      matchlen += scan for next non-zero in pbKey2
         *      x = pbKey2[matchlen]
         *
         * 3. If we reach the end of pbKey2 without finding a non-zero byte,
         *      x = TERMBYTE
         */

        ptAssert(matchlen == len1);
        ptAssert(len1 < len2);

        pbKey2 += matchlen;
        /* pbKey2 -> first byte in pbKey2 past end of pbKey1 */

        if (*pbKey2 != TERMBYTE) { /* next byte in found key is NOT TERMBYTE */
            x = *pbKey2 ^ TERMBYTE;
        } else {
            /* next byte in pbKey2 IS TERMBYTE, find next non-zero byte */
            do {
                pbKey2++;                       /* try next byte */
                matchlen++;             /* matchlen = index of non-zero byte */
            } while (matchlen < len2 && *pbKey2 == '\0') ;

            if (matchlen == len2)       /* past end of pbKey2? */
                x = TERMBYTE;           /*  yes, use TERMBYTE */
            else
                x = *pbKey2;            /* x = first non-zero byte */
        }
    }

    /* return index of first differing bit = index * 8 + bit */

    return( (BI) (matchlen << 3) + FirstBit(x) );
}


/***EP PTInsert - inserts a new key into the PTree
 *
 * ENTRY:       hPTree  - handle to the ptree
 *              pbKey   - pointer to key string
 *              iKeyLen - length of key string in bytes
 *              phKey   - pointer to key handle to be filled in on success
 *
 * RETURN:      NO_ERROR if key is found. *phKey is filled in with handle.
 *              Otherwise error code.
 *
 * CALLS:       KSEMRequestExclusive, ptFindNode, GetKey, CountMatch,
 *              ptFirstDiff, VMAllocKHB, VMFreeKHB, KSEMRelease, KeyAlloc
 *              ptFindNodeStop, BitTestCheck
 */

long
PTInsert(hPTree, pbKey, iKeyLen, phKey)
    HPTREE              hPTree;
    register uchar_t *  pbKey;
    KEYLEN              iKeyLen;
    HPTKEY *            phKey;
{
    register P_PTNODE   pn;
    P_PTNODE            pnNew;
    P_PTNODE            pnParent;
    register uchar_t *  pb;
    KEYLEN              matchlen;
    BI                  bi;
    int                 rc;
    VMHKH               heap;

    ptAssert(0 <= iKeyLen && iKeyLen < MAXKEYLEN); /* valid */

    if (rc = KSEMRequestExclusive((HKSEM) &hPTree->pth_ksem, -1))
        return(rc);

#ifdef VMSTRICT
    ptCheckTree(hPTree);
#endif

    /* Look up the closest match in the existing tree.  If it's an exact
     * match, use that; otherwise find where to insert it based on what
     * bits differ from the found node.
     */

    pn = ptFindNode( hPTree, pbKey, (BI) (BITS_PER_BYTE * iKeyLen) );

    if (!IsRootNode(pn))                /* not header node */
    {
        pb = hPTree->pth_GetKey(pn->ptn_hKey);

        /* compare only up to min of lengths */
        matchlen = CountMatch(pb, pbKey, min(iKeyLen, (KEYLEN) pn->ptn_iKeyLen) );

        /* if matches for full length and lengths are equal then already in tree */
        if ( matchlen == iKeyLen && iKeyLen == (KEYLEN) pn->ptn_iKeyLen )
        {
            /* panic if panicinsert flag set */
            ptAssert((hPTree->pth_lFlags & PTF_PANICINSERT) == 0);

            KSEMRelease((HKSEM) &hPTree->pth_ksem);
            *phKey = pn->ptn_hKey;
            return( NO_ERROR );
        }

        /* get bit index of first differing bit */
        bi = ptFirstDiff( pbKey, iKeyLen, pb, (KEYLEN) pn->ptn_iKeyLen, matchlen );
    }
    else
    {
        /* header node found, get first differing bit */
        bi = ptFirstDiff( NULL, -1, pbKey, iKeyLen, 0 );
    }

    /* allocate new PTree node only if not past cMaxNodes */
    if (hPTree->pth_cNodes >= hPTree->pth_cMaxNodes)
    {
        rc = ERROR_NOT_ENOUGH_MEMORY;   /* return error indication */
    }
    else
    {
        /* BUGBUG bryand 1-8-90 - allocate PTree node from BMP32 */

        if (hPTree->pth_lFlags & PTF_NODESWAP)
        {
            heap = VM_HKH_PUB_SWAPRW;
        }
        else
        {
            heap = VM_HKH_PUB_RESRW;
        }

        rc = VMAllocKHB(heap, sizeof(PTNODE), hPTree->pth_owner, 0, (void **) SSToDS(&pnNew));
    }

    if ( rc != NO_ERROR )
    {
        KSEMRelease((HKSEM) &hPTree->pth_ksem);
        return(rc);     /* return error indication */
    }

    pnNew->ptn_iKeyLen = (I_KEYLEN) iKeyLen;
    pnNew->ptn_bi = bi;

    /* call user code to allocate and init the object and return a handle */

    rc = hPTree->pth_KeyAlloc(pbKey, iKeyLen, &pnNew->ptn_hKey);

    if ( rc != NO_ERROR )
    {
        KSEMRelease((HKSEM) &hPTree->pth_ksem);

        VMFreeKHB(heap,pnNew);
        return(rc);
    }

    /* The key may have moved during KeyAlloc if the user code
     * copied the key string into a newly allocated structure,
     * so re-get the pointer to the key.
     */
    pbKey = hPTree->pth_GetKey(pnNew->ptn_hKey);

#ifdef VMSTRICT
    if((hPTree->pth_lFlags & 0x4000) != 0)
    {
        printf("I %s\n",pbKey + 2);
    }
#endif

    /* Find the appropriate place to insert the new node */
    /* searching only up to the bit that differs. */

    pn = ptFindNodeStop( hPTree, pbKey, iKeyLen, bi, SSToDS(&pnParent) );

    /* BUGBUG performance: upgrade readlock to write lock here */

    if ( BitTestCheck( pbKey, bi, (BI) (BITS_PER_BYTE * iKeyLen) ) == 0 )
    {
        pnNew->ptn_pnLeft  = pnNew;
        pnNew->ptn_pnRight = pn;
    }
    else
    {
        pnNew->ptn_pnLeft  = pn;
        pnNew->ptn_pnRight = pnNew;
    }

    ptAssert(pnParent->ptn_bi < bi);

    /* if parent is root, or parents bit is zero, attatch on left */
    if ( pnParent->ptn_bi == -1 ||
         BitTestCheck( pbKey, pnParent->ptn_bi, (BI) (BITS_PER_BYTE * iKeyLen) ) == 0 )
    {
        pnParent->ptn_pnLeft  = pnNew;
    }
    else
    {
        pnParent->ptn_pnRight = pnNew;
    }

    hPTree->pth_cNodes++;       /* inc cNodes BEFORE clearing ksem */

    ptAssert(!GetTag(pnNew));   /* assert tag bit off */

#ifdef VMSTRICT
    ptCheckTree(hPTree);
#endif

    KSEMRelease((HKSEM) &hPTree->pth_ksem);
    *phKey = pnNew->ptn_hKey;

    return( NO_ERROR );
}


/***EP PTFind() - finds a specific key in the ptree
 *
 * ENTRY:       hPTree  - handle to the ptree
 *              pbKey   - pointer to key string
 *              iKeyLen - length of key string in bytes
 *              phKey   - pointer to key handle to be filled in on success
 *
 * RETURN:      NO_ERROR if key is found. *phKey is filled in with handle.
 *              Otherwise error code.
 *
 * CALLS:       KSEMRequestShared, ptFindNode, memcmp, GetKey, KSEMRelease
 */

long
PTFind( hPTree, pbKey, iKeyLen, phKey )
    HPTREE      hPTree;
    uchar_t *   pbKey;
    KEYLEN      iKeyLen;
    HPTKEY *    phKey;
{
    P_PTNODE    pn;
    int         rc;

    ptAssert(0 <= iKeyLen && iKeyLen < MAXKEYLEN); /* valid */

    if (rc = KSEMRequestShared((HKSEM) &hPTree->pth_ksem, -1))
        return(rc);

    pn = ptFindNode( hPTree, pbKey, (BI) (BITS_PER_BYTE * iKeyLen) );

    /* if node found is same length and key matches */
    if ( (KEYLEN) pn->ptn_iKeyLen == iKeyLen &&
         memcmp( pbKey, hPTree->pth_GetKey(pn->ptn_hKey), iKeyLen ) == 0 ) {

        *phKey = pn->ptn_hKey;
        rc = NO_ERROR;          /* found */

    } else
        rc = -1;                /* not found */

    KSEMRelease((HKSEM) &hPTree->pth_ksem);

    return(rc);
}


/***EP PTFindFromPrefix() - finds a key with the given key as a prefix
 *
 * ENTRY:       hPTree  - handle to the ptree
 *              pbKey   - pointer to key string
 *              iKeyLen - length of key string in bytes
 *              phKey   - pointer to key handle to be filled in on success
 *
 * RETURN:      NO_ERROR if key is found. *phKey is filled in with handle.
 *              Otherwise error code.
 *
 * NOTE:        There may be multiple keys in the tree that have the search
 *              key as a prefix.  Only the first found is returned.
 *              We could enable finding all prefixes by allowing to continue
 *              searching from a specific node (all prefixes will be in the
 *              same subtree).
 *
 * WARNING:     For this to work properly finding a path prefix that is on
 *              a path separator boundary, the search string must contain
 *              a trailing path separator.  Otherwise "c:\foo" is a prefix
 *              of "c:\foobar\baz".  What you want is for "c:\foo\" to be
 *              a prefix of "c:\foo\bar\baz".
 *
 * CALLS:       KSEMRequestShared, ptFindNodeStop, memcmp, GetKey, KSEMRelease
 */

long
PTFindFromPrefix( hPTree, pbKey, iKeyLen, phKey )
    HPTREE      hPTree;
    uchar_t *   pbKey;
    KEYLEN      iKeyLen;
    HPTKEY *    phKey;
{
    P_PTNODE    pn;
    int         rc;

    ptAssert(0 <= iKeyLen && iKeyLen < MAXKEYLEN); /* valid */

    if (rc = KSEMRequestShared((HKSEM) &hPTree->pth_ksem, -1))
        return(rc);

    pn = ptFindNodeStop(hPTree, pbKey, iKeyLen,
                            (BI) (BITS_PER_BYTE * iKeyLen), NULL);

    /* if node found is same length or longer and key matches */
    if ( (KEYLEN) pn->ptn_iKeyLen >= iKeyLen &&
         memcmp( pbKey, hPTree->pth_GetKey(pn->ptn_hKey), iKeyLen ) == 0 ) {

        *phKey = pn->ptn_hKey;
        rc = NO_ERROR;

    } else
        rc = -1;

    KSEMRelease((HKSEM) &hPTree->pth_ksem);

    return(rc);
}


/***EP PTFindMaxPrefix() - finds the longest prefix of the given key
 *
 * ENTRY:       hPTree  - handle to the ptree
 *              pbKey   - pointer to key string
 *              iKeyLen - length of key string in bytes
 *              phKey   - pointer to key handle to be filled in on success
 *
 * RETURN:      NO_ERROR if key is found. *phKey is filled in with handle.
 *              Otherwise error code.
 *
 * Finds the key that has the longest proper prefix of the search key.
 *
 * Thus, if the tree included "ca" and "cast", and the search key
 * was "cas", "ca" would be found rather than "cast".
 *
 * NOTE - There may be multiple keys in the tree that are prefixes of
 * the search key.  Only the (first) longest found is returned.
 * We could enable finding all prefixes by allowing to continue searching
 * from a specific node (all prefixes will be in the same subtree).
 *
 * walk down the tree comparing for a match of length of node key.
 *
 * CALLS:       KSEMRequestShared, BitTest, memcmp, GetKey, KSEMRelease
 */

long
PTFindMaxPrefix( hPTree, pbKey, iKeyLen, phKey )
    HPTREE              hPTree;
    register uchar_t *  pbKey;
    KEYLEN              iKeyLen;
    HPTKEY *            phKey;
{
    BI                  biMax = (BI) (BITS_PER_BYTE * iKeyLen);
    register BI         bi;
    register P_PTNODE   pn;
    P_PTNODE            pnBest = NULL;
    I_KEYLEN            iBest = 0;
    int                 rc;

    ptAssert(0 <= iKeyLen && iKeyLen < MAXKEYLEN); /* valid */

    if (rc = KSEMRequestShared((HKSEM) &hPTree->pth_ksem, -1))
        return(rc);

    pn = hPTree->pth_nHeader.ptn_pnLeft;

    /* go till we follow an up pointer */
    if (!IsRootNode(pn))        /* non-empty tree: walk tree */
    do {
        bi = pn->ptn_bi;
        if ( bi >= biMax )
            break;

        if ( (KEYLEN) pn->ptn_iKeyLen <= iKeyLen &&
             (KEYLEN) pn->ptn_iKeyLen >  iBest   &&
             memcmp(pbKey, hPTree->pth_GetKey(pn->ptn_hKey), pn->ptn_iKeyLen) == 0 ) {
            pnBest = pn;
            iBest  = pn->ptn_iKeyLen;
        }

        if ( BitTest( pbKey, bi ) == 0 )
            pn = pn->ptn_pnLeft;
        else
            pn = pn->ptn_pnRight;

    } while ( pn->ptn_bi > bi ) ;

    if (pnBest) {
        *phKey = pnBest->ptn_hKey;
        rc = NO_ERROR;
    } else
        rc = -1;

    KSEMRelease((HKSEM) &hPTree->pth_ksem);

    return(rc);
}


/***LP ptDeleteNode() - delete a node from the PTree
 *
 * BUGBUG - documentation
 *
 * We need to find "both" parents of the node to be deleted, the
 * parent with a down-link to the delete node and the parent with the
 * up-link to the delete node. The up-link parent is "moved up" to take
 * the place of the node being deleted, which means it assumes the bit
 * index and pointers of the node being deleted (with a few exceptions).
 *
 * The down-link parent is changed to point to the node which was "moved up".
 * The parent of the up-link parent is changed to point to the node which
 * was below the up-link parent before it was "moved up".
 *
 * Hong Lee Yu (hongly@microsoft) inspired this deletion algorithm.
 *
 * ENTRY:       hPTree  - handle to the ptree
 *              pnDelete- pointer to node to delete
 *              biMax   - length of pnDelete's key string in bits
 *
 * RETURN:      NO_ERROR if key is found in ptree and successfully deleted.
 *              Otherwise error code.
 */

void
ptDeleteNode( HPTREE hPTree, register P_PTNODE pnDelete, BI biMax)
{
    register P_PTNODE   pn;
    P_PTNODE            pnDownPar;      /* down-link parent. */
    register P_PTNODE   pnUpPar;        /* up-link parent. */
    P_PTNODE            pnParUpPar;     /* parent of up-link parent. */
    P_PTNODE            pnChildUpPar;   /* child of up-link parent. */
    uchar_t *           pb;
    int                 rc;
    VMHKH               heap;
#ifdef VMSTRICT
    int                 fParentFound = 0;       /* assert parent found once */
#endif

    /* Walk the tree, looking for both of 'pnDelete's parents:
     * the internal parent (whose bit number is less than 'pnDelete's),
     * and the external parent (whose bit is not less than 'pnDelete's).
     * Internal parent is the same as the down-link parent, external parent
     * is the same as the up-link parent.
     */

    pb = hPTree->pth_GetKey(pnDelete->ptn_hKey);
    pnUpPar = &hPTree->pth_nHeader;
    pn = pnUpPar->ptn_pnLeft;

    do {
        if ( pn == pnDelete ) {
            pnDownPar = pnUpPar;
#ifdef VMSTRICT
            ptAssert(fParentFound++ == 0);      /* assert parent found once */
#endif
        }
        pnParUpPar = pnUpPar;                   /* Advance parent of up-link. */
        pnUpPar = pn;                           /* Advance  up-link. */
        if ( BitTestCheck( pb, pn->ptn_bi, biMax ) == 0 ) /* Advance pointer. */
            pn = pn->ptn_pnLeft;
        else
            pn = pn->ptn_pnRight;

    }while((pn->ptn_bi >= pnUpPar->ptn_bi) && (pn != pnUpPar));

    ptAssert(pn == pnDelete);
#ifdef VMSTRICT
    ptAssert(fParentFound == 1);                /* assert parent found once */
#endif

    /* Determine the child of the up-link parent of pnDelete.
     * This child is the child that is not pnDelete. (In other words, the
     * pointer that does not point up to pnDelete.)
     */

    if ( pnUpPar->ptn_pnLeft == pnDelete ) {
        pnChildUpPar = pnUpPar->ptn_pnRight;
    } else {
        pnChildUpPar = pnUpPar->ptn_pnLeft;
    }

#ifdef STANDALONE
    if ( hPTree->pth_lFlags & PTF_DEBUG ) {
     printf("ptDeleteNode:\n");
     printf(" pnDelete     = %s\n", hPTree->pth_GetKey(pnDelete    ->ptn_hKey));
     printf(" pnDownPar    = %s\n", hPTree->pth_GetKey(pnDownPar   ->ptn_hKey));
     printf(" pnUpPar      = %s\n", hPTree->pth_GetKey(pnUpPar     ->ptn_hKey));
     printf(" pnParUpPar   = %s\n", hPTree->pth_GetKey(pnParUpPar  ->ptn_hKey));
     printf(" pnChildUpPar = %s\n", hPTree->pth_GetKey(pnChildUpPar->ptn_hKey));
    }
#endif /* STANDALONE */

    /* The following steps are order sensitive. They include:
     * 1. Down_Par   = Up_Par.
     * 2. Par_Up_Par = Child_Up_Par.
     * 3. "Move up" Up_Par to assume Delete's position (bi and pointers).
     */

    if ( pnDownPar->ptn_pnLeft == pnDelete )
        pnDownPar->ptn_pnLeft  = pnUpPar;
    else
        pnDownPar->ptn_pnRight = pnUpPar;

    if ( pnParUpPar->ptn_pnLeft == pnUpPar )
        pnParUpPar->ptn_pnLeft  = pnChildUpPar;
    else
        pnParUpPar->ptn_pnRight = pnChildUpPar;

    /* Move up the up-link parent to assume pnDelete's role. */

    pnUpPar->ptn_bi = pnDelete->ptn_bi;
    pnUpPar->ptn_pnLeft  = pnDelete->ptn_pnLeft;
    pnUpPar->ptn_pnRight = pnDelete->ptn_pnRight;

    rc = hPTree->pth_KeyFree( pnDelete->ptn_hKey );
    ptAssert(rc == NO_ERROR);

    if (hPTree->pth_lFlags & PTF_NODESWAP)
        heap = VM_HKH_PUB_SWAPRW;
    else
        heap = VM_HKH_PUB_RESRW;
    VMFreeKHB(heap,pnDelete);
}


/***EP PTDelete() - delete a key from the ptree
 *
 * ENTRY:       hPTree  - handle to the ptree
 *              pbKey   - pointer to key string
 *              iKeyLen - length of key string in bytes
 *
 * RETURN:      NO_ERROR if key is found. *phKey is filled in with handle.
 *              Otherwise error code.
 *
 * CALLS:       KSEMRequestExclusive, ptFindNode, memcmp, GetKey, ptDeleteNode,
 *              KSEMRelease
 */

long
PTDelete( HPTREE hPTree, uchar_t *pbKey, KEYLEN iKeyLen )
{
    register P_PTNODE   pnDelete;
    int                 rc;

    ptAssert(0 <= iKeyLen && iKeyLen < MAXKEYLEN); /* valid */

    if (rc = KSEMRequestExclusive((HKSEM) &hPTree->pth_ksem, -1))
        return(rc);

#ifdef VMSTRICT
    ptCheckTree(hPTree);

    if((hPTree->pth_lFlags & 0x4000) != 0)
    {
        printf("D %s\n",pbKey + 2);
    }
#endif

    pnDelete = ptFindNode( hPTree, pbKey, (BI) (BITS_PER_BYTE * iKeyLen) );

    /* don't try to delete header node */
    if ( pnDelete->ptn_iKeyLen == (I_KEYLEN) iKeyLen &&
         memcmp(hPTree->pth_GetKey(pnDelete->ptn_hKey), pbKey, iKeyLen ) == 0) {

        /* Found a key that matches the search key. */

        ptDeleteNode( hPTree, pnDelete, (BI) (BITS_PER_BYTE * iKeyLen) );

        hPTree->pth_cNodes--;           /* dec cNodes BEFORE clearing ksem */
        ptAssert(hPTree->pth_cNodes >= 0);

        rc = NO_ERROR;                  /* key deleted */
    } else {
        /* key not found, fail or panic if panicdelete flag set */
        ptAssert((hPTree->pth_lFlags & PTF_PANICDELETE) == 0);
        rc = -1;                        /* not found */
    }

#ifdef VMSTRICT
    ptCheckTree(hPTree);
#endif

    KSEMRelease((HKSEM) &hPTree->pth_ksem);

    return(rc);
}


/***EP PTDestroy() - delete entire ptree
 *
 * BUGBUG       NOT IMPLEMENTED
 *
 * ENTRY:       hPTree  - handle to the ptree
 *
 * RETURN:      NO_ERROR if ptree is destroyed
 *              Otherwise error code.
 *
 * CALLS:       NONE
 */

long
PTDestroy(HPTREE hPTree)
{
    hPTree;
    return(ERROR_CALL_NOT_IMPLEMENTED);
}


/***LP ptWalkWorker() - call user function with HKEY instead of P_PTNODE
 *
 * The supplied function is called with each key in the ptree.
 *
 * ENTRY:       hPTree          - handle to PTree
 *              pn              - pointer to node to call user function with
 *              hPTree->pfWalk  - pointer to user function to call
 *
 * RETURN:      return code returned from user functoin hPTree->pfWalk.
 */

long
ptWalkWorker( HPTREE hPTree, P_PTNODE pn )
{
    return ((hPTree->pth_pfWalk)(hPTree, pn->ptn_hKey));
}


/***EP PTWalk() - walk ptree calling user function
 *
 * The supplied function is called with each key in the ptree.
 * The ptree is walked until there are no more keys,
 * OR the user function returns a non-zero return code.
 *
 * ENTRY:       hPTree  - handle to the ptree
 *              pfWalk  - pointer to function to call for each key
 *
 * RETURN:      NO_ERROR if entire ptree is walked
 *              Otherwise error code returned from pfWalk.
 */

long
PTWalk( hPTree, pfWalk )
    HPTREE      hPTree;
    PF_WALK     pfWalk;
{
    int         rc;

    if (rc = KSEMRequestExclusive((HKSEM) &hPTree->pth_ksem, -1))
        return(rc);

    hPTree->pth_pfWalk = pfWalk;

    rc = ptWalkNodeWorker( hPTree, ptWalkWorker );

    hPTree->pth_pfWalk = NULL;

    KSEMRelease((HKSEM) &hPTree->pth_ksem);

    return(rc);
}


/***LP ptWalkNodeWorker() - walk ptree calling user function
 *
 * The supplied function is called with each node in the ptree.
 * The ptree is walked until there are no more nodes,
 * OR the user function returns a non-zero return code.
 *
 * ENTRY:       hPTree          - handle to the ptree
 *              pfWalkNode      - pointer to function to call for each key
 *
 * RETURN:      NO_ERROR if entire ptree is walked
 *              Otherwise error code returned from pfWalkNode.
 *
 * PSEUDOCODE:
 *
 *      Link Inversion Traversal
 *
 *      Data Structure Techniques by Thomas A. Standish - 1980 - Page 76
 *
 *      In order to avoid using a large amount of stack space to walk the
 *      tree using recursion, I chose to use a link inversion traversal.
 *
 *      Here is the alogorithm as presented in the book:
 *
 * 1:   pres -> root node
 *      prev =  null
 *
 * 2:   if (preorder)
 *          visit(pres)
 *
 * 3:   next = pres->left
 *      if (next != null)
 *          pres->left = prev
 *          prev = pres
 *          pres = next
 *          goto 2
 *
 * 4:   if (inorder)
 *          visit(pres)
 *
 * 5:   next = pres->right
 *      if (next != null)
 *          pres->tag = 1
 *          pres->right = prev
 *          prev = pres
 *          pres = next
 *          goto 2
 *
 * 6:   if (postorder)
 *          visit(pres)
 *
 * 7:   if (prev == null)
 *          goto 8
 *      else if (prev->tag == 0)
 *          next = prev->left
 *          prev->left = pres
 *          pres = prev
 *          prev = next
 *          goto 4
 *      else
 *          next = prev->right
 *          prev->tag = 0
 *          prev->right = pres
 *          pres = prev
 *          prev = next
 *          goto 6
 *
 * 8:   Done
 *
 *
 *      The above algorithm makes some assumptions that are not true
 *      for PTrees.  It assumes that leaf nodes have null left and right
 *      pointers, whereas PTree leaf nodes have up pointers that can be
 *      distinguished by the fact that the bit index will be smaller or
 *      equal to the current bit index.
 *
 *      Putting the tag bit into the low bit of the left or right pointer
 *      would work as long as the memory was word aligned, but this might
 *      not work in the standalone version using malloc().
 *      It would also require masking the pointer every time we used it.
 *
 *      Putting the tag bit into the high bit of the bit index would turn
 *      the bit index negative.  This would be bad as the bit index is
 *      used to tell if the pointer is up pointer (leaf node).
 *
 *      So, the tag bit is now on the Key Length field.
 *      See GetTag, SetTag and ClearTag macros above.
 *
 *      Currently, the user function is called in pre-order order.
 *      This is the only time that we can guarantee that the node
 *      is in it's original state (tag is clear and left and right
 *      pointers point to their normal places).
 *
 *      We could add a flag to specify which order to call the user function.
 *      However, we can only guarantee the left and right pointers and the
 *      key length are correct if called in pre-order.
 *      As long as the user only cares about the hKey, it doesn't matter
 *      which order it is called in.  If the user code wants to look at
 *      the key length it could take the absolute value of the key
 *      length as a negative value can only be for a tag set or the root.
 *
 *      NOTE: This will NOT call the user routine for the root node of the
 *      tree (the root node is not a real node).
 *      The user routine is called only with real nodes.
 *      If the tree is empty, the user routine is never called.
 */

long
ptWalkNodeWorker(HPTREE hPTree, PF_WALKNODE pfWalkNode)
{
    P_PTNODE    pnPres = hPTree->pth_nHeader.ptn_pnLeft;
    P_PTNODE    pnPrev = 0;
    P_PTNODE    pnNext;
    long        rc = 0;

    if (!IsRootNode(pnPres)) {

Preorder:
        // if (preorder) visit(pres)
        if (rc == 0)                    // call user only if last rc == 0
            rc = (pfWalkNode)(hPTree, pnPres);

        // follow left link
        pnNext = pnPres->ptn_pnLeft;
        if (pnNext->ptn_bi > pnPres->ptn_bi) {
            pnPres->ptn_pnLeft = pnPrev;
            pnPrev = pnPres;
            pnPres = pnNext;
            goto Preorder;
        }

Inorder:
        // if (inorder) visit(pres)

        // follow right link
        pnNext = pnPres->ptn_pnRight;
        if (pnNext->ptn_bi > pnPres->ptn_bi) {
            SetTag(pnPres);
            pnPres->ptn_pnRight = pnPrev;
            pnPrev = pnPres;
            pnPres = pnNext;
            goto Preorder;
        }

Postorder:
        // if (postorder) visit(pres)

        if (pnPrev == NULL)
            goto Done;

        // go up fixing pointers
        if (GetTag(pnPrev) == 0) {
            pnNext = pnPrev->ptn_pnLeft;
            pnPrev->ptn_pnLeft = pnPres;
            pnPres = pnPrev;
            pnPrev = pnNext;
            goto Inorder;
        } else {
            pnNext = pnPrev->ptn_pnRight;
            ClearTag(pnPrev);
            pnPrev->ptn_pnRight = pnPres;
            pnPres = pnPrev;
            pnPrev = pnNext;
            goto Postorder;
        }
Done:   ;
    }
    return(rc);
}


/***EP PTWalkNode() - walk ptree calling user function
 *
 * The supplied function is called with each node in the ptree.
 * The ptree is walked until there are no more nodes,
 * OR the user function returns a non-zero return code.
 *
 * ENTRY:       hPTree          - handle to the ptree
 *              pfWalkNode      - pointer to function to call for each node
 *
 * RETURN:      NO_ERROR if entire ptree is walked
 *              Otherwise error code returned from pfWalkNode.
 */

long
PTWalkNode( HPTREE hPTree, PF_WALKNODE pfWalkNode )
{
    int         rc;

    if (rc = KSEMRequestExclusive((HKSEM) &hPTree->pth_ksem, -1))
        return(rc);

    rc = ptWalkNodeWorker( hPTree, pfWalkNode);

    KSEMRelease((HKSEM) &hPTree->pth_ksem);

    return(rc);
}


#ifndef STANDALONE

/***EP PTInsert_16() - 16 bit interface to PTInsert */

long
PTInsert_16( hPTree, selKey, offKey, iKeyLen, phKey )
    HPTREE      hPTree;
    SEL         selKey;         /* 16 bit selector */
    uchar_t *   offKey;         /* 32 bit offset */
    KEYLEN      iKeyLen;
    HPTKEY      *phKey;
{
    uchar_t *   pbKey;

    pbKey = (uchar_t *) SELVirtToLin((ulong_t) offKey, selKey);
    if ((long) pbKey == -1)
        return(-1);
    return( PTInsert( hPTree, pbKey, iKeyLen, phKey ) );
}


/***EP PTFind_16() - 16 bit interface to PTFind */

long
PTFind_16( hPTree, selKey, offKey, iKeyLen, phKey )
    HPTREE      hPTree;
    SEL         selKey;         /* 16 bit selector */
    uchar_t *   offKey;         /* 32 bit offset */
    KEYLEN      iKeyLen;
    HPTKEY      *phKey;
{
    uchar_t *   pbKey;

    pbKey = (uchar_t *) SELVirtToLin((ulong_t) offKey, selKey);
    if ((long) pbKey == -1)
        return(-1);
    return( PTFind( hPTree, pbKey, iKeyLen, phKey ) );
}


/***EP PTFindFromPrefix_16() - 16 bit interface to PTFindFromPrefix */

long
PTFindFromPrefix_16( hPTree, selKey, offKey, iKeyLen, phKey )
    HPTREE      hPTree;
    SEL         selKey;         /* 16 bit selector */
    uchar_t *   offKey;         /* 32 bit offset */
    KEYLEN      iKeyLen;
    HPTKEY      *phKey;
{
    uchar_t *   pbKey;

    pbKey = (uchar_t *) SELVirtToLin((ulong_t) offKey, selKey);
    if ((long) pbKey == -1)
        return(-1);
    return( PTFindFromPrefix( hPTree, pbKey, iKeyLen, phKey ) );
}


/***EP PTFindMaxPrefix_16() - 16 bit interface to PTFindMaxPrefix */

long
PTFindMaxPrefix_16( hPTree, selKey, offKey, iKeyLen, phKey )
    HPTREE      hPTree;
    SEL         selKey;         /* 16 bit selector */
    uchar_t *   offKey;         /* 32 bit offset */
    KEYLEN      iKeyLen;
    HPTKEY      *phKey;
{
    uchar_t *   pbKey;

    pbKey = (uchar_t *) SELVirtToLin((ulong_t) offKey, selKey);
    if ((long) pbKey == -1)
        return(-1);
    return( PTFindMaxPrefix( hPTree, pbKey, iKeyLen, phKey ) );
}


/***EP PTDelete_16() - 16 bit interface to PTDelete */

long
PTDelete_16( hPTree, selKey, offKey, iKeyLen )
    HPTREE      hPTree;
    SEL         selKey;         /* 16 bit selector */
    uchar_t *   offKey;         /* 32 bit offset */
    KEYLEN      iKeyLen;
{
    uchar_t *   pbKey;

    pbKey = (uchar_t *) SELVirtToLin((ulong_t) offKey, selKey);
    if ((long) pbKey == -1)
        return(-1);
    return( PTDelete( hPTree, pbKey, iKeyLen ) );
}

#endif

#ifdef VMSTRICT
void ptCheckTree(register HPTREE hPTree)
{
    if(hPTree->pth_lFlags & PTF_DEBUG)
    {
        ptCheckNode(hPTree, &(hPTree->pth_nHeader));
    }
}

void ptCheckNode(register HPTREE hPTree, register P_PTNODE pn)
{
    register uchar_t *pb;

    if((hPTree->pth_lFlags & 0x4000) != 0)
    {
        printf("%lx %x %x %lx %lx %lx ", pn, pn->ptn_bi, pn->ptn_iKeyLen,
                                      pn->ptn_pnLeft, pn->ptn_pnRight,
                                      pn->ptn_hKey);
        if(IsRootNode(pn))
        {
            printf("\n");
        }
        else
        {
            pb = hPTree->pth_GetKey(pn->ptn_hKey);
            printf("%s\n", pb+2);
        }
    }

    ptAssert((pn->ptn_bi != (pn->ptn_pnLeft)->ptn_bi) ||
                 (pn == pn->ptn_pnLeft));

    if((pn->ptn_pnLeft)->ptn_bi > pn->ptn_bi)
    {
        ptCheckNode(hPTree, pn->ptn_pnLeft);
    }

    ptAssert((pn->ptn_bi != (pn->ptn_pnRight)->ptn_bi) ||
                 (pn == pn->ptn_pnRight));

    if((pn->ptn_pnRight)->ptn_bi > pn->ptn_bi)
    {
        ptCheckNode(hPTree, pn->ptn_pnRight);
    }
}
#endif
