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