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
isl_blk_empty()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
isl_blk_is_empty(struct isl_blk block)24 static int isl_blk_is_empty(struct isl_blk block)
25 {
26 return block.size == 0 && block.data == NULL;
27 }
28
isl_blk_error()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
isl_blk_is_error(struct isl_blk block)37 int isl_blk_is_error(struct isl_blk block)
38 {
39 return block.size == -1 && block.data == NULL;
40 }
41
isl_blk_free_force(struct isl_ctx * ctx,struct isl_blk block)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
extend(struct isl_ctx * ctx,struct isl_blk block,size_t new_n)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
isl_blk_alloc(struct isl_ctx * ctx,size_t n)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
isl_blk_extend(struct isl_ctx * ctx,struct isl_blk block,size_t new_n)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
isl_blk_free(struct isl_ctx * ctx,struct isl_blk block)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
isl_blk_clear_cache(struct isl_ctx * ctx)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