--- 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;
}
|
