From aa755206da4bcce3261ecd5dbfa41570a0155c73 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Thu, 16 Nov 2000 09:18:38 +0000 Subject: [PATCH] - Added balanced tree management stuff as well. (It is not finished yet.) --- lib/rbl.c | 85 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/rbl.h | 71 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 156 insertions(+) create mode 100644 lib/rbl.c create mode 100644 lib/rbl.h diff --git a/lib/rbl.c b/lib/rbl.c new file mode 100644 index 00000000..765236c2 --- /dev/null +++ b/lib/rbl.c @@ -0,0 +1,85 @@ +/* + rbl.c -- red-black tree + linked list convenience + Copyright (C) 2000 Ivo Timmermans , + 2000 Guus Sliepen + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + $Id: rbl.c,v 1.1.2.1 2000/11/16 09:18:38 guus Exp $ +*/ + +rbl_t *new_rbl(rbltree_t *tree) +{ + rbl_t *rbl; + + rbl = xmalloc(sizeof(*rbl)); + + if(rbl) + { + memset(rbl, 0, sizeof(*rbl)); + rbl->tree = tree; + } + + return rbl; +} + +void free_rbl(rbl_t *rbl) +{ + free(rbl); +} + +rbl_t rbl_search_closest(rbltree_t *tree, void *data) +{ + rbl_t *rbl, *next; + int result; + + for(next = rbltree->head; next; next = rbl) + { + result = rbltree->compare(rbl->data, data) + if(result < 0) + next = rbl->left; + else if(result > 0) + next = rbl->right; + else + break; + } + + return rbl; +} + +rbl_t rbl_search(rbltree_t *tree, void *data) +{ + rbl_t *rbl, *next; + int result; + + for(next = rbltree->head; next; next = rbl) + { + result = rbltree->compare(rbl->data, data) + if(result < 0) + next = rbl->left; + else if(result > 0) + next = rbl->right; + else + return rbl; + } + + return NULL; +} + +rbl_t rbl_insert(rbltree_t *tree, void *data) +{ + rbl_t *rbl; + +} diff --git a/lib/rbl.h b/lib/rbl.h new file mode 100644 index 00000000..40a1c69d --- /dev/null +++ b/lib/rbl.h @@ -0,0 +1,71 @@ +/* + rbl.h -- header file for rbl.c + Copyright (C) 2000 Ivo Timmermans , + 2000 Guus Sliepen + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + + $Id: rbl.h,v 1.1.2.1 2000/11/16 09:18:38 guus Exp $ +*/ + +typedef int (*rbl_compare_t) (const void *, const void *); +typedef void (*rbl_delete_t) (const void *); + +typedef struct rbl_t +{ + /* 'red-black tree' part */ + + struct rbltree_t *tree; + + int color; + + rbl_t *parent; + rbl_t *left; + rbl_t *right; + + /* 'linked list' part */ + + rbl_t *prev; + rbl_t *next; + + /* payload */ + + void *data; + +} rbl_t; + +typedef struct rbltree_t +{ + rbl_compare_t *compare; + rbl_delete_t *delete; + struct rbl_t *head; +} rbltree_t; + +enum +{ + RBL_RED; + RBL_BLACK; +}; + +extern rbl_t rbl_search(rbltree_t *, void *); +extern rbl_t rbl_search_closest(rbltree_t *, void *); +extern rbl_t rbl_insert(rbltree_t *, void *); +extern rbl_t rbl_unlink(rbltree_t *, void *); +extern rbl_t rbl_delete(rbltree_t *, void *); +extern rbl_t rbl_insert_rbl(rbltree_t *, rbl_t *); +extern rbl_t rbl_unlink_rbl(rbltree_t *, rbl_t *); +extern rbl_t rbl_delete_rbl(rbltree_t *, rbl_t *); +extern rbl_t rbl_prev(rbl_t *); +extern rbl_t rbl_next(rbl_t *); -- 2.39.5