[linux-2.6-block.git] / drivers / md / persistent-data / dm-array.h

/*
 * Copyright (C) 2012 Red Hat, Inc.
 *
 * This file is released under the GPL.
 */
#ifndef _LINUX_DM_ARRAY_H
#define _LINUX_DM_ARRAY_H

#include "dm-btree.h"

/*----------------------------------------------------------------*/

/*
 * The dm-array is a persistent version of an array.  It packs the data
 * more efficiently than a btree which will result in less disk space use,
 * and a performance boost.  The element get and set operations are still
 * O(ln(n)), but with a much smaller constant.
 *
 * The value type structure is reused from the btree type to support proper
 * reference counting of values.
 *
 * The arrays implicitly know their length, and bounds are checked for
 * lookups and updated.  It doesn't store this in an accessible place
 * because it would waste a whole metadata block.  Make sure you store the
 * size along with the array root in your encompassing data.
 *
 * Array entries are indexed via an unsigned integer starting from zero.
 * Arrays are not sparse; if you resize an array to have 'n' entries then
 * 'n - 1' will be the last valid index.
 *
 * Typical use:
 *
 * a) initialise a dm_array_info structure.  This describes the array
 *    values and ties it into a specific transaction manager.  It holds no
 *    instance data; the same info can be used for many similar arrays if
 *    you wish.
 *
 * b) Get yourself a root.  The root is the index of a block of data on the
 *    disk that holds a particular instance of an array.  You may have a
 *    pre existing root in your metadata that you wish to use, or you may
 *    want to create a brand new, empty array with dm_array_empty().
 *
 * Like the other data structures in this library, dm_array objects are
 * immutable between transactions.  Update functions will return you the
 * root for a _new_ array.  If you've incremented the old root, via
 * dm_tm_inc(), before calling the update function you may continue to use
 * it in parallel with the new root.
 *
 * c) resize an array with dm_array_resize().
 *
 * d) Get a value from the array with dm_array_get_value().
 *
 * e) Set a value in the array with dm_array_set_value().
 *
 * f) Walk an array of values in index order with dm_array_walk().  More
 *    efficient than making many calls to dm_array_get_value().
 *
 * g) Destroy the array with dm_array_del().  This tells the transaction
 *    manager that you're no longer using this data structure so it can
 *    recycle it's blocks.  (dm_array_dec() would be a better name for it,
 *    but del is in keeping with dm_btree_del()).
 */

/*
 * Describes an array.  Don't initialise this structure yourself, use the
 * init function below.
 */
struct dm_array_info {
	struct dm_transaction_manager *tm;
	struct dm_btree_value_type value_type;
	struct dm_btree_info btree_info;
};

/*
 * Sets up a dm_array_info structure.  You don't need to do anything with
 * this structure when you finish using it.
 *
 * info - the structure being filled in.
 * tm   - the transaction manager that should supervise this structure.
 * vt   - describes the leaf values.
 */
void dm_array_info_init(struct dm_array_info *info,
			struct dm_transaction_manager *tm,
			struct dm_btree_value_type *vt);

/*
 * Create an empty, zero length array.
 *
 * info - describes the array
 * root - on success this will be filled out with the root block
 */
int dm_array_empty(struct dm_array_info *info, dm_block_t *root);

/*
 * Resizes the array.
 *
 * info - describes the array
 * root - the root block of the array on disk
 * old_size - the caller is responsible for remembering the size of
 *            the array
 * new_size - can be bigger or smaller than old_size
 * value - if we're growing the array the new entries will have this value
 * new_root - on success, points to the new root block
 *
 * If growing the inc function for 'value' will be called the appropriate
 * number of times.  So if the caller is holding a reference they may want
 * to drop it.
 */
int dm_array_resize(struct dm_array_info *info, dm_block_t root,
		    uint32_t old_size, uint32_t new_size,
		    const void *value, dm_block_t *new_root)
	__dm_written_to_disk(value);

/*
 * Frees a whole array.  The value_type's decrement operation will be called
 * for all values in the array
 */
int dm_array_del(struct dm_array_info *info, dm_block_t root);

/*
 * Lookup a value in the array
 *
 * info - describes the array
 * root - root block of the array
 * index - array index
 * value - the value to be read.  Will be in on-disk format of course.
 *
 * -ENODATA will be returned if the index is out of bounds.
 */
int dm_array_get_value(struct dm_array_info *info, dm_block_t root,
		       uint32_t index, void *value);

/*
 * Set an entry in the array.
 *
 * info - describes the array
 * root - root block of the array
 * index - array index
 * value - value to be written to disk.  Make sure you confirm the value is
 *         in on-disk format with__dm_bless_for_disk() before calling.
 * new_root - the new root block
 *
 * The old value being overwritten will be decremented, the new value
 * incremented.
 *
 * -ENODATA will be returned if the index is out of bounds.
 */
int dm_array_set_value(struct dm_array_info *info, dm_block_t root,
		       uint32_t index, const void *value, dm_block_t *new_root)
	__dm_written_to_disk(value);

/*
 * Walk through all the entries in an array.
 *
 * info - describes the array
 * root - root block of the array
 * fn - called back for every element
 * context - passed to the callback
 */
int dm_array_walk(struct dm_array_info *info, dm_block_t root,
		  int (*fn)(void *context, uint64_t key, void *leaf),
		  void *context);

/*----------------------------------------------------------------*/

#endif	/* _LINUX_DM_ARRAY_H */
Commit	Line	Data
6513c29f JT	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	*/
68	struct 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	*/
82	void 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	*/
92	int 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	*/
109	int 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	*/
118	int 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	*/
130	int 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	*/
148	int 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	*/
160	int 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 */