Convert rangeset implementation from a hashtable to GSequence.

[bluesky.git] / bluesky / util.c

diff --git a/bluesky/util.c b/bluesky/util.c
index be378ef..4e8b011 100644 (file)
--- a/bluesky/util.c
+++ b/bluesky/util.c
@@ -229,30 +229,66 @@ BlueSkyInode *bluesky_list_tail(GList *head)
  * should be extended later to track properly. */
 
 struct BlueSkyRangeset {
-    GHashTable *hashtable;
+    GSequence *seq;
 };
 
+static gint compare64(gconstpointer a, gconstpointer b, gpointer user_data)
+{
+    uint64_t x = *(uint64_t *)a;
+    uint64_t y = *(uint64_t *)b;
+
+    if (x < y)
+        return -1;
+    else if (x > y)
+        return 1;
+    else
+        return 0;
+}
+
 BlueSkyRangeset *bluesky_rangeset_new()
 {
     BlueSkyRangeset *rangeset = g_new(BlueSkyRangeset, 1);
-    rangeset->hashtable = g_hash_table_new(g_direct_hash, g_direct_equal);
+    rangeset->seq = g_sequence_new(g_free);
     return rangeset;
 }
 
 void bluesky_rangeset_free(BlueSkyRangeset *rangeset)
 {
-    g_hash_table_unref(rangeset->hashtable);
+    g_sequence_free(rangeset->seq);
     g_free(rangeset);
 }
 
 gboolean bluesky_rangeset_insert(BlueSkyRangeset *rangeset,
-                                 int start, int length, gpointer data)
+                                 uint64_t start, uint64_t length,
+                                 gpointer data)
 {
-    g_hash_table_insert(rangeset->hashtable, GINT_TO_POINTER(start), data);
+    GSequenceIter *i;
+    i = g_sequence_search(rangeset->seq, &start, compare64, NULL);
+    i = g_sequence_iter_prev(i);
+
+    /* TODO: Checks that no other item overlaps. */
+
+    BlueSkyRangesetItem *item = g_new(BlueSkyRangesetItem, 1);
+    item->start = start;
+    item->length = length;
+    item->data = data;
+    g_sequence_insert_sorted(rangeset->seq, item, compare64, NULL);
+
     return TRUE;
 }
 
-gpointer bluesky_rangeset_lookup(BlueSkyRangeset *rangeset, int start)
+const BlueSkyRangesetItem *bluesky_rangeset_lookup(BlueSkyRangeset *rangeset,
+                                                   uint64_t offset)
 {
-    return g_hash_table_lookup(rangeset->hashtable, GINT_TO_POINTER(start));
+    GSequenceIter *i;
+    i = g_sequence_search(rangeset->seq, &offset, compare64, NULL);
+    i = g_sequence_iter_prev(i);
+    if (g_sequence_iter_is_end(i))
+        return NULL;
+
+    BlueSkyRangesetItem *item = (BlueSkyRangesetItem *)g_sequence_get(i);
+    if (offset >= item->start && offset < item->start + item->length)
+        return item;
+    else
+        return NULL;
 }