Changeset 169 for trunk/include/range_list.h
- Timestamp:
- 03/03/10 14:24:58 (14 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/include/range_list.h
r168 r169 1 /** 2 * @file 3 * 4 * Copyright (C) 2008-2009 Timothy D. Morgan 1 /* 2 * Copyright (C) 2008-2010 Timothy D. Morgan 5 3 * 6 4 * This program is free software; you can redistribute it and/or modify … … 18 16 * 19 17 * $Id$ 18 */ 19 20 /** 21 * @file 22 * 23 * A data structure which stores a list of address ranges. 24 * 25 * range_lists support basic in-place modifications and maintain the address 26 * space in sorted order. Looking up a range_list_element is implemented 27 * through binary search. 20 28 */ 21 29 … … 38 46 39 47 48 /** XXX: document this. */ 40 49 typedef struct _range_list 41 50 { … … 46 55 47 56 48 /* range_list_new(): 49 * Allocates a new range_list. 57 /** Allocates a new range_list. 50 58 * 51 * Returns: 52 * A newly allocated range_list, or NULL if an error occurred. 59 * @return A newly allocated range_list, or NULL if an error occurred. 53 60 */ 54 61 range_list* range_list_new(); 55 62 56 63 57 /* range_list_free(): 58 * Frees the memory associated with a range_list, including the elements, but 59 * not any data parameters referenced by those elements. If rl is NULL, does 60 * nothing. 64 /** Frees the memory associated with a range_list, including the elements, but 65 * not any data parameters referenced by those elements. 61 66 * 62 * Arguments: 63 * rl -- the range_list to be free()d. 67 * If rl is NULL, does nothing. 68 * 69 * @param rl the range_list to be free()d. 64 70 */ 65 71 void range_list_free(range_list* rl); 66 72 67 73 68 /* range_list_size(): 69 * Query the current number of elements on a range_list 74 /** Query the current number of elements on a range_list 70 75 * 71 * Arguments: 72 * rl -- the range_list to query 76 * @param rl the range_list to query 73 77 * 74 * Returns: 75 * The number of elements currently in the list. 78 * @return The number of elements currently in the list. 76 79 */ 77 80 uint32_t range_list_size(const range_list* rl); 78 81 79 82 80 /* range_list_add(): 81 * Adds an element to the range_list. 82 * The new element must not overlap with others. 83 * NOTE: this is a slow operation. 83 /** Adds an element to the range_list. 84 84 * 85 * Arguments: 86 * rl -- the range list to update 87 * offset -- the starting point for the range 88 * length -- the length of the range 89 * data -- misc data associated with this range element 90 * Returns: 91 * true on success, false on failure. 92 * Failures can occur due to memory limitations, max_size limitations, 93 * or if the submitted range overlaps with an existing element. Other 94 * errors may also be possible. 85 * The new element must not overlap with others. 86 * NOTE: this is a slow operation. 87 * 88 * @param rl the range list to update 89 * @param offset the starting point for the range 90 * @param length the length of the range 91 * @param data misc data associated with this range element 92 * 93 * @return true on success, false on failure. 94 * 95 * Failures can occur due to memory limitations, max_size limitations, 96 * or if the submitted range overlaps with an existing element. Other 97 * errors may also be possible. 95 98 */ 96 99 bool range_list_add(range_list* rl, uint32_t offset, uint32_t length, void* data); 97 100 98 101 99 /* range_list_remove(): 100 * Removes an element from the list. The element data structure will be 101 * freed, but the data property will not be. 102 /** Removes an element from the list. 102 103 * 103 * Arguments: 104 * rl -- the range_list to modify 105 * index -- the element index to remove 104 * The element data structure will be freed, but the data property will not be. 106 105 * 107 * Returns: 108 * true if the element was successfully removed, false otherwise. 106 * @param rl the range_list to modify 107 * @param index the element index to remove 108 * 109 * @return true if the element was successfully removed, false otherwise. 109 110 */ 110 111 bool range_list_remove(range_list* rl, uint32_t index); 111 112 112 113 113 /* range_list_get(): 114 * Retrieves the element for a given index. 114 /** Retrieves the element for a given index. 115 115 * 116 * Arguments: 117 * rl -- the range_list being queried. 118 * index -- the element index desired. 116 * @param rl the range_list being queried. 117 * @param index the element index desired. 119 118 * 120 * Returns:121 * The element for a given index, or NULL if the element is notavailable.119 * @return The element for a given index, or NULL if the element is not 120 * available. 122 121 */ 123 122 const range_list_element* range_list_get(const range_list* rl, uint32_t index); 124 123 125 124 126 /* range_list_find(): 127 * Attempts to find the unique element whose range encompasses offset. 125 /** Attempts to find the unique element whose range encompasses offset. 128 126 * 129 * Arguments: 130 * rl -- the range_list being queried. 131 * offset -- the location for which an element is desired. 127 * @param rl the range_list being queried. 128 * @param offset the location for which an element is desired. 132 129 * 133 * Returns: 134 * A matching element index or a negative value if none could be found. 130 * @return A matching element index or a negative value if none could be found. 135 131 */ 136 132 int32_t range_list_find(const range_list* rl, uint32_t offset); 137 133 138 134 139 /* range_list_find_data(): 140 * Same as range_list_find(), but returns the data associated with an element. 135 /** Same as range_list_find(), but returns the data associated with an element. 141 136 * 142 * Arguments: 143 * rl -- the range_list being queried. 144 * offset -- the address to search for in the ranges 137 * @param rl the range_list being queried. 138 * @param offset the address to search for in the ranges 145 139 * 146 * Returns: 147 * The data element of the matching element index or NULL if none could 148 * be found. 140 * @return The data element of the matching element index or NULL if none could 141 * be found. 149 142 * 150 * NOTE: May also return NULL if an element matched but ifthe data143 * NOTE: May also return NULL if an element matched but the data 151 144 * element was never set. 152 145 */ … … 154 147 155 148 156 /* range_list_split_element(): 157 * Splits an existing element into two elements in place. 149 /** Splits an existing element into two elements in place. 158 150 * 159 * 160 * 161 * 162 * 163 * 164 * 151 * The resulting list will contain an additional element whose offset 152 * is the one provided and whose length extends to the end of the old element 153 * (the one identified by the index). The original element's offset will 154 * remain the same while it's length is shortened such that it is contiguous 155 * with the newly created element. The newly created element will have an index 156 * of one more than the current element. 165 157 * 166 * 167 * 158 * Both the original element and the newly created element will reference the 159 * original element's data. 168 160 * 169 * Arguments: 170 * rl -- the range_list to modify 171 * index -- the index of the element to be split 172 * offset -- the at which the element will be split 161 * @param rl the range_list to modify 162 * @param index the index of the element to be split 163 * @param offset the at which the element will be split 173 164 * 174 * Returns: 175 * true if the element was successfully split, false otherwise. 176 * 177 * 165 * @return true if the element was successfully split, false otherwise. 178 166 */ 179 167 bool range_list_split_element(range_list* rl, uint32_t index, uint32_t offset); 180 168 181 169 182 /* range_list_has_range(): 183 * Determines whether or not a specified range exists contiguously within the 170 /** Determines whether or not a specified range exists contiguously within the 184 171 * range_list. 185 172 * 186 * Arguments: 187 * rl -- the range_list to search 188 * start -- the offset at the beginning of the range 189 * length -- the length of the range 173 * @param rl the range_list to search 174 * @param start the offset at the beginning of the range 175 * @param length the length of the range 190 176 * 191 * Returns: 192 * true if the specified range exists and is complete, false otherwise. 177 * @return true if the specified range exists and is complete, false otherwise. 193 178 */ 194 179 bool range_list_has_range(range_list* rl, uint32_t start, uint32_t length);
Note: See TracChangeset
for help on using the changeset viewer.