Accumulate spacetime graph over alloc_fn.

1 files changed, 209 insertions, 94 deletions

diff --git a/src/spacetime.c b/src/spacetime.c
index ce4a91b..a623b02 100644
--- a/src/spacetime.c
+++ b/src/spacetime.c
@@ -31,6 +31,7 @@
 #define _(x) x
 
 typedef struct _spacetime_data SpacetimeData;
+typedef struct _spacetime_allocator SpacetimeAllocator;
 
 struct _spacetime_data {
     guint time;
@@ -38,11 +39,22 @@ struct _spacetime_data {
     SpacetimeData *next, *prev;
 };
 
+struct _spacetime_allocator {
+    const gchar *alloc_fn;
+    guint64 bytes;
+    guint n_allocs;
+
+    GSList *allocators;
+    guint n_allocators;
+};
+
 struct _spacetime {
     GtkWidget widget;
 
-    Allocator *allocators, **sorted;
+    Allocator *allocators;
+    SpacetimeAllocator *sorted;
     guint n_allocators;
+    GSList *list_mem;
 
     SpacetimeData *data, *tail;
     guint max_time;
@@ -99,94 +111,133 @@ spacetime_realize (GtkWidget *widget)
     attributes.visual = gtk_widget_get_visual (widget);
     attributes.colormap = gtk_widget_get_colormap (widget);
     attributes.event_mask = GDK_BUTTON_PRESS_MASK |
-	GDK_POINTER_MOTION_MASK |
-	GDK_LEAVE_NOTIFY_MASK |
-	GDK_EXPOSURE_MASK;
+	                    GDK_POINTER_MOTION_MASK |
+			    GDK_LEAVE_NOTIFY_MASK |
+			    GDK_EXPOSURE_MASK;
 
     widget->window = gdk_window_new (gtk_widget_get_parent_window (widget),
-	    &attributes,
-	    GDK_WA_X | GDK_WA_Y |
-	    GDK_WA_VISUAL | GDK_WA_COLORMAP);
+	                             &attributes,
+				     GDK_WA_X | GDK_WA_Y |
+				     GDK_WA_VISUAL | GDK_WA_COLORMAP);
     gdk_window_set_user_data (widget->window, widget);
 
     widget->style = gtk_style_attach (widget->style, widget->window);
     gtk_style_set_background (widget->style, widget->window, GTK_STATE_NORMAL);
 }
 
-static gint
-allocators_cmp_by_bytes (gconstpointer A, gconstpointer B)
-{
-    const Allocator *a = *(Allocator **) A, *b = *(Allocator **) B;
-    if (a->max_bytes < b->max_bytes)
-	return 1;
-    if (a->max_bytes > b->max_bytes)
-	return -1;
-    if (a->time_tail->bytes < b->time_tail->bytes)
-	return 1;
-    if (a->time_tail->bytes > b->time_tail->bytes)
-	return -1;
-    if (a->time_tail->n_allocs < b->time_tail->n_allocs)
-	return 1;
-    if (a->time_tail->n_allocs > b->time_tail->n_allocs)
-	return -1;
-    return 0;
-}
-
 #define BORDER 4
 
 static gboolean
-allocator_path (Spacetime *self, const Allocator *A, cairo_t *cr,
-	        const AllocatorTime **_At,
+allocator_path (Spacetime *self,
+	        const SpacetimeAllocator *sA,
+		cairo_t *cr,
 		SpacetimeData **_data)
 {
-    const AllocatorTime *At;
-    guint64 last_bytes;
+    GSList *l;
+    const Allocator *A;
+    const AllocatorTime **At;
+    guint64 bytes;
     SpacetimeData *data, *start, *last;
+    guint n, n_allocators;
+    guint min_time, last_time;
 
     data = *_data;
-    At = *_At;
-    while (At != NULL) {
-	if (At->bytes != At->freed)
-	    break;
-	At = At->next;
+    if (data == NULL)
+	return FALSE;
+
+    At = g_newa (const AllocatorTime *, sA->n_allocators);
+
+    n = 0;
+    min_time = (guint) -1;
+    for (l = sA->allocators; l != NULL; l = g_slist_next (l)) {
+	A = l->data;
+	At[n] = A->time;
+	while (At[n] != NULL && At[n]->time < data->time) {
+	    At[n] = At[n]->next;
+	}
+	while (At[n] != NULL) {
+	    if (At[n]->bytes != At[n]->freed)
+		break;
+	    At[n] = At[n]->next;
+	}
+	if (At[n] != NULL) {
+	    if (At[n]->time < min_time)
+		min_time = At[n]->time;
+	    n++;
+	}
     }
-    if (At == NULL)
+    if (n == 0)
 	return FALSE;
 
+    n_allocators = n;
+
     cairo_new_path (cr);
-    while (data->time < At->time)
+
+    while (data->time < min_time)
 	data = data->next;
-    if (data->prev == NULL)
+    if (data->prev == NULL) {
 	cairo_move_to (cr, 0, 0);
-    else
+	last_time = 0;
+    } else {
 	cairo_move_to (cr, data->prev->time, data->prev->sum_bytes);
+	last_time = data->prev->time;
+    }
     start = data->prev;
     last = data;
 
-    last_bytes = At->bytes - At->freed;
+    bytes = 0;
+    min_time = (guint) -1;
+    for (n = 0; n < n_allocators; n++) {
+	while (At[n] != NULL &&
+	       At[n]->time > last_time &&
+	       At[n]->time <= data->time)
+	{
+	    bytes += At[n]->bytes;
+	    At[n] = At[n]->next;
+	}
+	if (At[n] != NULL && At[n]->time < min_time)
+	    min_time = At[n]->time;
+    }
 
     data->prev_bytes = data->sum_bytes;
-    data->sum_bytes += last_bytes;
+    data->sum_bytes += bytes;
     cairo_line_to (cr, data->time, data->sum_bytes);
     data = data->next;
 
-    for (At = At->next; At != NULL; At = At->next) {
-	while (data->time < At->time) {
+    while (min_time != (guint) -1) {
+	while (data->time < min_time) {
 	    data->prev_bytes = data->sum_bytes;
-	    data->sum_bytes += last_bytes;
+	    data->sum_bytes += bytes;
 	    cairo_line_to (cr, data->time, data->sum_bytes);
 	    last = data;
 	    data = data->next;
+	    if (data == NULL)
+		goto out;
+	}
+
+	bytes = 0;
+	min_time = (guint) -1;
+	last_time = data->prev->time;
+	for (n = 0; n < n_allocators; n++) {
+	    while (At[n] != NULL &&
+		   At[n]->time > last_time &&
+		   At[n]->time <= data->time)
+	    {
+		bytes += At[n]->bytes;
+		At[n] = At[n]->next;
+	    }
+	    if (At[n] != NULL && At[n]->time < min_time)
+		min_time = At[n]->time;
 	}
-	last_bytes = At->bytes - At->freed;
-	if (last_bytes == 0)
+	if (bytes == 0)
 	    break;
     }
 
-    if (last_bytes) {
+out:
+    if (bytes) {
 	while (data != NULL) {
 	    data->prev_bytes = data->sum_bytes;
-	    data->sum_bytes += last_bytes;
+	    data->sum_bytes += bytes;
 	    cairo_line_to (cr, data->time, data->sum_bytes);
 	    last = data;
 	    data = data->next;
@@ -200,8 +251,7 @@ allocator_path (Spacetime *self, const Allocator *A, cairo_t *cr,
 
     cairo_close_path (cr);
 
-    *_At = At;
-    *_data = data;
+    *_data = last->next;
 
     return TRUE;
 }
@@ -214,13 +264,98 @@ _cairo_set_source_hsv (cairo_t *cr, gdouble h, gdouble s, gdouble v)
     cairo_set_source_rgb (cr, rgb[0], rgb[1], rgb[2]);
 }
 
+static void
+ht_to_array (const gchar *alloc_fn, GSList *list, SpacetimeAllocator **sorted)
+{
+    guint64 bytes;
+    guint n_allocs;
+    guint n_allocators;
+    GSList *l;
+
+    (*sorted)->alloc_fn = alloc_fn;
+    (*sorted)->allocators = list;
+
+    n_allocators = 0;
+    n_allocs = 0;
+    bytes = 0;
+    for (l = list; l != NULL; l = g_slist_next (l)) {
+	Allocator *A = l->data;
+	n_allocators++;
+	n_allocs += A->time_tail->n_allocs;
+	bytes += A->max_bytes;
+    }
+    (*sorted)->bytes = bytes;
+    (*sorted)->n_allocs = n_allocs;
+    (*sorted)->n_allocators = n_allocators;
+
+    ++*sorted;
+}
+
+static gint
+allocators_cmp_by_bytes (gconstpointer A, gconstpointer B)
+{
+    const SpacetimeAllocator *a = A, *b = B;
+    if (a->bytes < b->bytes)
+	return 1;
+    if (a->bytes > b->bytes)
+	return -1;
+    if (a->n_allocs < b->n_allocs)
+	return 1;
+    if (a->n_allocs > b->n_allocs)
+	return -1;
+    return 0;
+}
+
+static void
+_spacetime_accumulate (Spacetime *self)
+{
+    Allocator *A;
+    guint n_allocators, n;
+    guint64 max_bytes;
+    GSList *list;
+    SpacetimeAllocator *sorted;
+    GHashTable *ht;
+
+    n_allocators = 0;
+    for (A = self->allocators; A != NULL; A = A->next)
+	n_allocators++;
+
+    g_free (self->list_mem);
+    self->list_mem = g_new (GSList, n_allocators);
+    list = self->list_mem;
+
+    ht = g_hash_table_new (NULL, NULL);
+
+    for (A = self->allocators; A != NULL; A = A->next) {
+	list->next = g_hash_table_lookup (ht, A->alloc_fn);
+	list->data = A;
+	g_hash_table_replace (ht, (gpointer) A->alloc_fn, list++);
+    }
+
+    n_allocators = g_hash_table_size (ht);
+    sorted = self->sorted = g_new (SpacetimeAllocator, n_allocators);
+    g_hash_table_foreach (ht, (GHFunc) ht_to_array, &sorted);
+    g_hash_table_destroy (ht);
+
+    qsort (self->sorted, n_allocators, sizeof (SpacetimeAllocator),
+	    allocators_cmp_by_bytes);
+
+    max_bytes = self->sorted[0].bytes;
+    for (n = 1; n < n_allocators; n++) {
+	const SpacetimeAllocator *sA = &self->sorted[n];
+	if (sA->bytes < max_bytes / 40)
+	    break;
+    }
+    self->n_allocators = n;
+}
+
 static gboolean
 spacetime_expose (GtkWidget *widget, GdkEventExpose *ev)
 {
     Spacetime *self = (Spacetime *) widget;
     SpacetimeData *data, *first;
     cairo_t *cr;
-    Allocator *A, **sorted;
+    SpacetimeAllocator *sorted;
     guint n_allocators, n;
     gboolean redraw;
     gdouble y, width, height;
@@ -235,30 +370,11 @@ spacetime_expose (GtkWidget *widget, GdkEventExpose *ev)
 
     first = self->data;
     if (first != NULL) {
-	if (self->sorted == NULL) {
-	    n_allocators = 0;
-	    for (A = self->allocators; A != NULL; A = A->next)
-		n_allocators++;
-	    sorted = g_new (Allocator *, n_allocators);
-	    n_allocators = 0;
-	    for (A = self->allocators; A != NULL; A = A->next)
-		sorted[n_allocators++] = A;
-	    qsort (sorted, n_allocators, sizeof (Allocator *),
-		   allocators_cmp_by_bytes);
-
-	    for (n = 0; n < n_allocators; n++) {
-		A = sorted[n];
-		if (A->max_bytes < self->max_bytes / 40)
-		    break;
-	    }
-	    n_allocators = n;
+	if (self->sorted == NULL)
+	    _spacetime_accumulate (self);
 
-	    self->n_allocators = n_allocators;
-	    self->sorted = sorted;
-	} else {
-	    n_allocators = self->n_allocators;
-	    sorted = self->sorted;
-	}
+	n_allocators = self->n_allocators;
+	sorted = self->sorted;
 
 	cairo_set_line_width (cr, 1);
 
@@ -272,15 +388,12 @@ spacetime_expose (GtkWidget *widget, GdkEventExpose *ev)
 	    data->sum_bytes = 0.;
 
 	for (n = 0; n < n_allocators; n++) {
-	    const AllocatorTime *At;
-	    A = sorted[n];
-	    At = A->time;
 	    data = first;
-	    while (allocator_path (self, A, cr, &At, &data)) {
-		_cairo_set_source_hsv (cr, n / (gdouble) n_allocators, .6, .6);
+	    while (allocator_path (self, &sorted[n], cr, &data)) {
+		_cairo_set_source_hsv (cr, n / (4 * G_PI) + n / (gdouble) n_allocators, .66, .66);
 		cairo_fill_preserve (cr);
 
-		_cairo_set_source_hsv (cr, n / (gdouble) n_allocators, .9, .9);
+		_cairo_set_source_hsv (cr, n / (4 * G_PI) + n / (gdouble) n_allocators, .9, .9);
 		cairo_stroke (cr);
 	    }
 	}
@@ -329,9 +442,7 @@ spacetime_expose (GtkWidget *widget, GdkEventExpose *ev)
 	width = 0;
 	height = 0;
 	for (n = 0; n < n_allocators; n++) {
-	    A = sorted[n];
-
-	    pango_layout_set_text (text, A->alloc_fn, -1);
+	    pango_layout_set_text (text, sorted[n].alloc_fn, -1);
 	    pango_layout_get_pixel_extents (text, NULL, &logical);
 
 	    height += logical.height + 4;
@@ -348,17 +459,22 @@ spacetime_expose (GtkWidget *widget, GdkEventExpose *ev)
 	cairo_set_source_rgb (cr, 0.3, 0.3, 0.3);
 	cairo_stroke (cr);
 
+	cairo_set_line_width (cr, 1.);
+
 	y = 2 * BORDER;
 	for (n = 0; n < n_allocators; n++) {
-	    A = sorted[n];
+	    _cairo_set_source_hsv (cr, n / (4 * G_PI) + n / (gdouble) n_allocators, .66, .66);
 
-	    _cairo_set_source_hsv (cr, n / (gdouble) n_allocators, .6, .6);
-
-	    pango_layout_set_text (text, A->alloc_fn, -1);
+	    pango_layout_set_text (text, sorted[n].alloc_fn, -1);
 	    pango_layout_get_pixel_extents (text, NULL, &logical);
 
 	    cairo_rectangle (cr, 2*BORDER + 10, y, 24, logical.height);
-	    cairo_fill (cr);
+	    cairo_fill_preserve (cr);
+	    cairo_save (cr);
+	    _cairo_set_source_hsv (cr, n / (4 * G_PI) + n / (gdouble) n_allocators, .9, .9);
+	    cairo_stroke (cr);
+	    cairo_restore (cr);
+
 	    cairo_move_to (cr, 2*BORDER + 34 + 4, y);
 	    pango_cairo_show_layout (cr, text);
 	    y += logical.height + 4;
@@ -407,24 +523,22 @@ spacetime_query_tooltip (GtkWidget  *widget,
 	data->sum_bytes = 0.;
 
     for (n = 0; n < self->n_allocators; n++) {
-	const Allocator *A = self->sorted[n];
-	const AllocatorTime *At = A->time;
 	data = self->data;
-	while (allocator_path (self, A, cr, &At, &data)) {
+	while (allocator_path (self, &self->sorted[n], cr, &data)) {
 	    if (cairo_in_fill (cr, xx, yy)) {
 		char *text;
 		gchar bytes[160], blocks[80];
 		gint len;
 
-		len = g_snprintf (bytes + 80, 80, "%" G_GUINT64_FORMAT, A->time_tail->bytes);
+		len = g_snprintf (bytes + 80, 80, "%" G_GUINT64_FORMAT, self->sorted[n].bytes);
 		pretty_print_number (bytes + 80, len, bytes);
 
-		len = g_snprintf (blocks + 40, 40, "%d", A->time_tail->n_allocs);
+		len = g_snprintf (blocks + 40, 40, "%d", self->sorted[n].n_allocs);
 		pretty_print_number (blocks + 40, len, blocks);
 
 		text = g_strdup_printf (
 			"%s: Allocated %s bytes over %s blocks.",
-			A->alloc_fn, bytes, blocks);
+			self->sorted[n].alloc_fn, bytes, blocks);
 		gtk_tooltip_set_text (tooltip, text);
 		g_free (text);
 
@@ -446,6 +560,7 @@ spacetime_finalize (GObject *object)
     Spacetime *self = (Spacetime *) object;
 
     g_free (self->sorted);
+    g_free (self->list_mem);
 
     G_OBJECT_CLASS (spacetime_parent_class)->finalize (object);
 }