# HG changeset patch # User gqview # Date 1112989405 0 # Node ID e46aedb70f67ef3c341b646842cb8a725c08c594 # Parent 772fe5a509b1248c9ebfdf667b3ce49f39ebf838 Fri Apr 8 15:31:38 2005 John Ellis * pan-view.c: Optimize pan_layout_intersect by dividing object list into smaller sets (of ~ 1000 each) grouped by coordinates, this makes drawing tiles much faster when the window contains > 100,000 images. This adds the complexity of walking two lists when searching for a specific item, but the speed increase is worth it. ##### Note: GQview CVS on sourceforge is not always up to date, please use ##### ##### an offical release when making enhancements and translation updates. ##### diff -r 772fe5a509b1 -r e46aedb70f67 ChangeLog --- a/ChangeLog Thu Apr 07 12:50:57 2005 +0000 +++ b/ChangeLog Fri Apr 08 19:43:25 2005 +0000 @@ -1,3 +1,11 @@ +Fri Apr 8 15:31:38 2005 John Ellis + + * pan-view.c: Optimize pan_layout_intersect by dividing object list + into smaller sets (of ~ 1000 each) grouped by coordinates, this makes + drawing tiles much faster when the window contains > 100,000 images. + This adds the complexity of walking two lists when searching for a + specific item, but the speed increase is worth it. + Thu Apr 7 08:42:54 2005 John Ellis * pixbuf-renderer.c (pr_queue_to_tiles): Fix logic in test for diff -r 772fe5a509b1 -r e46aedb70f67 src/pan-view.c --- a/src/pan-view.c Thu Apr 07 12:50:57 2005 +0000 +++ b/src/pan-view.c Fri Apr 08 19:43:25 2005 +0000 @@ -209,6 +209,8 @@ gint image_size; GList *list; + GList *list_static; + GList *list_grid; GList *cache_list; GList *cache_todo; @@ -227,6 +229,15 @@ gint idle_id; }; +typedef struct _PanGrid PanGrid; +struct _PanGrid { + gint x; + gint y; + gint w; + gint h; + GList *list; +}; + typedef struct _PanCacheData PanCacheData; struct _PanCacheData { FileData fd; @@ -469,6 +480,135 @@ return TRUE; } +/* + *----------------------------------------------------------------------------- + * item grid + *----------------------------------------------------------------------------- + */ + +static void pan_grid_clear(PanWindow *pw) +{ + GList *work; + + work = pw->list_grid; + while (work) + { + PanGrid *pg; + + pg = work->data; + work = work->next; + + g_list_free(pg->list); + g_free(pg); + } + + g_list_free(pw->list_grid); + pw->list_grid = NULL; + + pw->list = g_list_concat(pw->list, pw->list_static); + pw->list_static = NULL; +} + +static void pan_grid_build(PanWindow *pw, gint width, gint height, gint grid_size) +{ + GList *work; + gint col, row; + gint cw, ch; + gint l; + gdouble total; + gdouble s; + gdouble aw, ah; + gint i, j; + + pan_grid_clear(pw); + + l = g_list_length(pw->list); + + if (l < 1) return; + + total = (gdouble)width * (gdouble)height / (gdouble)l; + s = sqrt(total); + + aw = (gdouble)width / s; + ah = (gdouble)height / s; + + col = (gint)(sqrt((gdouble)l / grid_size) * width / height + 0.999); + col = CLAMP(col, 1, l / grid_size + 1); + row = (gint)((gdouble)l / grid_size / col); + if (row < 1) row = 1; + + /* limit minimum size of grid so that a tile will always fit regardless of position */ + cw = MAX((gint)ceil((gdouble)width / col), PAN_TILE_SIZE * 2); + ch = MAX((gint)ceil((gdouble)height / row), PAN_TILE_SIZE * 2); + + row = row * 2 - 1; + col = col * 2 - 1; + + printf("intersect speedup grid is %dx%d, based on %d average per grid\n", col, row, grid_size); + + for (j = 0; j < row; j++) + for (i = 0; i < col; i++) + { + if ((i + 1) * cw / 2 < width && (j + 1) * ch / 2 < height) + { + PanGrid *pg; + + pg = g_new0(PanGrid, 1); + pg->x = i * cw / 2; + pg->y = j * ch / 2; + pg->w = cw; + pg->h = ch; + pg->list = NULL; + + pw->list_grid = g_list_prepend(pw->list_grid, pg); + + if (debug) printf("grid section: %d,%d (%dx%d)\n", pg->x, pg->y, pg->w, pg->h); + } + } + + work = pw->list; + while (work) + { + PanItem *pi; + GList *grid; + + pi = work->data; + work = work->next; + + grid = pw->list_grid; + while (grid) + { + PanGrid *pg; + gint rx, ry, rw, rh; + + pg = grid->data; + grid = grid->next; + + if (util_clip_region(pi->x, pi->y, pi->width, pi->height, + pg->x, pg->y, pg->w, pg->h, + &rx, &ry, &rw, &rh)) + { + pg->list = g_list_prepend(pg->list, pi); + } + } + } + + work = pw->list_grid; + while (work) + { + PanGrid *pg; + + pg = work->data; + work = work->next; + + pg->list = g_list_reverse(pg->list); + } + + pw->list_static = pw->list; + pw->list = NULL; +} + + /* *----------------------------------------------------------------------------- @@ -493,6 +633,8 @@ { GList *work; + pan_grid_clear(pw); + work = pw->list; while (work) { @@ -843,21 +985,31 @@ } work = work->prev; } + work = g_list_last(pw->list_static); + while (work) + { + PanItem *pi; + + pi = work->data; + if ((pi->type == type || type == ITEM_NONE) && + pi->key && strcmp(pi->key, key) == 0) + { + return pi; + } + work = work->prev; + } return NULL; } /* when ignore_case and partial are TRUE, path should be converted to lower case */ -static GList *pan_item_find_by_path(PanWindow *pw, ItemType type, const gchar *path, - gint ignore_case, gint partial) +static GList *pan_item_find_by_path_l(GList *list, GList *search_list, + ItemType type, const gchar *path, + gint ignore_case, gint partial) { - GList *list = NULL; GList *work; - if (!path) return NULL; - if (partial && path[0] == '/') return NULL; - - work = g_list_last(pw->list); + work = g_list_last(search_list); while (work) { PanItem *pi; @@ -903,14 +1055,29 @@ work = work->prev; } + return list; +} + +/* when ignore_case and partial are TRUE, path should be converted to lower case */ +static GList *pan_item_find_by_path(PanWindow *pw, ItemType type, const gchar *path, + gint ignore_case, gint partial) +{ + GList *list = NULL; + + if (!path) return NULL; + if (partial && path[0] == '/') return NULL; + + list = pan_item_find_by_path_l(list, pw->list_static, type, path, ignore_case, partial); + list = pan_item_find_by_path_l(list, pw->list, type, path, ignore_case, partial); + return g_list_reverse(list); } -static PanItem *pan_item_find_by_coord(PanWindow *pw, ItemType type, gint x, gint y, const gchar *key) +static PanItem *pan_item_find_by_coord_l(GList *list, ItemType type, gint x, gint y, const gchar *key) { GList *work; - work = pw->list; + work = list; while (work) { PanItem *pi; @@ -929,6 +1096,16 @@ return NULL; } +static PanItem *pan_item_find_by_coord(PanWindow *pw, ItemType type, gint x, gint y, const gchar *key) +{ + PanItem *pi; + + pi = pan_item_find_by_coord_l(pw->list, type, x, y, key); + if (pi) return pi; + + return pan_item_find_by_coord_l(pw->list_static, type, x, y, key); +} + /* *----------------------------------------------------------------------------- * layout generation @@ -2068,12 +2245,12 @@ printf("computed %d objects\n", g_list_length(pw->list)); } -static GList *pan_layout_intersect(PanWindow *pw, gint x, gint y, gint width, gint height) +static GList *pan_layout_intersect_l(GList *list, GList *item_list, + gint x, gint y, gint width, gint height) { - GList *list = NULL; GList *work; - work = pw->list; + work = item_list; while (work) { PanItem *pi; @@ -2093,6 +2270,39 @@ return list; } +static GList *pan_layout_intersect(PanWindow *pw, gint x, gint y, gint width, gint height) +{ + GList *list = NULL; + GList *grid; + PanGrid *pg = NULL; + + grid = pw->list_grid; + while (grid && !pg) + { + pg = grid->data; + grid = grid->next; + + if (x < pg->x || x + width > pg->x + pg->w || + y < pg->y || y + height > pg->y + pg->h) + { + pg = NULL; + } + } + + list = pan_layout_intersect_l(list, pw->list, x, y, width, height); + + if (pg) + { + list = pan_layout_intersect_l(list, pg->list, x, y, width, height); + } + else + { + list = pan_layout_intersect_l(list, pw->list_static, x, y, width, height); + } + + return list; +} + /* *----------------------------------------------------------------------------- * tile generation @@ -2687,7 +2897,7 @@ return; } - work = pw->list; + work = pw->list_static; if (pw->layout == LAYOUT_CALENDAR) { while (work) @@ -2817,6 +3027,8 @@ printf("Canvas size is %d x %d\n", width, height); + pan_grid_build(pw, width, height, 1000); + pixbuf_renderer_set_tiles(PIXBUF_RENDERER(pw->imd->pr), width, height, PAN_TILE_SIZE, PAN_TILE_SIZE, 10, pan_window_request_tile_cb, @@ -3116,7 +3328,7 @@ if (!pi) return; - printf("info set to %s\n", pi->fd->path); + if (debug) printf("info set to %s\n", pi->fd->path); pbox = pan_item_new_box(pw, NULL, pi->x + pi->width + 4, pi->y, 10, 10, PAN_POPUP_BORDER, @@ -3299,7 +3511,7 @@ GList *list = NULL; GList *work; - work = g_list_last(pw->list); + work = g_list_last(pw->list_static); while (work) { PanItem *pi; @@ -3856,7 +4068,10 @@ pw->size = LAYOUT_SIZE_THUMB_NORMAL; pw->thumb_size = PAN_THUMB_SIZE_NORMAL; pw->thumb_gap = PAN_THUMB_GAP_NORMAL; + pw->list = NULL; + pw->list_static = NULL; + pw->list_grid = NULL; pw->fs = NULL; pw->overlay_id = -1;