usr/src/cmd/lvm/metassist/common/volume_dlist.h

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License, Version 1.0 only
   6  * (the "License").  You may not use this file except in compliance
   7  * with the License.
   8  *
   9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  10  * or http://www.opensolaris.org/os/licensing.
  11  * See the License for the specific language governing permissions
  12  * and limitations under the License.
  13  *
  14  * When distributing Covered Code, include this CDDL HEADER in each
  15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16  * If applicable, add the following below this CDDL HEADER, with the
  17  * fields enclosed by brackets "[]" replaced with your own identifying
  18  * information: Portions Copyright [yyyy] [name of copyright owner]
  19  *
  20  * CDDL HEADER END
  21  */
  22 /*
  23  * Copyright 2003 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26
  27 #ifndef _VOLUME_DLIST_H
  28 #define _VOLUME_DLIST_H
  29
  30 #pragma ident   "%Z%%M% %I%     %E% SMI"
  31
  32 #ifdef __cplusplus
  33 extern "C" {
  34 #endif
  35
  36 #include <sys/types.h>
  37
  38 /*
  39  * Structure defining a doubly linked list of arbitrary objects
  40  */
  41 typedef struct dlist {
  42
  43     struct dlist        *next;
  44     struct dlist        *prev;
  45     void                *obj;
  46
  47 } dlist_t;
  48
  49 /*
  50  * module globals
  51  */
  52 extern const boolean_t ASCENDING;
  53 extern const boolean_t DESCENDING;
  54 extern const boolean_t AT_TAIL;
  55 extern const boolean_t AT_HEAD;
  56
  57 /* from types.h */
  58 #ifndef TRUE
  59 #define TRUE    B_TRUE
  60 #endif
  61
  62 #ifndef FALSE
  63 #define FALSE   B_FALSE
  64 #endif
  65
  66 /*
  67  * doubly linked list utility methods
  68  */
  69
  70 /*
  71  * count the number of elements currently in the list
  72  */
  73 extern int       dlist_length(dlist_t *list);
  74
  75 /*
  76  * Traverse the list pointed to by head and free each
  77  * list node.  If freefunc is non-NULL, call freefunc
  78  * for each node's object.
  79  */
  80 extern void     dlist_free_items(dlist_t *list, void (freefunc(void *)));
  81
  82 /*
  83  * append item to list.  If atend is true, the item is
  84  * added at the end of the list, otherwise it is added
  85  * at the beginning.
  86  *
  87  * returns the possibly changed head of the list.
  88  */
  89 extern dlist_t  *dlist_append(
  90         dlist_t *item,
  91         dlist_t *list,
  92         boolean_t atend);
  93
  94 /*
  95  * Create a dlist_t element for the given object and append to list.
  96  *
  97  * @param       object
  98  *              the obj member of the dlist_t element to be created
  99  *
 100  * @param       list
 101  *              the list to which to append the new dlist_t element
 102  *
 103  * @param       attail
 104  *              whether to append at the beginning (AT_HEAD) or end
 105  *              (AT_TAIL) of the list
 106  *
 107  * @return      0
 108  *              if successful
 109  *
 110  * @return      ENOMEM
 111  *              if a dlist_t could not be allocated
 112  */
 113 extern int dlist_append_object(
 114         void *object,
 115         dlist_t **list,
 116         boolean_t attail);
 117
 118 /*
 119  * Appends list2 to the end of list1.
 120  *
 121  * Returns the resulting list.
 122  */
 123 extern dlist_t *dlist_append_list(
 124         dlist_t *list1,
 125         dlist_t *list2);
 126
 127 /*
 128  * Remove the first node pointing to same content as item from list,
 129  * clear it's next and prev pointers, return new list head.
 130  *
 131  * The caller is responsible for freeing the removed item if it is no
 132  * longer needed.
 133  *
 134  * The comparison function should be of the form:
 135  *
 136  *     int compare(void *obj1, void* obj2);
 137  *
 138  * When called, obj1 will be the object passed into
 139  * dlist_remove_equivalent_item and obj2 will be an object pointed to by an
 140  * item in the list.
 141  *
 142  * The function should return 0 if the two objects are equivalent The
 143  * function should return nonzero otherwise
 144  *
 145  * @param       list
 146  *              the list containing the item to remove
 147  *
 148  * @param       obj
 149  *              the object with which to compare each item
 150  *
 151  * @param       compare
 152  *              the comparison function, passed obj and the obj member
 153  *              of each item, to return 0 if item should be removed
 154  *
 155  * @param       removed
 156  *              RETURN: the removed item, or NULL if none was found
 157  *
 158  * @return      the first element of the resulting list
 159  */
 160 extern dlist_t  *dlist_remove_equivalent_item(
 161         dlist_t *list,
 162         void    *obj,
 163         int     (compare)(void *obj1, void *obj2),
 164         dlist_t **removed);
 165
 166 /*
 167  * Remove an item from its list.  Return the resulting list.
 168  *
 169  * @param       item
 170  *              the item to remove, with prev and next pointers
 171  *              set to NULL
 172  *
 173  * @return      the first element of the resulting list
 174  */
 175 dlist_t *
 176 dlist_remove(
 177         dlist_t *item);
 178
 179 /*
 180  * allocates memory for a new list item.  The list item will
 181  * point at obj.
 182  *
 183  * returns the new list item.
 184  */
 185 extern dlist_t  *dlist_new_item(void *obj);
 186
 187 /*
 188  * inserts item in the correct position within the list based on
 189  * the comparison function.  if ascending is true, the list will
 190  * be in ascending order, otherwise descending.
 191  *
 192  * the comparison function should be of the form:
 193  *
 194  *     int compare(void *obj1, void *obj2);
 195  *
 196  * When called, obj1 will be the object pointed to by the item to
 197  * be added to the list, obj2 will be an object pointed to by an
 198  * item currently in the list.
 199  *
 200  * The function should return 0 if the two objects are equivalent
 201  * The function should return <0 if obj1 comes before obj2
 202  * The function should return >0 if obj1 comes after obj2
 203  *
 204  * dlist_insert_ordered returns the possibly changed head
 205  * of the list.
 206  */
 207 extern dlist_t  *dlist_insert_ordered(
 208         dlist_t *item,
 209         dlist_t *list,
 210         boolean_t       ascending,
 211         int     (compare)(void *obj1, void *obj2));
 212
 213 /*
 214  * Locates the item in the list which contains object.
 215  *
 216  * the comparison function should be of the form:
 217  *
 218  *     int compare(void *obj1, void *obj2);
 219  *
 220  * When called, obj1 will be the input object, obj2 will be
 221  * an object pointed to by an item currently in the list.
 222  *
 223  * The function should return 0 if the two objects are equivalent
 224  * The function should return non-zero otherwise
 225  *
 226  * dlist_find() returns the found item or NULL if one was not found.
 227  */
 228 extern dlist_t  *dlist_find(
 229         dlist_t *list,
 230         void    *obj,
 231         int     (compare)(void *obj1, void *obj2));
 232
 233 /*
 234  * Determines if list has an item which contains object.
 235  *
 236  * the comparison function should be of the form:
 237  *
 238  *     int compare(void *obj1, void *obj2);
 239  *
 240  * When called, obj1 will be the input object, obj2 will be
 241  * an object pointed to by an item currently in the list.
 242  *
 243  * The function should return 0 if the two objects are equivalent
 244  * The function should return non-zero otherwise
 245  *
 246  * dlist_contains() returns TRUE if the object is already
 247  * in the list or FALSE otherwise.
 248  */
 249 extern boolean_t        dlist_contains(
 250         dlist_t *list,
 251         void    *obj,
 252         int     (compare)(void *obj1, void *obj2));
 253
 254 /*
 255  * Order the given list such that the number of similar elements
 256  * adjacent to each other are minimized.  Two elements are considered
 257  * similar if the given compare function returns 0.
 258  *
 259  * @param       list
 260  *              the list to order
 261  *
 262  * @param       compare
 263  *              the comparison function, passed the obj members
 264  *              of two items, to return 0 if the items can be
 265  *              considered similar
 266  *
 267  * @return      the first element of the resulting list
 268  */
 269 extern dlist_t *
 270 dlist_separate_similar_elements(
 271         dlist_t *list,
 272         int(*equals)(void *, void *));
 273
 274 #ifdef __cplusplus
 275 }
 276 #endif
 277
 278 #endif /* _VOLUME_DLIST_H */