1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
/*
* Copyright (C) 2008-2010 Timothy D. Morgan
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; version 3 of the License.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*
* $Id$
*/
/**
* @file
*
* A data structure which stores a list of address ranges.
*
* range_lists support basic in-place modifications and maintain the address
* space in sorted order. Looking up a range_list_element is implemented
* through binary search.
*/
#ifndef _RANGE_LIST_H
#define _RANGE_LIST_H
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include <math.h>
#include <talloc.h>
#include "compat.h"
typedef struct _range_list_element
{
uint32_t offset;
uint32_t length;
void* data;
} range_list_element;
/** XXX: document this. */
typedef struct _range_list
{
range_list_element** elements;
uint32_t elem_alloced;
uint32_t size;
} range_list;
/** Allocates a new range_list.
*
* @return A newly allocated range_list, or NULL if an error occurred.
*/
_EXPORT()
range_list* range_list_new();
/** Frees the memory associated with a range_list, including the elements, but
* not any data parameters referenced by those elements.
*
* If rl is NULL, does nothing.
*
* @param rl the range_list to be free()d.
*/
_EXPORT()
void range_list_free(range_list* rl);
/** Query the current number of elements on a range_list
*
* @param rl the range_list to query
*
* @return The number of elements currently in the list.
*/
_EXPORT()
uint32_t range_list_size(const range_list* rl);
/** Adds an element to the range_list.
*
* The new element must not overlap with others.
* NOTE: this is a slow operation.
*
* @param rl the range list to update
* @param offset the starting point for the range
* @param length the length of the range
* @param data misc data associated with this range element
*
* @return true on success, false on failure.
*
* Failures can occur due to memory limitations, max_size limitations,
* or if the submitted range overlaps with an existing element. Other
* errors may also be possible.
*/
_EXPORT()
bool range_list_add(range_list* rl, uint32_t offset, uint32_t length, void* data);
/** Removes an element from the list.
*
* The element data structure will be freed, but the data property will not be.
*
* @param rl the range_list to modify
* @param index the element index to remove
*
* @return true if the element was successfully removed, false otherwise.
*/
_EXPORT()
bool range_list_remove(range_list* rl, uint32_t index);
/** Retrieves the element for a given index.
*
* @param rl the range_list being queried.
* @param index the element index desired.
*
* @return The element for a given index, or NULL if the element is not
* available.
*/
_EXPORT()
const range_list_element* range_list_get(const range_list* rl, uint32_t index);
/** Attempts to find the unique element whose range encompasses offset.
*
* @param rl the range_list being queried.
* @param offset the location for which an element is desired.
*
* @return A matching element index or a negative value if none could be found.
*/
_EXPORT()
int32_t range_list_find(const range_list* rl, uint32_t offset);
/** Same as range_list_find(), but returns the data associated with an element.
*
* @param rl the range_list being queried.
* @param offset the address to search for in the ranges
*
* @return The data element of the matching element index or NULL if none could
* be found.
*
* NOTE: May also return NULL if an element matched but the data
* element was never set.
*/
_EXPORT()
void* range_list_find_data(const range_list* rl, uint32_t offset);
/** Splits an existing element into two elements in place.
*
* The resulting list will contain an additional element whose offset
* is the one provided and whose length extends to the end of the old element
* (the one identified by the index). The original element's offset will
* remain the same while it's length is shortened such that it is contiguous
* with the newly created element. The newly created element will have an index
* of one more than the current element.
*
* Both the original element and the newly created element will reference the
* original element's data.
*
* @param rl the range_list to modify
* @param index the index of the element to be split
* @param offset the at which the element will be split
*
* @return true if the element was successfully split, false otherwise.
*/
_EXPORT()
bool range_list_split_element(range_list* rl, uint32_t index, uint32_t offset);
/** Determines whether or not a specified range exists contiguously within the
* range_list.
*
* @param rl the range_list to search
* @param start the offset at the beginning of the range
* @param length the length of the range
*
* @return true if the specified range exists and is complete, false otherwise.
*/
_EXPORT()
bool range_list_has_range(range_list* rl, uint32_t start, uint32_t length);
#endif
|
