mtr.h Source File

00001 
00032 #ifndef __MTR
00033 #define __MTR
00034 
00035 /*---------------------------------------------------------------------------*/
00036 /* Nested includes                                                           */
00037 /*---------------------------------------------------------------------------*/
00038 
00039 
00040 /*---------------------------------------------------------------------------*/
00041 /* Constant declarations                                                     */
00042 /*---------------------------------------------------------------------------*/
00043 
00044 #ifndef SIZEOF_VOID_P
00045 #define SIZEOF_VOID_P 4
00046 #endif
00047 #ifndef SIZEOF_INT
00048 #define SIZEOF_INT 4
00049 #endif
00050 
00051 #undef CONST
00052 #if defined(__STDC__) || defined(__cplusplus)
00053 #define CONST           const
00054 #else /* !(__STDC__ || __cplusplus) */
00055 #define CONST
00056 #endif /* !(__STDC__ || __cplusplus) */
00057 
00058 /* These are potential duplicates. */
00059 #ifndef EXTERN
00060 #   ifdef __cplusplus
00061 # define EXTERN extern "C"
00062 #   else
00063 # define EXTERN extern
00064 #   endif
00065 #endif
00066 #ifndef ARGS
00067 #   if defined(__STDC__) || defined(__cplusplus)
00068 # define ARGS(protos)    protos          /* ANSI C */
00069 #   else /* !(__STDC__ || __cplusplus) */
00070 # define ARGS(protos)    ()              /* K&R C */
00071 #   endif /* !(__STDC__ || __cplusplus) */
00072 #endif
00073 
00074 #if defined(__GNUC__)
00075 #define MTR_INLINE __inline__
00076 # if (__GNUC__ >2 || __GNUC_MINOR__ >=7)
00077 #   define MTR_UNUSED __attribute__ ((unused))
00078 # else
00079 #   define MTR_UNUSED
00080 # endif
00081 #else
00082 #define MTR_INLINE
00083 #define MTR_UNUSED
00084 #endif
00085  
00086 /* Flag definitions */
00087 #define MTR_DEFAULT 0x00000000
00088 #define MTR_TERMINAL  0x00000001
00089 #define MTR_SOFT  0x00000002
00090 #define MTR_FIXED 0x00000004
00091 #define MTR_NEWNODE 0x00000008
00092 
00093 /* MTR_MAXHIGH is defined in such a way that on 32-bit and 64-bit
00094 ** machines one can cast a value to (int) without generating a negative
00095 ** number.
00096 */
00097 #if SIZEOF_VOID_P == 8 && SIZEOF_INT == 4
00098 #define MTR_MAXHIGH (((MtrHalfWord) ~0) >> 1)
00099 #else
00100 #define MTR_MAXHIGH ((MtrHalfWord) ~0)
00101 #endif
00102 
00103 
00104 /*---------------------------------------------------------------------------*/
00105 /* Stucture declarations                                                     */
00106 /*---------------------------------------------------------------------------*/
00107 
00108 
00109 /*---------------------------------------------------------------------------*/
00110 /* Type declarations                                                         */
00111 /*---------------------------------------------------------------------------*/
00112 
00113 #if SIZEOF_VOID_P == 8 && SIZEOF_INT == 4
00114 typedef unsigned int   MtrHalfWord;
00115 #else
00116 typedef unsigned short MtrHalfWord;
00117 #endif
00118 
00119 typedef struct MtrNode {
00120     MtrHalfWord flags;
00121     MtrHalfWord low;
00122     MtrHalfWord size;
00123     MtrHalfWord index;
00124     struct MtrNode *parent;
00125     struct MtrNode *child;
00126     struct MtrNode *elder;
00127     struct MtrNode *younger;
00128 } MtrNode;
00129 
00130 
00131 /*---------------------------------------------------------------------------*/
00132 /* Variable declarations                                                     */
00133 /*---------------------------------------------------------------------------*/
00134 
00135 
00136 /*---------------------------------------------------------------------------*/
00137 /* Macro declarations                                                        */
00138 /*---------------------------------------------------------------------------*/
00139 
00140 /* Flag manipulation macros */
00141 #define MTR_SET(node, flag)   (node->flags |= (flag))
00142 #define MTR_RESET(node, flag) (node->flags &= ~ (flag))
00143 #define MTR_TEST(node, flag)  (node->flags & (flag))
00144 
00145 
00148 /*---------------------------------------------------------------------------*/
00149 /* Function prototypes                                                       */
00150 /*---------------------------------------------------------------------------*/
00151 
00152 EXTERN MtrNode * Mtr_AllocNode ARGS(());
00153 EXTERN void Mtr_DeallocNode ARGS((MtrNode *node));
00154 EXTERN MtrNode * Mtr_InitTree ARGS(());
00155 EXTERN void Mtr_FreeTree ARGS((MtrNode *node));
00156 EXTERN MtrNode * Mtr_CopyTree ARGS((MtrNode *node, int expansion));
00157 EXTERN void Mtr_MakeFirstChild ARGS((MtrNode *parent, MtrNode *child));
00158 EXTERN void Mtr_MakeLastChild ARGS((MtrNode *parent, MtrNode *child));
00159 EXTERN MtrNode * Mtr_CreateFirstChild ARGS((MtrNode *parent));
00160 EXTERN MtrNode * Mtr_CreateLastChild ARGS((MtrNode *parent));
00161 EXTERN void Mtr_MakeNextSibling ARGS((MtrNode *first, MtrNode *second));
00162 EXTERN void Mtr_PrintTree ARGS((MtrNode *node));
00163 EXTERN MtrNode * Mtr_InitGroupTree ARGS((int lower, int size));
00164 EXTERN MtrNode * Mtr_MakeGroup ARGS((MtrNode *root, unsigned int low, unsigned int high, unsigned int flags));
00165 EXTERN MtrNode * Mtr_DissolveGroup ARGS((MtrNode *group));
00166 EXTERN MtrNode * Mtr_FindGroup ARGS((MtrNode *root, unsigned int low, unsigned int high));
00167 EXTERN int Mtr_SwapGroups ARGS((MtrNode *first, MtrNode *second));
00168 EXTERN void Mtr_PrintGroups ARGS((MtrNode *root, int silent));
00169 EXTERN MtrNode * Mtr_ReadGroups ARGS((FILE *fp, int nleaves));
00170 
00173 #endif /* __MTR */