fs/reiser4/plugin/node/node.c

   1 /* Copyright 2001, 2002, 2003 by Hans Reiser, licensing governed by reiser4/README */
   2
   3 /* Node plugin interface.
   4
   5    Description: The tree provides the abstraction of flows, which it
   6    internally fragments into items which it stores in nodes.
   7
   8    A key_atom is a piece of data bound to a single key.
   9
  10    For reasonable space efficiency to be achieved it is often
  11    necessary to store key_atoms in the nodes in the form of items, where
  12    an item is a sequence of key_atoms of the same or similar type. It is
  13    more space-efficient, because the item can implement (very)
  14    efficient compression of key_atom's bodies using internal knowledge
  15    about their semantics, and it can often avoid having a key for each
  16    key_atom. Each type of item has specific operations implemented by its
  17    item handler (see balance.c).
  18
  19    Rationale: the rest of the code (specifically balancing routines)
  20    accesses leaf level nodes through this interface. This way we can
  21    implement various block layouts and even combine various layouts
  22    within the same tree. Balancing/allocating algorithms should not
  23    care about peculiarities of splitting/merging specific item types,
  24    but rather should leave that to the item's item handler.
  25
  26    Items, including those that provide the abstraction of flows, have
  27    the property that if you move them in part or in whole to another
  28    node, the balancing code invokes their is_left_mergeable()
  29    item_operation to determine if they are mergeable with their new
  30    neighbor in the node you have moved them to.  For some items the
  31    is_left_mergeable() function always returns null.
  32
  33    When moving the bodies of items from one node to another:
  34
  35      if a partial item is shifted to another node the balancing code invokes
  36      an item handler method to handle the item splitting.
  37
  38      if the balancing code needs to merge with an item in the node it
  39      is shifting to, it will invoke an item handler method to handle
  40      the item merging.
  41
  42      if it needs to move whole item bodies unchanged, the balancing code uses xmemcpy()
  43      adjusting the item headers after the move is done using the node handler.
  44 */
  45
  46 #include "../../forward.h"
  47 #include "../../debug.h"
  48 #include "../../key.h"
  49 #include "../../coord.h"
  50 #include "../plugin_header.h"
  51 #include "../item/item.h"
  52 #include "node.h"
  53 #include "../plugin.h"
  54 #include "../../znode.h"
  55 #include "../../tree.h"
  56 #include "../../super.h"
  57 #include "../../reiser4.h"
  58
  59 /**
  60  * leftmost_key_in_node - get the smallest key in node
  61  * @node:
  62  * @key: store result here
  63  *
  64  * Stores the leftmost key of @node in @key.
  65  */
  66 reiser4_key *leftmost_key_in_node(const znode *node, reiser4_key *key)
  67 {
  68         assert("nikita-1634", node != NULL);
  69         assert("nikita-1635", key != NULL);
  70
  71         if (!node_is_empty(node)) {
  72                 coord_t first_item;
  73
  74                 coord_init_first_unit(&first_item, (znode *) node);
  75                 item_key_by_coord(&first_item, key);
  76         } else
  77                 *key = *reiser4_max_key();
  78         return key;
  79 }
  80
  81 node_plugin node_plugins[LAST_NODE_ID] = {
  82         [NODE40_ID] = {
  83                 .h = {
  84                         .type_id = REISER4_NODE_PLUGIN_TYPE,
  85                         .id = NODE40_ID,
  86                         .pops = NULL,
  87                         .label = "unified",
  88                         .desc = "unified node layout",
  89                         .linkage = {NULL, NULL}
  90                 },
  91                 .item_overhead = item_overhead_node40,
  92                 .free_space = free_space_node40,
  93                 .lookup = lookup_node40,
  94                 .num_of_items = num_of_items_node40,
  95                 .item_by_coord = item_by_coord_node40,
  96                 .length_by_coord = length_by_coord_node40,
  97                 .plugin_by_coord = plugin_by_coord_node40,
  98                 .key_at = key_at_node40,
  99                 .estimate = estimate_node40,
 100                 .check = check_node40,
 101                 .parse = parse_node40,
 102                 .init = init_node40,
 103 #ifdef GUESS_EXISTS
 104                 .guess = guess_node40,
 105 #endif
 106                 .change_item_size = change_item_size_node40,
 107                 .create_item = create_item_node40,
 108                 .update_item_key = update_item_key_node40,
 109                 .cut_and_kill = kill_node40,
 110                 .cut = cut_node40,
 111                 .shift = shift_node40,
 112                 .shrink_item = shrink_item_node40,
 113                 .fast_insert = fast_insert_node40,
 114                 .fast_paste = fast_paste_node40,
 115                 .fast_cut = fast_cut_node40,
 116                 .max_item_size = max_item_size_node40,
 117                 .prepare_removal = prepare_removal_node40,
 118                 .set_item_plugin = set_item_plugin_node40
 119         }
 120 };
 121
 122 /*
 123    Local variables:
 124    c-indentation-style: "K&R"
 125    mode-name: "LC"
 126    c-basic-offset: 8
 127    tab-width: 8
 128    fill-column: 120
 129    scroll-step: 1
 130    End:
 131 */