X-Git-Url: https://git.kernel.dk/?p=fio.git;a=blobdiff_plain;f=log.c;h=2b90f452e8c22bca740b235ebb26094a12892574;hp=dbca3ccb7f023f37df7d4a9a52aa291cfd45a7a7;hb=4b87898e8d76aaf05baec83077a11311c1447397;hpb=171e38ab2b03683a9d559ee9fffcbe052484baba

diff --git a/log.c b/log.c
index dbca3ccb..2b90f452 100644
--- a/log.c
+++ b/log.c
@@ -29,11 +29,11 @@ int read_iolog_get(struct thread_data *td, struct io_u *io_u)
 void prune_io_piece_log(struct thread_data *td)
 {
 	struct io_piece *ipo;
+	struct rb_node *n;
 
-	while (!list_empty(&td->io_hist_list)) {
-		ipo = list_entry(td->io_hist_list.next, struct io_piece, list);
-
-		list_del(&ipo->list);
+	while ((n = rb_first(&td->io_hist_tree)) != NULL) {
+		ipo = rb_entry(n, struct io_piece, rb_node);
+		rb_erase(n, &td->io_hist_tree);
 		free(ipo);
 	}
 }
@@ -43,36 +43,33 @@ void prune_io_piece_log(struct thread_data *td)
  */
 void log_io_piece(struct thread_data *td, struct io_u *io_u)
 {
-	struct io_piece *ipo = malloc(sizeof(struct io_piece));
-	struct list_head *entry;
+	struct rb_node **p = &td->io_hist_tree.rb_node;
+	struct rb_node *parent = NULL;
+	struct io_piece *ipo, *__ipo;
 
-	INIT_LIST_HEAD(&ipo->list);
+	ipo = malloc(sizeof(struct io_piece));
+	memset(&ipo->rb_node, 0, sizeof(ipo->rb_node));
 	ipo->file = io_u->file;
 	ipo->offset = io_u->offset;
 	ipo->len = io_u->buflen;
 
 	/*
-	 * for random io where the writes extend the file, it will typically
-	 * be laid out with the block scattered as written. it's faster to
-	 * read them in in that order again, so don't sort
-	 */
-	if (!td_random(td) || !td->o.overwrite) {
-		list_add_tail(&ipo->list, &td->io_hist_list);
-		return;
-	}
-
-	/*
-	 * for random io, sort the list so verify will run faster
+	 * Sort the entry into the verification list
 	 */
-	entry = &td->io_hist_list;
-	while ((entry = entry->prev) != &td->io_hist_list) {
-		struct io_piece *__ipo = list_entry(entry, struct io_piece, list);
-
-		if (__ipo->offset < ipo->offset)
+	while (*p) {
+		parent = *p;
+
+		__ipo = rb_entry(parent, struct io_piece, rb_node);
+		if (ipo->offset < __ipo->offset)
+			p = &(*p)->rb_left;
+		else if (ipo->offset > __ipo->offset)
+			p = &(*p)->rb_right;
+		else
 			break;
 	}
 
-	list_add(&ipo->list, entry);
+	rb_link_node(&ipo->rb_node, parent, p);
+	rb_insert_color(&ipo->rb_node, &td->io_hist_tree);
 }
 
 void write_iolog_close(struct thread_data *td)