user/vmm: add and use a load_elf function
[akaros.git] / kern / include / radix.h
1 /* Copyright (c) 2010 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Radix Tree, modeled after Linux's (described here:
6  * http://lwn.net/Articles/175432/).
7  *
8  * It maps unsigned longs to void*s, growing the depth of the tree as needed to
9  * handle more items.  It won't allow the insertion of existing keys, and it
10  * can fail due to lack of memory.
11  *
12  * There are some utility functions, probably unimplemented til we need them,
13  * that will make the tree have enough memory for future calls.
14  *
15  * You can also store a tag along with the void* for a given item, and do
16  * lookups based on those tags.  Or you will be able to, once it is
17  * implemented. */
18
19 #pragma once
20
21 #define LOG_RNODE_SLOTS 6
22 #define NR_RNODE_SLOTS (1 << LOG_RNODE_SLOTS)
23
24 #include <ros/common.h>
25
26 struct radix_node {
27         void                                            *items[NR_RNODE_SLOTS];
28         unsigned int                            num_items;
29         bool                                            leaf;
30         struct radix_node                       *parent;
31         struct radix_node                       **my_slot;
32 };
33
34 /* Defines the whole tree. */
35 struct radix_tree {
36         struct radix_node                       *root;
37         unsigned int                            depth;
38         unsigned long                           upper_bound;
39 };
40
41 void radix_init(void);          /* initializes the whole radix system */
42 #define RADIX_INITIALIZER {0, 0, 0}
43 void radix_tree_init(struct radix_tree *tree);  /* inits one tree */
44 void radix_tree_destroy(struct radix_tree *tree);
45
46 /* Item management */
47 int radix_insert(struct radix_tree *tree, unsigned long key, void *item,
48                  void ***slot_p);
49 void *radix_delete(struct radix_tree *tree, unsigned long key);
50 void *radix_lookup(struct radix_tree *tree, unsigned long key);
51 void **radix_lookup_slot(struct radix_tree *tree, unsigned long key);
52 int radix_gang_lookup(struct radix_tree *tree, void **results,
53                       unsigned long first, unsigned int max_items);
54
55 /* Memory management */
56 int radix_grow(struct radix_tree *tree, unsigned long max);
57 int radix_preload(struct radix_tree *tree, int flags);
58
59 /* Tag management */
60 void *radix_tag_set(struct radix_tree *tree, unsigned long key, int tag);
61 void *radix_tag_clear(struct radix_tree *tree, unsigned long key, int tag);
62 int radix_tag_get(struct radix_tree *tree, unsigned long key, int tag);
63 int radix_tree_tagged(struct radix_tree *tree, int tag);
64 int radix_tag_gang_lookup(struct radix_tree *tree, void **results,
65                           unsigned long first, unsigned int max_items, int tag);
66
67 /* Debugging */
68 void print_radix_tree(struct radix_tree *tree);