1/* 2 * Copyright 2008-2009 Katholieke Universiteit Leuven 3 * 4 * Use of this software is governed by the MIT license 5 * 6 * Written by Sven Verdoolaege, K.U.Leuven, Departement 7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium 8 */ 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 100 15 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 struct isl_blk extend(struct isl_ctx *ctx, struct isl_blk block, 43 size_t new_n) 44{ 45 int i; 46 isl_int *p; 47 48 if (block.size >= new_n) 49 return block; 50 51 p = block.data; 52 block.data = isl_realloc_array(ctx, block.data, isl_int, new_n); 53 if (!block.data) { 54 free(p); 55 return isl_blk_error(); 56 } 57 58 for (i = block.size; i < new_n; ++i) 59 isl_int_init(block.data[i]); 60 block.size = new_n; 61 62 return block; 63} 64 65static void isl_blk_free_force(struct isl_ctx *ctx, struct isl_blk block) 66{ 67 int i; 68 69 for (i = 0; i < block.size; ++i) 70 isl_int_clear(block.data[i]); 71 free(block.data); 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 else 124 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