# HG changeset patch # User Thinker K.F. Li # Date 1217463000 -28800 # Node ID ed55009d96d351213129b3ade73749e274db96cb # Parent 79e9edf4c00af52e7dde850da08e03b30b315fee refactory for redrawing diff -r 79e9edf4c00a -r ed55009d96d3 src/X_main.c --- a/src/X_main.c Mon Jul 28 17:45:36 2008 +0800 +++ b/src/X_main.c Thu Jul 31 08:10:00 2008 +0800 @@ -26,6 +26,7 @@ rdman_add_shape(&rdman, (shape_t *)path, coord); sh_path_transform(path); sh_path_draw(path, cr); + sh_path_free(path); } void drawing(cairo_surface_t *surface, int w, int h) { diff -r 79e9edf4c00a -r ed55009d96d3 src/coord.c --- a/src/coord.c Mon Jul 28 17:45:36 2008 +0800 +++ b/src/coord.c Thu Jul 31 08:10:00 2008 +0800 @@ -102,7 +102,7 @@ *y = ny; } -coord_t *preorder_coord_tree(coord_t *last) { +coord_t *preorder_coord_subtree(coord_t *root, coord_t *last) { coord_t *next; ASSERT(last == NULL); @@ -111,8 +111,10 @@ next = STAILQ_HEAD(last->children); else { next = last; - while(next != NULL && STAILQ_NEXT(coord_t, sibling, next) == NULL) + while(next != root && STAILQ_NEXT(coord_t, sibling, next) == NULL) next = next->parent; + if(next == root) + next = NULL; if(next) next = STAILQ_NEXT(coord_t, sibling, next); } @@ -193,7 +195,7 @@ CU_ASSERT(y == 99); } -void test_preorder_coord_tree(void) { +void test_preorder_coord_subtree(void) { coord_t elms[6]; coord_t *last; @@ -205,17 +207,17 @@ coord_init(elms + 5, elms + 2); last = elms; - last = preorder_coord_tree(last); + last = preorder_coord_subtree(elms, last); CU_ASSERT(last == elms + 1); - last = preorder_coord_tree(last); + last = preorder_coord_subtree(elms, last); CU_ASSERT(last == elms + 3); - last = preorder_coord_tree(last); + last = preorder_coord_subtree(elms, last); CU_ASSERT(last == elms + 4); - last = preorder_coord_tree(last); + last = preorder_coord_subtree(elms, last); CU_ASSERT(last == elms + 2); - last = preorder_coord_tree(last); + last = preorder_coord_subtree(elms, last); CU_ASSERT(last == elms + 5); - last = preorder_coord_tree(last); + last = preorder_coord_subtree(elms, last); CU_ASSERT(last == NULL); } @@ -224,7 +226,7 @@ suite = CU_add_suite("Suite_coord", NULL, NULL); CU_ADD_TEST(suite, test_update_aggr_matrix); - CU_ADD_TEST(suite, test_preorder_coord_tree); + CU_ADD_TEST(suite, test_preorder_coord_subtree); return suite; } diff -r 79e9edf4c00a -r ed55009d96d3 src/geo.c --- a/src/geo.c Mon Jul 28 17:45:36 2008 +0800 +++ b/src/geo.c Thu Jul 31 08:10:00 2008 +0800 @@ -18,7 +18,7 @@ return 1; } -static int _is_overlay(geo_t *r1, geo_t *r2) { +static int _is_overlay(area_t *r1, area_t *r2) { if(!is_scale_overlay(r1->x, r1->w, r2->x, r2->w)) return 0; if(!is_scale_overlay(r1->y, r1->h, r2->y, r2->h)) @@ -27,7 +27,7 @@ return 1; } -int is_overlay(geo_t *r1, geo_t *r2) { +int is_overlay(area_t *r1, area_t *r2) { return _is_overlay(r1, r2); } @@ -51,10 +51,14 @@ else if(y > max_y) max_y = y; } - g->x = min_x; - g->w = max_x - min_x; - g->y = min_y; - g->h = max_y - min_y; + + g->cur_area = g->areas; + g->last_area = g->areas + 1; + + g->cur_area->x = min_x; + g->cur_area->w = max_x - min_x; + g->cur_area->y = min_y; + g->cur_area->h = max_y - min_y; } void geo_mark_overlay(geo_t *g, int n_others, geo_t **others, @@ -63,7 +67,7 @@ ov_idx = 0; for(i = 0; i < n_others; i++) { - if(_is_overlay(g, others[i])) + if(_is_overlay(g->cur_area, others[i]->cur_area)) overlays[ov_idx++] = others[i]; } *n_overlays = ov_idx; @@ -81,28 +85,31 @@ geo_t g; geo_init(&g, 4, data); - CU_ASSERT(g.x == 14); - CU_ASSERT(g.w == 35); - CU_ASSERT(g.y == 12); - CU_ASSERT(g.h == 44); + CU_ASSERT(g.cur_area->x == 14); + CU_ASSERT(g.cur_area->w == 35); + CU_ASSERT(g.cur_area->y == 12); + CU_ASSERT(g.cur_area->h == 44); } void test_geo_mark_overlay(void) { geo_t _geos[3], *geos[3], *overlays[3]; geo_t g; + co_aix pos[2][2]; int i, n_ov; for(i = 0; i < 3; i++) { - _geos[i].x = i * 50; - _geos[i].y = i * 50; - _geos[i].w = 55; - _geos[i].h = 66; + pos[0][0] = i * 50; + pos[0][1] = i * 50; + pos[1][0] = i * 50 + 55; + pos[1][1] = i * 50 + 66; + geo_init(_geos + i, 2, pos); geos[i] = _geos + i; } - g.x = 88; - g.y = 79; - g.w = 70; - g.h = 70; + pos[0][0] = 88; + pos[0][1] = 79; + pos[1][0] = 88 + 70; + pos[1][1] = 79 + 70; + geo_init(&g, 2, pos); /* overlay with geos[1] and geos[2] */ geo_mark_overlay(&g, 3, geos, &n_ov, overlays); @@ -111,10 +118,11 @@ CU_ASSERT(overlays[1] == geos[2]); /* right side of geos[1], and up side of geos[2] */ - g.x = 105; - g.y = 50; - g.w = 50; - g.h = 51; + pos[0][0] = 105; + pos[0][1] = 50; + pos[1][0] = 105 + 50; + pos[1][1] = 50 + 51; + geo_init(&g, 2, pos); geo_mark_overlay(&g, 3, geos, &n_ov, overlays); CU_ASSERT(n_ov == 1); CU_ASSERT(overlays[0] == geos[2]); diff -r 79e9edf4c00a -r ed55009d96d3 src/mb_types.h --- a/src/mb_types.h Mon Jul 28 17:45:36 2008 +0800 +++ b/src/mb_types.h Thu Jul 31 08:10:00 2008 +0800 @@ -6,6 +6,33 @@ typedef float co_aix; typedef struct _shape shape_t; typedef struct _geo geo_t; +typedef struct _area area_t; + +struct _area { + co_aix x, y; + co_aix w, h; +}; + +/*! \brief Geometry data of a shape or a group of shape. + */ +struct _geo { + unsigned int order; + unsigned int flags; + shape_t *shape; + geo_t *next; /*!< \brief Link all geo objects. */ + + area_t *cur_area, *last_area; + area_t areas[2]; +}; +#define GEF_DIRTY 0x1 + +extern int is_overlay(area_t *r1, area_t *r2); +extern void geo_init(geo_t *g, int n_pos, co_aix pos[][2]); +extern void geo_mark_overlay(geo_t *g, int n_others, geo_t **others, + int *n_overlays, geo_t **overlays); +#define geo_get_shape(g) ((g)->shape) +#define geo_set_shape(g, sh) do {(g)->shape = sh;} while(0) + /*! \brief A coordination system. * @@ -25,19 +52,26 @@ * \enddot */ typedef struct _coord { - unsigned int seq; + unsigned int order; + unsigned int flags; + area_t *cur_area, *last_area; + co_aix matrix[6]; co_aix aggr_matrix[6]; + struct _coord *parent; STAILQ(struct _coord) children; struct _coord *sibling; - STAILQ(shape_t) members; /*!< All shape objects in this coord. */ + + STAILQ(shape_t) members; /*!< All shape_t objects in this coord. */ } coord_t; +#define COF_DIRTY 0x1 +#define COF_RECOMP 0x2 extern void coord_init(coord_t *co, coord_t *parent); extern void coord_trans_pos(coord_t *co, co_aix *x, co_aix *y); extern void update_aggr_matrix(coord_t *start); -extern coord_t *preorder_coord_tree(coord_t *last); +extern coord_t *preorder_coord_subtree(coord_t *root, coord_t *last); /*! \brief A grahpic shape. @@ -57,7 +91,6 @@ geo_t *geo; coord_t *coord; shape_t *coord_mem_next; - struct _shape *sibling; }; enum { SHT_UNKNOW, SHT_PATH, SHT_TEXT }; @@ -74,22 +107,4 @@ extern void sh_attach_coord(shape_t *sh, coord_t *coord); extern void sh_detach_coord(shape_t *sh); - -/*! \brief Geometry data of a shape or a group of shape. - */ -struct _geo { - shape_t *shape; - co_aix x, y; - co_aix w, h; - geo_t *next; /*!< \brief Link geo_t objects. */ - unsigned int seq; -}; - -extern int is_overlay(geo_t *r1, geo_t *r2); -extern void geo_init(geo_t *g, int n_pos, co_aix pos[][2]); -extern void geo_mark_overlay(geo_t *g, int n_others, geo_t **others, - int *n_overlays, geo_t **overlays); -#define geo_get_shape(g) ((g)->shape) -#define geo_set_shape(g, sh) do {(g)->shape = sh;} while(0) - #endif /* __MB_TYPES_H_ */ diff -r 79e9edf4c00a -r ed55009d96d3 src/redraw_man.c --- a/src/redraw_man.c Mon Jul 28 17:45:36 2008 +0800 +++ b/src/redraw_man.c Thu Jul 31 08:10:00 2008 +0800 @@ -9,6 +9,9 @@ #define OK 0 #define ERR -1 +#define OFFSET(type, field) ((void *)&((type *)NULL)->field - (void *)NULL) +#define SWAP(a, b, t) do { t c; c = a; a = b; b = c; } while(0) + int redraw_man_init(redraw_man_t *rdman) { extern void redraw_man_destroy(redraw_man_t *rdman); @@ -27,7 +30,7 @@ rdman->root_coord = elmpool_elm_alloc(rdman->coord_pool); if(rdman->root_coord == NULL) redraw_man_destroy(rdman); - + rdman->n_coords = 1; coord_init(rdman->root_coord, NULL); return OK; @@ -36,6 +39,10 @@ void redraw_man_destroy(redraw_man_t *rdman) { elmpool_free(rdman->coord_pool); elmpool_free(rdman->geo_pool); + if(rdman->dirty_coords) + free(rdman->dirty_coords); + if(rdman->redrawing_geos) + free(rdman->redrawing_geos); } @@ -106,6 +113,8 @@ int rdman_add_shape(redraw_man_t *rdman, shape_t *shape, coord_t *coord) { geo_t *geo; + geo_t *visit; + unsigned int next_order; geo = elmpool_elm_alloc(rdman->geo_pool); if(geo == NULL) @@ -113,6 +122,17 @@ sh_attach_geo(shape, geo); STAILQ_INS_TAIL(rdman->all_geos, geo_t, next, geo); rdman->n_geos++; + + geo->order = ++rdman->next_geo_order; + if(geo->order == 0) { + next_order = 0; + for(visit = STAILQ_HEAD(rdman->all_geos); + visit != NULL; + visit = STAILQ_NEXT(geo_t, next, visit)) + visit->order = ++next_order; + rdman->next_geo_order = next_order; + } + sh_attach_coord(shape, coord); return OK; @@ -128,13 +148,27 @@ } coord_t *rdman_coord_new(redraw_man_t *rdman, coord_t *parent) { - coord_t *coord; + coord_t *coord, *root_coord; + coord_t *visit; coord = elmpool_elm_alloc(rdman->coord_pool); if(coord == NULL) return NULL; coord_init(coord, parent); + rdman->n_coords++; + + coord->order = ++rdman->next_coord_order; + if(coord->order == 0) { + rdman->next_coord_order = 0; + root_coord = visit = rdman->root_coord; + /* skip root coord. */ + visit = preorder_coord_subtree(root_coord, visit); + while(visit) { + visit->order = ++rdman->next_coord_order; + visit = preorder_coord_subtree(root_coord, visit); + } + } return coord; } @@ -159,11 +193,246 @@ STAILQ_REMOVE(parent->children, coord_t, sibling, coord); elmpool_elm_free(rdman->coord_pool, coord); + rdman->n_coords--; + + return OK; +} + +static int extend_memblk(void **buf, int o_size, int n_size) { + void *new_buf; + + new_buf = realloc(*buf, n_size); + if(new_buf == NULL) + return ERR; + + if(new_buf != *buf) { + memcpy(new_buf, *buf, o_size); + free(*buf); + *buf = new_buf; + } + + return OK; +} + +static int add_dirty_geo(redraw_man_t *rdman, geo_t *geo) { + int max_redrawing_geos; + int r; + + if(rdman->n_redrawing_geos >= rdman->max_redrawing_geos) { + max_redrawing_geos = rdman->n_geos + rdman->n_coords; + r = extend_memblk((void **)&rdman->redrawing_geos, + sizeof(geo_t *) * rdman->n_redrawing_geos, + sizeof(geo_t *) * max_redrawing_geos); + if(r != OK) + return ERR; + rdman->max_redrawing_geos = max_redrawing_geos; + } + + rdman->redrawing_geos[rdman->n_redrawing_geos++] = geo; + return OK; +} + +static int add_dirty_area(redraw_man_t *rdman, area_t *area) { + int max_dirty_areas; + int r; + + if(rdman->n_dirty_areas >= rdman->max_dirty_areas) { + max_dirty_areas = (rdman->n_geos + rdman->n_coords) * 2; + r = extend_memblk((void **)&rdman->dirty_areas, + sizeof(area_t *) * rdman->n_dirty_areas, + sizeof(area_t *) * max_dirty_areas); + if(r != OK) + return ERR; + rdman->max_dirty_areas = max_dirty_areas; + } + + rdman->dirty_areas[++rdman->n_dirty_areas] = area; + return OK; +} + +/*! \brief Mark a coord is changed. + * + * A changed coord_t object is marked as dirty and put + * into dirty_coords list. + */ +int rdman_coord_changed(redraw_man_t *rdman, coord_t *coord) { + int max_dirty_coords; + int r; + + if(coord->flags & COF_DIRTY) + return OK; + + if(rdman->n_dirty_coords >= rdman->max_dirty_coords) { + /* Max of dirty_coords is not big enough. */ + max_dirty_coords = rdman->max_dirty_coords + 16; + + r = extend_memblk((void **)&rdman->dirty_coords, + sizeof(coord_t *) * rdman->n_dirty_coords, + sizeof(coord_t *) * max_dirty_coords); + rdman->max_dirty_coords = max_dirty_coords; + } + + rdman->dirty_coords[rdman->n_dirty_coords++] = coord; + coord->flags |= COF_DIRTY; + + return OK; +} + +/*! \brief Mark a shape is changed. + * + * The geo_t object of a changed shape is mark as dirty and + * put into redrawing_geos list. + */ +int rdman_shape_changed(redraw_man_t *rdman, shape_t *shape) { + geo_t *geo; + int r; + + geo = shape->geo; + + if(geo->flags & GEF_DIRTY) + return OK; + + r = add_dirty_geo(rdman, geo); + if(r == ERR) + return ERR; + geo->flags |= GEF_DIRTY; return OK; } -void rdman_coord_changed(redraw_man_t *rdman, coord_t *coord) { +/*! \brief Sort a list of element by a unsigned integer. + * + * The result is in ascend order. The unsigned integers is + * at offset specified by 'off' from start address of elemnts. + */ +static void _insert_sort(void **elms, int num, int off) { + int i, j; + unsigned int val; + + for(i = 1; i < num; i++) { + val = *(unsigned int *)(elms[i] + off); + for(j = i; j > 0; j--) { + if(*(unsigned int *)(elms[j - 1] + off) <= val) + break; + elms[j] = elms[j - 1]; + } + elms[j] = elms[i]; + } +} + +static void make_redrawing_members(redraw_man_t *rdman, coord_t *coord) { + shape_t *shape; + + for(shape = STAILQ_HEAD(coord->members); + shape != NULL; + shape = STAILQ_NEXT(shape_t, coord_mem_next, shape)) { + shape->geo->flags &= ~GEF_DIRTY; + add_dirty_geo(rdman, shape->geo); + } +} + +static void compute_coord_geo(coord_t *coord) { +} + +static void transform_shape(shape_t *shape) { +} + +static void draw_shape(shape_t *shape) { +} + +/*! \brief Re-draw all changed shapes or shapes affected by changed coords. + * + * A coord object has a geo to keep track the range that it's members will + * draw on. Geo of a coord should be recomputed when the coord is changed. + * Geo of a coord used to accelerate finding overlay shape objects of + * a specified geo. A coord object also must be recomputed when one of + * it's members is changed. + * + * New and old geo values of a coord object that is recomputed for + * changing of it-self must be used to find overlay shape objects. + * New and old geo values of a shape should also be used to find + * overlay shape objects, too. If a shape's coord is changed, shape's + * geo object is not used to find overlay shape objects any more. + * + * steps: + * - update chagned coord objects + * - recompute geo for changed coord objects + * - recompute geo for members shape objects + * - recompute geo for changed shape objects + * - finding overlaid shape objects for recomputed geo objects. + * - overlaid shape objects is invoked by traveling tree of coord. + * - members of changed coord object are marked computed and dirty. + * + * assert(n_redrawing_geos <= (num_of(shape) + num_of(coord))) + * Because + * - num_of(geo from coord) < num_of(coord) + * - num_of(geo from shape) < num_of(shape) + */ +int rdman_redraw_changed(redraw_man_t *rdman) { + int i, j; + int n_dirty_coords; + coord_t **dirty_coords; + coord_t *visit_coord; + geo_t *visit_geo, **redrawing_geos; + int n_redrawing_geos; + int n_dirty_areas; + + if(rdman->n_dirty_coords > 0) { + _insert_sort((void **)rdman->dirty_coords, + rdman->n_dirty_coords, + OFFSET(coord_t, order)); + n_dirty_coords = rdman->n_dirty_coords; + dirty_coords = rdman->dirty_coords; + for(i = 0; i < n_dirty_coords; i++) { + if(!(dirty_coords[i]->flags & COF_DIRTY)) + continue; + + update_aggr_matrix(dirty_coords[i]); + for(visit_coord = dirty_coords[i]; + visit_coord != NULL; + visit_coord = preorder_coord_subtree(dirty_coords[i], + visit_coord)) { + /* Dirty member, here, and members of this coord + * will not be visited anymore. */ + visit_coord->flags &= ~COF_DIRTY; + visit_coord->flags |= COF_RECOMP; + + SWAP(visit_coord->cur_area, visit_coord->last_area, area_t *); + compute_coord_geo(visit_coord); + add_dirty_area(rdman, visit_coord->cur_area); + add_dirty_area(rdman, visit_coord->last_area); + make_redrawing_members(rdman, visit_coord); + } + } + rdman->n_dirty_coords = 0; + } + + n_redrawing_geos = rdman->n_redrawing_geos; + if(n_redrawing_geos > 0) { + redrawing_geos = rdman->redrawing_geos; + for(i = 0; i < n_redrawing_geos; i++) { + visit_geo = redrawing_geos[i]; + if(!(visit_geo->flags & GEF_DIRTY)) + continue; + + SWAP(visit_geo->cur_area, visit_geo->last_area, area_t *); + transform_shape(visit_geo->shape); + visit_geo->flags &= ~GEF_DIRTY; + add_dirty_area(rdman, visit_geo->cur_area); + add_dirty_area(rdman, visit_geo->last_area); + } + + n_dirty_areas = rdman->n_dirty_areas; + for(visit_geo = STAILQ_HEAD(rdman->all_geos); + visit_geo != NULL; + visit_geo = STAILQ_NEXT(geo_t, next, visit_geo)) { + if(visit_geo->flags & GEF_DIRTY) + continue; + + } + } + + return OK; } /* @@ -189,6 +458,12 @@ * - shapes should be called to give them a chance to update geometries. */ +/* + * functions: + * - redraw all + * - redraw changed + */ + #ifdef UNITTEST #include @@ -247,6 +522,7 @@ coord_t *coords[3]; shape_t *shapes[5]; geo_t **overlays; + co_aix pos[2][2]; int n; int i; @@ -271,10 +547,11 @@ for(i = 0; i < 5; i++) sh_dummy_transform(shapes[i]); - geo.x = 100; - geo.y = 120; - geo.w = 140; - geo.h = 40; + pos[0][0] = 100; + pos[0][1] = 120; + pos[1][0] = 100 + 140; + pos[1][1] = 120 + 40; + geo_init(&geo, 2, pos); n = rdman_find_overlaid_shapes(&rdman, &geo, &overlays); CU_ASSERT(n == 2); diff -r 79e9edf4c00a -r ed55009d96d3 src/redraw_man.h --- a/src/redraw_man.h Mon Jul 28 17:45:36 2008 +0800 +++ b/src/redraw_man.h Thu Jul 31 08:10:00 2008 +0800 @@ -4,14 +4,44 @@ #include "tools.h" #include "mb_types.h" -/*! \brief Manage redrawing of shapes (graphic elements). */ +/*! \brief Manage redrawing of shapes (graphic elements). + * + * Every coord_t and geo_t object is assigned with a unique + * incremental order. The order is a unsigned integer. + * Every time a new coord_t or geo_t object is added, it is + * assigned with a order number that 1 bigger than last one + * until reaching maximum of unsigned integer. + * When a maximum is meet, all coord_t or geo_t objects + * are reasigned with a new order number from 1. It means + * order numbers that have been assigned and then removed + * later are recycled. + * + * Dirty flag is clear when the transformation matrix of a coord + * object been recomputed or when a geo_t objects been redrawed. + */ typedef struct _redraw_man { + unsigned int next_geo_order; int n_geos; STAILQ(geo_t) all_geos; + + unsigned int next_coord_order; + int n_coords; coord_t *root_coord; + elmpool_t *geo_pool; elmpool_t *coord_pool; - unsigned int seq; + + int max_dirty_coords; + int n_dirty_coords; + coord_t **dirty_coords; + + int max_redrawing_geos; + int n_redrawing_geos; + geo_t **redrawing_geos; + + int max_dirty_areas; + int n_dirty_areas; + area_t **dirty_areas; } redraw_man_t; extern int redraw_man_init(redraw_man_t *rdman); diff -r 79e9edf4c00a -r ed55009d96d3 src/tools.h --- a/src/tools.h Mon Jul 28 17:45:36 2008 +0800 +++ b/src/tools.h Thu Jul 31 08:10:00 2008 +0800 @@ -19,6 +19,7 @@ do { \ (q).head = (q).tail = NULL; \ } while(0) +#define STAILQ_CLEAN(q) STAILQ_INIT(q) #define STAILQ_HEAD(q) ((q).head) #define STAILQ_TAIL(q) ((q).tail) #define STAILQ_NEXT(type, field, elm) ((elm)->field)