ossp-pkg/act/act_grid.c
1.5
/*
** Act - Abstract Container Type Library
** Copyright (c) 1999-2002 Ralf S. Engelschall <rse@engelschall.com>
**
** This file is part of Act, a library for dealing with Abstract
** Container Types which can be found at http://www.ossp.org/pkg/act/.
**
** Permission to use, copy, modify, and distribute this software for
** any purpose with or without fee is hereby granted, provided that
** the above copyright notice and this permission notice appear in all
** copies.
**
** THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
** WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
** MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
** IN NO EVENT SHALL THE AUTHORS AND COPYRIGHT HOLDERS AND THEIR
** CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
** LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
** USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
** ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
** OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
** OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
** SUCH DAMAGE.
**
** 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"
/* 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;
act_grid_seg_t *g_seg_first;
int g_seg_num;
size_t g_tile_size;
int g_tile_num_first;
};
/* create a grid segment [INTERNAL] */
static act_rc_t
act_grid_seg_create(
act_ctx_t *ctx,
act_grid_seg_t **pseg,
size_t tile_size,
int tile_num)
{
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 */
act_argcheck(ctx != NULL);
act_argcheck(tile_size >= 1);
act_argcheck(tile_num >= 1);
/* determine (aligned) sizes */
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)
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 rc;
}
/* 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_tile_num_first = tile_num;
/* pass grid to caller */
*pgrid = grid;
return ACT_OK;
}
/* destroy a grid */
act_rc_t
act_grid_destroy(
act_grid_t *grid)
{
act_grid_seg_t *seg;
act_grid_seg_t *seg_last;
/* consistency checks */
act_argcheck(grid != NULL);
/* 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);
}
/* destroy top-level grid structure */
act_mem_free_ctx(grid->g_ctx, grid);
return ACT_OK;
}
/* allocate a tile from a grid */
act_rc_t
act_grid_alloc(
act_grid_t *grid,
void **ptile)
{
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;
/* consistency checks */
act_argcheck(grid != NULL);
act_argcheck(ptile != NULL);
/* 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;
}
/* 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;
}
/* 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 *_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)
{
act_grid_tile_t *tile;
/* cast to internal structure */
tile = (act_grid_tile_t *)_tile;
/* consistency checks */
act_argcheck(grid != NULL);
act_argcheck(tile != NULL);
/* just try to find a segment */
return act_grid_seg_find(grid, NULL, tile);
}