Main Page | Directories | File List | Globals

btree.c

Go to the documentation of this file.
00001 /*
00002  * kernel_libs/data_structures/btree.c
00003  *
00004  * Copyright (c) 2003-2004 Lukasz Dembinski <dembol@nasa.com.pl>
00005  * All Rights Reserved
00006  * 
00007  * Date:        2004/05
00008  * Author:      Lukasz Dembinski
00009  * Info:        btree.c core file
00010  * Contact:     mailto: <dembol@nasa.com.pl>
00011  * Status:      started
00012  */
00013 
00014 #include <agnix/agnix.h>
00015 #include <agnix/resources.h>
00016 #include <agnix/memory.h>
00017 #include <agnix/spinlock.h>
00018 #include <agnix/list.h>
00019 #include <agnix/console.h>
00020 
00021 #define MOD_NAME        "BTREE: "
00022 #define MAX_BTREES      16
00023 
00024 #define MAX_BTREE_NODE_RATIO            16
00025 
00026 #define BTREE_NODE_ENTRY_PRESENT        0x01
00027 #define BTREE_NODE_ENTRY_EMPTY          0x02
00028 #define BTREE_NODE_ENTRY_END            0x04
00029 #define BTREE_NODE_ENTRY_LEAF           0x08
00030 
00031 #define BTREE_NODE_ROOT                 0x10
00032 #define BTREE_NODE_MIDDLE               0x20
00033 
00034 #define BTREE_SEARCH_FOUND              0
00035 #define BTREE_SEARCH_NOT_EXISTS         -1
00036 #define BTREE_SEARCH_ROOT_NOT_EXISTS    -2
00037 
00038 #define BTREE_INSERT_OK                 0
00039 #define BTREE_INSERT_EXISTS             -1
00040 
00041 struct btree_ops_s;
00042 
00043 struct btree_s {
00044     const char *         btree_name;
00045     int                  btree_ratio;
00046     struct list_head     btree_root_list;    
00047     spinlock_t           btree_lock;
00048     struct btree_ops_s * btree_ops;
00049 };
00050 
00051 struct btree_ops_s {
00052         
00053 };
00054 
00055 struct btree_node_entry_s {
00056     struct list_head    node_entry_list;
00057     int                 node_entry_status;
00058     u32                 node_entry_key;
00059     u32                 node_entry_address;
00060 };
00061 
00062 struct btree_node_s {
00063     struct btree_node_entry_s * node_entries;
00064     int                         node_entries_count;
00065     int                         node_ratio;
00066     struct list_head            node_list;
00067 };
00068 
00069 struct btree_s btrees[MAX_BTREES];
00070 
00071 u32 btree_bitmap[MAX_BTREES];
00072 
00073 int btree_resource_desc;
00074 struct resource_s btree_resource = {
00075     .resource_name      = "btree",
00076     .resource_bitmap    = btree_bitmap,
00077     .resource_len       = MAX_BTREES,
00078 };
00079 
00080 struct btree_node_s *btree_alloc_node(int node_ratio)
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 }
00118 
00119 int btree_search_lock(struct btree_s *btree, u32 key, struct btree_node_s **node_parent, 
00120                       struct btree_node_s **node_found, int *key_position);
00121 
00122 int btree_insert_overflow_lock(struct btree_node_s *node_found, struct btree_node_s *node_parent, u32 key, 
00123                                u32 address, int key_position)
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 }
00147 
00148 int btree_insert_entry_lock(struct btree_node_s *node, u32 key, u32 address, int key_position)
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 }
00166 
00167 int btree_insert_lock(struct btree_s *btree, u32 key, u32 address)
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 }
00194 
00195 int btree_insert(int btree_desc, u32 key, u32 address)
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 }
00212 
00213 int btree_search_node_lock(struct btree_node_s *node, u32 key, struct btree_node_s **node_parent, 
00214                            struct btree_node_s **node_found, int *key_position)
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 }
00262 
00263 int btree_search_lock(struct btree_s *btree, u32 key, struct btree_node_s **node_parent, 
00264                       struct btree_node_s **node_found, int *key_position)
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 }
00278 
00279 u32 btree_search(int btree_desc, u32 key)
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 }
00302 
00303 int put_free_btree(int btree_desc)
00304 {
00305     return put_free_resource(btree_resource_desc, btree_desc);
00306 }
00307 
00308 int get_free_btree(void)
00309 {
00310     return get_free_resource(btree_resource_desc);
00311 }
00312 
00313 int register_btree(int btree_ratio, const char *btree_name)
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 }
00332 
00333 int unregister_btree(int btree_desc)
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 }
00341 
00342 int btree_init(void)
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 }
Dokumentacje wygenerowano programem Doxygen 1.4.2 dla projektu Agnix