From c46faad66a8d44b67b9b270649c0b9812bf9eff7 Mon Sep 17 00:00:00 2001 From: Russell King Date: Sun, 8 Dec 2013 22:10:39 +0000 Subject: Update vmeta to BMMv2 Update vmeta to use the dma_buf handling now provided by libbmm v2. This permits more flexible buffer management, as the buffers can now be passed via a standardized mechanism to other subsystems (such as DRM), and image data to be encoded can be accepted directly from other subsystems without needing to be copied. Signed-off-by: Russell King --- rb.h | 128 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 128 insertions(+) create mode 100644 rb.h (limited to 'rb.h') diff --git a/rb.h b/rb.h new file mode 100644 index 0000000..80f433c --- /dev/null +++ b/rb.h @@ -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)) -- cgit