cover/mysql_cache.COVER.html

1 %% Minicache. Feel free to rename this module and include it in other projects.
2 %%-----------------------------------------------------------------------------
3 %% Copyright 2014 Viktor Söderqvist
4 %%
5 %% Licensed under the Apache License, Version 2.0 (the "License");
6 %% you may not use this file except in compliance with the License.
7 %% You may obtain a copy of the License at
8 %%
9 %% http://www.apache.org/licenses/LICENSE-2.0
10 %%
11 %% Unless required by applicable law or agreed to in writing, software
12 %% distributed under the License is distributed on an "AS IS" BASIS,
13 %% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 %% See the License for the specific language governing permissions and
15 %% limitations under the License.
16
17 %% @doc A minimalistic time triggered dict based cache data structure.
18 %%
19 %% The cache keeps track of when each key was last used. Elements are evicted
20 %% using manual calls to evict_older_than/2. Most of the functions return a new
21 %% updated cache object which should be used in subsequent calls.
22 %%
23 %% A cache can be initialized to 'empty' which represents the empty cache.
24 %%
25 %% Properties:
26 %%
27 %% <ul>
28 %% <li>Embeddable in a gen_server or other process</li>
29 %% <li>Small overhead when unused (the empty cache is a single atom)</li>
30 %% <li>Evicting K elements is O(N + K * log N) which means low overhead when
31 %% nothing or few elements are evicted</li>
32 %% </ul>
33 %% @private
34 -module(mysql_cache).
35
36 -export_type([cache/2]).
37 -export([evict_older_than/2, lookup/2, new/0, size/1, store/3]).
38
39 -type cache(K, V) ::
40 {cache, erlang:timestamp(), dict:dict(K, {V, non_neg_integer()})} | empty.
41
42 %% @doc Deletes the entries that have not been used for `MaxAge' milliseconds
43 %% and returns them along with the new state.
44 -spec evict_older_than(Cache :: cache(K, V), MaxAge :: non_neg_integer()) ->
45 {Evicted :: [{K, V}], NewCache :: cache(K, V)}.
46 evict_older_than({cache, StartTs, Dict}, MaxAge) ->
47 5 MinTime = timer:now_diff(os:timestamp(), StartTs) div 1000 - MaxAge,
48 5 {Evicted, Dict1} = dict:fold(
49 fun (Key, {Value, Time}, {EvictedAcc, DictAcc}) ->
50 5 if
51 Time < MinTime ->
52 2 {[{Key, Value} | EvictedAcc], dict:erase(Key, DictAcc)};
53 Time >= MinTime ->
54 3 {EvictedAcc, DictAcc}
55 end
56 end,
57 {[], Dict},
58 Dict),
59 5 Cache1 = case dict:size(Dict1) of
60 2 0 -> empty;
61 3 _ -> {cache, StartTs, Dict1}
62 end,
63 5 {Evicted, Cache1};
64 evict_older_than(empty, _) ->
65 1 {[], empty}.
66
67 %% @doc Looks up a key in a cache. If found, returns the value and a new cache
68 %% with the 'last used' timestamp updated for the key.
69 -spec lookup(Key :: K, Cache :: cache(K, V)) ->
70 {found, Value :: V, UpdatedCache :: cache(K, V)} | not_found.
71 lookup(Key, {cache, StartTs, Dict}) ->
72 10 case dict:find(Key, Dict) of
73 {ok, {Value, _OldTime}} ->
74 4 NewTime = timer:now_diff(os:timestamp(), StartTs) div 1000,
75 4 Dict1 = dict:store(Key, {Value, NewTime}, Dict),
76 4 Cache1 = {cache, StartTs, Dict1},
77 4 {found, Value, Cache1};
78 error ->
79 6 not_found
80 end;
81 lookup(_Key, empty) ->
82 7 not_found.
83
84 %% @doc Returns the atom `empty' which represents an empty cache.
85 -spec new() -> cache(K :: term(), V :: term()).
86 new() ->
87 1 empty.
88
89 %% @doc Returns the number of elements in the cache.
90 -spec size(cache(K :: term(), V :: term())) -> non_neg_integer().
91 size({cache, _, Dict}) ->
92 1 dict:size(Dict);
93 size(empty) ->
94 2 0.
95
96 %% @doc Stores a key-value pair in the cache. If the key already exists, the
97 %% associated value is replaced by `Value'.
98 -spec store(Key :: K, Value :: V, Cache :: cache(K, V)) -> cache(K, V)
99 when K :: term(), V :: term().
100 store(Key, Value, {cache, StartTs, Dict}) ->
101 5 Time = timer:now_diff(os:timestamp(), StartTs) div 1000,
102 5 {cache, StartTs, dict:store(Key, {Value, Time}, Dict)};
103 store(Key, Value, empty) ->
104 7 {cache, os:timestamp(), dict:store(Key, {Value, 0}, dict:new())}.
105
106 -ifdef(TEST).
107 -include_lib("eunit/include/eunit.hrl").
108
109 empty_test() ->
110 1 ?assertEqual(empty, ?MODULE:new()),
111 1 ?assertEqual(0, ?MODULE:size(empty)),
112 1 ?assertEqual(not_found, ?MODULE:lookup(foo, empty)),
113 1 ?assertMatch({[], empty}, ?MODULE:evict_older_than(empty, 10)).
114
115 nonempty_test() ->
116 1 Cache = ?MODULE:store(foo, bar, empty),
117 1 ?assertMatch({found, bar, _}, ?MODULE:lookup(foo, Cache)),
118 1 ?assertMatch(not_found, ?MODULE:lookup(baz, Cache)),
119 1 ?assertMatch({[], _}, ?MODULE:evict_older_than(Cache, 50)),
120 1 ?assertMatch({cache, _, _}, Cache),
121 1 ?assertEqual(1, ?MODULE:size(Cache)),
122 1 receive after 51 -> ok end, %% expire cache
123 1 ?assertEqual({[{foo, bar}], empty}, ?MODULE:evict_older_than(Cache, 50)),
124 %% lookup un-expires cache
125 1 {found, bar, NewCache} = ?MODULE:lookup(foo, Cache),
126 1 ?assertMatch({[], {cache, _, _}}, ?MODULE:evict_older_than(NewCache, 50)),
127 %% store also un-expires
128 1 NewCache2 = ?MODULE:store(foo, baz, Cache),
129 1 ?assertMatch({[], {cache, _, _}}, ?MODULE:evict_older_than(NewCache2, 50)).
130
131 -endif.
Line Hits Source