Index: ossp-pkg/act/act_grid.c RCS File: /v/ossp/cvs/ossp-pkg/act/act_grid.c,v rcsdiff -q -kk '-r1.5' '-r1.6' -u '/v/ossp/cvs/ossp-pkg/act/act_grid.c,v' 2>/dev/null --- act_grid.c 2002/01/18 17:31:39 1.5 +++ act_grid.c 2002/01/19 13:16:32 1.6 @@ -93,25 +93,24 @@ /* the structure of a grid tile */ struct act_grid_tile_st { - act_grid_tile_t *gt_next; + ACT_LIST_ELEM(act_grid_tile_t) gt_link; /* linkage to next tile */ }; /* the structure of a grid segment */ struct act_grid_seg_st { - act_grid_seg_t *gs_next; - act_grid_tile_t *gs_tile_base; - int gs_tile_num; - act_grid_tile_t *gs_tile_free_first; - int gs_tile_free_num; + ACT_RING_ELEM(act_grid_seg_t) gs_link; /* linkage to next+prev segments */ + act_grid_tile_t *gs_tile_base; /* pointer to tile base */ + int gs_tile_num; /* number of tiles */ + ACT_LIST_HEAD(act_grid_tile_t) gs_tile_free_list; /* list of free tiles */ + int gs_tile_free_num; /* number of free tiles */ }; /* the structure of a grid */ struct act_grid_st { - act_ctx_t *g_ctx; - act_grid_seg_t *g_seg_first; - int g_seg_num; - size_t g_tile_size; - int g_tile_num_first; + act_ctx_t *g_ctx; /* context structure */ + ACT_RING_HEAD(act_grid_seg_t) g_seg; /* ring of segments */ + size_t g_tile_size; /* size of a tile */ + int g_tile_num_first; /* number of tiles in first segment */ }; /* create a grid segment [INTERNAL] */ @@ -137,19 +136,21 @@ return ACT_ERR_SYS; /* initialize first segment */ - seg->gs_next = NULL; - seg->gs_tile_base = (act_grid_tile_t *)((char *)seg + seg_top_size); - seg->gs_tile_num = tile_num; - seg->gs_tile_free_first = seg->gs_tile_base; - seg->gs_tile_free_num = seg->gs_tile_num; + ACT_RING_ELEM_INIT(seg, gs_link); + seg->gs_tile_base = (act_grid_tile_t *)((char *)seg + seg_top_size); + seg->gs_tile_num = tile_num; + ACT_LIST_ELEM_INIT(seg->gs_tile_base, gt_link); + ACT_LIST_INIT(&seg->gs_tile_free_list); + ACT_LIST_INSERT_HEAD(&seg->gs_tile_free_list, seg->gs_tile_base, gt_link); + seg->gs_tile_free_num = seg->gs_tile_num; /* initialize free tile list in first segment */ - tile = seg->gs_tile_free_first; + tile = ACT_LIST_FIRST(&seg->gs_tile_free_list); for (i = 0; i < seg->gs_tile_free_num-1; i++) { - tile->gt_next = (act_grid_tile_t *)((char *)tile+tile_size); - tile = tile->gt_next; + ACT_LIST_NEXT(tile, gt_link) = (act_grid_tile_t *)((char *)tile+tile_size); + tile = ACT_LIST_NEXT(tile, gt_link); } - tile->gt_next = NULL; + ACT_LIST_NEXT(tile, gt_link) = NULL; /* pass segment to caller */ *pseg = seg; @@ -175,7 +176,7 @@ act_argcheck(tile_num >= 1); /* determine (aligned) sizes */ - tile_size = act_mem_align(tile_size); + tile_size = act_mem_align(tile_size); /* allocate top-level grid structure */ if ((grid = (act_grid_t *)act_mem_alloc_ctx(ctx, sizeof(act_grid_t))) == NULL) @@ -188,10 +189,10 @@ } /* initialize top-level structure */ - grid->g_ctx = act_ctx_dup(ctx, NULL); - grid->g_seg_first = seg; - grid->g_seg_num = 1; - grid->g_tile_size = tile_size; + grid->g_ctx = act_ctx_dup(ctx, NULL); + ACT_RING_INIT(&grid->g_seg, act_grid_seg_t, gs_link); + ACT_RING_INSERT_HEAD(&grid->g_seg, seg, act_grid_seg_t, gs_link); + grid->g_tile_size = tile_size; grid->g_tile_num_first = tile_num; /* pass grid to caller */ @@ -212,9 +213,9 @@ act_argcheck(grid != NULL); /* destroy grid segments */ - seg_last = grid->g_seg_first; - while (seg_last != NULL) { - seg = seg_last->gs_next; + seg_last = ACT_RING_FIRST(&grid->g_seg); + while (seg_last != ACT_RING_SENTINEL(&grid->g_seg, act_grid_seg_t, gs_link)) { + seg = ACT_RING_NEXT(seg_last, gs_link); act_mem_free_ctx(grid->g_ctx, seg_last); } @@ -244,17 +245,17 @@ /* find segment with first free tile */ seg_l2 = NULL; seg_l1 = NULL; - seg = grid->g_seg_first; - while (seg != NULL) { + seg = ACT_RING_FIRST(&grid->g_seg); + while (seg != ACT_RING_SENTINEL(&grid->g_seg, act_grid_seg_t, gs_link)) { if (seg->gs_tile_free_num > 0) break; seg_l2 = seg_l1; seg_l1 = seg; - seg = seg->gs_next; + seg = ACT_RING_NEXT(seg, gs_link); } /* if no more segment with a free tile exists, add new segment */ - if (seg == NULL) { + if (seg == ACT_RING_SENTINEL(&grid->g_seg, act_grid_seg_t, gs_link)) { /* tile_num increases with Fibonacci behaviour, i.e, tile_num(seg) = tile_num(seg_l1) + tile_num(seg_l2). This way the segments grow in size exponentially but not as fast as @@ -265,15 +266,12 @@ tile_num = seg_l1->gs_tile_num + seg_l2->gs_tile_num; if ((rc = act_grid_seg_create(grid->g_ctx, &seg, grid->g_tile_size, tile_num)) != ACT_OK) return rc; - if (seg_l1 == NULL) - grid->g_seg_first = seg; - else - seg_l1->gs_next = seg; + ACT_RING_INSERT_TAIL(&grid->g_seg, seg, act_grid_seg_t, gs_link); } /* allocate tile from segment */ - tile = seg->gs_tile_free_first; - seg->gs_tile_free_first = tile->gt_next; + tile = ACT_LIST_FIRST(&seg->gs_tile_free_list); + ACT_LIST_REMOVE_HEAD(&seg->gs_tile_free_list, gt_link); seg->gs_tile_free_num--; /* pass tile to caller */ @@ -291,15 +289,15 @@ { act_grid_seg_t *seg; - seg = grid->g_seg_first; - while (seg != NULL) { + seg = ACT_RING_FIRST(&grid->g_seg); + while (seg != ACT_RING_SENTINEL(&grid->g_seg, act_grid_seg_t, gs_link)) { if ( seg->gs_tile_base <= tile && tile < (seg->gs_tile_base+(grid->g_tile_size*seg->gs_tile_num))) { if (pseg != NULL) *pseg = seg; return ACT_OK; } - seg = seg->gs_next; + seg = ACT_RING_NEXT(seg, gs_link); } return ACT_ERR_INT; } @@ -311,7 +309,6 @@ void *_tile) { act_grid_seg_t *seg; - act_grid_seg_t *seg_last; act_grid_tile_t *tile; act_rc_t rc; @@ -327,20 +324,21 @@ return rc; /* move into list of free tiles */ - tile->gt_next = seg->gs_tile_free_first; - seg->gs_tile_free_first = tile; + ACT_LIST_INSERT_HEAD(&seg->gs_tile_free_list, tile, gt_link); seg->gs_tile_free_num++; /* free last segment if it is empty and if segment before (this one here) is now also empty */ +#if 0 if ( seg->gs_tile_num == seg->gs_tile_free_num - && (seg_last = seg->gs_next) != NULL ) { + && (seg_last = seg->gs_link) != NULL ) { if ( seg_last->gs_tile_num == seg_last->gs_tile_free_num - && seg_last->gs_next == NULL ) { + && seg_last->gs_link == NULL ) { act_mem_free_ctx(grid->g_ctx, seg_last); - seg->gs_next = NULL; + seg->gs_link = NULL; } } +#endif return ACT_OK; }