fs/reiser4/coord.h

   1 /* Copyright 2001, 2002, 2003 by Hans Reiser, licensing governed by reiser4/README */
   2
   3 /* Coords */
   4
   5 #if !defined( __REISER4_COORD_H__ )
   6 #define __REISER4_COORD_H__
   7
   8 #include "forward.h"
   9 #include "debug.h"
  10 #include "dformat.h"
  11 #include "key.h"
  12
  13 /* insertions happen between coords in the tree, so we need some means
  14    of specifying the sense of betweenness. */
  15 typedef enum {
  16         BEFORE_UNIT,            /* Note: we/init_coord depends on this value being zero. */
  17         AT_UNIT,
  18         AFTER_UNIT,
  19         BEFORE_ITEM,
  20         AFTER_ITEM,
  21         INVALID_COORD,
  22         EMPTY_NODE,
  23 } between_enum;
  24
  25 /* location of coord w.r.t. its node */
  26 typedef enum {
  27         COORD_ON_THE_LEFT = -1,
  28         COORD_ON_THE_RIGHT = +1,
  29         COORD_INSIDE = 0
  30 } coord_wrt_node;
  31
  32 typedef enum {
  33         COORD_CMP_SAME = 0, COORD_CMP_ON_LEFT = -1, COORD_CMP_ON_RIGHT = +1
  34 } coord_cmp;
  35
  36 struct coord {
  37         /* node in a tree */
  38         /*  0 */ znode *node;
  39
  40         /* position of item within node */
  41         /*  4 */ pos_in_node_t item_pos;
  42         /* position of unit within item */
  43         /*  6 */ pos_in_node_t unit_pos;
  44         /* optimization: plugin of item is stored in coord_t. Until this was
  45            implemented, item_plugin_by_coord() was major CPU consumer. ->iplugid
  46            is invalidated (set to 0xff) on each modification of ->item_pos,
  47            and all such modifications are funneled through coord_*_item_pos()
  48            functions below.
  49          */
  50         /*  8 */ char iplugid;
  51         /* position of coord w.r.t. to neighboring items and/or units.
  52            Values are taken from &between_enum above.
  53          */
  54         /*  9 */ char between;
  55         /* padding. It will be added by the compiler anyway to conform to the
  56          * C language alignment requirements. We keep it here to be on the
  57          * safe side and to have a clear picture of the memory layout of this
  58          * structure. */
  59         /* 10 */ __u16 pad;
  60         /* 12 */ int offset;
  61 #if REISER4_DEBUG
  62         unsigned long plug_v;
  63         unsigned long body_v;
  64 #endif
  65 };
  66
  67 #define INVALID_PLUGID  ((char)((1 << 8) - 1))
  68 #define INVALID_OFFSET -1
  69
  70 static inline void coord_clear_iplug(coord_t * coord)
  71 {
  72         assert("nikita-2835", coord != NULL);
  73         coord->iplugid = INVALID_PLUGID;
  74         coord->offset = INVALID_OFFSET;
  75 }
  76
  77 static inline int coord_is_iplug_set(const coord_t * coord)
  78 {
  79         assert("nikita-2836", coord != NULL);
  80         return coord->iplugid != INVALID_PLUGID;
  81 }
  82
  83 static inline void coord_set_item_pos(coord_t * coord, pos_in_node_t pos)
  84 {
  85         assert("nikita-2478", coord != NULL);
  86         coord->item_pos = pos;
  87         coord_clear_iplug(coord);
  88 }
  89
  90 static inline void coord_dec_item_pos(coord_t * coord)
  91 {
  92         assert("nikita-2480", coord != NULL);
  93         --coord->item_pos;
  94         coord_clear_iplug(coord);
  95 }
  96
  97 static inline void coord_inc_item_pos(coord_t * coord)
  98 {
  99         assert("nikita-2481", coord != NULL);
 100         ++coord->item_pos;
 101         coord_clear_iplug(coord);
 102 }
 103
 104 static inline void coord_add_item_pos(coord_t * coord, int delta)
 105 {
 106         assert("nikita-2482", coord != NULL);
 107         coord->item_pos += delta;
 108         coord_clear_iplug(coord);
 109 }
 110
 111 static inline void coord_invalid_item_pos(coord_t * coord)
 112 {
 113         assert("nikita-2832", coord != NULL);
 114         coord->item_pos = (unsigned short)~0;
 115         coord_clear_iplug(coord);
 116 }
 117
 118 /* Reverse a direction. */
 119 static inline sideof sideof_reverse(sideof side)
 120 {
 121         return side == LEFT_SIDE ? RIGHT_SIDE : LEFT_SIDE;
 122 }
 123
 124 /* NOTE: There is a somewhat odd mixture of the following opposed terms:
 125
 126    "first" and "last"
 127    "next" and "prev"
 128    "before" and "after"
 129    "leftmost" and "rightmost"
 130
 131    But I think the chosen names are decent the way they are.
 132 */
 133
 134 /* COORD INITIALIZERS */
 135
 136 /* Initialize an invalid coordinate. */
 137 extern void coord_init_invalid(coord_t * coord, const znode * node);
 138
 139 extern void coord_init_first_unit_nocheck(coord_t * coord, const znode * node);
 140
 141 /* Initialize a coordinate to point at the first unit of the first item.  If the node is
 142    empty, it is positioned at the EMPTY_NODE. */
 143 extern void coord_init_first_unit(coord_t * coord, const znode * node);
 144
 145 /* Initialize a coordinate to point at the last unit of the last item.  If the node is
 146    empty, it is positioned at the EMPTY_NODE. */
 147 extern void coord_init_last_unit(coord_t * coord, const znode * node);
 148
 149 /* Initialize a coordinate to before the first item.  If the node is empty, it is
 150    positioned at the EMPTY_NODE. */
 151 extern void coord_init_before_first_item(coord_t * coord, const znode * node);
 152
 153 /* Initialize a coordinate to after the last item.  If the node is empty, it is positioned
 154    at the EMPTY_NODE. */
 155 extern void coord_init_after_last_item(coord_t * coord, const znode * node);
 156
 157 /* Initialize a coordinate to after last unit in the item. Coord must be set
 158    already to existing item */
 159 void coord_init_after_item_end(coord_t * coord);
 160
 161 /* Initialize a coordinate to before the item. Coord must be set already to existing item */
 162 void coord_init_before_item(coord_t *);
 163 /* Initialize a coordinate to after the item. Coord must be set already to existing item */
 164 void coord_init_after_item(coord_t *);
 165
 166 /* Calls either coord_init_first_unit or coord_init_last_unit depending on sideof argument. */
 167 extern void coord_init_sideof_unit(coord_t * coord, const znode * node,
 168                                    sideof dir);
 169
 170 /* Initialize a coordinate by 0s. Used in places where init_coord was used and
 171    it was not clear how actually
 172    FIXME-VS: added by vs (2002, june, 8) */
 173 extern void coord_init_zero(coord_t * coord);
 174
 175 /* COORD METHODS */
 176
 177 /* after shifting of node content, coord previously set properly may become
 178    invalid, try to "normalize" it. */
 179 void coord_normalize(coord_t * coord);
 180
 181 /* Copy a coordinate. */
 182 extern void coord_dup(coord_t * coord, const coord_t * old_coord);
 183
 184 /* Copy a coordinate without check. */
 185 void coord_dup_nocheck(coord_t * coord, const coord_t * old_coord);
 186
 187 unsigned coord_num_units(const coord_t * coord);
 188
 189 /* Return the last valid unit number at the present item (i.e.,
 190    coord_num_units() - 1). */
 191 static inline unsigned coord_last_unit_pos(const coord_t * coord)
 192 {
 193         return coord_num_units(coord) - 1;
 194 }
 195
 196 #if REISER4_DEBUG
 197 /* For assertions only, checks for a valid coordinate. */
 198 extern int coord_check(const coord_t * coord);
 199
 200 extern unsigned long znode_times_locked(const znode * z);
 201
 202 static inline void coord_update_v(coord_t * coord)
 203 {
 204         coord->plug_v = coord->body_v = znode_times_locked(coord->node);
 205 }
 206 #endif
 207
 208 extern int coords_equal(const coord_t * c1, const coord_t * c2);
 209
 210 extern void print_coord(const char *mes, const coord_t * coord, int print_node);
 211
 212 /* If coord_is_after_rightmost return NCOORD_ON_THE_RIGHT, if coord_is_after_leftmost
 213    return NCOORD_ON_THE_LEFT, otherwise return NCOORD_INSIDE. */
 214 extern coord_wrt_node coord_wrt(const coord_t * coord);
 215
 216 /* Returns true if the coordinates are positioned at adjacent units, regardless of
 217    before-after or item boundaries. */
 218 extern int coord_are_neighbors(coord_t * c1, coord_t * c2);
 219
 220 /* Assuming two coordinates are positioned in the same node, return NCOORD_CMP_ON_RIGHT,
 221    NCOORD_CMP_ON_LEFT, or NCOORD_CMP_SAME depending on c1's position relative to c2.  */
 222 extern coord_cmp coord_compare(coord_t * c1, coord_t * c2);
 223
 224 /* COORD PREDICATES */
 225
 226 /* Returns true if the coord was initializewd by coord_init_invalid (). */
 227 extern int coord_is_invalid(const coord_t * coord);
 228
 229 /* Returns true if the coordinate is positioned at an existing item, not before or after
 230    an item.  It may be placed at, before, or after any unit within the item, whether
 231    existing or not.  If this is true you can call methods of the item plugin.  */
 232 extern int coord_is_existing_item(const coord_t * coord);
 233
 234 /* Returns true if the coordinate is positioned after a item, before a item, after the
 235    last unit of an item, before the first unit of an item, or at an empty node. */
 236 extern int coord_is_between_items(const coord_t * coord);
 237
 238 /* Returns true if the coordinate is positioned at an existing unit, not before or after a
 239    unit. */
 240 extern int coord_is_existing_unit(const coord_t * coord);
 241
 242 /* Returns true if the coordinate is positioned at an empty node. */
 243 extern int coord_is_empty(const coord_t * coord);
 244
 245 /* Returns true if the coordinate is positioned at the first unit of the first item.  Not
 246    true for empty nodes nor coordinates positioned before the first item. */
 247 extern int coord_is_leftmost_unit(const coord_t * coord);
 248
 249 /* Returns true if the coordinate is positioned after the last item or after the last unit
 250    of the last item or it is an empty node. */
 251 extern int coord_is_after_rightmost(const coord_t * coord);
 252
 253 /* Returns true if the coordinate is positioned before the first item or it is an empty
 254    node. */
 255 extern int coord_is_before_leftmost(const coord_t * coord);
 256
 257 /* Calls either coord_is_before_leftmost or coord_is_after_rightmost depending on sideof
 258    argument. */
 259 extern int coord_is_after_sideof_unit(coord_t * coord, sideof dir);
 260
 261 /* COORD MODIFIERS */
 262
 263 /* Advances the coordinate by one unit to the right.  If empty, no change.  If
 264    coord_is_rightmost_unit, advances to AFTER THE LAST ITEM.  Returns 0 if new position is
 265    an existing unit. */
 266 extern int coord_next_unit(coord_t * coord);
 267
 268 /* Advances the coordinate by one item to the right.  If empty, no change.  If
 269    coord_is_rightmost_unit, advances to AFTER THE LAST ITEM.  Returns 0 if new position is
 270    an existing item. */
 271 extern int coord_next_item(coord_t * coord);
 272
 273 /* Advances the coordinate by one unit to the left.  If empty, no change.  If
 274    coord_is_leftmost_unit, advances to BEFORE THE FIRST ITEM.  Returns 0 if new position
 275    is an existing unit. */
 276 extern int coord_prev_unit(coord_t * coord);
 277
 278 /* Advances the coordinate by one item to the left.  If empty, no change.  If
 279    coord_is_leftmost_unit, advances to BEFORE THE FIRST ITEM.  Returns 0 if new position
 280    is an existing item. */
 281 extern int coord_prev_item(coord_t * coord);
 282
 283 /* If the coordinate is between items, shifts it to the right.  Returns 0 on success and
 284    non-zero if there is no position to the right. */
 285 extern int coord_set_to_right(coord_t * coord);
 286
 287 /* If the coordinate is between items, shifts it to the left.  Returns 0 on success and
 288    non-zero if there is no position to the left. */
 289 extern int coord_set_to_left(coord_t * coord);
 290
 291 /* If the coordinate is at an existing unit, set to after that unit.  Returns 0 on success
 292    and non-zero if the unit did not exist. */
 293 extern int coord_set_after_unit(coord_t * coord);
 294
 295 /* Calls either coord_next_unit or coord_prev_unit depending on sideof argument. */
 296 extern int coord_sideof_unit(coord_t * coord, sideof dir);
 297
 298 /* iterate over all units in @node */
 299 #define for_all_units( coord, node )                                    \
 300         for( coord_init_before_first_item( ( coord ), ( node ) ) ;      \
 301              coord_next_unit( coord ) == 0 ; )
 302
 303 /* iterate over all items in @node */
 304 #define for_all_items( coord, node )                                    \
 305         for( coord_init_before_first_item( ( coord ), ( node ) ) ;      \
 306              coord_next_item( coord ) == 0 ; )
 307
 308 /* COORD/ITEM METHODS */
 309
 310 extern int item_utmost_child_real_block(const coord_t * coord, sideof side,
 311                                         reiser4_block_nr * blk);
 312 extern int item_utmost_child(const coord_t * coord, sideof side,
 313                              jnode ** child);
 314
 315 /* a flow is a sequence of bytes being written to or read from the tree.  The
 316    tree will slice the flow into items while storing it into nodes, but all of
 317    that is hidden from anything outside the tree.  */
 318
 319 struct flow {
 320         reiser4_key key;        /* key of start of flow's sequence of bytes */
 321         loff_t length;          /* length of flow's sequence of bytes */
 322         char *data;             /* start of flow's sequence of bytes */
 323         int user;               /* if 1 data is user space, 0 - kernel space */
 324         rw_op op;               /* NIKITA-FIXME-HANS: comment is where?  */
 325 };
 326
 327 void move_flow_forward(flow_t * f, unsigned count);
 328
 329 /* &reiser4_item_data - description of data to be inserted or pasted
 330
 331    Q: articulate the reasons for the difference between this and flow.
 332
 333    A: Becides flow we insert into tree other things: stat data, directory
 334    entry, etc.  To insert them into tree one has to provide this structure. If
 335    one is going to insert flow - he can use insert_flow, where this structure
 336    does not have to be created
 337 */
 338 struct reiser4_item_data {
 339         /* actual data to be inserted. If NULL, ->create_item() will not
 340            do xmemcpy itself, leaving this up to the caller. This can
 341            save some amount of unnecessary memory copying, for example,
 342            during insertion of stat data.
 343
 344          */
 345         char *data;
 346         /* 1 if 'char * data' contains pointer to user space and 0 if it is
 347            kernel space */
 348         int user;
 349         /* amount of data we are going to insert or paste */
 350         int length;
 351         /* "Arg" is opaque data that is passed down to the
 352            ->create_item() method of node layout, which in turn
 353            hands it to the ->create_hook() of item being created. This
 354            arg is currently used by:
 355
 356            .  ->create_hook() of internal item
 357            (fs/reiser4/plugin/item/internal.c:internal_create_hook()),
 358            . ->paste() method of directory item.
 359            . ->create_hook() of extent item
 360
 361            For internal item, this is left "brother" of new node being
 362            inserted and it is used to add new node into sibling list
 363            after parent to it was just inserted into parent.
 364
 365            While ->arg does look somewhat of unnecessary compication,
 366            it actually saves a lot of headache in many places, because
 367            all data necessary to insert or paste new data into tree are
 368            collected in one place, and this eliminates a lot of extra
 369            argument passing and storing everywhere.
 370
 371          */
 372         void *arg;
 373         /* plugin of item we are inserting */
 374         item_plugin *iplug;
 375 };
 376
 377 /* __REISER4_COORD_H__ */
 378 #endif
 379
 380 /* Make Linus happy.
 381    Local variables:
 382    c-indentation-style: "K&R"
 383    mode-name: "LC"
 384    c-basic-offset: 8
 385    tab-width: 8
 386    fill-column: 120
 387    scroll-step: 1
 388    End:
 389 */