1/*
  2 * Copyright (C) 2012 Red Hat, Inc.
  3 *
  4 * This file is released under the GPL.
  5 */
  6#ifndef _LINUX_DM_ARRAY_H
  7#define _LINUX_DM_ARRAY_H
  8
  9#include "dm-btree.h"
 10
 11/*----------------------------------------------------------------*/
 12
 13/*
 14 * The dm-array is a persistent version of an array.  It packs the data
 15 * more efficiently than a btree which will result in less disk space use,
 16 * and a performance boost.  The element get and set operations are still
 17 * O(ln(n)), but with a much smaller constant.
 18 *
 19 * The value type structure is reused from the btree type to support proper
 20 * reference counting of values.
 21 *
 22 * The arrays implicitly know their length, and bounds are checked for
 23 * lookups and updated.  It doesn't store this in an accessible place
 24 * because it would waste a whole metadata block.  Make sure you store the
 25 * size along with the array root in your encompassing data.
 26 *
 27 * Array entries are indexed via an unsigned integer starting from zero.
 28 * Arrays are not sparse; if you resize an array to have 'n' entries then
 29 * 'n - 1' will be the last valid index.
 30 *
 31 * Typical use:
 32 *
 33 * a) initialise a dm_array_info structure.  This describes the array
 34 *    values and ties it into a specific transaction manager.  It holds no
 35 *    instance data; the same info can be used for many similar arrays if
 36 *    you wish.
 37 *
 38 * b) Get yourself a root.  The root is the index of a block of data on the
 39 *    disk that holds a particular instance of an array.  You may have a
 40 *    pre existing root in your metadata that you wish to use, or you may
 41 *    want to create a brand new, empty array with dm_array_empty().
 42 *
 43 * Like the other data structures in this library, dm_array objects are
 44 * immutable between transactions.  Update functions will return you the
 45 * root for a _new_ array.  If you've incremented the old root, via
 46 * dm_tm_inc(), before calling the update function you may continue to use
 47 * it in parallel with the new root.
 48 *
 49 * c) resize an array with dm_array_resize().
 50 *
 51 * d) Get a value from the array with dm_array_get_value().
 52 *
 53 * e) Set a value in the array with dm_array_set_value().
 54 *
 55 * f) Walk an array of values in index order with dm_array_walk().  More
 56 *    efficient than making many calls to dm_array_get_value().
 57 *
 58 * g) Destroy the array with dm_array_del().  This tells the transaction
 59 *    manager that you're no longer using this data structure so it can
 60 *    recycle it's blocks.  (dm_array_dec() would be a better name for it,
 61 *    but del is in keeping with dm_btree_del()).
 62 */
 63
 64/*
 65 * Describes an array.  Don't initialise this structure yourself, use the
 66 * init function below.
 67 */
 68struct dm_array_info {
 69	struct dm_transaction_manager *tm;
 70	struct dm_btree_value_type value_type;
 71	struct dm_btree_info btree_info;
 72};
 73
 74/*
 75 * Sets up a dm_array_info structure.  You don't need to do anything with
 76 * this structure when you finish using it.
 77 *
 78 * info - the structure being filled in.
 79 * tm   - the transaction manager that should supervise this structure.
 80 * vt   - describes the leaf values.
 81 */
 82void dm_array_info_init(struct dm_array_info *info,
 83			struct dm_transaction_manager *tm,
 84			struct dm_btree_value_type *vt);
 85
 86/*
 87 * Create an empty, zero length array.
 88 *
 89 * info - describes the array
 90 * root - on success this will be filled out with the root block
 91 */
 92int dm_array_empty(struct dm_array_info *info, dm_block_t *root);
 93
 94/*
 95 * Resizes the array.
 96 *
 97 * info - describes the array
 98 * root - the root block of the array on disk
 99 * old_size - the caller is responsible for remembering the size of
100 *            the array
101 * new_size - can be bigger or smaller than old_size
102 * value - if we're growing the array the new entries will have this value
103 * new_root - on success, points to the new root block
104 *
105 * If growing the inc function for 'value' will be called the appropriate
106 * number of times.  So if the caller is holding a reference they may want
107 * to drop it.
108 */
109int dm_array_resize(struct dm_array_info *info, dm_block_t root,
110		    uint32_t old_size, uint32_t new_size,
111		    const void *value, dm_block_t *new_root)
112	__dm_written_to_disk(value);
113
114/*
115 * Frees a whole array.  The value_type's decrement operation will be called
116 * for all values in the array
117 */
118int dm_array_del(struct dm_array_info *info, dm_block_t root);
119
120/*
121 * Lookup a value in the array
122 *
123 * info - describes the array
124 * root - root block of the array
125 * index - array index
126 * value - the value to be read.  Will be in on-disk format of course.
127 *
128 * -ENODATA will be returned if the index is out of bounds.
129 */
130int dm_array_get_value(struct dm_array_info *info, dm_block_t root,
131		       uint32_t index, void *value);
132
133/*
134 * Set an entry in the array.
135 *
136 * info - describes the array
137 * root - root block of the array
138 * index - array index
139 * value - value to be written to disk.  Make sure you confirm the value is
140 *         in on-disk format with__dm_bless_for_disk() before calling.
141 * new_root - the new root block
142 *
143 * The old value being overwritten will be decremented, the new value
144 * incremented.
145 *
146 * -ENODATA will be returned if the index is out of bounds.
147 */
148int dm_array_set_value(struct dm_array_info *info, dm_block_t root,
149		       uint32_t index, const void *value, dm_block_t *new_root)
150	__dm_written_to_disk(value);
151
152/*
153 * Walk through all the entries in an array.
154 *
155 * info - describes the array
156 * root - root block of the array
157 * fn - called back for every element
158 * context - passed to the callback
159 */
160int dm_array_walk(struct dm_array_info *info, dm_block_t root,
161		  int (*fn)(void *context, uint64_t key, void *leaf),
162		  void *context);
163
164/*----------------------------------------------------------------*/
165
166#endif	/* _LINUX_DM_ARRAY_H */