diff options
| -rw-r--r-- | Makefile.am | 2 | ||||
| -rw-r--r-- | bmm_lib.c | 264 | ||||
| -rw-r--r-- | rb.c | 549 | ||||
| -rw-r--r-- | rb.h | 128 |
4 files changed, 888 insertions, 55 deletions
diff --git a/Makefile.am b/Makefile.am index c135cb7..02ab833 100644 --- a/Makefile.am +++ b/Makefile.am @@ -5,7 +5,7 @@ libbmm_la_LTLIBRARIES = libbmm.la libbmm_ladir = $(libdir) libbmm_la_LDFLAGS = -no-undefined -export-symbols-regex "bmm_*" \ -version-info @ABI_VERSION@:@ABI_REVISION@:@ABI_AGE@ -libbmm_la_SOURCES = bmm_lib.c bmm_lib_priv.h +libbmm_la_SOURCES = bmm_lib.c bmm_lib_priv.h rb.c rb.h libbmm_laincludedir = $(includedir) libbmm_lainclude_HEADERS = bmm_lib.h @@ -15,11 +15,15 @@ #include <sys/types.h> #include <sys/stat.h> #include <sys/mman.h> +#include <assert.h> #include <fcntl.h> +#include <pthread.h> +#include <stdlib.h> #include <unistd.h> #include "bmm_lib_priv.h" #include "bmm_lib.h" +#include "rb.h" #undef DEBUG @@ -38,6 +42,108 @@ static unsigned bmm_api; static int bmm_fd = -1; +static pthread_mutex_t bmm_mutex = PTHREAD_MUTEX_INITIALIZER; +static Rb_node virt_rb; +static Rb_node phys_rb; + +struct bmm_buffer { + void *vaddr; + unsigned long paddr; + size_t size; + int attr; +}; + +static int cmp_virt(const void *key, const void *val) +{ + const struct bmm_buffer *buf = val; + void *k = (void *)key; + + return (k < buf->vaddr) ? -1 : + (k - buf->vaddr < buf->size) ? 0 : 1; +} + +static int cmp_phys(const void *key, const void *val) +{ + const struct bmm_buffer *buf = val; + unsigned long k = (unsigned long)key; + + return (k < buf->paddr) ? -1 : + (k - buf->paddr < buf->size) ? 0 : 1; +} + +static struct bmm_buffer *bmm_buf_find_virt(void *virt) +{ + struct bmm_buffer *buf = NULL; + Rb_node node; + int found = 0; + + node = rb_find_key_n(virt_rb, virt, cmp_virt, &found); + if (found) { + buf = rb_val(node); + + pr_debug("rb: %s(%p) phys=0x%08lx virt=%p size=0x%08lx\n", + "find_virt", virt, buf->paddr, buf->vaddr, buf->size); + } else { + pr_debug("rb: %s(%p): not found\n", + "find_virt", virt); + } + + return buf; +} + +static struct bmm_buffer *bmm_buf_find_phys(unsigned long phys) +{ + struct bmm_buffer *buf = NULL; + Rb_node node; + int found = 0; + + node = rb_find_key_n(phys_rb, (void *)phys, cmp_phys, &found); + if (found) { + buf = rb_val(node); + + pr_debug("rb: %s(0x%08lx) phys=0x%08lx virt=%p size=0x%08lx\n", + "find_phys", (unsigned long)phys, buf->paddr, buf->vaddr, buf->size); + } else { + pr_debug("rb: %s(0x%08lx): not found\n", + "find_phys", (unsigned long)phys); + } + + return buf; +} + +static void bmm_buf_remove(struct bmm_buffer *buf) +{ + Rb_node node; + int found = 0; + + pr_debug("rb: %s phys=0x%08lx virt=%p size=0x%08lx\n", + "remove", buf->paddr, buf->vaddr, buf->size); + + node = rb_find_key_n(virt_rb, buf->vaddr, cmp_virt, &found); + assert(found); + rb_delete_node(node); + + node = rb_find_key_n(phys_rb, (void *)buf->paddr, cmp_phys, &found); + assert(found); + rb_delete_node(node); +} + +static void bmm_buf_insert(struct bmm_buffer *buf) +{ + Rb_node node; + int found = 0; + + pr_debug("rb: %s phys=0x%08lx virt=%p size=0x%08lx\n", + "insert", buf->paddr, buf->vaddr, buf->size); + + node = rb_find_key_n(virt_rb, buf->vaddr, cmp_virt, &found); + assert(found == 0); + rb_insert_b(node, buf); + + node = rb_find_key_n(phys_rb, (void *)buf->paddr, cmp_phys, &found); + assert(found == 0); + rb_insert_b(node, buf); +} static int bmm_get_api_version(void) { @@ -64,10 +170,14 @@ static int bmm_get_api_version(void) int bmm_init() { - /* attempt to open the BMM driver */ - if(bmm_fd < 0) { - bmm_fd = open(BMM_DEVICE_FILE, O_RDWR | O_CLOEXEC); + if (bmm_fd < 0) { + virt_rb = make_rb(); + phys_rb = make_rb(); + if (!virt_rb || !phys_rb) + goto err_rb; + /* attempt to open the BMM driver */ + bmm_fd = open(BMM_DEVICE_FILE, O_RDWR | O_CLOEXEC); pr_debug("BMM device fd: %d\n", bmm_fd); if (bmm_fd < 0) goto err_open; @@ -82,18 +192,29 @@ int bmm_init() close(bmm_fd); bmm_fd = -1; err_open: + err_rb: + if (phys_rb) + rb_free_tree(phys_rb); + if (virt_rb) + rb_free_tree(virt_rb); + phys_rb = virt_rb = NULL; return bmm_fd; } void bmm_exit() { - if(bmm_fd >= 0) + if (bmm_fd >= 0) { close(bmm_fd); + rb_free_tree(phys_rb); + rb_free_tree(virt_rb); + phys_rb = virt_rb = NULL; + } bmm_fd = -1; } void *bmm_malloc_aligned(unsigned long size, int attr, unsigned align) { + struct bmm_buffer *buf; int ret; void *vaddr; ioctl_arg_t io; @@ -104,6 +225,10 @@ void *bmm_malloc_aligned(unsigned long size, int attr, unsigned align) if(bmm_init() < 0) return NULL; + buf = malloc(sizeof(*buf)); + if (!buf) + return NULL; + pr_debug("%s(size=%lu,attr=%x,align=%u)\n", __FUNCTION__, size, attr, align); /* obsolete, only for back-compatible */ @@ -118,13 +243,31 @@ void *bmm_malloc_aligned(unsigned long size, int attr, unsigned align) io.output = 0; io.arg = attr; ret = ioctl(bmm_fd, BMM_MALLOC_ALIGNED, &io); - if(ret < 0 || io.output == 0) - return NULL; + if (ret < 0 || io.output == 0) + goto err_free_buf; pr_debug("bmm_malloc return paddr = 0x%08lx\n", io.output); vaddr = mmap(0, size, PROT_READ | PROT_WRITE, MAP_SHARED, bmm_fd, io.output); - return ((int)vaddr == -1) ? NULL : vaddr; + if ((int)vaddr == -1) { + /* FIXME: we can't free the bmm buffer without a vaddr! */ + goto err_free_buf; + } + + buf->vaddr = vaddr; + buf->paddr = io.output; + buf->size = size; + buf->attr = attr; + + pthread_mutex_lock(&bmm_mutex); + bmm_buf_insert(buf); + pthread_mutex_unlock(&bmm_mutex); + + return vaddr; + + err_free_buf: + free(buf); + return NULL; } void *bmm_malloc(unsigned long size, int attr) @@ -134,19 +277,27 @@ void *bmm_malloc(unsigned long size, int attr) void bmm_free(void *vaddr) { - unsigned long size; + struct bmm_buffer *buf; ioctl_arg_t io; - if(bmm_init() < 0) + if (bmm_init() < 0) return; - size = bmm_get_mem_size(vaddr); - munmap(vaddr, size); + pthread_mutex_lock(&bmm_mutex); + buf = bmm_buf_find_virt(vaddr); + if (buf) + bmm_buf_remove(buf); + pthread_mutex_unlock(&bmm_mutex); - io.input = (unsigned long)vaddr; + assert(buf); + + munmap(buf->vaddr, buf->size); + + io.input = (unsigned long)buf->vaddr; io.output = 0; io.arg = 0; ioctl(bmm_fd, BMM_FREE, &io); + free(buf); } void *bmm_attach(unsigned long paddr, unsigned long len) @@ -174,38 +325,36 @@ void bmm_detach(void *vaddr, unsigned long len) void *bmm_get_vaddr(unsigned long paddr) { - int ret; - ioctl_arg_t io; + struct bmm_buffer *buf; + void *va = NULL; - if(bmm_init() < 0) - return NULL; + if (bmm_init() < 0) + return 0; - io.input = paddr; - io.output = 0; - io.arg = 0; - ret = ioctl(bmm_fd, BMM_GET_VIRT_ADDR, &io); - if(ret < 0) - return NULL; + pthread_mutex_lock(&bmm_mutex); + buf = bmm_buf_find_phys(paddr); + if (buf) + va = buf->vaddr + (paddr - buf->paddr); + pthread_mutex_unlock(&bmm_mutex); - return (void *)io.output; + return va; } unsigned long bmm_get_paddr(void *vaddr) { - int ret; - ioctl_arg_t io; + struct bmm_buffer *buf; + unsigned long pa = 0; - if(bmm_init() < 0) + if (bmm_init() < 0) return 0; - io.input = (unsigned long)vaddr; - io.output = 0; - io.arg = 0; - ret = ioctl(bmm_fd,BMM_GET_PHYS_ADDR, &io); - if(ret < 0) - return 0; + pthread_mutex_lock(&bmm_mutex); + buf = bmm_buf_find_virt(vaddr); + if (buf) + pa = buf->paddr + (vaddr - buf->vaddr); + pthread_mutex_unlock(&bmm_mutex); - return io.output; + return pa; } int bmm_get_dmabuf_fd(void *vaddr) @@ -227,42 +376,41 @@ int bmm_get_dmabuf_fd(void *vaddr) unsigned long bmm_get_mem_size(void *vaddr) { - int ret; - ioctl_arg_t io; + struct bmm_buffer *buf; + unsigned long size = 0; - if(bmm_init() < 0) + if (bmm_init() < 0) return 0; - io.input = (unsigned long)vaddr; - io.output = 0; - io.arg = 0; - ret = ioctl(bmm_fd,BMM_GET_MEM_SIZE, &io); - if(ret < 0) - return 0; + pthread_mutex_lock(&bmm_mutex); + buf = bmm_buf_find_virt(vaddr); + if (buf) + size = buf->size; + pthread_mutex_unlock(&bmm_mutex); - return io.output; + return size; } int bmm_get_mem_attr(void *vaddr) { - int ret; - ioctl_arg_t io; + struct bmm_buffer *buf; + int attr = 0; - if(bmm_init() < 0) + if (bmm_init() < 0) return 0; - io.input = (unsigned long)vaddr; - io.output = 0; - io.arg = 0; - ret = ioctl(bmm_fd, BMM_GET_MEM_ATTR, &io); - if(ret < 0) - return 0; + pthread_mutex_lock(&bmm_mutex); + buf = bmm_buf_find_virt(vaddr); + if (buf) + attr = buf->attr; + pthread_mutex_unlock(&bmm_mutex); - return (int)io.output; + return attr; } int bmm_set_mem_attr(void *vaddr, int attr) { + struct bmm_buffer *buf; int ret; ioctl_arg_t io; @@ -276,7 +424,15 @@ int bmm_set_mem_attr(void *vaddr, int attr) if(ret < 0) return 0; - return (int)io.output; + attr = io.output; + + pthread_mutex_lock(&bmm_mutex); + buf = bmm_buf_find_virt(vaddr); + if (buf) + buf->attr = attr; + pthread_mutex_unlock(&bmm_mutex); + + return attr; } unsigned long bmm_get_total_space() @@ -0,0 +1,549 @@ +/* +Generic C code for red-black trees. +Copyright (C) 2000 James S. Plank + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ +/* Revision 1.2. Jim Plank */ + +/* Original code by Jim Plank (plank@cs.utk.edu) */ +/* modified for THINK C 6.0 for Macintosh by Chris Bartley */ + +/* Modified by Russell King to support embedded keys only */ + +#include <assert.h> +#include <string.h> +#include <stdio.h> +#include <stdlib.h> +#include <ctype.h> +#include "rb.h" + +static void mk_new_int(Rb_node l, Rb_node r, Rb_node p, int il); +static Rb_node lprev(Rb_node n); +static Rb_node rprev(Rb_node n); +static void recolor(Rb_node n); +static void single_rotate(Rb_node y, int l); +#ifdef DEBUG +static void rb_print_tree(Rb_node t, int level); +static void rb_iprint_tree(Rb_node t, int level); +#endif + + +#define isred(n) (n->s.red) +#define isblack(n) (!isred(n)) +#define isleft(n) (n->s.left) +#define isright(n) (!isleft(n)) +#define isint(n) (n->s.internal) +#define isext(n) (!isint(n)) +#define ishead(n) (n->s.head) +#define isroot(n) (n->s.root) +#define setred(n) n->s.red = 1 +#define setblack(n) n->s.red = 0 +#define setleft(n) n->s.left = 1 +#define setright(n) n->s.left = 0 +#define sethead(n) n->s.head = 1 +#define setroot(n) n->s.root = 1 +#define setint(n) n->s.internal = 1 +#define setext(n) n->s.internal = 0 +#define setnormal(n) { n->s.root = 0; n ->s.head = 0; } +#define sibling(n) ((isleft(n)) ? n->p.parent->c.child.right \ + : n->p.parent->c.child.left) + +static void insert(Rb_node item, Rb_node list) /* Inserts to the end of a list */ +{ + Rb_node last_node; + + last_node = list->c.list.blink; + + list->c.list.blink = item; + last_node->c.list.flink = item; + item->c.list.blink = last_node; + item->c.list.flink = list; +} + +static void delete_item(Rb_node item) /* Deletes an arbitrary iterm */ +{ + item->c.list.flink->c.list.blink = item->c.list.blink; + item->c.list.blink->c.list.flink = item->c.list.flink; +} + +#define mk_new_ext(new, vvval) {\ + new = (Rb_node) malloc(sizeof(struct rb_node));\ + new->v.val = vvval;\ + setext(new);\ + setblack(new);\ + setnormal(new);\ +} + +static void mk_new_int(Rb_node l, Rb_node r, Rb_node p, int il) +{ + Rb_node newnode; + + newnode = (Rb_node) malloc(sizeof(struct rb_node)); + setint(newnode); + setred(newnode); + setnormal(newnode); + newnode->c.child.left = l; + newnode->c.child.right = r; + newnode->p.parent = p; + newnode->k.lext = l; + newnode->v.rext = r; + l->p.parent = newnode; + r->p.parent = newnode; + setleft(l); + setright(r); + if (ishead(p)) { + p->p.root = newnode; + setroot(newnode); + } else if (il) { + setleft(newnode); + p->c.child.left = newnode; + } else { + setright(newnode); + p->c.child.right = newnode; + } + recolor(newnode); +} + + +Rb_node lprev(Rb_node n) +{ + if (ishead(n)) return n; + while (!isroot(n)) { + if (isright(n)) return n->p.parent; + n = n->p.parent; + } + return n->p.parent; +} + +Rb_node rprev(Rb_node n) +{ + if (ishead(n)) return n; + while (!isroot(n)) { + if (isleft(n)) return n->p.parent; + n = n->p.parent; + } + return n->p.parent; +} + +Rb_node make_rb(void) +{ + Rb_node head; + + head = (Rb_node) malloc (sizeof(struct rb_node)); + head->c.list.flink = head; + head->c.list.blink = head; + head->p.root = head; + sethead(head); + return head; +} + +Rb_node rb_find_key_n(Rb_node n, const void *key, rb_key_cmp_fn cmp, int *fnd) +{ + int rc; + *fnd = 0; +#ifdef DEBUG + if (!ishead(n)) { + fprintf(stderr, "%s called on non-head %p\n", __FUNCTION__, n); + exit(1); + } +#else + assert(ishead(n)); +#endif + if (n->p.root == n) return n; + rc = cmp(key, n->c.list.blink->v.val); + if (rc == 0) { + *fnd = 1; + return n->c.list.blink; + } + if (rc > 0) return n; + else n = n->p.root; + while (1) { + if (isext(n)) return n; + rc = cmp(key, n->k.lext->v.val); + if (rc == 0) { + *fnd = 1; + return n->k.lext; + } + n = rc < 0 ? n->c.child.left : n->c.child.right; + } +} + +Rb_node rb_find_key(Rb_node n, const void *key, rb_key_cmp_fn cmp) +{ + int fnd; + return rb_find_key_n(n, key, cmp, &fnd); +} + +Rb_node rb_insert_b(Rb_node n, void *val) +{ + Rb_node newleft, newright, newnode, p; + + if (ishead(n)) { + if (n->p.root == n) { /* Tree is empty */ + mk_new_ext(newnode, val); + insert(newnode, n); + n->p.root = newnode; + newnode->p.parent = n; + setroot(newnode); + return newnode; + } else { + mk_new_ext(newright, val); + insert(newright, n); + newleft = newright->c.list.blink; + setnormal(newleft); + mk_new_int(newleft, newright, newleft->p.parent, isleft(newleft)); + p = rprev(newright); + if (!ishead(p)) p->k.lext = newright; + return newright; + } + } else { + mk_new_ext(newleft, val); + insert(newleft, n); + setnormal(n); + mk_new_int(newleft, n, n->p.parent, isleft(n)); + p = lprev(newleft); + if (!ishead(p)) p->v.rext = newleft; + return newleft; + } +} + +static void recolor(Rb_node n) +{ + Rb_node p, gp, s; + int done = 0; + + while(!done) { + if (isroot(n)) { + setblack(n); + return; + } + + p = n->p.parent; + + if (isblack(p)) return; + + if (isroot(p)) { + setblack(p); + return; + } + + gp = p->p.parent; + s = sibling(p); + if (isred(s)) { + setblack(p); + setred(gp); + setblack(s); + n = gp; + } else { + done = 1; + } + } + /* p's sibling is black, p is red, gp is black */ + + if ((isleft(n) == 0) == (isleft(p) == 0)) { + single_rotate(gp, isleft(n)); + setblack(p); + setred(gp); + } else { + single_rotate(p, isleft(n)); + single_rotate(gp, isleft(n)); + setblack(n); + setred(gp); + } +} + +static void single_rotate(Rb_node y, int l) +{ + int rl, ir; + Rb_node x, yp; + + ir = isroot(y); + yp = y->p.parent; + if (!ir) { + rl = isleft(y); + } + + if (l) { + x = y->c.child.left; + y->c.child.left = x->c.child.right; + setleft(y->c.child.left); + y->c.child.left->p.parent = y; + x->c.child.right = y; + setright(y); + } else { + x = y->c.child.right; + y->c.child.right = x->c.child.left; + setright(y->c.child.right); + y->c.child.right->p.parent = y; + x->c.child.left = y; + setleft(y); + } + + x->p.parent = yp; + y->p.parent = x; + if (ir) { + yp->p.root = x; + setnormal(y); + setroot(x); + } else { + if (rl) { + yp->c.child.left = x; + setleft(x); + } else { + yp->c.child.right = x; + setright(x); + } + } +} + +void rb_delete_node(Rb_node n) +{ + Rb_node s, p, gp; + char ir; + +#ifdef DEBUG + if (isint(n)) { + fprintf(stderr, "Cannot delete an internal node: %p\n", n); + exit(1); + } + if (ishead(n)) { + fprintf(stderr, "Cannot delete the head of an rb_tree: %p\n", n); + exit(1); + } +#else + assert(!isint(n)); + assert(!ishead(n)); +#endif + delete_item(n); /* Delete it from the list */ + p = n->p.parent; /* The only node */ + if (isroot(n)) { + p->p.root = p; + free(n); + return; + } + s = sibling(n); /* The only node after deletion */ + if (isroot(p)) { + s->p.parent = p->p.parent; + s->p.parent->p.root = s; + setroot(s); + free(p); + free(n); + return; + } + gp = p->p.parent; /* Set parent to sibling */ + s->p.parent = gp; + if (isleft(p)) { + gp->c.child.left = s; + setleft(s); + } else { + gp->c.child.right = s; + setright(s); + } + ir = isred(p); + free(p); + free(n); + + if (isext(s)) { /* Update proper rext and lext values */ + p = lprev(s); + if (!ishead(p)) p->v.rext = s; + p = rprev(s); + if (!ishead(p)) p->k.lext = s; + } else if (isblack(s)) { +#ifdef DEBUG + fprintf(stderr, "DELETION PROB -- sib is black, internal\n"); + exit(1); +#else + assert(1); +#endif + } else { + p = lprev(s); + if (!ishead(p)) p->v.rext = s->c.child.left; + p = rprev(s); + if (!ishead(p)) p->k.lext = s->c.child.right; + setblack(s); + return; + } + + if (ir) return; + + /* Recolor */ + + n = s; + p = n->p.parent; + s = sibling(n); + while(isblack(p) && isblack(s) && isint(s) && + isblack(s->c.child.left) && isblack(s->c.child.right)) { + setred(s); + n = p; + if (isroot(n)) return; + p = n->p.parent; + s = sibling(n); + } + + if (isblack(p) && isred(s)) { /* Rotation 2.3b */ + single_rotate(p, isright(n)); + setred(p); + setblack(s); + s = sibling(n); + } + + { Rb_node x, z; char il; +#ifdef DEBUG + if (isext(s)) { + fprintf(stderr, "DELETION ERROR: sibling not internal\n"); + exit(1); + } +#else + assert(!isext(s)); +#endif + + il = isleft(n); + x = il ? s->c.child.left : s->c.child.right; + z = sibling(x); + + if (isred(z)) { /* Rotation 2.3f */ + single_rotate(p, !il); + setblack(z); + if (isred(p)) setred(s); else setblack(s); + setblack(p); + } else if (isblack(x)) { /* Recoloring only (2.3c) */ +#ifdef DEBUG + if (isred(s) || isblack(p)) { + fprintf(stderr, "DELETION ERROR: 2.3c not quite right\n"); + exit(1); + } +#else + assert(!isred(s) && !isblack(p)); +#endif + setblack(p); + setred(s); + return; + } else if (isred(p)) { /* 2.3d */ + single_rotate(s, il); + single_rotate(p, !il); + setblack(x); + setred(s); + return; + } else { /* 2.3e */ + single_rotate(s, il); + single_rotate(p, !il); + setblack(x); + return; + } + } +} + + +#ifdef DEBUG +void rb_print_tree(Rb_node t, int level) +{ + int i; + if (ishead(t) && t->p.parent == t) { + printf("tree %p is empty\n", t); + } else if (ishead(t)) { + printf("Head: %p. Root = %p\n", t, t->p.root); + rb_print_tree(t->p.root, 0); + } else { + if (isext(t)) { + for (i = 0; i < level; i++) putchar(' '); + printf("Ext node %p: %c,%c: p=0x%x, k=%s\n", + t, isred(t)?'R':'B', isleft(t)?'l':'r', t->p.parent, t->k.key); + } else { + rb_print_tree(t->c.child.left, level+2); + rb_print_tree(t->c.child.right, level+2); + for (i = 0; i < level; i++) putchar(' '); + printf("Int node %p: %c,%c: l=0x%x, r=0x%x, p=0x%x, lr=(%s,%s)\n", + t, isred(t)?'R':'B', isleft(t)?'l':'r', t->c.child.left, + t->c.child.right, + t->p.parent, t->k.lext->k.key, t->v.rext->k.key); + } + } +} +#endif + +int rb_nblack(Rb_node n) +{ + int nb; +#ifdef DEBUG + if (ishead(n) || isint(n)) { + fprintf(stderr, "ERROR: rb_nblack called on a non-external node %p\n", + n); + exit(1); + } +#else + assert(!ishead(n)); + assert(!isint(n)); +#endif + nb = 0; + while(!ishead(n)) { + if (isblack(n)) nb++; + n = n->p.parent; + } + return nb; +} + +int rb_plength(Rb_node n) +{ + int pl; +#ifdef DEBUG + if (ishead(n) || isint(n)) { + fprintf(stderr, "ERROR: rb_plength called on a non-external node %p\n", + n); + exit(1); + } +#else + assert(!ishead(n)); + assert(!isint(n)); +#endif + pl = 0; + while(!ishead(n)) { + pl++; + n = n->p.parent; + } + return pl; +} + +void rb_free_tree(Rb_node n) +{ +#ifdef DEBUG + if (!ishead(n)) { + fprintf(stderr, "ERROR: Rb_free_tree called on a non-head node\n"); + exit(1); + } +#else + assert(ishead(n)); +#endif + + while(rb_first(n) != rb_nil(n)) { + rb_delete_node(rb_first(n)); + } + free(n); +} + +void *rb_val(Rb_node n) +{ + return n->v.val; +} + +Rb_node rb_insert_a(Rb_node nd, void *val) +{ + return rb_insert_b(nd->c.list.flink, val); +} + +Rb_node rb_insert(Rb_node tree, const void *key, rb_key_cmp_fn cmp, void *val) +{ + return rb_insert_b(rb_find_key(tree, key, cmp), val); +} @@ -0,0 +1,128 @@ +/* +Generic C code for red-black trees. +Copyright (C) 2000 James S. Plank + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Lesser General Public +License as published by the Free Software Foundation; either +version 2.1 of the License, or (at your option) any later version. + +This library 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 +Lesser General Public License for more details. + +You should have received a copy of the GNU Lesser General Public +License along with this library; if not, write to the Free Software +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* Revision 1.2. Jim Plank */ + +/* Original code by Jim Plank (plank@cs.utk.edu) */ +/* modified for THINK C 6.0 for Macintosh by Chris Bartley */ + +/* Modified by Russell King to support embedded keys only */ + +typedef struct { + unsigned red : 1 ; + unsigned internal : 1 ; + unsigned left : 1 ; + unsigned root : 1 ; + unsigned head : 1 ; +} status; + +/* Main rb_node. You only ever use the fields + + c.list.flink + c.list.blink + + k.key or k.ikey + v.val +*/ + +typedef int (*rb_key_cmp_fn)(const void *, const void *); + +typedef struct rb_node { + union { + struct { + struct rb_node *flink; + struct rb_node *blink; + } list; + struct { + struct rb_node *left; + struct rb_node *right; + } child; + } c; + union { + struct rb_node *parent; + struct rb_node *root; + } p; + status s; + union { + struct rb_node *lext; + } k; + union { + void *val; + struct rb_node *rext; + } v; +} *Rb_node; + + +extern Rb_node make_rb(void); /* Creates a new rb-tree */ + + + +/* Creates a node with key key and val val and inserts it into the tree. + rb_insert uses strcmp() as comparison funcion. rb_inserti uses <>=, + rb_insertg uses func() */ + +extern Rb_node rb_insert(Rb_node tree, const void *key, + rb_key_cmp_fn fn, void *data); + + +/* returns an external node in t whose value is equal + k or whose value is the smallest value greater than k. */ + +extern Rb_node rb_find_key(Rb_node root, const void *key, + rb_key_cmp_fn fn); + + +/* Works just like the find_key versions only it returns whether or not + it found the key in the integer variable found */ + +extern Rb_node rb_find_key_n(Rb_node root, const void *key, + rb_key_cmp_fn fn, int *found); + + +/* Creates a node with key key and val val and inserts it into the + tree before/after node nd. Does not check to ensure that you are + keeping the correct order */ + +extern Rb_node rb_insert_b(Rb_node nd, void *val); +extern Rb_node rb_insert_a(Rb_node nd, void *val); + + +extern void rb_delete_node(Rb_node node); /* Deletes and frees a node (but + not the key or val) */ +extern void rb_free_tree(Rb_node root); /* Deletes and frees an entire tree */ + +extern void *rb_val(Rb_node node); /* Returns node->v.val -- this is to shut + lint up */ + +extern int rb_nblack(Rb_node n); /* returns # of black nodes in path from + n to the root */ +int rb_plength(Rb_node n); /* returns the # of nodes in path from + n to the root */ + +#define rb_first(n) (n->c.list.flink) +#define rb_last(n) (n->c.list.blink) +#define rb_next(n) (n->c.list.flink) +#define rb_prev(n) (n->c.list.blink) +#define rb_empty(t) (t->c.list.flink == t) +#ifndef rb_nil +#define rb_nil(t) (t) +#endif + +#define rb_traverse(ptr, lst) \ + for(ptr = rb_first(lst); ptr != rb_nil(lst); ptr = rb_next(ptr)) |