Index: rhythmdb/rhythmdb-query-model.c
===================================================================
--- rhythmdb/rhythmdb-query-model.c	(revision 4815)
+++ rhythmdb/rhythmdb-query-model.c	(working copy)
@@ -168,6 +168,26 @@ static gboolean rhythmdb_query_model_wit
 						   RhythmDBEntry *entry);
 static gboolean rhythmdb_query_model_reapply_query_cb (RhythmDBQueryModel *model);
 
+static gboolean rhythmdb_query_model_contains_entry (RhythmDBQueryModel *model,
+						     RhythmDBEntry *entry);
+static EggSequenceIter* rhythmdb_query_model_get_iter_for_entry (RhythmDBQueryModel *model,
+								 RhythmDBEntry *entry);
+static void rhythmdb_query_model_add_entry_iter (RhythmDBQueryModel *model,
+						 RhythmDBEntry *entry,
+						 EggSequenceIter *iter);
+static void rhythmdb_query_model_remove_entry_iter (RhythmDBQueryModel *model,
+						    RhythmDBEntry *entry);
+static gboolean rhythmdb_query_model_contains_limited_entry (RhythmDBQueryModel *model,
+							     RhythmDBEntry *entry);
+static EggSequenceIter* rhythmdb_query_model_get_iter_for_limited_entry (RhythmDBQueryModel *model,
+									 RhythmDBEntry *entry);
+static void rhythmdb_query_model_add_limited_entry_iter (RhythmDBQueryModel *model,
+							 RhythmDBEntry *entry,
+							 EggSequenceIter *iter);
+static void rhythmdb_query_model_remove_limited_entry_iter (RhythmDBQueryModel *model,
+							    RhythmDBEntry *entry);
+
+
 struct RhythmDBQueryModelUpdate
 {
 	RhythmDBQueryModel *model;
@@ -221,6 +241,7 @@ struct RhythmDBQueryModelPrivate
 	RhythmDBQueryModelLimitType limit_type;
 	GValueArray *limit_value;
 
+	glong total_count;
 	glong total_duration;
 	guint64 total_size;
 
@@ -848,7 +869,7 @@ rhythmdb_query_model_entry_added_cb (Rhy
 
 	/* check if it's in the base model */
 	if (model->priv->base_model) {
-	       if (g_hash_table_lookup (model->priv->base_model->priv->reverse_map, entry) == NULL) {
+	       if (!rhythmdb_query_model_contains_entry (model->priv->base_model, entry)) {
 		       return;
 	       }
 	}
@@ -878,7 +899,7 @@ rhythmdb_query_model_entry_changed_cb (R
 
 	hidden = (!model->priv->show_hidden && rhythmdb_entry_get_boolean (entry, RHYTHMDB_PROP_HIDDEN));
 
-	if (g_hash_table_lookup (model->priv->reverse_map, entry) == NULL) {
+	if (!rhythmdb_query_model_contains_entry (model, entry)) {
 		if (hidden == FALSE) {
 			/* the changed entry may now satisfy the query
 			 * so we test it */
@@ -990,7 +1011,7 @@ rhythmdb_query_model_base_entry_prop_cha
 					      const GValue *new_value,
 					      RhythmDBQueryModel *model)
 {
-	if (g_hash_table_lookup (model->priv->reverse_map, entry)) {
+	if (rhythmdb_query_model_contains_entry (model, entry)) {
 		/* propagate the signal */
 		g_signal_emit (G_OBJECT (model),
 			       rhythmdb_query_model_signals[ENTRY_PROP_CHANGED], 0,
@@ -1004,8 +1025,8 @@ rhythmdb_query_model_entry_deleted_cb (R
 				       RhythmDBQueryModel *model)
 {
 
-	if (g_hash_table_lookup (model->priv->reverse_map, entry) ||
-	    g_hash_table_lookup (model->priv->limited_reverse_map, entry))
+	if (rhythmdb_query_model_contains_entry (model, entry) ||
+	    rhythmdb_query_model_contains_limited_entry (model, entry))
 		rhythmdb_query_model_remove_entry (model, entry);
 }
 
@@ -1043,8 +1064,7 @@ idle_process_update (struct RhythmDBQuer
 
 			if (update->model->priv->show_hidden || !rhythmdb_entry_get_boolean (entry, RHYTHMDB_PROP_HIDDEN)) {
 				RhythmDBQueryModel *base_model = update->model->priv->base_model;
-				if (base_model &&
-				    g_hash_table_lookup (base_model->priv->reverse_map, entry) == NULL)
+				if (base_model && !rhythmdb_query_model_contains_entry (base_model, entry))
 					       continue;
 
 				rhythmdb_query_model_do_insert (update->model, entry, -1);
@@ -1121,7 +1141,7 @@ rhythmdb_query_model_get_duration (Rhyth
 	return model->priv->total_duration;
 }
 
-static void
+static EggSequenceIter*
 rhythmdb_query_model_insert_into_main_list (RhythmDBQueryModel *model,
 					    RhythmDBEntry *entry,
 					    gint index)
@@ -1162,10 +1182,13 @@ rhythmdb_query_model_insert_into_main_li
 	}
 
 	/* the hash now owns this reference to the entry */
-	g_hash_table_insert (model->priv->reverse_map, entry, ptr);
+	rhythmdb_query_model_add_entry_iter (model, entry, ptr);
 
 	model->priv->total_duration += rhythmdb_entry_get_ulong (entry, RHYTHMDB_PROP_DURATION);
 	model->priv->total_size += rhythmdb_entry_get_uint64 (entry, RHYTHMDB_PROP_FILE_SIZE);
+	model->priv->total_count++;
+
+	return ptr;
 }
 
 static void
@@ -1202,7 +1225,7 @@ rhythmdb_query_model_insert_into_limited
 	}
 
 	/* the hash now owns this reference to the entry */
-	g_hash_table_insert (model->priv->limited_reverse_map, entry, ptr);
+	rhythmdb_query_model_add_limited_entry_iter (model, entry, ptr);
 }
 
 static void
@@ -1213,7 +1236,7 @@ rhythmdb_query_model_remove_from_main_li
 	int index;
 	GtkTreePath *path;
 
-	ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
+	ptr = rhythmdb_query_model_get_iter_for_entry (model, entry);
 	index = egg_sequence_iter_get_position (ptr);
 
 	path = gtk_tree_path_new ();
@@ -1224,6 +1247,7 @@ rhythmdb_query_model_remove_from_main_li
 
 	model->priv->total_duration -= rhythmdb_entry_get_ulong (entry, RHYTHMDB_PROP_DURATION);
 	model->priv->total_size -= rhythmdb_entry_get_uint64 (entry, RHYTHMDB_PROP_FILE_SIZE);
+	model->priv->total_count--;
 
 	/* take temporary ref */
 	rhythmdb_entry_ref (entry);
@@ -1231,9 +1255,9 @@ rhythmdb_query_model_remove_from_main_li
 	/* find the sequence pointer again in case a row-deleted
 	 * signal handler moved it.
 	 */
-	ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
+	ptr = rhythmdb_query_model_get_iter_for_entry (model, entry);
 	egg_sequence_remove (ptr);
-	g_assert (g_hash_table_remove (model->priv->reverse_map, entry));
+	rhythmdb_query_model_remove_entry_iter (model, entry);
 
 	g_signal_emit (G_OBJECT (model), rhythmdb_query_model_signals[POST_ENTRY_DELETE], 0, entry);
 
@@ -1245,12 +1269,12 @@ static void
 rhythmdb_query_model_remove_from_limited_list (RhythmDBQueryModel *model,
 					       RhythmDBEntry *entry)
 {
-	EggSequenceIter *ptr = g_hash_table_lookup (model->priv->limited_reverse_map, entry);
+	EggSequenceIter *ptr = rhythmdb_query_model_get_iter_for_limited_entry (model, entry);
 
 	/* take temporary ref */
 	rhythmdb_entry_ref (entry);
 	egg_sequence_remove (ptr);
-	g_hash_table_remove (model->priv->limited_reverse_map, entry);
+	rhythmdb_query_model_remove_limited_entry_iter (model, entry);
 	/* release temporary ref */
 	rhythmdb_entry_unref (entry);
 }
@@ -1292,11 +1316,10 @@ rhythmdb_query_model_update_limited_entr
 		/* take temporary ref */
 		rhythmdb_entry_ref (entry);
 		rhythmdb_query_model_remove_from_limited_list (model, entry);
-		rhythmdb_query_model_insert_into_main_list (model, entry, -1);
+		ptr = rhythmdb_query_model_insert_into_main_list (model, entry, -1);
 		/* release temporary ref */
 		rhythmdb_entry_unref (entry);
 
-		ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
 		iter.stamp = model->priv->stamp;
 		iter.user_data = ptr;
 		path = rhythmdb_query_model_get_path (GTK_TREE_MODEL (model),
@@ -1399,7 +1422,7 @@ rhythmdb_query_model_do_reorder (RhythmD
 		}
 	}
 
-	ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
+	ptr = rhythmdb_query_model_get_iter_for_entry (model, entry);
 	iter.stamp = model->priv->stamp;
 	iter.user_data = ptr;
 	path = rhythmdb_query_model_get_path (GTK_TREE_MODEL (model),
@@ -1412,7 +1435,7 @@ rhythmdb_query_model_do_reorder (RhythmD
 	rhythmdb_entry_ref (entry);
 
 	/* it may have moved, check for a re-order */
-	g_hash_table_remove (model->priv->reverse_map, entry);
+	rhythmdb_query_model_remove_entry_iter (model, entry);
 	old_pos = egg_sequence_iter_get_position (ptr);
 	egg_sequence_remove (ptr);
 
@@ -1422,7 +1445,7 @@ rhythmdb_query_model_do_reorder (RhythmD
 	new_pos = egg_sequence_iter_get_position (ptr);
 
 	/* the hash now owns this reference to the entry */
-	g_hash_table_insert (model->priv->reverse_map, entry, ptr);
+	rhythmdb_query_model_add_entry_iter (model, entry, ptr);
 
 	return rhythmdb_query_model_emit_reorder (model, old_pos, new_pos);
 }
@@ -1439,24 +1462,23 @@ rhythmdb_query_model_do_insert (RhythmDB
 	g_assert (model->priv->show_hidden || !rhythmdb_entry_get_boolean (entry, RHYTHMDB_PROP_HIDDEN));
 
 	/* we check again if the entry already exists in the hash table */
-	if (g_hash_table_lookup (model->priv->reverse_map, entry) != NULL)
+	if (rhythmdb_query_model_contains_entry (model, entry))
 		return;
 
 	/* take temporary ref */
 	rhythmdb_entry_ref (entry);
 
-	ptr = g_hash_table_lookup (model->priv->limited_reverse_map, entry);
+	ptr = rhythmdb_query_model_get_iter_for_limited_entry (model, entry);
 	if (ptr != NULL) {
 		rhythmdb_query_model_remove_from_limited_list (model, entry);
 	}
 
-	rhythmdb_query_model_insert_into_main_list (model, entry, index);
+	ptr = rhythmdb_query_model_insert_into_main_list (model, entry, index);
 
 	/* release temporary ref */
 	rhythmdb_entry_unref (entry);
 
 	/* it was added to the main list, send out the inserted signal */
-	ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
 	iter.stamp = model->priv->stamp;
 	iter.user_data = ptr;
 	path = rhythmdb_query_model_get_path (GTK_TREE_MODEL (model),
@@ -1474,14 +1496,14 @@ rhythmdb_query_model_filter_out_entry (R
 {
 	EggSequenceIter *ptr;
 
-	ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
+	ptr = rhythmdb_query_model_get_iter_for_entry (model, entry);
 	if (ptr != NULL) {
 		rhythmdb_query_model_remove_from_main_list (model, entry);
 		rhythmdb_query_model_update_limited_entries (model);
 		return;
 	}
 
-	ptr = g_hash_table_lookup (model->priv->limited_reverse_map, entry);
+	ptr = rhythmdb_query_model_get_iter_for_limited_entry (model, entry);
 	if (ptr != NULL) {
 		rhythmdb_query_model_remove_from_limited_list (model, entry);
 		rhythmdb_query_model_update_limited_entries (model);
@@ -1498,7 +1520,7 @@ rhythmdb_query_model_move_entry (RhythmD
 	EggSequenceIter *nptr;
 	gint old_pos;
 
-	ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
+	ptr = rhythmdb_query_model_get_iter_for_entry (model, entry);
 	if (ptr == NULL)
 		return;
 
@@ -1512,14 +1534,14 @@ rhythmdb_query_model_move_entry (RhythmD
 	/* remove from old position */
 	old_pos = egg_sequence_iter_get_position (ptr);
 	egg_sequence_remove (ptr);
-	g_hash_table_remove (model->priv->reverse_map, entry);
+	rhythmdb_query_model_remove_entry_iter (model, entry);
 
 	/* insert into new position */
 	egg_sequence_insert_before (nptr, entry);
 	ptr = egg_sequence_iter_prev (nptr);
 
 	/* the hash now owns this reference to the entry */
-	g_hash_table_insert (model->priv->reverse_map, entry, ptr);
+	rhythmdb_query_model_add_entry_iter (model, entry, ptr);
 
 	rhythmdb_query_model_emit_reorder (model, old_pos, index);
 }
@@ -1528,8 +1550,8 @@ gboolean
 rhythmdb_query_model_remove_entry (RhythmDBQueryModel *model,
 				   RhythmDBEntry *entry)
 {
-	gboolean present = (g_hash_table_lookup (model->priv->reverse_map, entry) == NULL) ||
-			    (g_hash_table_lookup (model->priv->limited_reverse_map, entry) == NULL);
+	gboolean present = (!rhythmdb_query_model_contains_entry (model, entry)) ||
+			   (!rhythmdb_query_model_contains_limited_entry (model, entry));
 	g_return_val_if_fail (present, FALSE);
 
 	if (model->priv->base_model != NULL)
@@ -1554,7 +1576,7 @@ rhythmdb_query_model_entry_to_iter (Rhyt
 {
 	EggSequenceIter *ptr;
 
-	ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
+	ptr = rhythmdb_query_model_get_iter_for_entry (model, entry);
 
 	if (G_UNLIKELY (ptr == NULL)) {
 		/* Invalidate iterator so future uses break quickly. */
@@ -1822,7 +1844,7 @@ rhythmdb_query_model_drag_data_received 
 				gint old_pos = 0;
 				gint new_pos;
 
-				old_ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
+				old_ptr = rhythmdb_query_model_get_iter_for_entry (model, entry);
 				/* trying to drag drop an entry on itself ! */
 				if (old_ptr == ptr)
 					continue;
@@ -1838,7 +1860,7 @@ rhythmdb_query_model_drag_data_received 
 
 					old_pos = egg_sequence_iter_get_position (old_ptr);
 					egg_sequence_remove (old_ptr);
-					g_assert (g_hash_table_remove (model->priv->reverse_map, entry));
+					rhythmdb_query_model_remove_entry_iter (model, entry);
 				} else {
 					model->priv->reorder_drag_and_drop = FALSE;
 				}
@@ -1851,7 +1873,7 @@ rhythmdb_query_model_drag_data_received 
 				tem_iter.stamp = model->priv->stamp;
 				tem_iter.user_data = tem_ptr;
 				/* the hash now owns this reference to the entry */
-				g_hash_table_insert (model->priv->reverse_map, entry, tem_ptr);
+				rhythmdb_query_model_add_entry_iter (model, entry, tem_ptr);
 
 				if (old_ptr) {
 					rb_debug ("moving entry %p from %d to %d", entry, old_pos, new_pos);
@@ -2159,9 +2181,9 @@ apply_updated_entry_sequence (RhythmDBQu
 		gpointer entry = egg_sequence_get (ptr);
 		EggSequenceIter *old_ptr;
 
-		old_ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
+		old_ptr = rhythmdb_query_model_get_iter_for_entry (model, entry);
 		reorder_map[i] = egg_sequence_iter_get_position (old_ptr);
-		g_hash_table_replace (model->priv->reverse_map, rhythmdb_entry_ref (entry), ptr);
+		rhythmdb_query_model_add_entry_iter (model, rhythmdb_entry_ref (entry), ptr);
 
 		ptr = egg_sequence_iter_next (ptr);
 	}
@@ -2248,7 +2270,7 @@ rhythmdb_query_model_child_index_to_base
 		return -1;
 	entry = (RhythmDBEntry*)egg_sequence_get (ptr);
 
-	ptr = g_hash_table_lookup (model->priv->base_model->priv->reverse_map, entry);
+	ptr = rhythmdb_query_model_get_iter_for_entry (model->priv->base_model, entry);
 	g_assert (ptr); /* all child model entries are in the base model */
 
 	return egg_sequence_iter_get_position (ptr);
@@ -2270,7 +2292,7 @@ rhythmdb_query_model_base_index_to_child
 		return -1;
 	entry = (RhythmDBEntry*)egg_sequence_get (ptr);
 
-	ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
+	ptr = rhythmdb_query_model_get_iter_for_entry (model, entry);
 	if (ptr == NULL)
 		return -1;
 
@@ -2282,7 +2304,7 @@ static int
 rhythmdb_query_model_get_entry_index (RhythmDBQueryModel *model,
 				      RhythmDBEntry *entry)
 {
-	EggSequenceIter *ptr = g_hash_table_lookup (model->priv->reverse_map, entry);
+	EggSequenceIter *ptr = rhythmdb_query_model_get_iter_for_entry (model, entry);
 
 	if (ptr)
 		return egg_sequence_iter_get_position (ptr);
@@ -2311,7 +2333,7 @@ rhythmdb_query_model_base_row_inserted (
 	if (rhythmdb_evaluate_query (model->priv->db, model->priv->query, entry)) {
 		/* find the closest previous entry that is in the filter model, and it it after that */
 		prev_entry = rhythmdb_query_model_get_previous_from_entry (base_model, entry);
-		while (prev_entry && g_hash_table_lookup (model->priv->reverse_map, prev_entry) == NULL) {
+		while (prev_entry && !rhythmdb_query_model_contains_entry (model, prev_entry)) {
 			rhythmdb_entry_unref (prev_entry);
 			prev_entry = rhythmdb_query_model_get_previous_from_entry (base_model, prev_entry);
 		}
@@ -2372,7 +2394,7 @@ typedef struct {
 static void
 _base_rows_reordered_foreach_cb (RhythmDBEntry *entry, _BaseRowsReorderedData *data)
 {
-	if (g_hash_table_lookup (data->model->priv->reverse_map, entry))
+	if (rhythmdb_query_model_contains_entry (data->model, entry))
 		egg_sequence_append (data->new_entries, entry);
 }
 
@@ -2401,7 +2423,7 @@ rhythmdb_query_model_base_entry_removed 
 					 RhythmDBEntry *entry,
 					 RhythmDBQueryModel *model)
 {
-	if (g_hash_table_lookup (model->priv->reverse_map, entry)) {
+	if (rhythmdb_query_model_contains_entry (model, entry)) {
 		/* propagate the signal out to any attached property models */
 		g_signal_emit (G_OBJECT (model),
 			       rhythmdb_query_model_signals[ENTRY_REMOVED], 0,
@@ -2754,7 +2776,7 @@ rhythmdb_query_model_within_limit (Rhyth
 			gulong current_count;
 
 			limit_count = g_value_get_ulong (g_value_array_get_nth (model->priv->limit_value, 0));
-			current_count = g_hash_table_size (model->priv->reverse_map);
+			current_count = model->priv->total_count;
 
 			if (entry)
 				current_count++;
@@ -2835,3 +2857,184 @@ rhythmdb_query_model_reapply_query_cb (R
 	GDK_THREADS_LEAVE ();
 	return TRUE;
 }
+
+
+static gboolean
+rhythmdb_query_model_get_sorting (RhythmDBQueryModel *model,
+				  GCompareDataFunc *sort_func,
+				  gpointer *sort_data,
+				  gboolean *sort_reverse)
+{
+	RhythmDBQueryModel *m;
+
+	for (m = model; m != NULL; m = m->priv->base_model) {
+		if (model->priv->sort_func != NULL) {
+			if (sort_func != NULL)
+				*sort_func = model->priv->sort_func;
+			if (sort_data != NULL)
+				*sort_data = model->priv->sort_data;
+			if (sort_reverse != NULL)
+				*sort_reverse = model->priv->sort_reverse;
+			return TRUE;
+		}
+	}
+
+	return FALSE;
+}
+
+
+static gboolean
+rhythmdb_query_model_contains_entry (RhythmDBQueryModel *model, RhythmDBEntry *entry)
+{
+	return (rhythmdb_query_model_get_iter_for_entry (model, entry) != NULL);
+}
+
+static EggSequenceIter*
+rhythmdb_query_model_get_iter_for_entry (RhythmDBQueryModel *model, RhythmDBEntry *entry)
+{
+	GCompareDataFunc sort_func;
+	gpointer sort_data;
+	gboolean sort_reverse;
+
+	if (rhythmdb_query_model_get_sorting (model, &sort_func, &sort_data, &sort_reverse)) {
+		/* we have a sorting order, so we can find the entry in log2(n) time */
+		struct ReverseSortData reverse_data;
+		EggSequenceIter *iter;
+
+		if (sort_reverse) {
+			reverse_data.func = sort_func;
+			reverse_data.data = sort_data;
+			sort_func = (GCompareDataFunc) _reverse_sorting_func;
+			sort_data = &reverse_data;
+		}
+
+		iter = egg_sequence_search (model->priv->entries, entry,
+					    sort_func, sort_data);
+		/* egg_sequence_search returns the closest node /strictly greater/
+		 * than the thing we're looking for. So we need to go back one, and
+		 * check if it was the right one.
+		 */
+		iter = egg_sequence_iter_prev (iter);
+		if (iter == NULL || egg_sequence_iter_is_end (iter)) {
+#ifdef RHYTHMDB_DEBUG
+			g_assert (NULL == g_hash_table_lookup (model->priv->reverse_map, entry));
+#endif
+			return NULL;
+		} else {
+			if (egg_sequence_get (iter) != entry) {
+				iter = NULL;
+			}
+#ifdef RHYTHMDB_DEBUG
+			g_assert (iter == g_hash_table_lookup (model->priv->reverse_map, entry));
+#endif
+			return iter;
+		}
+	} else {
+		return g_hash_table_lookup (model->priv->reverse_map, entry);
+	}
+}
+
+static void
+rhythmdb_query_model_add_entry_iter (RhythmDBQueryModel *model,
+				     RhythmDBEntry *entry,
+				     EggSequenceIter *iter)
+{
+#ifndef RHYTHMDB_DEBUG
+	if (rhythmdb_query_model_get_sorting (model, NULL, NULL, NULL)) {
+		/* release the reference that the hash table would have kept */
+		rhythmdb_entry_unref (entry);
+	} else {
+#else
+	{
+#endif
+		g_hash_table_replace (model->priv->reverse_map, entry, iter);
+	}
+}
+
+static void
+rhythmdb_query_model_remove_entry_iter (RhythmDBQueryModel *model,
+				       RhythmDBEntry *entry)
+{
+#ifndef RHYTHMDB_DEBUG
+	if (!rhythmdb_query_model_get_sorting (model, NULL, NULL, NULL))
+#endif
+		g_hash_table_remove (model->priv->reverse_map, entry);
+}
+
+static gboolean
+rhythmdb_query_model_contains_limited_entry (RhythmDBQueryModel *model, RhythmDBEntry *entry)
+{
+	return (rhythmdb_query_model_get_iter_for_limited_entry (model, entry) != NULL);
+}
+
+static EggSequenceIter*
+rhythmdb_query_model_get_iter_for_limited_entry (RhythmDBQueryModel *model, RhythmDBEntry *entry)
+{
+	GCompareDataFunc sort_func;
+	gpointer sort_data;
+	gboolean sort_reverse;
+
+	if (rhythmdb_query_model_get_sorting (model, &sort_func, &sort_data, &sort_reverse)) {
+		/* we have a sorting order, so we can find the entry in log2(n) time */
+		struct ReverseSortData reverse_data;
+		EggSequenceIter *iter;
+
+		if (sort_reverse) {
+			reverse_data.func = sort_func;
+			reverse_data.data = sort_data;
+			sort_func = (GCompareDataFunc) _reverse_sorting_func;
+			sort_data = &reverse_data;
+		}
+
+		iter = egg_sequence_search (model->priv->limited_entries, entry,
+					    sort_func, sort_data);
+		/* egg_sequence_search returns the closest node /strictly greater/
+		 * than the thing we're looking for. So we need to go back one, and
+		 * check if it was the right one.
+		 */
+		iter = egg_sequence_iter_prev (iter);
+		if (iter == NULL || egg_sequence_iter_is_end (iter)) {
+#ifdef RHYTHMDB_DEBUG
+			g_assert (NULL == g_hash_table_lookup (model->priv->limited_reverse_map, entry));
+#endif
+			return NULL;
+		} else {
+			if (egg_sequence_get (iter) != entry) {
+				iter = NULL;
+			}
+#ifdef RHYTHMDB_DEBUG
+			g_assert (iter == g_hash_table_lookup (model->priv->limited_reverse_map, entry));
+#endif
+			return iter;
+		}
+	} else {
+		return g_hash_table_lookup (model->priv->limited_reverse_map, entry);
+	}
+}
+
+static void
+rhythmdb_query_model_add_limited_entry_iter (RhythmDBQueryModel *model,
+				     RhythmDBEntry *entry,
+				     EggSequenceIter *iter)
+{
+#ifndef RHYTHMDB_DEBUG
+	if (rhythmdb_query_model_get_sorting (model, NULL, NULL, NULL)) {
+		/* release the reference that the hash table would have kept */
+		rhythmdb_entry_unref (entry);
+	} else {
+#else
+	{
+#endif
+		g_hash_table_replace (model->priv->limited_reverse_map, entry, iter);
+	}
+}
+
+static void
+rhythmdb_query_model_remove_limited_entry_iter (RhythmDBQueryModel *model,
+				       RhythmDBEntry *entry)
+{
+#ifndef RHYTHMDB_DEBUG
+	if (!rhythmdb_query_model_get_sorting (model, NULL, NULL, NULL))
+#endif
+		g_hash_table_remove (model->priv->limited_reverse_map, entry);
+}
Index: bindings/python/rhythmdb.defs
===================================================================
--- bindings/python/rhythmdb.defs	(revision 4815)
+++ bindings/python/rhythmdb.defs	(working copy)
@@ -251,6 +251,15 @@
   )
 )
 
+(define-method query_to_string
+  (of-object "RhythmDB")
+  (c-name "rhythmdb_query_to_string")
+  (return-type "char*")
+  (parameters
+    '("RhythmDBQuery*" "query")
+  )
+)
+
 (define-method query_deserialize
   (of-object "RhythmDB")
   (c-name "rhythmdb_query_deserialize")
