%%% -*- erlang -*- %%% %%% This file is part of hackney released under the Apache 2 license. %%% See the NOTICE for more information. %%% %%% Copyright (c) 2024-2026 Benoit Chesneau %%% %%% @doc Optimized HPACK header compression for HTTP/2 (RFC 7541). %%% %%% This implementation provides O(1) dynamic table lookups using %%% a combination of ring buffer for index access and maps for %%% field/name lookups during encoding. %%% %%% Key optimizations: %%% - Ring buffer (tuple) for O(1) index-based access %%% - Maps for O(1) field and name lookups %%% - Pre-computed static table as maps %%% - Lookup table for Huffman encoding %%% @end -module(hackney_hpack). -dialyzer(no_improper_lists). -export([init/0]). -export([init/1]). -export([set_max_size/2]). -export([decode/1]). -export([decode/2]). -export([encode/1]). -export([encode/2]). -export([encode/3]). %% Type definitions -type header() :: {binary(), binary()}. -type headers() :: [header()]. -type opts() :: map(). -export_type([state/0]). -export_type([opts/0]). -export_type([headers/0]). %% Include Huffman lookup tables -include("hackney_hpack_huffman.hrl"). %% Reuse existing Huffman decode lookup table from cowlib -include("hackney_hpack_huffman_dec.hrl"). %% Dynamic table entry size overhead per RFC 7541 Section 4.1 -define(ENTRY_OVERHEAD, 32). %% Static table size -define(STATIC_TABLE_SIZE, 61). %% Default ring buffer size (number of entries, will grow as needed) -define(DEFAULT_RING_SIZE, 128). %% State record with ring buffer + maps for O(1) operations -record(state, { size = 0 :: non_neg_integer(), max_size = 4096 :: non_neg_integer(), configured_max_size = 4096 :: non_neg_integer(), %% Ring buffer for O(1) index access %% Entries stored as {EntrySize, {Name, Value}} entries = {} :: tuple(), head = 0 :: non_neg_integer(), %% Position of newest entry count = 0 :: non_neg_integer(), %% Number of entries %% Maps for O(1) lookup during encoding field_index = #{} :: #{header() => pos_integer()}, %% {Name, Value} => absolute_index name_index = #{} :: #{binary() => pos_integer()}, %% Name => absolute_index %% Monotonic counter for absolute indexing insert_count = 0 :: non_neg_integer() }). -opaque state() :: #state{}. %%==================================================================== %% Static Table (RFC 7541 Appendix A) %%==================================================================== %% Static table as a tuple for O(1) index access -define(STATIC_TABLE, { {<<":authority">>, <<>>}, {<<":method">>, <<"GET">>}, {<<":method">>, <<"POST">>}, {<<":path">>, <<"/">>}, {<<":path">>, <<"/index.html">>}, {<<":scheme">>, <<"http">>}, {<<":scheme">>, <<"https">>}, {<<":status">>, <<"200">>}, {<<":status">>, <<"204">>}, {<<":status">>, <<"206">>}, {<<":status">>, <<"304">>}, {<<":status">>, <<"400">>}, {<<":status">>, <<"404">>}, {<<":status">>, <<"500">>}, {<<"accept-charset">>, <<>>}, {<<"accept-encoding">>, <<"gzip, deflate">>}, {<<"accept-language">>, <<>>}, {<<"accept-ranges">>, <<>>}, {<<"accept">>, <<>>}, {<<"access-control-allow-origin">>, <<>>}, {<<"age">>, <<>>}, {<<"allow">>, <<>>}, {<<"authorization">>, <<>>}, {<<"cache-control">>, <<>>}, {<<"content-disposition">>, <<>>}, {<<"content-encoding">>, <<>>}, {<<"content-language">>, <<>>}, {<<"content-length">>, <<>>}, {<<"content-location">>, <<>>}, {<<"content-range">>, <<>>}, {<<"content-type">>, <<>>}, {<<"cookie">>, <<>>}, {<<"date">>, <<>>}, {<<"etag">>, <<>>}, {<<"expect">>, <<>>}, {<<"expires">>, <<>>}, {<<"from">>, <<>>}, {<<"host">>, <<>>}, {<<"if-match">>, <<>>}, {<<"if-modified-since">>, <<>>}, {<<"if-none-match">>, <<>>}, {<<"if-range">>, <<>>}, {<<"if-unmodified-since">>, <<>>}, {<<"last-modified">>, <<>>}, {<<"link">>, <<>>}, {<<"location">>, <<>>}, {<<"max-forwards">>, <<>>}, {<<"proxy-authenticate">>, <<>>}, {<<"proxy-authorization">>, <<>>}, {<<"range">>, <<>>}, {<<"referer">>, <<>>}, {<<"refresh">>, <<>>}, {<<"retry-after">>, <<>>}, {<<"server">>, <<>>}, {<<"set-cookie">>, <<>>}, {<<"strict-transport-security">>, <<>>}, {<<"transfer-encoding">>, <<>>}, {<<"user-agent">>, <<>>}, {<<"vary">>, <<>>}, {<<"via">>, <<>>}, {<<"www-authenticate">>, <<>>} }). %% Static table field map for O(1) exact match lookup -define(STATIC_FIELD_MAP, #{ {<<":authority">>, <<>>} => 1, {<<":method">>, <<"GET">>} => 2, {<<":method">>, <<"POST">>} => 3, {<<":path">>, <<"/">>} => 4, {<<":path">>, <<"/index.html">>} => 5, {<<":scheme">>, <<"http">>} => 6, {<<":scheme">>, <<"https">>} => 7, {<<":status">>, <<"200">>} => 8, {<<":status">>, <<"204">>} => 9, {<<":status">>, <<"206">>} => 10, {<<":status">>, <<"304">>} => 11, {<<":status">>, <<"400">>} => 12, {<<":status">>, <<"404">>} => 13, {<<":status">>, <<"500">>} => 14, {<<"accept-charset">>, <<>>} => 15, {<<"accept-encoding">>, <<"gzip, deflate">>} => 16, {<<"accept-language">>, <<>>} => 17, {<<"accept-ranges">>, <<>>} => 18, {<<"accept">>, <<>>} => 19, {<<"access-control-allow-origin">>, <<>>} => 20, {<<"age">>, <<>>} => 21, {<<"allow">>, <<>>} => 22, {<<"authorization">>, <<>>} => 23, {<<"cache-control">>, <<>>} => 24, {<<"content-disposition">>, <<>>} => 25, {<<"content-encoding">>, <<>>} => 26, {<<"content-language">>, <<>>} => 27, {<<"content-length">>, <<>>} => 28, {<<"content-location">>, <<>>} => 29, {<<"content-range">>, <<>>} => 30, {<<"content-type">>, <<>>} => 31, {<<"cookie">>, <<>>} => 32, {<<"date">>, <<>>} => 33, {<<"etag">>, <<>>} => 34, {<<"expect">>, <<>>} => 35, {<<"expires">>, <<>>} => 36, {<<"from">>, <<>>} => 37, {<<"host">>, <<>>} => 38, {<<"if-match">>, <<>>} => 39, {<<"if-modified-since">>, <<>>} => 40, {<<"if-none-match">>, <<>>} => 41, {<<"if-range">>, <<>>} => 42, {<<"if-unmodified-since">>, <<>>} => 43, {<<"last-modified">>, <<>>} => 44, {<<"link">>, <<>>} => 45, {<<"location">>, <<>>} => 46, {<<"max-forwards">>, <<>>} => 47, {<<"proxy-authenticate">>, <<>>} => 48, {<<"proxy-authorization">>, <<>>} => 49, {<<"range">>, <<>>} => 50, {<<"referer">>, <<>>} => 51, {<<"refresh">>, <<>>} => 52, {<<"retry-after">>, <<>>} => 53, {<<"server">>, <<>>} => 54, {<<"set-cookie">>, <<>>} => 55, {<<"strict-transport-security">>, <<>>} => 56, {<<"transfer-encoding">>, <<>>} => 57, {<<"user-agent">>, <<>>} => 58, {<<"vary">>, <<>>} => 59, {<<"via">>, <<>>} => 60, {<<"www-authenticate">>, <<>>} => 61 }). %% Static table name map for O(1) name-only lookup -define(STATIC_NAME_MAP, #{ <<":authority">> => 1, <<":method">> => 2, <<":path">> => 4, <<":scheme">> => 6, <<":status">> => 8, <<"accept-charset">> => 15, <<"accept-encoding">> => 16, <<"accept-language">> => 17, <<"accept-ranges">> => 18, <<"accept">> => 19, <<"access-control-allow-origin">> => 20, <<"age">> => 21, <<"allow">> => 22, <<"authorization">> => 23, <<"cache-control">> => 24, <<"content-disposition">> => 25, <<"content-encoding">> => 26, <<"content-language">> => 27, <<"content-length">> => 28, <<"content-location">> => 29, <<"content-range">> => 30, <<"content-type">> => 31, <<"cookie">> => 32, <<"date">> => 33, <<"etag">> => 34, <<"expect">> => 35, <<"expires">> => 36, <<"from">> => 37, <<"host">> => 38, <<"if-match">> => 39, <<"if-modified-since">> => 40, <<"if-none-match">> => 41, <<"if-range">> => 42, <<"if-unmodified-since">> => 43, <<"last-modified">> => 44, <<"link">> => 45, <<"location">> => 46, <<"max-forwards">> => 47, <<"proxy-authenticate">> => 48, <<"proxy-authorization">> => 49, <<"range">> => 50, <<"referer">> => 51, <<"refresh">> => 52, <<"retry-after">> => 53, <<"server">> => 54, <<"set-cookie">> => 55, <<"strict-transport-security">> => 56, <<"transfer-encoding">> => 57, <<"user-agent">> => 58, <<"vary">> => 59, <<"via">> => 60, <<"www-authenticate">> => 61 }). %%==================================================================== %% State Initialization %%==================================================================== -spec init() -> state(). init() -> #state{entries = erlang:make_tuple(?DEFAULT_RING_SIZE, undefined)}. -spec init(non_neg_integer()) -> state(). init(MaxSize) -> #state{ max_size = MaxSize, configured_max_size = MaxSize, entries = erlang:make_tuple(?DEFAULT_RING_SIZE, undefined) }. -spec set_max_size(non_neg_integer(), State) -> State when State::state(). set_max_size(MaxSize, State) -> State#state{configured_max_size = MaxSize}. %%==================================================================== %% Decoding %%==================================================================== -spec decode(binary()) -> {headers(), state()}. decode(Data) -> decode(Data, init()). -spec decode(binary(), State) -> {headers(), State} when State::state(). %% Dynamic table size update is only allowed at the beginning of a HEADERS block. decode(<<0:2, 1:1, Rest/bits>>, State = #state{configured_max_size = ConfigMaxSize}) -> {MaxSize, Rest2} = dec_int5(Rest), if MaxSize =< ConfigMaxSize -> State2 = table_update_size(MaxSize, State), decode(Rest2, State2) end; decode(Data, State) -> decode(Data, State, []). decode(<<>>, State, Acc) -> {lists:reverse(Acc), State}; %% Indexed header field representation. decode(<<1:1, Rest/bits>>, State, Acc) -> dec_indexed(Rest, State, Acc); %% Literal header field with incremental indexing: new name. decode(<<0:1, 1:1, 0:6, Rest/bits>>, State, Acc) -> dec_lit_index_new_name(Rest, State, Acc); %% Literal header field with incremental indexing: indexed name. decode(<<0:1, 1:1, Rest/bits>>, State, Acc) -> dec_lit_index_indexed_name(Rest, State, Acc); %% Literal header field without indexing: new name. decode(<<0:8, Rest/bits>>, State, Acc) -> dec_lit_no_index_new_name(Rest, State, Acc); %% Literal header field without indexing: indexed name. decode(<<0:4, Rest/bits>>, State, Acc) -> dec_lit_no_index_indexed_name(Rest, State, Acc); %% Literal header field never indexed: new name. decode(<<0:3, 1:1, 0:4, Rest/bits>>, State, Acc) -> dec_lit_no_index_new_name(Rest, State, Acc); %% Literal header field never indexed: indexed name. decode(<<0:3, 1:1, Rest/bits>>, State, Acc) -> dec_lit_no_index_indexed_name(Rest, State, Acc). %% Indexed header field representation. dec_indexed(<<2#1111111:7, 0:1, Int:7, Rest/bits>>, State, Acc) -> {Name, Value} = table_get(127 + Int, State), decode(Rest, State, [{Name, Value} | Acc]); dec_indexed(<<2#1111111:7, Rest0/bits>>, State, Acc) -> {Index, Rest} = dec_big_int(Rest0, 127, 0), {Name, Value} = table_get(Index, State), decode(Rest, State, [{Name, Value} | Acc]); dec_indexed(<>, State, Acc) -> {Name, Value} = table_get(Index, State), decode(Rest, State, [{Name, Value} | Acc]). %% Literal header field with incremental indexing. dec_lit_index_new_name(Rest, State, Acc) -> {Name, Rest2} = dec_str(Rest), dec_lit_index(Rest2, State, Acc, Name). dec_lit_index_indexed_name(<<2#111111:6, 0:1, Int:7, Rest/bits>>, State, Acc) -> Name = table_get_name(63 + Int, State), dec_lit_index(Rest, State, Acc, Name); dec_lit_index_indexed_name(<<2#111111:6, Rest0/bits>>, State, Acc) -> {Index, Rest} = dec_big_int(Rest0, 63, 0), Name = table_get_name(Index, State), dec_lit_index(Rest, State, Acc, Name); dec_lit_index_indexed_name(<>, State, Acc) -> Name = table_get_name(Index, State), dec_lit_index(Rest, State, Acc, Name). dec_lit_index(Rest, State, Acc, Name) -> {Value, Rest2} = dec_str(Rest), State2 = table_insert({Name, Value}, State), decode(Rest2, State2, [{Name, Value} | Acc]). %% Literal header field without indexing. dec_lit_no_index_new_name(Rest, State, Acc) -> {Name, Rest2} = dec_str(Rest), dec_lit_no_index(Rest2, State, Acc, Name). dec_lit_no_index_indexed_name(<<2#1111:4, 0:1, Int:7, Rest/bits>>, State, Acc) -> Name = table_get_name(15 + Int, State), dec_lit_no_index(Rest, State, Acc, Name); dec_lit_no_index_indexed_name(<<2#1111:4, Rest0/bits>>, State, Acc) -> {Index, Rest} = dec_big_int(Rest0, 15, 0), Name = table_get_name(Index, State), dec_lit_no_index(Rest, State, Acc, Name); dec_lit_no_index_indexed_name(<>, State, Acc) -> Name = table_get_name(Index, State), dec_lit_no_index(Rest, State, Acc, Name). dec_lit_no_index(Rest, State, Acc, Name) -> {Value, Rest2} = dec_str(Rest), decode(Rest2, State, [{Name, Value} | Acc]). %% Integer decoding dec_int5(<<2#11111:5, Rest/bits>>) -> dec_big_int(Rest, 31, 0); dec_int5(<>) -> {Int, Rest}. dec_big_int(<<0:1, Value:7, Rest/bits>>, Int, M) -> {Int + (Value bsl M), Rest}; dec_big_int(<<1:1, Value:7, Rest/bits>>, Int, M) -> dec_big_int(Rest, Int + (Value bsl M), M + 7). %% String decoding dec_str(<<0:1, 2#1111111:7, Rest0/bits>>) -> {Length, Rest1} = dec_big_int(Rest0, 127, 0), <> = Rest1, {Str, Rest}; dec_str(<<0:1, Length:7, Rest0/bits>>) -> <> = Rest0, {Str, Rest}; dec_str(<<1:1, 2#1111111:7, Rest0/bits>>) -> {Length, Rest} = dec_big_int(Rest0, 127, 0), dec_huffman(Rest, Length, 0, <<>>); dec_str(<<1:1, Length:7, Rest/bits>>) -> dec_huffman(Rest, Length, 0, <<>>). %% Huffman decoding using lookup table dec_huffman(<>, Len, Huff0, Acc) when Len > 1 -> {_, CharA, Huff1} = dec_huffman_lookup(Huff0, A), {_, CharB, Huff} = dec_huffman_lookup(Huff1, B), case {CharA, CharB} of {undefined, undefined} -> dec_huffman(R, Len - 1, Huff, Acc); {CharA, undefined} -> dec_huffman(R, Len - 1, Huff, <>); {undefined, CharB} -> dec_huffman(R, Len - 1, Huff, <>); {CharA, CharB} -> dec_huffman(R, Len - 1, Huff, <>) end; dec_huffman(<>, 1, Huff0, Acc) -> {_, CharA, Huff} = dec_huffman_lookup(Huff0, A), {ok, CharB, _} = dec_huffman_lookup(Huff, B), case {CharA, CharB} of {CharA, undefined} -> {<>, Rest}; {undefined, CharB} -> {<>, Rest}; _ -> {<>, Rest} end; dec_huffman(Rest, 0, _, <<>>) -> {<<>>, Rest}. %%==================================================================== %% Encoding %%==================================================================== -spec encode(headers()) -> {iodata(), state()}. encode(Headers) -> encode(Headers, init(), huffman, []). -spec encode(headers(), State) -> {iodata(), State} when State::state(). encode(Headers, State = #state{max_size = MaxSize, configured_max_size = MaxSize}) -> encode(Headers, State, huffman, []); encode(Headers, State0 = #state{configured_max_size = MaxSize}) -> State1 = table_update_size(MaxSize, State0), {Data, State} = encode(Headers, State1, huffman, []), {[enc_int5(MaxSize, 2#001) | Data], State}. -spec encode(headers(), State, opts()) -> {iodata(), State} when State::state(). encode(Headers, State = #state{max_size = MaxSize, configured_max_size = MaxSize}, Opts) -> encode(Headers, State, huffman_opt(Opts), []); encode(Headers, State0 = #state{configured_max_size = MaxSize}, Opts) -> State1 = table_update_size(MaxSize, State0), {Data, State} = encode(Headers, State1, huffman_opt(Opts), []), {[enc_int5(MaxSize, 2#001) | Data], State}. huffman_opt(#{huffman := false}) -> no_huffman; huffman_opt(_) -> huffman. encode([], State, _, Acc) -> {lists:reverse(Acc), State}; encode([{Name, Value0} | Tail], State, HuffmanOpt, Acc) -> Value = if is_binary(Value0) -> Value0; true -> iolist_to_binary(Value0) end, Header = {Name, Value}, case table_find(Header, State) of %% Indexed header field representation. {field, Index} -> encode(Tail, State, HuffmanOpt, [enc_int7(Index, 2#1) | Acc]); %% Literal header field representation: indexed name. {name, Index} -> State2 = table_insert(Header, State), encode(Tail, State2, HuffmanOpt, [[enc_int6(Index, 2#01) | enc_str(Value, HuffmanOpt)] | Acc]); %% Literal header field representation: new name. not_found -> State2 = table_insert(Header, State), encode(Tail, State2, HuffmanOpt, [[<<0:1, 1:1, 0:6>> | [enc_str(Name, HuffmanOpt) | enc_str(Value, HuffmanOpt)]] | Acc]) end. %% Integer encoding enc_int5(Int, Prefix) when Int < 31 -> <>; enc_int5(Int, Prefix) -> enc_big_int(Int - 31, <>). enc_int6(Int, Prefix) when Int < 63 -> <>; enc_int6(Int, Prefix) -> enc_big_int(Int - 63, <>). enc_int7(Int, Prefix) when Int < 127 -> <>; enc_int7(Int, Prefix) -> enc_big_int(Int - 127, <>). enc_big_int(Int, Acc) when Int < 128 -> <>; enc_big_int(Int, Acc) -> enc_big_int(Int bsr 7, <>). %% String encoding enc_str(Str, huffman) -> Encoded = enc_huffman(Str), [enc_int7(byte_size(Encoded), 2#1) | Encoded]; enc_str(Str, no_huffman) -> [enc_int7(byte_size(Str), 2#0) | Str]. %% Huffman encoding using lookup table enc_huffman(Str) -> enc_huffman(Str, <<>>). enc_huffman(<<>>, Acc) -> %% Add EOS padding case bit_size(Acc) rem 8 of 0 -> Acc; N -> Padding = 8 - N, PadBits = (1 bsl Padding) - 1, <> end; enc_huffman(<>, Acc) -> {Code, Bits} = ?HUFFMAN_CODE(Byte), enc_huffman(Rest, <>). %%==================================================================== %% Table Operations %%==================================================================== %% Find header in table - O(1) using maps table_find(Header = {Name, _Value}, State) -> %% First check static table for exact match case maps:find(Header, ?STATIC_FIELD_MAP) of {ok, Index} -> {field, Index}; error -> %% Check dynamic table for exact match case find_in_dynamic_field(Header, State) of {ok, Index} -> {field, Index}; error -> %% Check static table for name match case maps:find(Name, ?STATIC_NAME_MAP) of {ok, Index} -> {name, Index}; error -> %% Check dynamic table for name match case find_in_dynamic_name(Name, State) of {ok, Index} -> {name, Index}; error -> not_found end end end end. %% Find exact field match in dynamic table find_in_dynamic_field(Header, #state{field_index = FieldIndex, insert_count = InsertCount, count = Count}) -> case maps:find(Header, FieldIndex) of {ok, AbsIndex} when InsertCount - AbsIndex < Count -> %% Convert absolute index to relative index %% Relative index = insert_count - abs_index + STATIC_TABLE_SIZE {ok, ?STATIC_TABLE_SIZE + (InsertCount - AbsIndex) + 1}; _ -> error end. %% Find name match in dynamic table find_in_dynamic_name(Name, #state{name_index = NameIndex, insert_count = InsertCount, count = Count}) -> case maps:find(Name, NameIndex) of {ok, AbsIndex} when InsertCount - AbsIndex < Count -> {ok, ?STATIC_TABLE_SIZE + (InsertCount - AbsIndex) + 1}; _ -> error end. %% Get entry by index (1-based) - O(1) table_get(Index, _State) when Index >= 1, Index =< ?STATIC_TABLE_SIZE -> element(Index, ?STATIC_TABLE); table_get(Index, State) when Index > ?STATIC_TABLE_SIZE -> DynIndex = Index - ?STATIC_TABLE_SIZE, get_dynamic_entry(DynIndex, State). %% Get name by index (1-based) - O(1) table_get_name(Index, State) -> {Name, _Value} = table_get(Index, State), Name. %% Get dynamic table entry by relative index (1 = newest) get_dynamic_entry(RelIndex, #state{entries = Entries, head = Head, count = Count}) when RelIndex >= 1, RelIndex =< Count -> RingSize = tuple_size(Entries), %% RelIndex 1 is at head, RelIndex 2 is at head-1, etc. Pos = ((Head - RelIndex + RingSize) rem RingSize) + 1, {_Size, Header} = element(Pos, Entries), Header. %% Insert entry into dynamic table - O(1) amortized table_insert(Entry = {Name, Value}, State = #state{ size = Size, max_size = MaxSize, insert_count = InsertCount }) -> EntrySize = byte_size(Name) + byte_size(Value) + ?ENTRY_OVERHEAD, if EntrySize > MaxSize -> %% Entry larger than table - clear everything State#state{ size = 0, head = 0, count = 0, field_index = #{}, name_index = #{}, insert_count = InsertCount + 1 }; EntrySize + Size =< MaxSize -> %% Add entry without eviction add_entry(Entry, EntrySize, State); true -> %% Need to evict entries first State2 = evict_entries(State, EntrySize), add_entry(Entry, EntrySize, State2) end. %% Add entry to ring buffer add_entry(Entry = {Name, _Value}, EntrySize, State = #state{ size = Size, entries = Entries, head = Head, count = Count, field_index = FieldIndex, name_index = NameIndex, insert_count = InsertCount }) -> RingSize = tuple_size(Entries), NewInsertCount = InsertCount + 1, %% Calculate new head position NewHead = (Head rem RingSize) + 1, %% Grow ring buffer if needed {NewEntries, _NewRingSize} = case Count >= RingSize of true -> %% Double the ring buffer size grow_ring_buffer(Entries, RingSize); false -> {Entries, RingSize} end, %% Insert entry NewEntries2 = setelement(NewHead, NewEntries, {EntrySize, Entry}), State#state{ size = Size + EntrySize, entries = NewEntries2, head = NewHead, count = Count + 1, field_index = FieldIndex#{Entry => NewInsertCount}, name_index = NameIndex#{Name => NewInsertCount}, insert_count = NewInsertCount }. %% Grow ring buffer by doubling its size grow_ring_buffer(Entries, OldSize) -> NewSize = OldSize * 2, NewEntries = erlang:make_tuple(NewSize, undefined), %% Copy existing entries NewEntries2 = copy_entries(Entries, NewEntries, 1, OldSize), {NewEntries2, NewSize}. copy_entries(_Old, New, I, Size) when I > Size -> New; copy_entries(Old, New, I, Size) -> copy_entries(Old, setelement(I, New, element(I, Old)), I + 1, Size). %% Evict oldest entries to make room evict_entries(State = #state{max_size = MaxSize}, NewEntrySize) -> TargetSize = MaxSize - NewEntrySize, evict_until(State, TargetSize). evict_until(State = #state{size = Size}, TargetSize) when Size =< TargetSize -> State; evict_until(State = #state{count = 0}, _TargetSize) -> State; evict_until(State = #state{ size = Size, entries = Entries, head = Head, count = Count, field_index = FieldIndex, name_index = NameIndex }, TargetSize) -> %% Find oldest entry (tail of ring) RingSize = tuple_size(Entries), TailPos = ((Head - Count + RingSize) rem RingSize) + 1, {EntrySize, {Name, _Value} = Entry} = element(TailPos, Entries), %% Remove from maps (only if pointing to this entry) NewFieldIndex = maps:remove(Entry, FieldIndex), NewNameIndex = maps:remove(Name, NameIndex), %% Clear entry and update state NewState = State#state{ size = Size - EntrySize, entries = setelement(TailPos, Entries, undefined), count = Count - 1, field_index = NewFieldIndex, name_index = NewNameIndex }, evict_until(NewState, TargetSize). %% Update table size table_update_size(0, State) -> State#state{ size = 0, max_size = 0, head = 0, count = 0, field_index = #{}, name_index = #{} }; table_update_size(MaxSize, State = #state{size = CurrentSize}) when CurrentSize =< MaxSize -> State#state{max_size = MaxSize}; table_update_size(MaxSize, State) -> %% Need to evict entries evict_until(State#state{max_size = MaxSize}, MaxSize).