source/rbTree.h

   1 /* $Id: rbTree.h,v 1.5 2004/11/09 21:58:44 yooden Exp $ */
   2 /*******************************************************************************
   3 *                                                                              *
   4 * rbTree.h -- Nirvana Editor Red-Black Balanced Binary Tree Header File        *
   5 *                                                                              *
   6 * Copyright 2002 The NEdit Developers                                          *
   7 *                                                                              *
   8 * This is free software; you can redistribute it and/or modify it under the    *
   9 * terms of the GNU General Public License as published by the Free Software    *
  10 * Foundation; either version 2 of the License, or (at your option) any later   *
  11 * version. In addition, you may distribute versions of this program linked to  *
  12 * Motif or Open Motif. See README for details.                                 *
  13 *                                                                              *
  14 * This software is distributed in the hope that it will be useful, but WITHOUT *
  15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
  16 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for    *
  17 * more details.                                                                *
  18 *                                                                              *
  19 * You should have received a copy of the GNU General Public License along with *
  20 * software; if not, write to the Free Software Foundation, Inc., 59 Temple     *
  21 * Place, Suite 330, Boston, MA  02111-1307 USA                                 *
  22 *                                                                              *
  23 * Nirvana Text Editor                                                          *
  24 * July 31, 2001                                                                *
  25 *                                                                              *
  26 *******************************************************************************/
  27
  28 #ifndef NEDIT_RBTREE_H_INCLUDED
  29 #define NEDIT_RBTREE_H_INCLUDED
  30
  31 typedef struct rbTreeNode {
  32     struct rbTreeNode *left;   /* left child */
  33     struct rbTreeNode *right;  /* right child */
  34     struct rbTreeNode *parent; /* parent */
  35     int color;                 /* node color (rbTreeNodeBlack, rbTreeNodeRed) */
  36 } rbTreeNode;
  37
  38 typedef int (*rbTreeCompareNodeCB)(rbTreeNode *left, rbTreeNode *right);
  39 typedef rbTreeNode *(*rbTreeAllocateNodeCB)(rbTreeNode *src);
  40 typedef rbTreeNode *(*rbTreeAllocateEmptyNodeCB)(void);
  41 typedef void (*rbTreeDisposeNodeCB)(rbTreeNode *src);
  42 typedef int (*rbTreeCopyToNodeCB)(rbTreeNode *dst, rbTreeNode *src);
  43
  44 rbTreeNode *rbTreeBegin(rbTreeNode *base);
  45 rbTreeNode *rbTreeReverseBegin(rbTreeNode *base);
  46 rbTreeNode *rbTreeFind(rbTreeNode *base, rbTreeNode *searchNode,
  47                         rbTreeCompareNodeCB compareRecords);
  48 rbTreeNode *rbTreeInsert(rbTreeNode *base, rbTreeNode *searchNode,
  49                             rbTreeCompareNodeCB compareRecords,
  50                             rbTreeAllocateNodeCB allocateNode,
  51                             rbTreeCopyToNodeCB copyToNode);
  52 rbTreeNode *rbTreeUnlinkNode(rbTreeNode *base, rbTreeNode *z);
  53 void rbTreeDeleteNode(rbTreeNode *base, rbTreeNode *foundNode,
  54                     rbTreeDisposeNodeCB disposeNode);
  55 int rbTreeDelete(rbTreeNode *base, rbTreeNode *searchNode,
  56                     rbTreeCompareNodeCB compareRecords,
  57                     rbTreeDisposeNodeCB disposeNode);
  58 rbTreeNode *rbTreeNext(rbTreeNode *x);
  59 rbTreeNode *rbTreePrevious(rbTreeNode *x);
  60 int rbTreeSize(rbTreeNode *base);
  61 rbTreeNode *rbTreeNew(rbTreeAllocateEmptyNodeCB allocateEmptyNode);
  62 void rbTreeDispose(rbTreeNode *base, rbTreeDisposeNodeCB disposeNode);
  63
  64 #endif /* NEDIT_RBTREE_H_INCLUDED */