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
|
#ifndef SCM_CACHE_INTERNAL_H
#define SCM_CACHE_INTERNAL_H
/* Copyright 2016,2018
Free Software Foundation, Inc.
This file is part of Guile.
Guile is free software: you can redistribute it and/or modify it
under the terms of the GNU Lesser General Public License as published
by the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
Guile is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
License for more details.
You should have received a copy of the GNU Lesser General Public
License along with Guile. If not, see
<https://www.gnu.org/licenses/>. */
#include <string.h>
#include "libguile/gc.h"
#include "libguile/hash.h"
/* A simple cache with 8 entries. The cache entries are stored in a
sorted vector. */
struct scm_cache_entry
{
scm_t_bits key;
scm_t_bits value;
};
#define SCM_CACHE_SIZE 16
struct scm_cache
{
scm_t_bits eviction_cookie;
struct scm_cache_entry entries[SCM_CACHE_SIZE];
};
static inline struct scm_cache*
scm_make_cache (void)
{
struct scm_cache *ret = scm_gc_typed_calloc (struct scm_cache);
ret->eviction_cookie = (scm_t_bits) ret;
return ret;
}
static inline int
scm_cache_full_p (struct scm_cache *cache)
{
return cache->entries[0].key != 0;
}
static inline void
scm_cache_evict_1 (struct scm_cache *cache, struct scm_cache_entry *evicted)
{
size_t idx;
cache->eviction_cookie = scm_ihashq (SCM_PACK (cache->eviction_cookie), -1);
idx = cache->eviction_cookie & (SCM_CACHE_SIZE - 1);
memcpy (evicted, cache->entries + idx, sizeof (*evicted));
memmove (cache->entries + 1,
cache->entries,
sizeof (cache->entries[0]) * idx);
cache->entries[0].key = 0;
cache->entries[0].value = 0;
}
static inline struct scm_cache_entry*
scm_cache_lookup (struct scm_cache *cache, SCM k)
{
scm_t_bits k_bits = SCM_UNPACK (k);
struct scm_cache_entry *entry = cache->entries;
/* Unrolled binary search, compiled to branchless cmp + cmov chain. */
if (entry[8].key <= k_bits) entry += 8;
if (entry[4].key <= k_bits) entry += 4;
if (entry[2].key <= k_bits) entry += 2;
if (entry[1].key <= k_bits) entry += 1;
return entry;
}
static inline void
scm_cache_insert (struct scm_cache *cache, SCM k, SCM v,
struct scm_cache_entry *evicted)
{
struct scm_cache_entry *entry;
if (scm_cache_full_p (cache))
scm_cache_evict_1 (cache, evicted);
entry = scm_cache_lookup (cache, k);
if (entry->key == SCM_UNPACK (k))
{
entry->value = SCM_UNPACK (v);
return;
}
memmove (cache->entries,
cache->entries + 1,
(entry - cache->entries) * sizeof (*entry));
entry->key = SCM_UNPACK (k);
entry->value = SCM_UNPACK (v);
}
#endif /* SCM_CACHE_INTERNAL_H */
|
