--- act_grid.c 2002/01/02 17:05:53 1.4
+++ act_grid.c 2002/01/18 17:31:39 1.5
@@ -26,101 +26,341 @@
** act_grid.c: memory grid (implementation)
*/
+/*
+ * This is a special-case memory management library dedicated to the
+ * speed- and memory-optimized allocation and deallocation of fixed
+ * size objects. Inside OSSP act we have lots of those objects and
+ * if we would manage them directly through malloc(3) it would be to
+ * run-time expensive and waste too much total memory.
+ *
+ * It works by collecting together larger segments (act_grid_seg_t) of
+ * those fixed size objects (act_grid_tile_t) and linking them into
+ * a top-level grid structure (act_grid_t). The number of tiles in a
+ * segment grows with the Fibonacci numbers f(n) = f(n-1)+f(n-2) in
+ * order to dynamically scale better to the allocation requests without
+ * having to waste too much memory (in contrast to the usual "double to
+ * twice of size" approach). Inside a grid segment, the tiles are just
+ * arranged as a linar array after a linkage structure. The free tiles
+ * are remembered in a single linked list. So the grid in memory looks
+ * like this:
+ *
+ * -----BEGIN EMBEDDED OBJECT-----
+ * Content-type: application/fig
+ * Description: grid memory allocator memory architecture
+ * Version: eo/1.0
+ * H4sIAFxTSDwCA61aTW/cNhA9R79CQM82+DUUdS7QIkBuvfYSJAvXQLIoYv9/VOKI
+ * b0itg/i5RhD6rcX5nqFm6P3tj49/zvE+TJ8+X78+ffn872X6/XJ9vvyYPl6//HN5
+ * mj5dnrdP8zx55+6dm/56vD58u0x3YfLBuTlMefbiZu+2ZdlB2TaFOcwb3P6HdZb6
+ * 0807+bZu/5a6yvRBSXc+ywA2HvoIIIxcyyzuF1yhEEDomGHPxtUfXBdleuc7pvuH
+ * XdDGNbqDtAI185WkqUlNwpLmJjXTUquJsVkfhSWVFg6hpeYmNQsRt+rYXeEkPZDm
+ * c4DIcM3uZAs000cA4lhdc1MRoHT5gT1k5t7am8WZX9ue6S5vxbe6I8Xrbq76VmfF
+ * MKBd+XUAVP2ddDIUOnbYRaSWQ/U6upCUzhaOOEJypCWvIBPHFuKKmIhjK3HtUodO
+ * RNdKsLPaEuQUXKoeO1eclgyZhqiiVG0ydDVU+qSxfWROv2T7LgOebru0NlX+viuE
+ * fUmULSNxh06mZfpNpj6AXw69Xku8QvIqLHHwTXJFpGRkhfqBe6OhEJRYeMkZkrlS
+ * KiigVQaEs7ZDVCmpOwejTMPjqSGhOjMkmCUdsvjgmvpEZB0iN6fTsRQ3oDcEqkDr
+ * whOviPJK55cmdTgQSxz6hXUndO9QcbcLl7orPOJdj04fsY/U+iU2CFyPvGOrYvRm
+ * l7o4eGyfntYRY0PcG8St8XLtt3W7/fbVRXQiHtnoU0PcYRhjM6OiQ6/XEidok4Qm
+ * zpCcecnVUmlO3hFLvMCdCy+5QHKhJpPq7ap2kgEtLQIdEop1dmejTMPjqaHF0VoX
+ * 6AqkSdfyxvYRrP3PjK9CzNdt315jHHcrxQ6FVi0d4qZ4G+Mj3YFEDPKoILJulDjz
+ * kjHMR36ajzZW8vN8xOAZ3zDRY6SPmOmjDfU25fJjfcRcD6NMw+OpIaGPbY3UMiA9
+ * 9fyAuN6nM9mCYh7GtI99bKAKtC488Yoor/y57OElz5/LAedy4PMrI6sMFWSVIS51
+ * EzySXY/U0CQ94nofPXleYKNuiG5AVO+jGg7e7FN3fHVb76P9UMILgepyTsQjm/MD
+ * cl4UtG1CNyr1paTEC92o1LeXEhde8qAx2eWMGpNdzqgx+VJXb0t7s3fo9FGE7XLU
+ * nYNRpuHNQnU5qg34nyUNUWAdkn5m/Jgd2Ed1OTo/u6Zfh0JL3A5RXU5VUomFv6RZ
+ * IHnhK7ZAcuElJ7QLjr4qVWJpgedennaXocSZrhu9mFrcgKRFoEORrpvRKNPweGpI
+ * 6GO7/UGrR3ae28J1OZ3JCEp3byQyoDcEqkDrwhOviPLKn8seXvL8uRxwFgU+vzKy
+ * ylBBVhniUnfBvUuRHunlyOJ6xHU5evK8wEbvYkQGxN3wFDl7s0/d0+Ec6PnQpuIU
+ * 6PlQiXdEEmdIzrxk34ZtvV/ydP+uhi8HYokTJCe6E+44GIrudvH0fDgaZRoeTw1F
+ * eojrVD8ZEd3ZCNabGbpmnnjpF5Z4heSVlpxwTZMcnwRJbhcLoaFED3HwZI9WyDS0
+ * 8Fq/wEbdUA8PoMObTOqO3jxQ6E8H20debeghswwo4T7N0Gno2eJ9mwRLfZSmD34D
+ * /r5+UeVeG4b960LHd1/c8f2IEkQ/AJz62rfJ6L4TsKPKvPTgfaSszZSKdub13QXw
+ * LlL0TevaK35nXlMI4F2kRIQltrikFpd0+PD/mxI3bvWiYQdHvuGnHxM3ul//USd2
+ * A50CXMjkrjmbkpLti8+bIOW46Tof19Hb1kVqRj78ePz6t3P+RJONZKl+V5X9ZsfT
+ * 5eH75fr8KiLNFpqqvEWWpiBLFTm7crVpzruWcQPPj98uleI/a7orF0koAAA=
+ * -----END EMBEDDED OBJECT-----
+ */
+
#include "act_p.h"
#include "act_grid.h"
-/* the top-level structure of a grid */
+/* forward declarations */
+struct act_grid_tile_st;
+struct act_grid_seg_st;
+
+/* corresponding types */
+typedef struct act_grid_tile_st act_grid_tile_t;
+typedef struct act_grid_seg_st act_grid_seg_t;
+
+/* the structure of a grid tile */
+struct act_grid_tile_st {
+ act_grid_tile_t *gt_next;
+};
+
+/* 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;
+};
+
+/* the structure of a grid */
struct act_grid_st {
- act_ctx_t *g_ctx;
- void *g_seg_block;
- void *g_seg_free;
- size_t g_seg_num;
- size_t g_seg_size;
+ 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_grid_t *
-act_grid_create(
+/* create a grid segment [INTERNAL] */
+static act_rc_t
+act_grid_seg_create(
act_ctx_t *ctx,
- size_t segnum,
- size_t segsize)
+ act_grid_seg_t **pseg,
+ size_t tile_size,
+ int tile_num)
{
- act_grid_t *grid = NULL;
- void *block;
- void *seg;
+ size_t seg_top_size;
+ size_t seg_size;
+ act_grid_seg_t *seg;
+ act_grid_tile_t *tile;
int i;
+ /* determine (aligned) sizes */
+ seg_top_size = act_mem_align(sizeof(act_grid_seg_t));
+ seg_size = seg_top_size + (tile_size * tile_num);
+
+ /* allocate first segment */
+ if ((seg = act_mem_alloc_ctx(ctx, seg_size)) == NULL)
+ 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;
+
+ /* initialize free tile list in first segment */
+ tile = seg->gs_tile_free_first;
+ 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;
+ }
+ tile->gt_next = NULL;
+
+ /* pass segment to caller */
+ *pseg = seg;
+
+ return ACT_OK;
+}
+
+/* create a grid */
+act_rc_t
+act_grid_create(
+ act_grid_t **pgrid,
+ act_ctx_t *ctx,
+ size_t tile_size,
+ int tile_num)
+{
+ act_grid_t *grid;
+ act_grid_seg_t *seg;
+ act_rc_t rc;
+
/* consistency checks */
- insist(ctx != NULL, NULL);
- insist(segnum >= 1, NULL);
- insist(segsize >= sizeof(void *), NULL);
+ act_argcheck(ctx != NULL);
+ act_argcheck(tile_size >= 1);
+ act_argcheck(tile_num >= 1);
- /* align segment size */
- segsize = act_mem_align(segsize);
+ /* determine (aligned) sizes */
+ tile_size = act_mem_align(tile_size);
- /* allocate memory chunks */
+ /* allocate top-level grid structure */
if ((grid = (act_grid_t *)act_mem_alloc_ctx(ctx, sizeof(act_grid_t))) == NULL)
- return NULL;
- if ((block = act_mem_alloc_ctx(ctx, segnum * segsize)) == NULL) {
+ return ACT_ERR_SYS;
+
+ /* allocate first segment */
+ if ((rc = act_grid_seg_create(ctx, &seg, tile_size, tile_num)) != ACT_OK) {
act_mem_free_ctx(ctx, grid);
- return NULL;
+ return rc;
}
/* initialize top-level structure */
- grid->g_ctx = act_ctx_dup(ctx, NULL);
- grid->g_seg_block = block;
- grid->g_seg_free = block;
- grid->g_seg_num = segnum;
- grid->g_seg_size = segsize;
+ 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_tile_num_first = tile_num;
- /* initialize segment block */
- seg = grid->g_seg_free;
- for (i = 0; i < segnum-1; i++) {
- *((void **)seg) = (char *)seg+segsize;
- seg = (char *)seg+segsize;
- }
- *((void **)seg) = NULL;
+ /* pass grid to caller */
+ *pgrid = grid;
- return grid;
+ return ACT_OK;
}
-int
+/* destroy a grid */
+act_rc_t
act_grid_destroy(
act_grid_t *grid)
{
- act_ctx_t *ctx;
+ act_grid_seg_t *seg;
+ act_grid_seg_t *seg_last;
+
+ /* consistency checks */
+ act_argcheck(grid != NULL);
- insist(grid != NULL, FALSE);
+ /* destroy grid segments */
+ seg_last = grid->g_seg_first;
+ while (seg_last != NULL) {
+ seg = seg_last->gs_next;
+ act_mem_free_ctx(grid->g_ctx, seg_last);
+ }
- ctx = grid->g_ctx;
- act_mem_free_ctx(ctx, grid->g_seg_block);
- act_mem_free_ctx(ctx, grid);
+ /* destroy top-level grid structure */
+ act_mem_free_ctx(grid->g_ctx, grid);
- return TRUE;
+ return ACT_OK;
}
-void *
+/* allocate a tile from a grid */
+act_rc_t
act_grid_alloc(
- act_grid_t *grid)
+ act_grid_t *grid,
+ void **ptile)
{
- void *chunk = NULL;
+ act_grid_seg_t *seg;
+ act_grid_seg_t *seg_l1;
+ act_grid_seg_t *seg_l2;
+ act_grid_tile_t *tile;
+ act_rc_t rc;
+ int tile_num;
- insist(grid != NULL, NULL);
+ /* consistency checks */
+ act_argcheck(grid != NULL);
+ act_argcheck(ptile != NULL);
- /* XXX */
+ /* find segment with first free tile */
+ seg_l2 = NULL;
+ seg_l1 = NULL;
+ seg = grid->g_seg_first;
+ while (seg != NULL) {
+ if (seg->gs_tile_free_num > 0)
+ break;
+ seg_l2 = seg_l1;
+ seg_l1 = seg;
+ seg = seg->gs_next;
+ }
- return chunk;
+ /* if no more segment with a free tile exists, add new segment */
+ if (seg == NULL) {
+ /* 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
+ twith he usual "double the size" approach. */
+ if (seg_l2 == NULL)
+ tile_num = grid->g_tile_num_first;
+ else
+ 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;
+ }
+
+ /* allocate tile from segment */
+ tile = seg->gs_tile_free_first;
+ seg->gs_tile_free_first = tile->gt_next;
+ seg->gs_tile_free_num--;
+
+ /* pass tile to caller */
+ *ptile = tile;
+
+ return ACT_OK;
}
-int
+/* find grid segment where tile is stored [INTERNAL] */
+static act_rc_t
+act_grid_seg_find(
+ act_grid_t *grid,
+ act_grid_seg_t **pseg,
+ act_grid_tile_t *tile)
+{
+ act_grid_seg_t *seg;
+
+ seg = grid->g_seg_first;
+ while (seg != NULL) {
+ 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;
+ }
+ return ACT_ERR_INT;
+}
+
+/* free a tile to a grid */
+act_rc_t
act_grid_free(
act_grid_t *grid,
- void *segptr)
+ void *_tile)
+{
+ act_grid_seg_t *seg;
+ act_grid_seg_t *seg_last;
+ act_grid_tile_t *tile;
+ act_rc_t rc;
+
+ /* cast to internal structure */
+ tile = (act_grid_tile_t *)_tile;
+
+ /* consistency checks */
+ act_argcheck(grid != NULL);
+ act_argcheck(tile != NULL);
+
+ /* find segment of tile */
+ if ((rc = act_grid_seg_find(grid, &seg, tile)) != ACT_OK)
+ return rc;
+
+ /* move into list of free tiles */
+ tile->gt_next = seg->gs_tile_free_first;
+ seg->gs_tile_free_first = tile;
+ seg->gs_tile_free_num++;
+
+ /* free last segment if it is empty and if segment
+ before (this one here) is now also empty */
+ if ( seg->gs_tile_num == seg->gs_tile_free_num
+ && (seg_last = seg->gs_next) != NULL ) {
+ if ( seg_last->gs_tile_num == seg_last->gs_tile_free_num
+ && seg_last->gs_next == NULL ) {
+ act_mem_free_ctx(grid->g_ctx, seg_last);
+ seg->gs_next = NULL;
+ }
+ }
+
+ return ACT_OK;
+}
+
+/* test whether a tile is inside a grid */
+act_rc_t
+act_grid_inside(
+ act_grid_t *grid,
+ void *_tile)
{
- insist(grid != NULL, FALSE);
- insist(segptr != NULL, FALSE);
+ act_grid_tile_t *tile;
+
+ /* cast to internal structure */
+ tile = (act_grid_tile_t *)_tile;
- /* XXX */
+ /* consistency checks */
+ act_argcheck(grid != NULL);
+ act_argcheck(tile != NULL);
- return TRUE;
+ /* just try to find a segment */
+ return act_grid_seg_find(grid, NULL, tile);
}
|
