isl_blk.c

   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 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
  65 static 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
  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 }