source: trunk/lib/range_list.c @ 168

Last change on this file since 168 was 168, checked in by tim, 15 years ago

merged remaining smb_deps items into regfi

began formatting API comments for use with doxygen

  • Property svn:keywords set to Id
File size: 7.7 KB
Line 
1/**
2 * @file
3 *
4 * Copyright (C) 2008-2009 Timothy D. Morgan
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; version 3 of the License.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 
18 *
19 * $Id: range_list.c 168 2010-03-03 00:08:42Z tim $
20 */
21
22#include "range_list.h"
23
24
25/*******************/
26/* Private symbols */
27/*******************/
28#define RANGE_LIST_ALLOC_SIZE 256
29
30#if 0 /* For debugging */
31#include <stdio.h>
32static void range_list_print(const range_list* rl)
33{
34  uint32_t i;
35  for(i=0; i<rl->size; i++)
36    fprintf(stderr, " %d=%p,%d,%d,%p", i, (void*)rl->elements[i],
37            rl->elements[i]->offset, rl->elements[i]->length,
38            rl->elements[i]->data);
39  fprintf(stderr, "\n");
40}
41#endif
42
43/*
44 * Inserts elem into rl at the specified index and updates rl->size.
45 * Memory reallocation of rl->elements is handled when necessary, and
46 * rl->elem_alloced is updated in this case..  Returns false if memory
47 * could not be allocated. 
48 */
49static bool range_list_insert(range_list* rl, range_list_element* elem, uint32_t index)
50{
51  uint32_t i;
52  range_list_element** tmp;
53
54  if(rl->size == rl->elem_alloced)
55  {
56    tmp = talloc_realloc(rl, rl->elements, range_list_element*, 
57                         (rl->elem_alloced+RANGE_LIST_ALLOC_SIZE));
58    if(tmp == NULL)
59      return false;
60    rl->elements = tmp;
61    rl->elem_alloced += RANGE_LIST_ALLOC_SIZE;
62  }
63
64  /* Do the shuffle to the right. */
65  for(i=rl->size; i > index; i--)
66    rl->elements[i] = rl->elements[i-1];
67  rl->elements[index] = elem;
68
69  rl->size++;
70  return true;
71}
72
73/*
74 * Finds the element with the closest offset to that provided, such that
75 * the element's offset <= the provided offset.  If no such element
76 * exists, this returns -1 which indicates that the provided offset
77 * appears before all elements.
78 */
79static int32_t range_list_find_previous(const range_list* rl, uint32_t offset)
80{
81  uint32_t h_idx, l_idx, cur_idx;
82  uint32_t h_val, l_val;
83  range_list_element* cur_elem;
84
85  if((rl->size == 0) || (offset < rl->elements[0]->offset))
86    return -1;
87
88  if(offset >= rl->elements[rl->size-1]->offset)
89    return rl->size-1;
90
91  h_idx = rl->size-1;
92  l_idx = 0;
93  while(h_idx != l_idx)
94  {
95    h_val = rl->elements[h_idx]->offset + rl->elements[h_idx]->length;
96    l_val = rl->elements[l_idx]->offset;
97    /* Make an educated guess as to the "middle" index based on the
98     * ratios of the offset and high/low values.
99     */
100    cur_idx = (uint32_t)ceil((((double)offset-l_val)/(h_val-l_val))*(h_idx-l_idx));
101    if(cur_idx > h_idx)
102      cur_idx = h_idx;
103    if(cur_idx < l_idx)
104      cur_idx = l_idx;
105    cur_elem = rl->elements[cur_idx];
106
107    if((offset >= cur_elem->offset) && (offset < rl->elements[cur_idx+1]->offset))
108      return cur_idx;
109   
110    if(offset < cur_elem->offset)
111      h_idx = cur_idx-1;
112    else
113      l_idx = cur_idx+1;
114  }
115
116  return h_idx;
117}
118
119
120/******************/
121/* Public symbols */
122/******************/
123range_list* range_list_new()
124{
125  range_list* rl;
126
127  rl = talloc(NULL, range_list);
128  if(rl == NULL)
129    return NULL;
130
131  rl->elements = talloc_array(rl, range_list_element*, RANGE_LIST_ALLOC_SIZE);
132  if(rl->elements == NULL)
133  {
134    talloc_free(rl);
135    return NULL;
136  }
137
138  rl->elem_alloced = RANGE_LIST_ALLOC_SIZE;
139  rl->size = 0;
140
141  return rl;
142}
143
144
145void range_list_free(range_list* rl)
146{
147  if(rl != NULL)
148    talloc_free(rl);
149}
150
151
152uint32_t range_list_size(const range_list* rl)
153{
154  return rl->size;
155}
156
157
158
159bool range_list_add(range_list* rl, uint32_t offset, uint32_t length, void* data)
160{
161  uint32_t insert_index;
162  range_list_element* elem;
163  range_list_element* prev_elem;
164  /*fprintf(stderr, "DEBUG: rl->size=%d\n", rl->size);*/
165  /* Sorry, limited to 2**31-1 elements. */
166  if(rl->size >= 0x7FFFFFFF)
167    return false;
168
169  /* 0-length ranges aren't allowed. */
170  if(length == 0)
171    return false;
172 
173  /* Check for integer overflows */
174  if((uint32_t)(offset+length) < offset || (uint32_t)(offset+length) < length)
175    return false;
176
177  /* Find insertion point and validate there are no overlaps */
178  insert_index = range_list_find_previous(rl, offset)+1;
179 
180  /* Does the previous element overlap with this one? */
181  if(insert_index > 0)
182  {
183    prev_elem = rl->elements[insert_index-1];
184    if(offset < prev_elem->length + prev_elem->offset)
185      return false;
186  }
187
188  /* Does this new element overlap with the next one? */
189  if((insert_index+1 < rl->size) 
190     && (offset+length > rl->elements[insert_index+1]->offset))
191    return false;
192
193  elem = talloc(rl->elements, range_list_element);
194  if(elem == NULL)
195    return false;
196  elem->offset = offset;
197  elem->length = length;
198  elem->data = data;
199 
200  if(!range_list_insert(rl, elem, insert_index))
201  {
202    talloc_free(elem);
203    return false;
204  }
205
206  return true;
207}
208
209
210bool range_list_remove(range_list* rl, uint32_t index)
211{
212  uint32_t i;
213  range_list_element** tmp;
214
215  if(index >= rl->size)
216    return false;
217
218  talloc_free(rl->elements[index]);
219
220  /* Do the shuffle to the left. */
221  for(i=index; i < (rl->size-1); i++)
222    rl->elements[i] = rl->elements[i+1];
223  rl->elements[rl->size-1] = NULL;
224  rl->size--;
225
226  /* Try to keep memory usage down */
227  if(rl->size + 2 * RANGE_LIST_ALLOC_SIZE  < rl->elem_alloced)
228  {
229    tmp = talloc_realloc(rl, rl->elements, range_list_element*, 
230                         (rl->elem_alloced-2*RANGE_LIST_ALLOC_SIZE));
231    if(tmp != NULL)
232    {
233      rl->elements = tmp;
234      rl->elem_alloced -= 2*RANGE_LIST_ALLOC_SIZE;
235    }
236  }
237
238  return true;
239}
240
241
242const range_list_element* range_list_get(const range_list* rl, uint32_t index)
243{
244  if(index >= rl->size)
245    return NULL;
246
247  return rl->elements[index];
248}
249
250
251int32_t range_list_find(const range_list* rl, uint32_t offset)
252{
253  uint32_t prev_idx;
254  range_list_element* elem;
255
256  if(rl->size == 0)
257    return -1;
258
259  if((offset < rl->elements[0]->offset)
260     || (offset > rl->elements[rl->size-1]->offset
261         + rl->elements[rl->size-1]->length))
262    return -2;
263
264  prev_idx = range_list_find_previous(rl, offset);
265  elem = rl->elements[prev_idx];
266  if(offset < elem->offset+elem->length)
267    return prev_idx;
268
269  return -3;
270}
271
272
273void* range_list_find_data(const range_list* rl, uint32_t offset)
274{
275  int32_t index = range_list_find(rl, offset);
276  if(index < 0)
277    return NULL;
278
279  return rl->elements[index]->data;
280}
281
282
283bool range_list_split_element(range_list* rl, uint32_t index, uint32_t offset)
284{
285  range_list_element* cur_elem;
286  range_list_element* new_elem;
287
288  if(index >= rl->size)
289    return false;
290
291  cur_elem = rl->elements[index];
292  if((offset <= cur_elem->offset) 
293     || (offset >= cur_elem->offset+cur_elem->length))
294    return false;
295
296  new_elem = talloc(rl->elements, range_list_element);
297  if(new_elem == NULL)
298    return false;
299 
300  new_elem->offset = offset;
301  new_elem->length = cur_elem->offset + cur_elem->length - offset;
302  new_elem->data = cur_elem->data;
303 
304  if(!range_list_insert(rl, new_elem, index+1))
305  {
306    talloc_free(new_elem);
307    return false;
308  }
309
310  cur_elem->length = new_elem->offset - cur_elem->offset;
311
312  return true;
313}
314
315
316bool range_list_has_range(range_list* rl, uint32_t start, uint32_t length)
317{
318  int32_t idx1, idx2;
319
320  idx1 = range_list_find(rl, start);
321  if(idx1 < 0)
322    return false;
323
324  idx2 = range_list_find(rl, start+length);
325  if(idx2 < 0)
326    return false;
327
328  if(idx1 == idx2)
329    return true;
330
331  while(idx1 != idx2)
332  {
333    if(rl->elements[idx1]->offset + rl->elements[idx1]->length
334       != rl->elements[idx1+1]->offset)
335      return false;
336    idx1++;
337  }
338
339  return true;
340}
Note: See TracBrowser for help on using the repository browser.