1 /* 2 * Copyright (c) 2007 The DragonFly Project. All rights reserved. 3 * 4 * This code is derived from software contributed to The DragonFly Project 5 * by Matthew Dillon <dillon@backplane.com> 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * 3. Neither the name of The DragonFly Project nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific, prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 * 34 * $DragonFly: src/sys/vfs/hammer/hammer_cursor.h,v 1.1 2007/11/19 00:53:40 dillon Exp $ 35 */ 36 37 /* 38 * The hammer_cursor structure is the primary in-memory management structure 39 * for B-Tree operations. 40 * 41 * The most important issue to make note of is that a hammer_cursor is a 42 * tracking structure. Any active hammer_cursor structure will be linked into 43 * hammer_node based lists and B-Tree operations executed by unrelated 44 * treads MAY MODIFY YOUR CURSOR when you are not holding an exclusive 45 * lock on the cursor's nodes. 46 * 47 * Most operations maintain an exclusive lock on their node and 48 * parent node, but certain cursor operations may temporarily release 49 * one or both locks. In particular, a cursor_up operation may have 50 * to temporarily release underlying locks to avoid a deadlock. 51 */ 52 struct hammer_cursor { 53 /* 54 * Parent B-Tree node, current B-Tree node, and related element 55 * indices. 56 */ 57 hammer_node_t parent; 58 int parent_index; 59 hammer_node_t node; 60 int index; 61 62 /* 63 * Pointer to the current node's bounds. Typically points to the 64 * appropriate boundary elements in the parent or points to bounds 65 * stored in the cluster. The right-boundary is range-exclusive. 66 */ 67 hammer_base_elm_t left_bound; 68 hammer_base_elm_t right_bound; 69 70 /* 71 * Key or key range governing search 72 */ 73 struct hammer_base_elm key_beg; 74 struct hammer_base_elm key_end; 75 76 /* 77 * Related data and record references. Note that the related buffers 78 * can be NULL when data and/or record is not, typically indicating 79 * information referenced via an in-memory record. 80 */ 81 struct hammer_buffer *data_buffer; /* extracted data & record */ 82 union hammer_data_ondisk *data; 83 struct hammer_buffer *record_buffer; 84 union hammer_record_ondisk *record; 85 86 /* 87 * Iteration and extraction control variables 88 */ 89 int flags; 90 int last_error; 91 92 /* 93 * Merged in-memory/on-disk iterations also use these fields. 94 */ 95 struct hammer_inode *ip; 96 struct hammer_record *iprec; 97 }; 98 99 typedef struct hammer_cursor *hammer_cursor_t; 100 101 #define HAMMER_BTREE_GET_RECORD 0x0001 102 #define HAMMER_BTREE_GET_DATA 0x0002 103 #define HAMMER_BTREE_CLUSTER_TAG 0x0004 /* stop at the cluster tag */ 104 #define HAMMER_BTREE_INSERT 0x0008 /* adjust for insert */ 105 #define HAMMER_BTREE_DELETE 0x0010 /* adjust for delete */ 106 107