source: trunk/lib/range_list.c @ 141

Last change on this file since 141 was 122, checked in by tim, 16 years ago

fixed an incorrect malloc in range_list.c
minor documentation updates

  • Property svn:keywords set to Id
File size: 7.9 KB
Line 
1/*
2 * Copyright (C) 2008 Timothy D. Morgan
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; version 3 of the License.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 
16 *
17 * $Id: range_list.c 122 2008-08-09 20:24:01Z tim $
18 */
19
20#include <math.h>
21#include "../include/range_list.h"
22
23
24/*******************/
25/* Private symbols */
26/*******************/
27#define RANGE_LIST_ALLOC_SIZE 256
28
29#if 0
30#include <stdio.h>
31static void range_list_print(const range_list* rl)
32{
33  uint32_t i;
34  for(i=0; i<rl->size; i++)
35    fprintf(stderr, " %d=%p,%d,%d,%p", i, (void*)rl->elements[i],
36            rl->elements[i]->offset, rl->elements[i]->length,
37            rl->elements[i]->data);
38  fprintf(stderr, "\n");
39}
40#endif
41
42/*
43 * Inserts elem into rl at the specified index and updates rl->size.
44 * Memory reallocation of rl->elements is handled when necessary, and
45 * rl->elem_alloced is updated in this case..  Returns false if memory
46 * could not be allocated. 
47 */
48static bool range_list_insert(range_list* rl, range_list_element* elem, uint32_t index)
49{
50  uint32_t i;
51  range_list_element** tmp;
52
53  if(rl->size == rl->elem_alloced)
54  {
55    tmp = (range_list_element**)realloc(rl->elements, 
56                                        (rl->elem_alloced+RANGE_LIST_ALLOC_SIZE)
57                                        * sizeof(range_list_element*));
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 = (range_list*)malloc(sizeof(range_list));
128  if(rl == NULL)
129    return NULL;
130
131  rl->elements = (range_list_element**)malloc(sizeof(range_list_element*)
132                                              * RANGE_LIST_ALLOC_SIZE);
133
134  if(rl->elements == NULL)
135  {
136    free(rl);
137    return NULL;
138  }
139
140  rl->elem_alloced = RANGE_LIST_ALLOC_SIZE;
141  rl->size = 0;
142
143  return rl;
144}
145
146
147void range_list_free(range_list* rl)
148{
149  uint32_t i;
150
151  if(rl == NULL)
152    return;
153
154  for(i=0; i < rl->size; i++)
155    free(rl->elements[i]);
156
157  free(rl->elements);
158  free(rl);
159}
160
161
162uint32_t range_list_size(const range_list* rl)
163{
164  return rl->size;
165}
166
167
168
169bool range_list_add(range_list* rl, uint32_t offset, uint32_t length, void* data)
170{
171  uint32_t insert_index;
172  range_list_element* elem;
173  range_list_element* prev_elem;
174  /*fprintf(stderr, "DEBUG: rl->size=%d\n", rl->size);*/
175  /* Sorry, limited to 2**31-1 elements. */
176  if(rl->size >= 0x7FFFFFFF)
177    return false;
178
179  /* 0-length ranges aren't allowed. */
180  if(length == 0)
181    return false;
182 
183  /* Check for integer overflows */
184  if((uint32_t)(offset+length) < offset || (uint32_t)(offset+length) < length)
185    return false;
186
187  /* Find insertion point and validate there are no overlaps */
188  insert_index = range_list_find_previous(rl, offset)+1;
189 
190  /* Does the previous element overlap with this one? */
191  if(insert_index > 0)
192  {
193    prev_elem = rl->elements[insert_index-1];
194    if(offset < prev_elem->length + prev_elem->offset)
195      return false;
196  }
197
198  /* Does this new element overlap with the next one? */
199  if((insert_index+1 < rl->size) 
200     && (offset+length > rl->elements[insert_index+1]->offset))
201    return false;
202
203  elem = (range_list_element*)malloc(sizeof(range_list_element));
204  if(elem == NULL)
205    return false;
206  elem->offset = offset;
207  elem->length = length;
208  elem->data = data;
209 
210  if(!range_list_insert(rl, elem, insert_index))
211  {
212    free(elem);
213    return false;
214  }
215
216  return true;
217}
218
219
220bool range_list_remove(range_list* rl, uint32_t index)
221{
222  uint32_t i;
223  range_list_element** tmp;
224
225  if(index >= rl->size)
226    return false;
227
228  free(rl->elements[index]);
229
230  /* Do the shuffle to the left. */
231  for(i=index; i < (rl->size-1); i++)
232    rl->elements[i] = rl->elements[i+1];
233  rl->elements[rl->size-1] = NULL;
234  rl->size--;
235
236  /* Try to keep memory usage down */
237  if(rl->size + 2 * RANGE_LIST_ALLOC_SIZE  < rl->elem_alloced)
238  {
239    tmp = (range_list_element**)realloc(rl->elements, 
240                                        (rl->elem_alloced-2*RANGE_LIST_ALLOC_SIZE)
241                                        * sizeof(range_list_element*));
242    if(tmp != NULL)
243    {
244      rl->elements = tmp;
245      rl->elem_alloced -= 2*RANGE_LIST_ALLOC_SIZE;
246    }
247  }
248
249  return true;
250}
251
252
253const range_list_element* range_list_get(const range_list* rl, uint32_t index)
254{
255  if(index >= rl->size)
256    return NULL;
257
258  return rl->elements[index];
259}
260
261
262int32_t range_list_find(const range_list* rl, uint32_t offset)
263{
264  uint32_t prev_idx;
265  range_list_element* elem;
266
267  if((offset < rl->elements[0]->offset)
268     || (offset > rl->elements[rl->size-1]->offset
269         + rl->elements[rl->size-1]->length))
270    return -1;
271
272  prev_idx = range_list_find_previous(rl, offset);
273  elem = rl->elements[prev_idx];
274  if(offset < elem->offset+elem->length)
275    return prev_idx;
276
277  return -2;
278}
279
280
281void* range_list_find_data(const range_list* rl, uint32_t offset)
282{
283  int32_t index = range_list_find(rl, offset);
284  if(index < 0)
285    return NULL;
286
287  return rl->elements[index]->data;
288}
289
290
291bool range_list_split_element(range_list* rl, uint32_t index, uint32_t offset)
292{
293  range_list_element* cur_elem;
294  range_list_element* new_elem;
295
296  if(index >= rl->size)
297    return false;
298
299  cur_elem = rl->elements[index];
300  if((offset <= cur_elem->offset) 
301     || (offset >= cur_elem->offset+cur_elem->length))
302    return false;
303
304  new_elem = (range_list_element*)malloc(sizeof(range_list_element));
305  if(new_elem == NULL)
306    return false;
307 
308  new_elem->offset = offset;
309  new_elem->length = cur_elem->offset + cur_elem->length - offset;
310  new_elem->data = cur_elem->data;
311 
312  if(!range_list_insert(rl, new_elem, index+1))
313  {
314    free(new_elem);
315    return false;
316  }
317
318  cur_elem->length = new_elem->offset - cur_elem->offset;
319
320  return true;
321}
322
323
324bool range_list_has_range(range_list* rl, uint32_t start, uint32_t length)
325{
326  int32_t idx1, idx2;
327
328  idx1 = range_list_find(rl, start);
329  if(idx1 < 0)
330    return false;
331
332  idx2 = range_list_find(rl, start+length);
333  if(idx2 < 0)
334    return false;
335
336  if(idx1 == idx2)
337    return true;
338
339  while(idx1 != idx2)
340  {
341    if(rl->elements[idx1]->offset + rl->elements[idx1]->length
342       != rl->elements[idx1+1]->offset)
343      return false;
344    idx1++;
345  }
346
347  return true;
348}
Note: See TracBrowser for help on using the repository browser.