/*static char *SCCSID = "@(#)ptree.h	6.1 90/11/17";*/
/*
 *	IBM/Microsoft Confidential
 *
 *	Copyright (c) IBM Corporation 1987, 1989
 *	Copyright (c) Microsoft Corporation 1987, 1989
 *
 *	All Rights Reserved
 *
 *	SCCSID = @(#)ptree.h	13.32 90/09/17
 */

/*** PTree (Patricia Tree)
 *
 * Implements creating, destroying and walking a PTree, and
 * inserting, searching, and deleting objects from a PTree.
 */


#ifdef STANDALONE
    typedef ulong_t	KSEM;
    typedef ushort_t	VMHOB;
    typedef ushort_t	VMHKH;

    #define VM_HKH_PUB_RESRW	1
    #define VM_HKH_PUB_SWAPRW	3
#endif


/* PTree Key String
 *
 * The client will always pass in both the key string and it's length.
 *
 * The key string consists of arbitrary data (nulls ok).
 */


/* HPTKEY - handle to a ptree key
 *
 * Returned by PTInsert, PTFind, PTFindFromPrefix and PTFindMaxPrefix.
 * It has direct meaning only to the caller.
 * When the ptree code needs to examine the actual key,
 * it calls the provided GetKey() function to convert
 * the handle into a pointer to the key.
 * This way the client can manage it's data in any way it wants.
 * The key handle is often actually a 32 bit flat pointer to a
 * data structure that contains the key (or a pointer to the key).
 */

typedef long	  HPTKEY;

/* BI - bit index - internal use only
 *
 * zero based, but signed for root node special case ptn_bi = -1
 */

typedef short	  BI;


/* KEYLEN - key length in bytes - external use only */

typedef long	  KEYLEN;


/* I_KEYLEN - key length in bytes - internal use only
 *
 * This is a short to save space in the nodes.
 * It may change to a long sometime.
 */

typedef short	  I_KEYLEN;


/* PTree Node and Header structure definitions */

struct sPTNODE {
    BI			ptn_bi;		/* index of bit to test during lookup */
					/*  (root bit index is -1) */
    I_KEYLEN		ptn_iKeyLen;	/* length of key object in bytes */
    struct sPTNODE	*ptn_pnLeft;	/* pointer to left  child node */
    struct sPTNODE	*ptn_pnRight;	/* pointer to right child node */
    HPTKEY		ptn_hKey;	/* handle of the key object */
};

typedef struct sPTNODE	PTNODE;
typedef struct sPTNODE	*P_PTNODE;


/* This needs to be defined before the structure for PF_WALK* */
typedef struct sPTHEAD	*HPTREE;


/* function pointer typedefs */
/* h2inc cannot translate these function pointer types */
/* XLATOFF */
typedef long      (*PF_KEYALLOC)(uchar_t *, KEYLEN, HPTKEY *);
typedef long      (*PF_KEYFREE)	(HPTKEY);
typedef uchar_t * (*PF_GETKEY)	(HPTKEY);

typedef long	  (*PF_WALK)	(HPTREE, HPTKEY);
typedef long	  (*PF_WALKNODE)(HPTREE, P_PTNODE);
/* XLATON */

/* ASM
PF_KEYALLOC struc
	dd ?
PF_KEYALLOC ends

PF_KEYFREE struc
	dd ?
PF_KEYFREE ends

PF_GETKEY struc
	dd ?
PF_GETKEY ends

PF_WALK struc
	dd ?
PF_WALK ends

PF_WALKNODE struc
	dd ?
PF_WALKNODE ends
 */


struct sPTHEAD {
    PTNODE	pth_nHeader;	/* header node				*/
    KSEMSHR	pth_ksem;	/* multiple reader, single writer ksem	*/
    ulong_t	pth_lFlags;	/* flags				*/
    VMHOB	pth_owner;	/* owner from vmowner.h			*/
    ulong_t	pth_cNodes;	/* number of nodes in this tree		*/
    ulong_t	pth_cMaxNodes;	/* maximum number of nodes in this tree	*/
    PF_KEYALLOC	pth_KeyAlloc;	/* allocate and init new key.		*/
				/* must be fast because tree is locked	*/
				/* may not call any other PTree calls	*/
				/*  or a deadlock will occur.		*/
    PF_KEYFREE	pth_KeyFree;	/* free key (given handle)		*/
    PF_GETKEY	pth_GetKey;	/* return key string (given handle)	*/
    PF_WALK	pth_pfWalk;	/* -> function called for PTWalk	*/
};

typedef struct sPTHEAD	PTHEAD;


#define PTF_HEADSWAP	0x0001	/* ptree head  is  swappable (heap) */
#define PTF_NODESWAP	0x0002	/* ptree nodes are swappable (heap) */
#define PTF_PANICINSERT	0x0010	/* panic insert if key already exists */
#define PTF_PANICDELETE	0x0020	/* panic delete if key doesn't exists */
#define PTF_DEBUG	0x8000	/* print debugging info while running */

/* XLATOFF */

/* 32 Bit PTree Interfaces (FLAT:32) */

long PTCreate(ulong_t, VMHOB, ulong_t, PF_KEYALLOC, PF_KEYFREE, PF_GETKEY, HPTREE *);
long PTInsert        (HPTREE, uchar_t *, KEYLEN, HPTKEY *);
long PTFind          (HPTREE, uchar_t *, KEYLEN, HPTKEY *);
long PTFindFromPrefix(HPTREE, uchar_t *, KEYLEN, HPTKEY *);
long PTFindMaxPrefix (HPTREE, uchar_t *, KEYLEN, HPTKEY *);
long PTDelete        (HPTREE, uchar_t *, KEYLEN);
long PTDestroy       (HPTREE);


/* PTWalkNode and PTWalk - walk tree calling function
 *
 * user function may not call any ptree functions - deadlock
 *
 * PTWalkNode calls the user function with a pointer to the node
 * PTWalk     calls the user function with a the key handle
 */
long PTWalkNode( HPTREE, PF_WALKNODE );
long PTWalk( HPTREE, PF_WALK );


/* 16:16 Bit PTree Interfaces (SEL:OFF) */

long PTInsert_16        (HPTREE, SEL, uchar_t *, KEYLEN, HPTKEY *);
long PTFind_16          (HPTREE, SEL, uchar_t *, KEYLEN, HPTKEY *);
long PTFindFromPrefix_16(HPTREE, SEL, uchar_t *, KEYLEN, HPTKEY *);
long PTFindMaxPrefix_16 (HPTREE, SEL, uchar_t *, KEYLEN, HPTKEY *);
long PTDelete_16        (HPTREE, SEL, uchar_t *, KEYLEN);
