Main Page | Directories | File List | Globals

btree.c File Reference

#include <agnix/agnix.h>
#include <agnix/resources.h>
#include <agnix/memory.h>
#include <agnix/spinlock.h>
#include <agnix/list.h>
#include <agnix/console.h>

Include dependency graph for btree.c:

Go to the source code of this file.

Defines

#define MOD_NAME   "BTREE: "
#define MAX_BTREES   16
#define MAX_BTREE_NODE_RATIO   16
#define BTREE_NODE_ENTRY_PRESENT   0x01
#define BTREE_NODE_ENTRY_EMPTY   0x02
#define BTREE_NODE_ENTRY_END   0x04
#define BTREE_NODE_ENTRY_LEAF   0x08
#define BTREE_NODE_ROOT   0x10
#define BTREE_NODE_MIDDLE   0x20
#define BTREE_SEARCH_FOUND   0
#define BTREE_SEARCH_NOT_EXISTS   -1
#define BTREE_SEARCH_ROOT_NOT_EXISTS   -2
#define BTREE_INSERT_OK   0
#define BTREE_INSERT_EXISTS   -1

Functions

btree_node_s * btree_alloc_node (int node_ratio)
int btree_search_lock (struct btree_s *btree, u32 key, struct btree_node_s **node_parent, struct btree_node_s **node_found, int *key_position)
int btree_insert_overflow_lock (struct btree_node_s *node_found, struct btree_node_s *node_parent, u32 key, u32 address, int key_position)
int btree_insert_entry_lock (struct btree_node_s *node, u32 key, u32 address, int key_position)
int btree_insert_lock (struct btree_s *btree, u32 key, u32 address)
int btree_insert (int btree_desc, u32 key, u32 address)
int btree_search_node_lock (struct btree_node_s *node, u32 key, struct btree_node_s **node_parent, struct btree_node_s **node_found, int *key_position)
u32 btree_search (int btree_desc, u32 key)
int put_free_btree (int btree_desc)
int get_free_btree (void)
int register_btree (int btree_ratio, const char *btree_name)
int unregister_btree (int btree_desc)
int btree_init (void)

Variables

btree_s btrees [MAX_BTREES]
u32 btree_bitmap [MAX_BTREES]
int btree_resource_desc
resource_s btree_resource


Define Documentation

#define BTREE_INSERT_EXISTS   -1
 

Definition at line 39 of file btree.c.

Referenced by btree_insert_lock().

#define BTREE_INSERT_OK   0
 

Definition at line 38 of file btree.c.

Referenced by btree_insert_entry_lock(), and btree_insert_lock().

#define BTREE_NODE_ENTRY_EMPTY   0x02
 

Definition at line 27 of file btree.c.

#define BTREE_NODE_ENTRY_END   0x04
 

Definition at line 28 of file btree.c.

Referenced by btree_alloc_node(), btree_insert_overflow_lock(), and btree_search_node_lock().

#define BTREE_NODE_ENTRY_LEAF   0x08
 

Definition at line 29 of file btree.c.

Referenced by btree_alloc_node(), and btree_insert_entry_lock().

#define BTREE_NODE_ENTRY_PRESENT   0x01
 

Definition at line 26 of file btree.c.

Referenced by btree_alloc_node(), btree_insert_entry_lock(), and btree_search_node_lock().

#define BTREE_NODE_MIDDLE   0x20
 

Definition at line 32 of file btree.c.

#define BTREE_NODE_ROOT   0x10
 

Definition at line 31 of file btree.c.

#define BTREE_SEARCH_FOUND   0
 

Definition at line 34 of file btree.c.

Referenced by btree_insert_lock(), btree_search(), and btree_search_node_lock().

#define BTREE_SEARCH_NOT_EXISTS   -1
 

Definition at line 35 of file btree.c.

Referenced by btree_search_node_lock().

#define BTREE_SEARCH_ROOT_NOT_EXISTS   -2
 

Definition at line 36 of file btree.c.

Referenced by btree_insert_lock(), and btree_search_lock().

#define MAX_BTREE_NODE_RATIO   16
 

Definition at line 24 of file btree.c.

Referenced by btree_alloc_node().

#define MAX_BTREES   16
 

Definition at line 22 of file btree.c.

#define MOD_NAME   "BTREE: "
 

Definition at line 21 of file btree.c.


Function Documentation

struct btree_node_s* btree_alloc_node int  node_ratio  ) 
 

Definition at line 80 of file btree.c.

References BTREE_NODE_ENTRY_END, BTREE_NODE_ENTRY_LEAF, BTREE_NODE_ENTRY_PRESENT, get_free_pages(), MAX_BTREE_NODE_RATIO, MOD_NAME, printk(), and put_free_pages().

Referenced by btree_insert_lock().

00081 {
00082     struct btree_node_s *node_alloc;
00083     struct btree_node_entry_s *node_entries_alloc;
00084     
00085     if (node_ratio > MAX_BTREE_NODE_RATIO) {
00086         printk(MOD_NAME "btree_node_ratio == MAX_BTREE_NODE_RATIO\n");
00087         return NULL;
00088     }
00089     
00090     node_alloc = (struct btree_node_s *)get_free_pages(0);
00091     
00092     if (node_alloc == NULL) {
00093         printk(MOD_NAME "btree_alloc_node failed, node_alloc == NULL\n");
00094         return NULL;
00095     }
00096     
00097     node_entries_alloc = (struct btree_node_entry_s *)get_free_pages(0);
00098 
00099     if (node_alloc == NULL) {
00100         printk(MOD_NAME "btree_alloc_node failed, node_alloc == NULL\n");
00101         goto btree_free_node;
00102     }
00103 
00104     node_alloc->node_entries_count      = 1; /* end pointer */
00105     node_alloc->node_list.next          = node_alloc->node_list.prev = NULL;
00106     node_alloc->node_ratio              = node_ratio;
00107     node_alloc->node_entries            = node_entries_alloc;
00108     
00109     node_entries_alloc[0].node_entry_status = BTREE_NODE_ENTRY_PRESENT | BTREE_NODE_ENTRY_END | 
00110                                               BTREE_NODE_ENTRY_LEAF;
00111     
00112     return node_alloc;
00113     
00114 btree_free_node:
00115     put_free_pages((u32)node_alloc, 0);
00116     return NULL;
00117 }

Here is the call graph for this function:

int btree_init void   ) 
 

Definition at line 342 of file btree.c.

References btree_resource, btree_resource_desc, memset(), MOD_NAME, printk(), and register_resource().

Referenced by data_structures_init().

00343 {
00344     printk(MOD_NAME "Initializing b-trees\n");
00345 
00346     memset(btrees, 0, sizeof(struct btree_s ) * MAX_BTREES);
00347     btree_resource_desc = register_resource(&btree_resource);
00348 
00349     return 0;
00350 }

Here is the call graph for this function:

int btree_insert int  btree_desc,
u32  key,
u32  address
 

Definition at line 195 of file btree.c.

References btree_insert_lock(), flags, MOD_NAME, and printk().

00196 {
00197     struct btree_s *btree = &btrees[btree_desc];
00198     u32 flags;
00199     int ret;
00200 
00201     if (!btree) {
00202         printk(MOD_NAME "btree pointer is NULL\n");
00203         return -1;
00204     }
00205 
00206     spin_lock_irqsave(&btree->btree_lock, flags);
00207     ret = btree_insert_lock(btree, key, address);
00208     spin_unlock_irqrestore(&btree->btree_lock, flags);
00209 
00210     return ret;
00211 }

Here is the call graph for this function:

int btree_insert_entry_lock struct btree_node_s *  node,
u32  key,
u32  address,
int  key_position
 

Definition at line 148 of file btree.c.

References BTREE_INSERT_OK, BTREE_NODE_ENTRY_LEAF, BTREE_NODE_ENTRY_PRESENT, and memcpy().

Referenced by btree_insert_lock().

00149 {
00150     struct btree_node_entry_s *entry = node->node_entries;
00151     int i;
00152     
00153 //    for (i = (node->node_ratio << 1) - 1; i > key_position; i--) {
00154     for (i = node->node_entries_count; i > key_position; i--) {
00155         memcpy(&entry[i], &entry[i - 1], sizeof(struct btree_node_entry_s));
00156     }
00157     
00158     entry[key_position].node_entry_list.next    = NULL;
00159     entry[key_position].node_entry_list.prev    = NULL; /* unused */
00160     entry[key_position].node_entry_key          = key;
00161     entry[key_position].node_entry_address      = address;
00162     entry[key_position].node_entry_status       = BTREE_NODE_ENTRY_PRESENT | BTREE_NODE_ENTRY_LEAF;
00163     
00164     return BTREE_INSERT_OK;
00165 }

Here is the call graph for this function:

int btree_insert_lock struct btree_s *  btree,
u32  key,
u32  address
 

Definition at line 167 of file btree.c.

References btree_alloc_node(), btree_insert_entry_lock(), BTREE_INSERT_EXISTS, BTREE_INSERT_OK, btree_insert_overflow_lock(), BTREE_SEARCH_FOUND, btree_search_lock(), and BTREE_SEARCH_ROOT_NOT_EXISTS.

Referenced by btree_insert().

00168 {
00169     struct btree_node_s *node_found;
00170     struct btree_node_s *node_parent;
00171     int key_position;
00172     int ret;
00173     
00174     ret = btree_search_lock(btree, key, &node_parent, &node_found, &key_position);
00175     
00176     if (ret == BTREE_SEARCH_FOUND)
00177         return BTREE_INSERT_EXISTS;
00178     else
00179     if (ret == BTREE_SEARCH_ROOT_NOT_EXISTS) {
00180         /* we have to alloc root node if it doesn't exists */
00181         node_parent  = NULL;
00182         node_found   = btree_alloc_node(btree->btree_ratio);
00183         key_position = 0;
00184         btree->btree_root_list.next = &node_found->node_list;
00185     }
00186 
00187     if ((node_found->node_ratio << 1) > node_found->node_entries_count)
00188         return btree_insert_entry_lock(node_found, key, address, key_position);
00189 
00190     btree_insert_overflow_lock(node_found, node_parent, key, address, key_position);
00191 
00192     return BTREE_INSERT_OK;
00193 }

Here is the call graph for this function:

int btree_insert_overflow_lock struct btree_node_s *  node_found,
struct btree_node_s *  node_parent,
u32  key,
u32  address,
int  key_position
 

Definition at line 122 of file btree.c.

References BTREE_NODE_ENTRY_END, and printk().

Referenced by btree_insert_lock().

00124 {
00125     struct btree_node_s *node_neigh_left;
00126     struct btree_node_s *node_neigh_right;
00127     int i;
00128 
00129     if (node_parent == NULL)
00130     {
00131         printk("Splitting root\n");
00132         return 0;
00133     }
00134 
00135     for (i = 0; i < node_parent->node_entries_count; i++) {
00136         if ((node_parent->node_entries[i].node_entry_key < key) || 
00137             (node_parent->node_entries[i].node_entry_status & BTREE_NODE_ENTRY_END))
00138             break;
00139     }
00140 
00141     node_neigh_right = list_entry(node_parent->node_entries[i].node_entry_list.next, struct btree_node_s, node_list);
00142     if (i + 1 < node_parent->node_entries_count) 
00143         node_neigh_left = list_entry(node_parent->node_entries[i + 1].node_entry_list.next, struct btree_node_s, node_list);
00144 
00145     return 0;
00146 }

Here is the call graph for this function:

u32 btree_search int  btree_desc,
u32  key
 

Definition at line 279 of file btree.c.

References BTREE_SEARCH_FOUND, btree_search_lock(), flags, MOD_NAME, and printk().

00280 {
00281     struct btree_s *btree = &btrees[btree_desc];
00282     struct btree_node_s *node_found;
00283     struct btree_node_s *node_parent;
00284     int key_position = -1;
00285     int ret;
00286     u32 flags;
00287 
00288     if (!btree) {
00289         printk(MOD_NAME "btree pointer is NULL\n");
00290         return 0;
00291     }
00292 
00293     spin_lock_irqsave(&btree->btree_lock, flags);
00294     ret = btree_search_lock(btree, key, &node_parent, &node_found, &key_position);
00295     spin_unlock_irqrestore(&btree->btree_lock, flags);
00296 
00297     if (ret == BTREE_SEARCH_FOUND)
00298             return node_found->node_entries[key_position].node_entry_address;
00299     
00300     return 0;
00301 }

Here is the call graph for this function:

int btree_search_lock struct btree_s *  btree,
u32  key,
struct btree_node_s **  node_parent,
struct btree_node_s **  node_found,
int *  key_position
 

Definition at line 263 of file btree.c.

References btree_search_node_lock(), and BTREE_SEARCH_ROOT_NOT_EXISTS.

Referenced by btree_insert_lock(), and btree_search().

00265 {
00266     struct btree_node_s *node;
00267     int ret;
00268 
00269     if (btree->btree_root_list.next == NULL)
00270         return BTREE_SEARCH_ROOT_NOT_EXISTS;
00271     
00272     node = list_entry(btree->btree_root_list.next, struct btree_node_s, node_list);
00273 
00274     ret = btree_search_node_lock(node, key, node_parent, node_found, key_position);
00275 
00276     return ret;
00277 }

Here is the call graph for this function:

int btree_search_node_lock struct btree_node_s *  node,
u32  key,
struct btree_node_s **  node_parent,
struct btree_node_s **  node_found,
int *  key_position
 

Definition at line 213 of file btree.c.

References BTREE_NODE_ENTRY_END, BTREE_NODE_ENTRY_PRESENT, BTREE_SEARCH_FOUND, and BTREE_SEARCH_NOT_EXISTS.

Referenced by btree_search_lock().

00215 {
00216     struct btree_node_s *node_child = NULL;
00217     struct btree_node_entry_s *node_entry;
00218     int i;
00219 
00220     *node_parent = NULL;
00221 
00222     if (node->node_entries == 0)
00223         return BTREE_SEARCH_NOT_EXISTS;
00224 
00225     for (i = 0; i < node->node_entries_count; i++) {
00226 
00227         node_entry = &node->node_entries[i];
00228         if (node_entry->node_entry_status & BTREE_NODE_ENTRY_PRESENT) {
00229         
00230             if (node_entry->node_entry_key < key || 
00231                (node_entry->node_entry_status & BTREE_NODE_ENTRY_END)) {
00232         
00233                 if (node_entry->node_entry_list.next == NULL) {
00234                     *key_position = i;
00235                     *node_found = node;
00236                     return BTREE_SEARCH_NOT_EXISTS;
00237                 }
00238         
00239                 node_child = list_entry(node_entry->node_entry_list.next, 
00240                                           struct btree_node_s, node_list);
00241                 break;
00242             }
00243         
00244             if (node_entry->node_entry_key == key) {
00245                 *key_position = i;
00246                 *node_found = node;
00247                 return BTREE_SEARCH_FOUND;
00248             }
00249         } else 
00250             return -1;
00251     }
00252     
00253     if (node_child != NULL) {
00254         *node_parent = node;
00255         return btree_search_node_lock(node_child, key, node_parent, node_found, key_position);
00256     } else {
00257         *key_position = i;
00258         *node_found = node;
00259         return BTREE_SEARCH_NOT_EXISTS;
00260     }
00261 }

int get_free_btree void   ) 
 

Definition at line 308 of file btree.c.

References btree_resource_desc, and get_free_resource().

Referenced by register_btree().

00309 {
00310     return get_free_resource(btree_resource_desc);
00311 }

Here is the call graph for this function:

int put_free_btree int  btree_desc  ) 
 

Definition at line 303 of file btree.c.

References btree_resource_desc, and put_free_resource().

Referenced by unregister_btree().

00304 {
00305     return put_free_resource(btree_resource_desc, btree_desc);
00306 }

Here is the call graph for this function:

int register_btree int  btree_ratio,
const char *  btree_name
 

Definition at line 313 of file btree.c.

References get_free_btree(), memset(), MOD_NAME, and printk().

00314 {
00315     int btree_desc;
00316 
00317     btree_desc = get_free_btree();
00318     
00319     if (btree_desc < 0) {
00320         printk(MOD_NAME "register_btree failed, there is no free resources\n");
00321         return -1;
00322     }
00323 
00324     printk(MOD_NAME "registering %s btree, btree_ratio = %d\n", btree_name, btree_ratio);
00325 
00326     memset(&btrees[btree_desc], 0, sizeof(struct btree_s));
00327     btrees[btree_desc].btree_name = btree_name;
00328     spin_lock_init(&btrees[btree_desc].btree_lock);
00329 
00330     return btree_desc;
00331 }

Here is the call graph for this function:

int unregister_btree int  btree_desc  ) 
 

Definition at line 333 of file btree.c.

References MOD_NAME, printk(), and put_free_btree().

00334 {
00335     put_free_btree(btree_desc);
00336 
00337     printk(MOD_NAME "registering %s btree\n", btrees[btree_desc].btree_name);
00338 
00339     return 0;
00340 }

Here is the call graph for this function:


Variable Documentation

u32 btree_bitmap[MAX_BTREES]
 

Definition at line 71 of file btree.c.

struct resource_s btree_resource
 

Initial value:

 {
    .resource_name      = "btree",
    .resource_bitmap    = btree_bitmap,
    .resource_len       = MAX_BTREES,
}

Definition at line 74 of file btree.c.

Referenced by btree_init().

int btree_resource_desc
 

Definition at line 73 of file btree.c.

Referenced by btree_init(), get_free_btree(), and put_free_btree().

struct btree_s btrees[MAX_BTREES]
 

Definition at line 69 of file btree.c.

Dokumentacje wygenerowano programem Doxygen 1.4.2 dla projektu Agnix