Index: trunk/lib/Makefile
===================================================================
--- trunk/lib/Makefile	(revision 97)
+++ trunk/lib/Makefile	(revision 98)
@@ -3,5 +3,5 @@
 ################################################################################
 
-FILES=regfi.o smb_deps.o void_stack.o
+FILES=regfi.o smb_deps.o void_stack.o range_list.o
 
 all: $(FILES)
@@ -16,4 +16,7 @@
 	$(CC) $(CFLAGS) $(OPTS) $(INC) -c -o $@ void_stack.c
 
+range_list.o: range_list.c
+	$(CC) $(CFLAGS) $(OPTS) $(INC) -c -o $@ range_list.c
+
 clean:
 	rm -f $(FILES)
Index: trunk/lib/range_list.c
===================================================================
--- trunk/lib/range_list.c	(revision 98)
+++ trunk/lib/range_list.c	(revision 98)
@@ -0,0 +1,300 @@
+/*
+ * Copyright (C) 2008 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: $
+ */
+
+#include <math.h>
+#include "../include/range_list.h"
+
+
+/*******************/
+/* Private symbols */
+/*******************/
+#define RANGE_LIST_ALLOC_SIZE 256
+
+/*
+ * Inserts elem into rl at the specified index and updates rl->size. 
+ * Memory reallocation of rl->elements is handled when necessary, and
+ * rl->elem_alloced is updated in this case..  Returns false if memory
+ * could not be allocated.  
+ */
+static bool range_list_insert(range_list* rl, range_list_element* elem, uint32_t index)
+{
+  uint32_t i;
+  range_list_element** tmp;
+
+  if(rl->size == rl->elem_alloced)
+  {
+    tmp = (range_list_element**)realloc(rl->elements, rl->elem_alloced+RANGE_LIST_ALLOC_SIZE);
+    if(tmp == NULL)
+      return false;
+    rl->elements = tmp;
+    rl->elem_alloced += RANGE_LIST_ALLOC_SIZE;
+  }
+
+  /* Do the shuffle to the right. */
+  for(i=rl->size; i > index; i--)
+    rl->elements[i] = rl->elements[i-1];
+  rl->elements[index] = elem;
+
+  rl->size++;
+  return true;
+}
+
+/*
+ * Finds the element with the closest offset to that provided, such that
+ * the element's offset <= the provided offset.  If no such element
+ * exists, this returns -1 which indicates that the provided offset
+ * appears before all elements.
+ */
+static int32_t range_list_find_previous(const range_list* rl, uint32_t offset)
+{
+  uint32_t h_idx, l_idx, cur_idx;
+  uint32_t h_val, l_val;
+  range_list_element* cur_elem;
+
+  if((rl->size == 0) || (offset < rl->elements[0]->offset))
+    return -1;
+
+  if(offset >= rl->elements[rl->size-1]->offset)
+    return rl->size-1;
+
+  h_idx = rl->size-1;
+  l_idx = 0;
+  while(h_idx != l_idx)
+  {
+    h_val = rl->elements[h_idx]->offset + rl->elements[h_idx]->length;
+    l_val = rl->elements[l_idx]->offset;
+    /* Make an educated guess as to the "middle" index based on the
+     * ratios of the offset and high/low values.
+     */
+    cur_idx = (uint32_t)ceil((((double)offset-l_val)/(h_val-l_val))*(h_idx-l_idx));
+    if(cur_idx > h_idx)
+      cur_idx = h_idx;
+    if(cur_idx < l_idx)
+      cur_idx = l_idx;
+    cur_elem = rl->elements[cur_idx];
+
+    if((offset >= cur_elem->offset) && (offset < (cur_elem+1)->offset))
+      return cur_idx;
+    
+    if(offset < cur_elem->offset)
+      h_idx = cur_idx-1;
+    else
+      l_idx = cur_idx+1;
+  }
+
+  return h_idx;
+}
+
+
+/******************/
+/* Public symbols */
+/******************/
+range_list* range_list_new()
+{
+  range_list* rl;
+
+  rl = (range_list*)malloc(sizeof(range_list*));
+  if(rl == NULL)
+    return NULL;
+
+  rl->elements = (range_list_element**)malloc(sizeof(range_list_element*)
+					      * RANGE_LIST_ALLOC_SIZE);
+  if(rl->elements == NULL)
+  {
+    free(rl);
+    return NULL;
+  }
+
+  rl->elem_alloced = RANGE_LIST_ALLOC_SIZE;
+  rl->size = 0;
+
+  return rl;
+}
+
+
+void range_list_free(range_list* rl)
+{
+  uint32_t i;
+  for(i=0; i < rl->size; i++)
+    free(rl->elements[i]);
+
+  free(rl->elements);
+  free(rl);
+}
+
+
+uint32_t range_list_size(const range_list* rl)
+{
+  return rl->size;
+}
+
+
+
+bool range_list_add(range_list* rl, uint32_t offset, uint32_t length, void* data)
+{
+  uint32_t insert_index;
+  range_list_element* elem;
+  range_list_element* prev_elem;
+
+  /* Sorry, limited to 2**31-1 elements. */
+  if(rl->size >= 0x7FFFFFFF)
+    return false;
+
+  /* 0-length ranges aren't allowed. */
+  if(length == 0)
+    return false;
+  
+  /* Check for integer overflows */
+  if((uint32_t)(offset+length) < offset || (uint32_t)(offset+length) < length)
+    return false;
+
+  /* Find insertion point and validate there are no overlaps */
+  insert_index = range_list_find_previous(rl, offset)+1;
+  
+  /* Does the previous element overlap with this one? */
+  if(insert_index > 0)
+  {
+    prev_elem = rl->elements[insert_index-1];
+    if(offset < prev_elem->length + prev_elem->offset)
+      return false;
+  }
+
+  /* Does this new element overlap with the next one? */
+  if((insert_index+1 < rl->size) 
+     && (offset+length > rl->elements[insert_index+1]->offset))
+    return false;
+
+  elem = (range_list_element*)malloc(sizeof(range_list_element));
+  if(elem == NULL)
+    return false;
+  elem->offset = offset;
+  elem->length = length;
+  elem->data = data;
+  
+  if(!range_list_insert(rl, elem, insert_index))
+  {
+    free(elem);
+    return false;
+  }
+
+  return true;
+}
+
+
+bool range_list_remove(range_list* rl, uint32_t index)
+{
+  uint32_t i;
+  range_list_element** tmp;
+
+  if(index >= rl->size)
+    return false;
+
+  free(rl->elements[index]);
+
+  /* Do the shuffle to the left. */
+  for(i=index; i < (rl->size-1); i++)
+    rl->elements[i] = rl->elements[i+1];
+  rl->elements[rl->size-1] = NULL;
+  rl->size--;
+
+  /* Try to keep memory usage down */
+  if(rl->size < (rl->elem_alloced - 2*RANGE_LIST_ALLOC_SIZE))
+  {
+    tmp = (range_list_element**)realloc(rl->elements, 
+					rl->elem_alloced - 2*RANGE_LIST_ALLOC_SIZE);
+    if(tmp != NULL)
+    {
+      rl->elements = tmp;
+      rl->elem_alloced -= 2*RANGE_LIST_ALLOC_SIZE;
+    }
+  }
+
+  return true;
+}
+
+
+const range_list_element* range_list_get(const range_list* rl, uint32_t index)
+{
+  if(index >= rl->size)
+    return NULL;
+
+  return rl->elements[index];
+}
+
+
+int32_t range_list_find(const range_list* rl, uint32_t offset)
+{
+  uint32_t prev_idx;
+  range_list_element* elem;
+
+  if((offset < rl->elements[0]->offset)
+     || (offset > rl->elements[rl->size-1]->offset 
+	 + rl->elements[rl->size-1]->length))
+    return -1;
+
+  prev_idx = range_list_find_previous(rl, offset);
+  elem = rl->elements[prev_idx];
+  if(offset < elem->offset+elem->length)
+    return prev_idx;
+
+  return -2;
+}
+
+
+void* range_list_find_data(const range_list* rl, uint32_t offset)
+{
+  int32_t index = range_list_find(rl, offset);
+  if(index < 0)
+    return NULL;
+
+  return rl->elements[index]->data;
+}
+
+
+bool range_list_split_element(range_list* rl, uint32_t index, uint32_t offset)
+{
+  range_list_element* cur_elem;
+  range_list_element* new_elem;
+
+  if(index >= rl->size)
+    return false;
+
+  cur_elem = rl->elements[index];
+  if((offset <= cur_elem->offset) 
+     || (offset >= cur_elem->offset+cur_elem->length))
+    return false;
+
+  new_elem = (range_list_element*)malloc(sizeof(range_list_element));
+  if(new_elem == NULL)
+    return false;
+  
+  new_elem->offset = offset;
+  new_elem->length = cur_elem->offset + cur_elem->length - offset;
+  new_elem->data = cur_elem->data;
+  
+  if(!range_list_insert(rl, new_elem, index+1))
+  {
+    free(new_elem);
+    return false;
+  }
+
+  cur_elem->length = new_elem->offset - cur_elem->offset;
+
+  return true;
+}
