135 lines · c
1/*2 * Copyright 2008-2009 Katholieke Universiteit Leuven3 *4 * Use of this software is governed by the MIT license5 *6 * Written by Sven Verdoolaege, K.U.Leuven, Departement7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium8 */9 10#include <isl_blk.h>11#include <isl_ctx_private.h>12 13/* The maximal number of cache misses before first element is evicted */14#define ISL_BLK_MAX_MISS 10015 16struct isl_blk isl_blk_empty()17{18 struct isl_blk block;19 block.size = 0;20 block.data = NULL;21 return block;22}23 24static int isl_blk_is_empty(struct isl_blk block)25{26 return block.size == 0 && block.data == NULL;27}28 29static struct isl_blk isl_blk_error()30{31 struct isl_blk block;32 block.size = -1;33 block.data = NULL;34 return block;35}36 37int isl_blk_is_error(struct isl_blk block)38{39 return block.size == -1 && block.data == NULL;40}41 42static void isl_blk_free_force(struct isl_ctx *ctx, struct isl_blk block)43{44 int i;45 46 for (i = 0; i < block.size; ++i)47 isl_int_clear(block.data[i]);48 free(block.data);49}50 51static struct isl_blk extend(struct isl_ctx *ctx, struct isl_blk block,52 size_t new_n)53{54 int i;55 isl_int *p;56 57 if (block.size >= new_n)58 return block;59 60 p = isl_realloc_array(ctx, block.data, isl_int, new_n);61 if (!p) {62 isl_blk_free_force(ctx, block);63 return isl_blk_error();64 }65 block.data = p;66 67 for (i = block.size; i < new_n; ++i)68 isl_int_init(block.data[i]);69 block.size = new_n;70 71 return block;72}73 74struct isl_blk isl_blk_alloc(struct isl_ctx *ctx, size_t n)75{76 int i;77 struct isl_blk block;78 79 block = isl_blk_empty();80 if (n && ctx->n_cached) {81 int best = 0;82 for (i = 1; ctx->cache[best].size != n && i < ctx->n_cached; ++i) {83 if (ctx->cache[best].size < n) {84 if (ctx->cache[i].size > ctx->cache[best].size)85 best = i;86 } else if (ctx->cache[i].size >= n &&87 ctx->cache[i].size < ctx->cache[best].size)88 best = i;89 }90 if (ctx->cache[best].size < 2 * n + 100) {91 block = ctx->cache[best];92 if (--ctx->n_cached != best)93 ctx->cache[best] = ctx->cache[ctx->n_cached];94 if (best == 0)95 ctx->n_miss = 0;96 } else if (ctx->n_miss++ >= ISL_BLK_MAX_MISS) {97 isl_blk_free_force(ctx, ctx->cache[0]);98 if (--ctx->n_cached != 0)99 ctx->cache[0] = ctx->cache[ctx->n_cached];100 ctx->n_miss = 0;101 }102 }103 104 return extend(ctx, block, n);105}106 107struct isl_blk isl_blk_extend(struct isl_ctx *ctx, struct isl_blk block,108 size_t new_n)109{110 if (isl_blk_is_empty(block))111 return isl_blk_alloc(ctx, new_n);112 113 return extend(ctx, block, new_n);114}115 116void isl_blk_free(struct isl_ctx *ctx, struct isl_blk block)117{118 if (isl_blk_is_empty(block) || isl_blk_is_error(block))119 return;120 121 if (ctx->n_cached < ISL_BLK_CACHE_SIZE)122 ctx->cache[ctx->n_cached++] = block;123 else124 isl_blk_free_force(ctx, block);125}126 127void isl_blk_clear_cache(struct isl_ctx *ctx)128{129 int i;130 131 for (i = 0; i < ctx->n_cached; ++i)132 isl_blk_free_force(ctx, ctx->cache[i]);133 ctx->n_cached = 0;134}135