How to retrieve a list of ets keys without scanning entire table?

Question

I'm using ets via elixir as a simple in-memory persistence layer to store and retrieve keys and also for the occasional foldl which involves reducing many duplicate keys that have different values. I am using the bag option.

Is there a simple, perhaps O(1) way to retrieve a list of just the current keys without having to do a more involved table traversal or match or foldl?

Erlang or Elixir syntax responses welcome.

:ets.new(:cache, [:bag, :named_table, :protected])

I have a static map of atom keys indexed by integer I am using to assist with insertions. But not all the keys are used..

chunk_key_map = %{2 => :chunk_key_2, ..... 28 => :chunk_key_28}

If there's no quick way, I am aware I can do an ets:lookup trying each of my static atom key values and testing for != [] and generating my own list, but wanted to see if ets supports such a feature.

Thanks

Answer 1

Thanks, that put me on the right track :)

Same thing but passing the previous key as accumulator:

def key_stream(table_name) do
  Stream.resource(
    fn -> :ets.first(table_name) end,
    fn :"$end_of_table" -> {:halt, nil}
       previous_key -> {[previous_key], :ets.next(table_name, previous_key)} end,
    fn _ -> :ok end)
end

Answer 2

For getting a list of keys in ets without touching their values you can use the combination of ets:first/1 and ets:next/2 functions this way:

-export([keys/1]).

keys(TableName) ->
    FirstKey = ets:first(TableName),
        keys(TableName, FirstKey, [FirstKey]).

keys(_TableName, '$end_of_table', ['$end_of_table'|Acc]) ->
    Acc;
keys(TableName, CurrentKey, Acc) ->
    NextKey = ets:next(TableName, CurrentKey),
    keys(TableName, NextKey, [NextKey|Acc]).

The exported API is keys/1. It gets the table name, fetches the first key of it, initiates an accumulator as state and internally calls keys/2 which fetches other keys and accumulating them in a recursive manner.

Note that bag tables type do not have order, so if your table type is bag the return value of keys/1 wouldn't be ordered.

Answer 3

So I didn't find the ets technique, but rather implemented the key list retrieve code in constant time in elixir as my key map is static.

    list = Enum.reduce(2..28, [], fn head, acc -> 
            case :ets.lookup(:cache, Map.get(chunk_key_map, head)) do
                [] -> acc
                _ -> [acc, head]
            end
        end)

    List.flatten(list)

UPDATE: Based on the replies, I took Hamidreza's ets traversal logic and wrapped it into an Elixir Stream using Stream.resource/3.

defp get_ets_keys_lazy(table_name) when is_atom(table_name) do
    eot = :"$end_of_table"

    Stream.resource(
        fn -> [] end,

        fn acc ->
            case acc do
                [] -> 
                    case :ets.first(table_name) do
                        ^eot -> {:halt, acc}
                        first_key -> {[first_key], first_key}                       
                    end

                acc -> 
                    case :ets.next(table_name, acc) do  
                        ^eot -> {:halt, acc}
                        next_key -> {[next_key], next_key}
                    end
            end
        end,

        fn _acc -> :ok end
    )
end

Then I ran the stream through a pipeline

get_ets_keys_lazy(table_name) 
    |> Stream.map(lambda1) 
    |> Stream.each(lambda2)
    |> Stream.run