fs/reiser4/coord.h

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