diff options
| -rw-r--r-- | base/Makefile | 1 | ||||
| -rw-r--r-- | base/data-struct/list.c (renamed from device_mapper/datastruct/list.c) | 4 | ||||
| -rw-r--r-- | base/data-struct/list.h | 209 | ||||
| -rw-r--r-- | device_mapper/Makefile | 1 | ||||
| -rw-r--r-- | device_mapper/libdevmapper.h | 209 |
5 files changed, 217 insertions, 207 deletions
diff --git a/base/Makefile b/base/Makefile index 27f539f64..4dcb6b6e6 100644 --- a/base/Makefile +++ b/base/Makefile @@ -12,6 +12,7 @@ BASE_SOURCE=\ base/data-struct/radix-tree.c \ + base/data-struct/list.c BASE_DEPENDS=$(addprefix $(top_builddir)/,$(subst .c,.d,$(BASE_SOURCE))) BASE_OBJECTS=$(addprefix $(top_builddir)/,$(subst .c,.o,$(BASE_SOURCE))) diff --git a/device_mapper/datastruct/list.c b/base/data-struct/list.c index bda802770..894e273b4 100644 --- a/device_mapper/datastruct/list.c +++ b/base/data-struct/list.c @@ -13,8 +13,10 @@ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ -#include "device_mapper/misc/dmlib.h" +#include "list.h" + #include <assert.h> +#include <stdlib.h> /* * Initialise a list before use. diff --git a/base/data-struct/list.h b/base/data-struct/list.h new file mode 100644 index 000000000..1a107d180 --- /dev/null +++ b/base/data-struct/list.h @@ -0,0 +1,209 @@ +#ifndef BASE_DATA_STRUCT_LIST_H +#define BASE_DATA_STRUCT_LIST_H + +//---------------------------------------------------------------- + +/* + * A list consists of a list head plus elements. + * Each element has 'next' and 'previous' pointers. + * The list head's pointers point to the first and the last element. + */ + +struct dm_list { + struct dm_list *n, *p; +}; + +/* + * String list. + */ +struct dm_str_list { + struct dm_list list; + const char *str; +}; + +/* + * Initialise a list before use. + * The list head's next and previous pointers point back to itself. + */ +#define DM_LIST_HEAD_INIT(name) { &(name), &(name) } +#define DM_LIST_INIT(name) struct dm_list name = DM_LIST_HEAD_INIT(name) +void dm_list_init(struct dm_list *head); + +/* + * Insert an element before 'head'. + * If 'head' is the list head, this adds an element to the end of the list. + */ +void dm_list_add(struct dm_list *head, struct dm_list *elem); + +/* + * Insert an element after 'head'. + * If 'head' is the list head, this adds an element to the front of the list. + */ +void dm_list_add_h(struct dm_list *head, struct dm_list *elem); + +/* + * Delete an element from its list. + * Note that this doesn't change the element itself - it may still be safe + * to follow its pointers. + */ +void dm_list_del(struct dm_list *elem); + +/* + * Remove an element from existing list and insert before 'head'. + */ +void dm_list_move(struct dm_list *head, struct dm_list *elem); + +/* + * Join 'head1' to the end of 'head'. + */ +void dm_list_splice(struct dm_list *head, struct dm_list *head1); + +/* + * Is the list empty? + */ +int dm_list_empty(const struct dm_list *head); + +/* + * Is this the first element of the list? + */ +int dm_list_start(const struct dm_list *head, const struct dm_list *elem); + +/* + * Is this the last element of the list? + */ +int dm_list_end(const struct dm_list *head, const struct dm_list *elem); + +/* + * Return first element of the list or NULL if empty + */ +struct dm_list *dm_list_first(const struct dm_list *head); + +/* + * Return last element of the list or NULL if empty + */ +struct dm_list *dm_list_last(const struct dm_list *head); + +/* + * Return the previous element of the list, or NULL if we've reached the start. + */ +struct dm_list *dm_list_prev(const struct dm_list *head, const struct dm_list *elem); + +/* + * Return the next element of the list, or NULL if we've reached the end. + */ +struct dm_list *dm_list_next(const struct dm_list *head, const struct dm_list *elem); + +/* + * Given the address v of an instance of 'struct dm_list' called 'head' + * contained in a structure of type t, return the containing structure. + */ +#define dm_list_struct_base(v, t, head) \ + ((t *)((const char *)(v) - (const char *)&((t *) 0)->head)) + +/* + * Given the address v of an instance of 'struct dm_list list' contained in + * a structure of type t, return the containing structure. + */ +#define dm_list_item(v, t) dm_list_struct_base((v), t, list) + +/* + * Given the address v of one known element e in a known structure of type t, + * return another element f. + */ +#define dm_struct_field(v, t, e, f) \ + (((t *)((uintptr_t)(v) - (uintptr_t)&((t *) 0)->e))->f) + +/* + * Given the address v of a known element e in a known structure of type t, + * return the list head 'list' + */ +#define dm_list_head(v, t, e) dm_struct_field(v, t, e, list) + +/* + * Set v to each element of a list in turn. + */ +#define dm_list_iterate(v, head) \ + for (v = (head)->n; v != head; v = v->n) + +/* + * Set v to each element in a list in turn, starting from the element + * in front of 'start'. + * You can use this to 'unwind' a list_iterate and back out actions on + * already-processed elements. + * If 'start' is 'head' it walks the list backwards. + */ +#define dm_list_uniterate(v, head, start) \ + for (v = (start)->p; v != head; v = v->p) + +/* + * A safe way to walk a list and delete and free some elements along + * the way. + * t must be defined as a temporary variable of the same type as v. + */ +#define dm_list_iterate_safe(v, t, head) \ + for (v = (head)->n, t = v->n; v != head; v = t, t = v->n) + +/* + * Walk a list, setting 'v' in turn to the containing structure of each item. + * The containing structure should be the same type as 'v'. + * The 'struct dm_list' variable within the containing structure is 'field'. + */ +#define dm_list_iterate_items_gen(v, head, field) \ + for (v = dm_list_struct_base((head)->n, __typeof__(*v), field); \ + &v->field != (head); \ + v = dm_list_struct_base(v->field.n, __typeof__(*v), field)) + +/* + * Walk a list, setting 'v' in turn to the containing structure of each item. + * The containing structure should be the same type as 'v'. + * The list should be 'struct dm_list list' within the containing structure. + */ +#define dm_list_iterate_items(v, head) dm_list_iterate_items_gen(v, (head), list) + +/* + * Walk a list, setting 'v' in turn to the containing structure of each item. + * The containing structure should be the same type as 'v'. + * The 'struct dm_list' variable within the containing structure is 'field'. + * t must be defined as a temporary variable of the same type as v. + */ +#define dm_list_iterate_items_gen_safe(v, t, head, field) \ + for (v = dm_list_struct_base((head)->n, __typeof__(*v), field), \ + t = dm_list_struct_base(v->field.n, __typeof__(*v), field); \ + &v->field != (head); \ + v = t, t = dm_list_struct_base(v->field.n, __typeof__(*v), field)) +/* + * Walk a list, setting 'v' in turn to the containing structure of each item. + * The containing structure should be the same type as 'v'. + * The list should be 'struct dm_list list' within the containing structure. + * t must be defined as a temporary variable of the same type as v. + */ +#define dm_list_iterate_items_safe(v, t, head) \ + dm_list_iterate_items_gen_safe(v, t, (head), list) + +/* + * Walk a list backwards, setting 'v' in turn to the containing structure + * of each item. + * The containing structure should be the same type as 'v'. + * The 'struct dm_list' variable within the containing structure is 'field'. + */ +#define dm_list_iterate_back_items_gen(v, head, field) \ + for (v = dm_list_struct_base((head)->p, __typeof__(*v), field); \ + &v->field != (head); \ + v = dm_list_struct_base(v->field.p, __typeof__(*v), field)) + +/* + * Walk a list backwards, setting 'v' in turn to the containing structure + * of each item. + * The containing structure should be the same type as 'v'. + * The list should be 'struct dm_list list' within the containing structure. + */ +#define dm_list_iterate_back_items(v, head) dm_list_iterate_back_items_gen(v, (head), list) + +/* + * Return the number of elements in a list by walking it. + */ +unsigned int dm_list_size(const struct dm_list *head); + +//---------------------------------------------------------------- + +#endif diff --git a/device_mapper/Makefile b/device_mapper/Makefile index b246f828d..4036cb480 100644 --- a/device_mapper/Makefile +++ b/device_mapper/Makefile @@ -13,7 +13,6 @@ DEVICE_MAPPER_SOURCE=\ device_mapper/datastruct/bitset.c \ device_mapper/datastruct/hash.c \ - device_mapper/datastruct/list.c \ device_mapper/libdm-common.c \ device_mapper/libdm-config.c \ device_mapper/libdm-deptree.c \ diff --git a/device_mapper/libdevmapper.h b/device_mapper/libdevmapper.h index 2438f74c1..f7ff4cec7 100644 --- a/device_mapper/libdevmapper.h +++ b/device_mapper/libdevmapper.h @@ -31,6 +31,10 @@ #include <stdlib.h> #include <stdio.h> +#include "base/data-struct/list.h" + +#include "base/data-struct/list.h" + #ifndef __GNUC__ # define __typeof__ typeof #endif @@ -2366,211 +2370,6 @@ void *dm_hash_lookup_with_count(struct dm_hash_table *t, const char *key, int *c for (v = dm_hash_get_first((h)); v; \ v = dm_hash_get_next((h), v)) -/**************** - * list functions - ****************/ - -/* - * A list consists of a list head plus elements. - * Each element has 'next' and 'previous' pointers. - * The list head's pointers point to the first and the last element. - */ - -struct dm_list { - struct dm_list *n, *p; -}; - -/* - * String list. - */ -struct dm_str_list { - struct dm_list list; - const char *str; -}; - -/* - * Initialise a list before use. - * The list head's next and previous pointers point back to itself. - */ -#define DM_LIST_HEAD_INIT(name) { &(name), &(name) } -#define DM_LIST_INIT(name) struct dm_list name = DM_LIST_HEAD_INIT(name) -void dm_list_init(struct dm_list *head); - -/* - * Insert an element before 'head'. - * If 'head' is the list head, this adds an element to the end of the list. - */ -void dm_list_add(struct dm_list *head, struct dm_list *elem); - -/* - * Insert an element after 'head'. - * If 'head' is the list head, this adds an element to the front of the list. - */ -void dm_list_add_h(struct dm_list *head, struct dm_list *elem); - -/* - * Delete an element from its list. - * Note that this doesn't change the element itself - it may still be safe - * to follow its pointers. - */ -void dm_list_del(struct dm_list *elem); - -/* - * Remove an element from existing list and insert before 'head'. - */ -void dm_list_move(struct dm_list *head, struct dm_list *elem); - -/* - * Join 'head1' to the end of 'head'. - */ -void dm_list_splice(struct dm_list *head, struct dm_list *head1); - -/* - * Is the list empty? - */ -int dm_list_empty(const struct dm_list *head); - -/* - * Is this the first element of the list? - */ -int dm_list_start(const struct dm_list *head, const struct dm_list *elem); - -/* - * Is this the last element of the list? - */ -int dm_list_end(const struct dm_list *head, const struct dm_list *elem); - -/* - * Return first element of the list or NULL if empty - */ -struct dm_list *dm_list_first(const struct dm_list *head); - -/* - * Return last element of the list or NULL if empty - */ -struct dm_list *dm_list_last(const struct dm_list *head); - -/* - * Return the previous element of the list, or NULL if we've reached the start. - */ -struct dm_list *dm_list_prev(const struct dm_list *head, const struct dm_list *elem); - -/* - * Return the next element of the list, or NULL if we've reached the end. - */ -struct dm_list *dm_list_next(const struct dm_list *head, const struct dm_list *elem); - -/* - * Given the address v of an instance of 'struct dm_list' called 'head' - * contained in a structure of type t, return the containing structure. - */ -#define dm_list_struct_base(v, t, head) \ - ((t *)((const char *)(v) - (const char *)&((t *) 0)->head)) - -/* - * Given the address v of an instance of 'struct dm_list list' contained in - * a structure of type t, return the containing structure. - */ -#define dm_list_item(v, t) dm_list_struct_base((v), t, list) - -/* - * Given the address v of one known element e in a known structure of type t, - * return another element f. - */ -#define dm_struct_field(v, t, e, f) \ - (((t *)((uintptr_t)(v) - (uintptr_t)&((t *) 0)->e))->f) - -/* - * Given the address v of a known element e in a known structure of type t, - * return the list head 'list' - */ -#define dm_list_head(v, t, e) dm_struct_field(v, t, e, list) - -/* - * Set v to each element of a list in turn. - */ -#define dm_list_iterate(v, head) \ - for (v = (head)->n; v != head; v = v->n) - -/* - * Set v to each element in a list in turn, starting from the element - * in front of 'start'. - * You can use this to 'unwind' a list_iterate and back out actions on - * already-processed elements. - * If 'start' is 'head' it walks the list backwards. - */ -#define dm_list_uniterate(v, head, start) \ - for (v = (start)->p; v != head; v = v->p) - -/* - * A safe way to walk a list and delete and free some elements along - * the way. - * t must be defined as a temporary variable of the same type as v. - */ -#define dm_list_iterate_safe(v, t, head) \ - for (v = (head)->n, t = v->n; v != head; v = t, t = v->n) - -/* - * Walk a list, setting 'v' in turn to the containing structure of each item. - * The containing structure should be the same type as 'v'. - * The 'struct dm_list' variable within the containing structure is 'field'. - */ -#define dm_list_iterate_items_gen(v, head, field) \ - for (v = dm_list_struct_base((head)->n, __typeof__(*v), field); \ - &v->field != (head); \ - v = dm_list_struct_base(v->field.n, __typeof__(*v), field)) - -/* - * Walk a list, setting 'v' in turn to the containing structure of each item. - * The containing structure should be the same type as 'v'. - * The list should be 'struct dm_list list' within the containing structure. - */ -#define dm_list_iterate_items(v, head) dm_list_iterate_items_gen(v, (head), list) - -/* - * Walk a list, setting 'v' in turn to the containing structure of each item. - * The containing structure should be the same type as 'v'. - * The 'struct dm_list' variable within the containing structure is 'field'. - * t must be defined as a temporary variable of the same type as v. - */ -#define dm_list_iterate_items_gen_safe(v, t, head, field) \ - for (v = dm_list_struct_base((head)->n, __typeof__(*v), field), \ - t = dm_list_struct_base(v->field.n, __typeof__(*v), field); \ - &v->field != (head); \ - v = t, t = dm_list_struct_base(v->field.n, __typeof__(*v), field)) -/* - * Walk a list, setting 'v' in turn to the containing structure of each item. - * The containing structure should be the same type as 'v'. - * The list should be 'struct dm_list list' within the containing structure. - * t must be defined as a temporary variable of the same type as v. - */ -#define dm_list_iterate_items_safe(v, t, head) \ - dm_list_iterate_items_gen_safe(v, t, (head), list) - -/* - * Walk a list backwards, setting 'v' in turn to the containing structure - * of each item. - * The containing structure should be the same type as 'v'. - * The 'struct dm_list' variable within the containing structure is 'field'. - */ -#define dm_list_iterate_back_items_gen(v, head, field) \ - for (v = dm_list_struct_base((head)->p, __typeof__(*v), field); \ - &v->field != (head); \ - v = dm_list_struct_base(v->field.p, __typeof__(*v), field)) - -/* - * Walk a list backwards, setting 'v' in turn to the containing structure - * of each item. - * The containing structure should be the same type as 'v'. - * The list should be 'struct dm_list list' within the containing structure. - */ -#define dm_list_iterate_back_items(v, head) dm_list_iterate_back_items_gen(v, (head), list) - -/* - * Return the number of elements in a list by walking it. - */ -unsigned int dm_list_size(const struct dm_list *head); - /********* * selinux *********/ |