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 16 struct isl_blk isl_blk_empty() 17 { 18 struct isl_blk block; 19 block.size = 0; 20 block.data = NULL; 21 return block; 22 } 23 24 static int isl_blk_is_empty(struct isl_blk block) 25 { 26 return block.size == 0 && block.data == NULL; 27 } 28 29 static 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 37 int isl_blk_is_error(struct isl_blk block) 38 { 39 return block.size == -1 && block.data == NULL; 40 } 41 42 static 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 51 static 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 74 struct 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 107 struct 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 116 void 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 127 void 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