mtr.h

Go to the documentation of this file.

#ifndef __MTR
#define __MTR

/*---------------------------------------------------------------------------*/
/* Nested includes                                                           */
/*---------------------------------------------------------------------------*/

#ifdef __cplusplus
extern "C" {
#endif

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/

#ifndef SIZEOF_VOID_P
#define SIZEOF_VOID_P 4
#endif
#ifndef SIZEOF_INT
#define SIZEOF_INT 4
#endif

#if defined(__GNUC__)
#define MTR_INLINE __inline__
# if (__GNUC__ >2 || __GNUC_MINOR__ >=7)
#   define MTR_UNUSED __attribute__ ((unused))
# else
#   define MTR_UNUSED
# endif
#else
#define MTR_INLINE
#define MTR_UNUSED
#endif

/* Flag definitions */
#define MTR_DEFAULT 0x00000000
#define MTR_TERMINAL    0x00000001
#define MTR_SOFT    0x00000002
#define MTR_FIXED   0x00000004
#define MTR_NEWNODE 0x00000008

/* MTR_MAXHIGH is defined in such a way that on 32-bit and 64-bit
** machines one can cast a value to (int) without generating a negative
** number.
*/
#if SIZEOF_VOID_P == 8 && SIZEOF_INT == 4
#define MTR_MAXHIGH (((MtrHalfWord) ~0) >> 1)
#else
#define MTR_MAXHIGH ((MtrHalfWord) ~0)
#endif


/*---------------------------------------------------------------------------*/
/* Stucture declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/

#if SIZEOF_VOID_P == 8 && SIZEOF_INT == 4
typedef unsigned int   MtrHalfWord;
#else
typedef unsigned short MtrHalfWord;
#endif

typedef struct MtrNode {
    MtrHalfWord flags;
    MtrHalfWord low;
    MtrHalfWord size;
    MtrHalfWord index;
    struct MtrNode *parent;
    struct MtrNode *child;
    struct MtrNode *elder;
    struct MtrNode *younger;
} MtrNode;


/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/

/* Flag manipulation macros */
#define MTR_SET(node, flag) (node->flags |= (flag))
#define MTR_RESET(node, flag)   (node->flags &= ~ (flag))
#define MTR_TEST(node, flag)    (node->flags & (flag))


/*---------------------------------------------------------------------------*/
/* Function prototypes                                                       */
/*---------------------------------------------------------------------------*/

extern MtrNode * Mtr_AllocNode (void);
extern void Mtr_DeallocNode (MtrNode *node);
extern MtrNode * Mtr_InitTree (void);
extern void Mtr_FreeTree (MtrNode *node);
extern MtrNode * Mtr_CopyTree (MtrNode *node, int expansion);
extern void Mtr_MakeFirstChild (MtrNode *parent, MtrNode *child);
extern void Mtr_MakeLastChild (MtrNode *parent, MtrNode *child);
extern MtrNode * Mtr_CreateFirstChild (MtrNode *parent);
extern MtrNode * Mtr_CreateLastChild (MtrNode *parent);
extern void Mtr_MakeNextSibling (MtrNode *first, MtrNode *second);
extern void Mtr_PrintTree (MtrNode *node);
extern MtrNode * Mtr_InitGroupTree (int lower, int size);
extern MtrNode * Mtr_MakeGroup (MtrNode *root, unsigned int low, unsigned int high, unsigned int flags);
extern MtrNode * Mtr_DissolveGroup (MtrNode *group);
extern MtrNode * Mtr_FindGroup (MtrNode *root, unsigned int low, unsigned int high);
extern int Mtr_SwapGroups (MtrNode *first, MtrNode *second);
extern void Mtr_ReorderGroups(MtrNode *treenode, int *permutation);
  
extern void Mtr_PrintGroups (MtrNode *root, int silent);
  extern int Mtr_PrintGroupedOrder(MtrNode * root, int *invperm, FILE *fp);
extern MtrNode * Mtr_ReadGroups (FILE *fp, int nleaves);

#ifdef __cplusplus
}
#endif

#endif /* __MTR */