From e823e546e3a4b78f52136c56669713dae8f3ebde Mon Sep 17 00:00:00 2001
From: Thomas White <taw@physics.org>
Date: Fri, 1 Jul 2011 11:45:17 +0200
Subject: New deserialization framework makes loading reflection lists much
 faster

---
 src/reflist-utils.c |  7 +++++--
 src/reflist.c       | 52 +++++++++++++++++++++++++++++++++++++++++++++++-----
 src/reflist.h       |  2 ++
 3 files changed, 54 insertions(+), 7 deletions(-)

diff --git a/src/reflist-utils.c b/src/reflist-utils.c
index 016fa317..0ae1f31b 100644
--- a/src/reflist-utils.c
+++ b/src/reflist-utils.c
@@ -302,7 +302,10 @@ RefList *read_reflections_from_file(FILE *fh)
 		if ( rval == NULL ) continue;
 		chomp(line);
 
-		if ( strcmp(line, REFLECTION_END_MARKER) == 0 ) return out;
+		if ( strcmp(line, REFLECTION_END_MARKER) == 0 ) {
+			optimise_reflist(out);
+			return out;
+		}
 
 		r = sscanf(line, "%i %i %i %f %s %f %s %i %f %f",
 		           &h, &k, &l, &intensity, phs, &sigma, ress, &cts,
@@ -318,7 +321,7 @@ RefList *read_reflections_from_file(FILE *fh)
 			double ph;
 			char *v;
 
-			refl = add_refl(out, h, k, l);
+			refl = add_serialised_refl(out, h, k, l);
 			set_int(refl, intensity);
 			set_detector_pos(refl, 0.0, fs, ss);
 			set_esd_intensity(refl, sigma);
diff --git a/src/reflist.c b/src/reflist.c
index d6773a09..06ff167b 100644
--- a/src/reflist.c
+++ b/src/reflist.c
@@ -101,6 +101,7 @@ struct _reflection {
 struct _reflist {
 
 	struct _reflection *head;
+	struct _reflection *tail;
 
 };
 
@@ -144,6 +145,7 @@ RefList *reflist_new()
 	/* Create pseudo-root with invalid indices.
 	 * The "real" root will be the left child of this. */
 	new->head = new_node(1<<31);
+	new->tail = new->head;
 
 	return new;
 }
@@ -188,7 +190,8 @@ void reflist_free(RefList *list)
  * Returns: The found reflection, or NULL if no reflection with the given
  * indices could be found.
  **/
-Reflection *find_refl(const RefList *list, signed int h, signed int k, signed int l)
+Reflection *find_refl(const RefList *list,
+                      signed int h, signed int k, signed int l)
 {
 	unsigned int search = SERIAL(h, k, l);
 	Reflection *refl = list->head->child[0];
@@ -583,12 +586,51 @@ Reflection *add_refl(RefList *list, signed int h, signed int k, signed int l)
 
 	new = new_node(SERIAL(h, k, l));
 
-	if ( list->head == NULL ) {
-		list->head = new;
-		new->parent = NULL;
+	insert_node(list->head, new);
+
+	return new;
+}
+
+
+/**
+ * add_serialised_refl:
+ * @list: A reflections list
+ * @h, @k, @l: Indices of new reflection
+ *
+ * Returns: The newly added reflection
+ *
+ * Adds a new reflection from a serialised (i.e. sorted by ascending
+ * search key) data source.  If you know the reflections you are adding to the
+ * list are in the required order, using this function is quicker than using
+ * add_refl().  You can only add reflections using this function to an empty
+ * list, or one that has only been added to using this function.  After adding
+ * all the reflections, you need to call optimise_reflist() or the list will
+ * exhibit worst-case performance.
+ *
+ * If you don't understand exactly what this function does and why it needs to
+ * exist, don't use it at all.
+ **/
+Reflection *add_serialised_refl(RefList *list,
+                                signed int h, signed int k, signed int l)
+{
+	Reflection *new;
+
+	assert(abs(h)<256);
+	assert(abs(k)<256);
+	assert(abs(l)<256);
+
+	new = new_node(SERIAL(h, k, l));
+
+	new->parent = list->tail;
+	assert(list->tail->child[0] == NULL);
+	assert(list->tail->child[1] == NULL);
+	if ( list->tail == list->head ) {
+		list->tail->child[0] = new;
 	} else {
-		insert_node(list->head, new);
+		assert(new->serial > list->tail->serial);
+		list->tail->child[1] = new;
 	}
+	list->tail = new;
 
 	return new;
 }
diff --git a/src/reflist.h b/src/reflist.h
index 580ea33c..393ac172 100644
--- a/src/reflist.h
+++ b/src/reflist.h
@@ -77,6 +77,8 @@ extern void set_symmetric_indices(Reflection *refl,
 /* Insertion */
 extern Reflection *add_refl(RefList *list,
                             signed int h, signed int k, signed int l);
+extern Reflection *add_serialised_refl(RefList *list, signed int h,
+                                       signed int k, signed int l);
 
 /* Deletion */
 extern void delete_refl(Reflection *refl);
-- 
cgit v1.2.3