mbtree.h

00001 /*
00002 ** $Id: btree.h 13036 2010-07-13 12:49:37Z dongjunjie $
00003 **
00004 ** btree.h: this head file declares btree structure.
00005 **
00006 ** Copyright (C) 2010 Feynman Software.
00007 **
00008 ** Create date: 2010/03/10
00009 */
00010 #if defined(_MGNCSCTRL_TEXTEDITOR) || (defined(_MGCTRL_TEXTEDIT) && defined(_MGCTRL_TEXTEDIT_USE_NEW_IMPL))
00011 
00012 #ifndef _COMM_BTREE_H
00013 #define _COMM_BTREE_H
00014 
00015 #define BTREE_ERRNO_SCHILD  1
00016 #define BTREE_ERRNO_SNEXT   0
00017 #define BTREE_ERRNO_SNULL  -1
00018 
00019 DECLARE_OBJECT(mCommBTreeNode)
00020 DECLARE_OBJECT(mCommBTree)
00021 DECLARE_OBJECT(mCommBTreeLeafIterator)
00022 
00023 #define mCommBTreeLeafIteratorHeader(Clss)       \
00024     mObjectHeader(Clss)                         \
00025     mCommBTree       *tree;                      \
00026     mCommBTreeNode   *current;
00027 
00028 #define mCommBTreeLeafIteratorClassHeader(Clss, Super)\
00029     mObjectClassHeader(Clss, Super)             \
00030     mCommBTreeNode* (*getCurrent)(Clss *self);   \
00031     BOOL (*hasNext)(Clss *self);                 \
00032     mCommBTreeNode* (*next)(Clss *self);         \
00033     void (*remove)(Clss *self);                 \
00034     void (*insert)(Clss *self, mCommBTreeNode *leaf);
00035 
00036 
00037 #define mCommBTreeNodeHeader(Clss)               \
00038     mObjectHeader(Clss)                         \
00039     Clss    *parent;                            \
00040     Clss    *next;                              \
00041     Clss    *children;                          \
00042     unsigned int level:16;                      \
00043     /* Number of children of this node. */      \
00044     unsigned int numChildren:16;                \
00045     /* Total number of leaves in the subtree rooted here. */\
00046     unsigned int numLeaves;
00047 
00048 
00049 #define mCommBTreeNodeClassHeader(Clss, Super)       \
00050     mObjectClassHeader(Clss, Super)                 \
00051     void (*resetKey)(Clss *self);                   \
00052     int (*compareNode)(Clss *self, void *cmpInfo);  \
00053     void (*recompute)(Clss *self, Clss *child);     \
00054     void (*changeKey)(Clss *self, void *diffInfo, int deltaChild); \
00055     BOOL (*isNullKey)(Clss *self);
00056 
00057 #define mCommBTreeHeader(Clss)   \
00058         mObjectHeader(Clss)         \
00059     mCommBTreeNode *rootNode;    \
00060     int minChildrenNum;         \
00061     int maxChildrenNum;         \
00062     int refCount;
00063 
00064 #define mCommBTreeClassHeader(Clss, Super)       \
00065     mObjectClassHeader(Clss, Super)             \
00066     void (*ref)(Clss *self);                    \
00067     void (*unref)(Clss *self);                  \
00068     mCommBTreeNode* (*getRoot)(Clss *self);      \
00069     void (*rebalanceNode)(Clss *self, mCommBTreeNode *node);     \
00070     void (*recomputeNodeInfo)(Clss *self, mCommBTreeNode *node); \
00071     void (*deleteNode)(Clss *self, mCommBTreeNode *node);        \
00072     BOOL (*insertLeaf)(Clss *self, mCommBTreeNode *parent,       \
00073             mCommBTreeNode *sibLeaf, mCommBTreeNode *leaf);       \
00074     mCommBTreeNode* (*search)(Clss *self, void* searchInfo, int flags);     \
00075     mCommBTreeNode* (*newNode)(Clss *self);                      \
00076     mCommBTreeNode* (*newLeaf)(Clss *self);
00077 
00078 //search flags
00079 enum {
00080         BTSF_RETLAST_IF_OUTOFRANGE = 0x1
00081 };
00082 
00083 DEFINE_OBJECT(mCommBTreeNode, mObject)
00084 DEFINE_OBJECT(mCommBTree, mObject)
00085 DEFINE_OBJECT(mCommBTreeLeafIterator, mObject)
00086 #endif
00087 #endif  //_MGHAVE_NEWTEXTEDIT || _MGNCSCTRL_TEXTEDITOR