You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@couchdb.apache.org by ja...@apache.org on 2019/02/21 03:52:31 UTC
[couchdb-ets-lru] 01/30: Initial import
This is an automated email from the ASF dual-hosted git repository.
jaydoane pushed a commit to branch time-unit-parameterization
in repository https://gitbox.apache.org/repos/asf/couchdb-ets-lru.git
commit 208d376766457b29de225b69e5bd9e132464acf0
Author: Paul J. Davis <pa...@gmail.com>
AuthorDate: Mon Dec 17 23:25:30 2012 -0600
Initial import
---
.gitignore | 1 +
rebar | Bin 0 -> 119440 bytes
src/ets_lru.app.src | 11 +++
src/ets_lru.erl | 200 ++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 212 insertions(+)
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..fc83a9a
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+ebin/
diff --git a/rebar b/rebar
new file mode 100755
index 0000000..ceabf62
Binary files /dev/null and b/rebar differ
diff --git a/src/ets_lru.app.src b/src/ets_lru.app.src
new file mode 100644
index 0000000..e7ebdcd
--- /dev/null
+++ b/src/ets_lru.app.src
@@ -0,0 +1,11 @@
+% Copyright 2012 Cloudant. All rights reserved.
+
+{application, ets_lru, [
+ {description, "ETS Base LRU Cache"},
+ {vsn, git},
+ {registered, []},
+ {applications, [
+ kernel,
+ stdlib
+ ]}
+]}.
diff --git a/src/ets_lru.erl b/src/ets_lru.erl
new file mode 100644
index 0000000..e74c343
--- /dev/null
+++ b/src/ets_lru.erl
@@ -0,0 +1,200 @@
+% Copyright 2012 Cloudant. All rights reserved.
+
+-module(ets_lru).
+
+
+-export([
+ create/2,
+ destroy/1,
+
+ insert/3,
+ lookup/2,
+ member/2,
+ remove/2,
+ hit/2,
+ expire/1,
+ clear/1
+]).
+
+
+-record(entry, {
+ key,
+ val,
+ atime
+}).
+
+-record(ets_lru, {
+ objects,
+ atimes,
+ named=false,
+
+ max_objs,
+ max_size,
+
+ lifetime
+}).
+
+
+create(Name, Options) ->
+ LRU = set_options(#ets_lru{}, Options),
+ Opts = case LRU#ets_lru.named of
+ true -> [named_table];
+ false -> []
+ end,
+ {OName, ATName} = table_names(Name),
+ {ok, LRU#ets_lru{
+ objects = ets:new(OName,
+ [set, protected, {keypos, #entry.key}] ++ Opts),
+ atimes = ets:new(ATName,
+ [ordered_set, protected] ++ Opts)
+ }}.
+
+
+destroy(#ets_lru{objects=Objs, atimes=ATimes}) ->
+ true = ets:delete(Objs),
+ true = ets:delete(ATimes),
+ ok.
+
+
+insert(#ets_lru{objects=Objs, atimes=ATs}=LRU, Key, Val) ->
+ NewATime = erlang:now(),
+ Pattern = #entry{key=Key, atime='$1', _='_'},
+ case ets:match(Objs, Pattern) of
+ [[ATime]] ->
+ true = ets:delete(ATs, ATime),
+ true = ets:insert(ATs, {NewATime, Key}),
+ true = ets:update_element(Objs, Key, {#entry.val, Val});
+ [] ->
+ true = ets:insert(ATs, {NewATime, Key}),
+ true = ets:insert(Objs, #entry{key=Key, val=Val, atime=NewATime})
+ end,
+ trim(LRU).
+
+
+lookup(#ets_lru{objects=Objs}=LRU, Key) ->
+ case ets:lookup(Objs, Key) of
+ [#entry{val=Val}] ->
+ hit(LRU, Key),
+ {ok, Val};
+ [] ->
+ not_found
+ end.
+
+
+member(#ets_lru{objects=Objs}, Key) ->
+ ets:member(Objs, Key).
+
+
+remove(#ets_lru{objects=Objs, atimes=ATs}=LRU, Key) ->
+ case ets:match(Objs, #entry{key=Key, atime='$1', _='_'}) of
+ [[ATime]] ->
+ true = ets:delete(ATs, ATime),
+ true = ets:delete(Objs, Key),
+ ok;
+ [] ->
+ ok
+ end,
+ false = member(LRU, Key),
+ ok.
+
+
+hit(#ets_lru{objects=Objs, atimes=ATs}=LRU, Key) ->
+ case ets:match(Objs, #entry{key=Key, atime='$1', _='_'}) of
+ [[ATime]] ->
+ NewATime = erlang:now(),
+ true = ets:delete(ATs, ATime),
+ true = ets:insert(ATs, {NewATime, Key}),
+ true = ets:update_element(Objs, Key, {#entry.atime, NewATime}),
+ ok;
+ [] ->
+ ok
+ end.
+
+
+expire(#ets_lru{lifetime=undefined}) ->
+ ok;
+expire(#ets_lru{objects=Objs, atimes=ATs, lifetime=LT}=LRU) ->
+ LTMicro = LT * 1000,
+ case ets:first(ATs) of
+ '$end_of_table' ->
+ ok;
+ ATime ->
+ case timer:now_diff(erlang:now(), ATime) > LTMicro of
+ true ->
+ [{ATime, Key}] = ets:lookup(ATs, ATime),
+ true = ets:delete(ATs, ATime),
+ true = ets:delete(Objs, Key),
+ expire(LRU);
+ false ->
+ ok
+ end
+ end.
+
+
+clear(#ets_lru{objects=Objs, atimes=ATs}) ->
+ true = ets:delete_all_objects(Objs),
+ true = ets:delete_all_objects(ATs),
+ ok.
+
+
+trim(#ets_lru{}=LRU) ->
+ case trim_count(LRU) of
+ trimmed -> trim(LRU);
+ _ -> ok
+ end,
+ case trim_size(LRU) of
+ trimmed -> trim(LRU);
+ _ -> ok
+ end.
+
+
+trim_count(#ets_lru{max_objs=undefined}) ->
+ ok;
+trim_count(#ets_lru{objects=Objs, max_objs=MO}=LRU) ->
+ case ets:info(Objs, size) > MO of
+ true -> drop_entry(LRU);
+ false -> ok
+ end.
+
+
+trim_size(#ets_lru{max_size=undefined}) ->
+ ok;
+trim_size(#ets_lru{objects=Objs, max_size=MS}=LRU) ->
+ case ets:info(Objs, memory) > MS of
+ true -> drop_entry(LRU);
+ false -> ok
+ end.
+
+
+drop_entry(#ets_lru{objects=Objs, atimes=ATs}) ->
+ case ets:first(ATs) of
+ '$end_of_table' ->
+ empty;
+ ATime ->
+ [{ATime, Key}] = ets:lookup(ATs, ATime),
+ true = ets:delete(ATs, ATime),
+ true = ets:delete(Objs, Key),
+ trimmed
+ end.
+
+
+set_options(LRU, []) ->
+ LRU;
+set_options(LRU, [named_tables | Rest]) ->
+ set_options(LRU#ets_lru{named=true}, Rest);
+set_options(LRU, [{max_objects, N} | Rest]) when is_integer(N), N > 0 ->
+ set_options(LRU#ets_lru{max_objs=N}, Rest);
+set_options(LRU, [{max_size, N} | Rest]) when is_integer(N), N > 0 ->
+ set_options(LRU#ets_lru{max_size=N}, Rest);
+set_options(LRU, [{lifetime, N} | Rest]) when is_integer(N), N > 0 ->
+ set_options(LRU#ets_lru{lifetime=N}, Rest);
+set_options(_, [Opt | _]) ->
+ throw({invalid_option, Opt}).
+
+
+table_names(Base) when is_atom(Base) ->
+ BList = atom_to_list(Base),
+ OName = list_to_atom(BList ++ "_objects"),
+ ATName = list_to_atom(BList ++ "_atimes"),
+ {OName, ATName}.
+