Home | History | Annotate | Line # | Download | only in dist 
      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