Messages in this thread | | | Date | Fri, 11 Apr 2003 05:13:08 -0700 | From | William Lee Irwin III <> | Subject | Re: [RFC] first try for swap prefetch |
| |
On Fri, Apr 11, 2003 at 01:51:55PM +0200, Thomas Schlichter wrote: > Sorry, but I think I can not. The list_del() needs the value returned by > radix_tree_lookup(), so I can not kick it... By the way, the only reason for > the radix tree is to make this list_del() not O(n) for searching the list... > Do you know how expensive the radix_tree_lookup() is? O(1) or O(log(n))?? For > my shame I do not really know that data structure... :-(
It's O(lg(keyspace)). This is regarded as constant by many.
-- wli - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |