1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
/*
* Copyright 2008-2009 Katholieke Universiteit Leuven
*
* Use of this software is governed by the MIT license
*
* Written by Sven Verdoolaege, K.U.Leuven, Departement
* Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
*/
#include <isl/blk.h>
#include <isl_ctx_private.h>
/* The maximal number of cache misses before first element is evicted */
#define ISL_BLK_MAX_MISS 100
struct isl_blk isl_blk_empty()
{
struct isl_blk block;
block.size = 0;
block.data = NULL;
return block;
}
static int isl_blk_is_empty(struct isl_blk block)
{
return block.size == 0 && block.data == NULL;
}
static struct isl_blk isl_blk_error()
{
struct isl_blk block;
block.size = -1;
block.data = NULL;
return block;
}
int isl_blk_is_error(struct isl_blk block)
{
return block.size == -1 && block.data == NULL;
}
static struct isl_blk extend(struct isl_ctx *ctx, struct isl_blk block,
size_t new_n)
{
int i;
isl_int *p;
if (block.size >= new_n)
return block;
p = block.data;
block.data = isl_realloc_array(ctx, block.data, isl_int, new_n);
if (!block.data) {
free(p);
return isl_blk_error();
}
for (i = block.size; i < new_n; ++i)
isl_int_init(block.data[i]);
block.size = new_n;
return block;
}
static void isl_blk_free_force(struct isl_ctx *ctx, struct isl_blk block)
{
int i;
for (i = 0; i < block.size; ++i)
isl_int_clear(block.data[i]);
free(block.data);
}
struct isl_blk isl_blk_alloc(struct isl_ctx *ctx, size_t n)
{
int i;
struct isl_blk block;
block = isl_blk_empty();
if (n && ctx->n_cached) {
int best = 0;
for (i = 1; ctx->cache[best].size != n && i < ctx->n_cached; ++i) {
if (ctx->cache[best].size < n) {
if (ctx->cache[i].size > ctx->cache[best].size)
best = i;
} else if (ctx->cache[i].size >= n &&
ctx->cache[i].size < ctx->cache[best].size)
best = i;
}
if (ctx->cache[best].size < 2 * n + 100) {
block = ctx->cache[best];
if (--ctx->n_cached != best)
ctx->cache[best] = ctx->cache[ctx->n_cached];
if (best == 0)
ctx->n_miss = 0;
} else if (ctx->n_miss++ >= ISL_BLK_MAX_MISS) {
isl_blk_free_force(ctx, ctx->cache[0]);
if (--ctx->n_cached != 0)
ctx->cache[0] = ctx->cache[ctx->n_cached];
ctx->n_miss = 0;
}
}
return extend(ctx, block, n);
}
struct isl_blk isl_blk_extend(struct isl_ctx *ctx, struct isl_blk block,
size_t new_n)
{
if (isl_blk_is_empty(block))
return isl_blk_alloc(ctx, new_n);
return extend(ctx, block, new_n);
}
void isl_blk_free(struct isl_ctx *ctx, struct isl_blk block)
{
if (isl_blk_is_empty(block) || isl_blk_is_error(block))
return;
if (ctx->n_cached < ISL_BLK_CACHE_SIZE)
ctx->cache[ctx->n_cached++] = block;
else
isl_blk_free_force(ctx, block);
}
void isl_blk_clear_cache(struct isl_ctx *ctx)
{
int i;
for (i = 0; i < ctx->n_cached; ++i)
isl_blk_free_force(ctx, ctx->cache[i]);
ctx->n_cached = 0;
}
|
