From f74db0b33d491a3189df7f909d382f93f9152c30 Mon Sep 17 00:00:00 2001 From: Pablo Neira Ayuso Date: Mon, 26 Sep 2011 11:44:57 +0200 Subject: add rb-tree implementation to libosmocore This patch adds red black trees implementation to libosmocore. This data structure is very useful to search for elements in ordered sets in O(log n) instead of O(n) that lists provide. The first client of this code will be one follow up patch that implements rbtree-based timer scheduler. --- include/osmocom/core/Makefile.am | 2 +- include/osmocom/core/linuxrbtree.h | 160 +++++++++++++++++++++++++++++++++++++ 2 files changed, 161 insertions(+), 1 deletion(-) create mode 100644 include/osmocom/core/linuxrbtree.h (limited to 'include/osmocom/core') diff --git a/include/osmocom/core/Makefile.am b/include/osmocom/core/Makefile.am index aabb775f..5465d5f1 100644 --- a/include/osmocom/core/Makefile.am +++ b/include/osmocom/core/Makefile.am @@ -2,7 +2,7 @@ osmocore_HEADERS = signal.h linuxlist.h timer.h select.h msgb.h bits.h \ bitvec.h statistics.h utils.h socket.h \ gsmtap.h write_queue.h prim.h \ logging.h rate_ctr.h gsmtap_util.h \ - crc16.h panic.h process.h \ + crc16.h panic.h process.h linuxrbtree.h \ backtrace.h conv.h application.h \ crcgen.h crc8gen.h crc16gen.h crc32gen.h crc64gen.h diff --git a/include/osmocom/core/linuxrbtree.h b/include/osmocom/core/linuxrbtree.h new file mode 100644 index 00000000..ee988918 --- /dev/null +++ b/include/osmocom/core/linuxrbtree.h @@ -0,0 +1,160 @@ +/* + Red Black Trees + (C) 1999 Andrea Arcangeli + + 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + linux/include/linux/rbtree.h + + To use rbtrees you'll have to implement your own insert and search cores. + This will avoid us to use callbacks and to drop drammatically performances. + I know it's not the cleaner way, but in C (not in C++) to get + performances and genericity... + + Some example of insert and search follows here. The search is a plain + normal search over an ordered tree. The insert instead must be implemented + int two steps: as first thing the code must insert the element in + order as a red leaf in the tree, then the support library function + rb_insert_color() must be called. Such function will do the + not trivial work to rebalance the rbtree if necessary. + +----------------------------------------------------------------------- +static inline struct page * rb_search_page_cache(struct inode * inode, + unsigned long offset) +{ + struct rb_node * n = inode->i_rb_page_cache.rb_node; + struct page * page; + + while (n) + { + page = rb_entry(n, struct page, rb_page_cache); + + if (offset < page->offset) + n = n->rb_left; + else if (offset > page->offset) + n = n->rb_right; + else + return page; + } + return NULL; +} + +static inline struct page * __rb_insert_page_cache(struct inode * inode, + unsigned long offset, + struct rb_node * node) +{ + struct rb_node ** p = &inode->i_rb_page_cache.rb_node; + struct rb_node * parent = NULL; + struct page * page; + + while (*p) + { + parent = *p; + page = rb_entry(parent, struct page, rb_page_cache); + + if (offset < page->offset) + p = &(*p)->rb_left; + else if (offset > page->offset) + p = &(*p)->rb_right; + else + return page; + } + + rb_link_node(node, parent, p); + + return NULL; +} + +static inline struct page * rb_insert_page_cache(struct inode * inode, + unsigned long offset, + struct rb_node * node) +{ + struct page * ret; + if ((ret = __rb_insert_page_cache(inode, offset, node))) + goto out; + rb_insert_color(node, &inode->i_rb_page_cache); + out: + return ret; +} +----------------------------------------------------------------------- +*/ + +#ifndef _LINUX_RBTREE_H +#define _LINUX_RBTREE_H + +#include + +struct rb_node +{ + unsigned long rb_parent_color; +#define RB_RED 0 +#define RB_BLACK 1 + struct rb_node *rb_right; + struct rb_node *rb_left; +} __attribute__((aligned(sizeof(long)))); + /* The alignment might seem pointless, but allegedly CRIS needs it */ + +struct rb_root +{ + struct rb_node *rb_node; +}; + + +#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) +#define rb_color(r) ((r)->rb_parent_color & 1) +#define rb_is_red(r) (!rb_color(r)) +#define rb_is_black(r) rb_color(r) +#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) +#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0) + +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) +{ + rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; +} +static inline void rb_set_color(struct rb_node *rb, int color) +{ + rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; +} + +#define RB_ROOT { NULL, } +#define rb_entry(ptr, type, member) container_of(ptr, type, member) + +#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) +#define RB_EMPTY_NODE(node) (rb_parent(node) == node) +#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) + +extern void rb_insert_color(struct rb_node *, struct rb_root *); +extern void rb_erase(struct rb_node *, struct rb_root *); + +/* Find logical next and previous nodes in a tree */ +extern struct rb_node *rb_next(struct rb_node *); +extern struct rb_node *rb_prev(struct rb_node *); +extern struct rb_node *rb_first(struct rb_root *); +extern struct rb_node *rb_last(struct rb_root *); + +/* Fast replacement of a single node without remove/rebalance/add/rebalance */ +extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, + struct rb_root *root); + +static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, + struct rb_node ** rb_link) +{ + node->rb_parent_color = (unsigned long )parent; + node->rb_left = node->rb_right = NULL; + + *rb_link = node; +} + +#endif /* _LINUX_RBTREE_H */ -- cgit v1.2.3 From 066c912fd3b4554d4475ae0837c1d62ef6c872d1 Mon Sep 17 00:00:00 2001 From: Pablo Neira Ayuso Date: Mon, 26 Sep 2011 11:45:03 +0200 Subject: timer: add scalable RB-tree based timer infrastructure This patch adds RB-tree based timers which scales better than the previous list-based implementation. It does not require any API changes. It breaks ABI because the osmo_timer_list structure has changed though (to avoid this in the future, we can put internal data in some private structure). The following table summarizes the worst-case computational complexity of this new implementation versus the previous one: rb-tree list-based ------- ---------- calculate next timer to expire O(1) O(n) insertion of new timer O(log n) O(n) deletion of timer O(log n) O(1) timer-fired scheduler O(log n) O(3n) The most repeated cases are: * the calculation of the next timer to expire, that happens in every loop of our select function. * the timer-fired scheduler execution. This new implementation only loses in the deletion of timer scenario, this happens because we may need to rebalance the tree after the removal. So I think there is some real gain if we have some situation in which we have to handle lots of timers. --- include/osmocom/core/timer.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'include/osmocom/core') diff --git a/include/osmocom/core/timer.h b/include/osmocom/core/timer.h index 8f8c826d..30f558b4 100644 --- a/include/osmocom/core/timer.h +++ b/include/osmocom/core/timer.h @@ -32,6 +32,7 @@ #include #include +#include /** * Timer management: @@ -51,11 +52,10 @@ */ /*! \brief A structure representing a single instance of a timer */ struct osmo_timer_list { - struct llist_head entry; /*!< \brief linked list header */ + struct rb_node node; /*!< \brief rb-tree node header */ + struct llist_head list; /*!< \brief internal list header */ struct timeval timeout; /*!< \brief expiration time */ unsigned int active : 1; /*!< \brief is it active? */ - unsigned int handled : 1; /*!< \brief did we already handle it */ - unsigned int in_list : 1; /*!< \brief is it in the global list? */ void (*cb)(void*); /*!< \brief call-back called at timeout */ void *data; /*!< \brief user data for callback */ -- cgit v1.2.3