%% ``The contents of this file are subject to the Erlang Public License, %% Version 1.1, (the "License"); you may not use this file except in %% compliance with the License. You should have received a copy of the %% Erlang Public License along with this software. If not, it can be %% retrieved via the world wide web at http://www.erlang.org/. %% %% Software distributed under the License is distributed on an "AS IS" %% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See %% the License for the specific language governing rights and limitations %% under the License. %% %% Copyright 2007 Fredrik Svahn %% %% $Id$ %% %% Implements "vlists" somewhat naively without optimizations %% %% Vlists is a list of arrays. Each list item consists of the tuple %% {Ofs, Pos, Size, Array}, where Ofs is the number of entries in the %% Array which are currently in use. Pos is used when iterating over %% the array, Size has a double usage: It holds the size of the array, %% and the signedness indicates which way to traverse the array (used %% e.g. for reversing lists). Array, finally, is the container holding %% the elements stored in the vlist. %% The size of the arrays grow by a factor R, in this case R=4 is used. %% %% This is how it would look like if numbers 1..6 where inserted %% and the 7..9 where appended using insert_last (corresponding to %% the list [6,5,4,3,2,1,7,8,9]): %% %% [ L3 L2 L1 L4 ] %% Size:16 Size:4 Size:1 Size:-4 %% Ofs: 1 Ofs: 4 Ofs: 1 Ofs: 3 %% 6 2^ 1 7v %% 3^ 8v %% 4^ 9v %% 5^ %% %% "^" and "v" indicates the direction used when traversing the array. %% Reversing the list yields: %% %% [ L4 L1 L2 L3 ] %% Size:4 Size:-1 Size:-4 Size:-16 %% Ofs: 3 Ofs: 1 Ofs: 4 Ofs: 1 %% 7^ 1v 2v 6 %% 8^ 3v %% 9^ 4v %% 5v %% %% Corresponding to [9,8,7,1,2,3,4,5,6]. -module(vlists). -export([new/1, vlist_to_list/1, get_first/1, nth/2, reverse/1, insert/2, insert_last/2, length/1]). -compile(export_all). %%--------------------------------------------------------------------------- %% %% %% Exported interface functions %% %% %%--------------------------------------------------------------------------- new(List) -> new(lists:reverse(List), []). new([], VList) -> VList; new([H|T], VList) -> new(T, insert(H, VList)). vlist_to_list(VList) -> vlist_to_list(get_first(VList), []). vlist_to_list(eol, List)-> lists:reverse(List); vlist_to_list({H, T}, List)-> vlist_to_list(get_first(T), [H | List]). get_first([])-> eol; get_first([{_, 0, _, _} | T]) -> get_first(T); get_first([{Ofs, Pos, Size, Array} | T]) when Size > 0 -> {hipe_bifs:array_sub(Array, Pos - 1), [{Ofs, Pos - 1, Size, Array} | T ]}; get_first([{Ofs, Pos, Size, Array} | T]) -> {hipe_bifs:array_sub(Array, Ofs-Pos), [{Ofs, Pos - 1, Size, Array} | T ]}. nth(0, _) -> erlang:fault(badarg); nth(_, []) -> erlang:fault(badarg); nth(N, [{Ofs, _, _, _} | L]) when N > Ofs -> nth(N - Ofs, L); nth(N, [{_, _, Size, Array} | _]) when Size < 0 -> hipe_bifs:array_sub(Array, N-1); nth(N, [{Ofs, _, _, Array} | _]) -> hipe_bifs:array_sub(Array, Ofs - N). length(L)-> lists:foldl(fun({Ofs,_,_,_}, Sum)-> Ofs + Sum end, 0, L). reverse(L)-> reverse(L,[]). reverse([], Acc) -> Acc; reverse([{Ofs, Pos, Size, Array}| T ], Acc) -> reverse(T, [{Ofs, Pos, -Size, Array}|Acc]). insert(Element, []) -> [{1, 1, 1, hipe_bifs:array(1, Element)}]; insert(Element, List = [{Ofs, Pos, Size, Array} | Tail ]) -> if Ofs < abs(Size) -> hipe_bifs:array_update(Array, Ofs, Element), [{Ofs + 1, Pos + 1, Size, Array} | Tail]; true -> [{1, 1, Size*4, hipe_bifs:array(abs(Size)*4, Element)}| List] end. insert_last(Element, []) -> [{1, 1, 1, hipe_bifs:array(1, Element)}]; insert_last(Element, List) -> [{Ofs, Pos, Size, Array}|TailRev] = lists:reverse(List), Body = lists:reverse(TailRev), ASize=abs(Size), if Ofs < ASize -> hipe_bifs:array_update(Array, Ofs, Element), Body++[{Ofs + 1, Pos + 1, Size, Array}]; true -> List++[{1, 1, -ASize*4, hipe_bifs:array(ASize*4, Element)}] end. %%--------------------------------------------------------------------------- %% %% %% Test functions %% %% %%--------------------------------------------------------------------------- %%Comparative lists-based interface for reference and test old_get_first([]) -> eol; old_get_first([First| Rest]) -> {First, Rest}. old_insert(Element, List) -> [Element|List]. old_nth(N, L)-> lists:nth(N, L). old_reverse(L)-> lists:reverse(L). old_insert_last(Element, L)-> L ++ [Element]. old_length(L)-> erlang:length(L). test()-> test(1000). test([Length])-> Len=list_to_integer(Length), io:format(" {insert,insert_last,iterate,first,last,reverse,length}~n"), {{T1,L1},{T2,L2},{T3,C1},{T4,1},{T5,1},{T6,L3},{T7,Len}}=test(Len, "old_"), io:format("lists: ~p~n", [{T1, T2, T3, T4, T5, T6, T7}]), {{X1,VL1},{X2,VL2},{X3,C1},{X4,1},{X5,1},{X6,VL3},{X7,Len}}=test(Len, ""), io:format("vlists: ~p~n", [{X1, X2, X3, X4, X5, X6, X7}]), %Assert that lists are equal after insert, insert_last, reverse L1=vlist_to_list(VL1), L2=vlist_to_list(VL2), L3=vlist_to_list(VL3), ok. test(Len, F)-> {T1,List} = timer:tc(?MODULE, add_entries, [Len div 2, [], list_to_atom(F++"insert")]), {T2,List2} = timer:tc(?MODULE, add_entries, [Len div 2, List, list_to_atom(F++"insert_last")]), R3 = timer:tc(?MODULE, iterate_over_list, [List2, list_to_atom(F++"get_first")]), R4 = timer:tc(?MODULE, list_to_atom(F++"nth"),[1, List2]), R5 = timer:tc(?MODULE, list_to_atom(F++"nth"),[Len, List2]), R6 = timer:tc(?MODULE, list_to_atom(F++"reverse"),[List2]), R7 = timer:tc(?MODULE, list_to_atom(F++"length"),[List2]), {{T1,List}, {T2,List2}, R3, R4, R5, R6, R7}. add_entries(0, List, _)-> List; add_entries(Size, List, F)-> add_entries(Size - 1, apply(?MODULE, F, [Size, List]), F). iterate_over_list(L, F)-> do_iterate_over_list(apply(?MODULE, F,[L]), F, 0). do_iterate_over_list(eol, _, Sum)-> Sum; do_iterate_over_list({H, T}, F, Sum)-> do_iterate_over_list(apply(?MODULE, F, [T]), F, Sum + H). %Make random operations on normal lists i/f and vlists i/f and compare results qc()-> qc(1, [], [], 0). qc(_, _, _, 10000)-> ok; qc(1, L, VL, Len)-> io:format("insert~n"), NewL = old_insert(Len, L), NewVL = insert(Len, VL), NewL = vlist_to_list(NewVL), qc(random:uniform(5), NewL, NewVL, Len+1); qc(2, L, VL, Len)-> io:format("insert_last~n"), NewL = old_insert_last(Len, L), NewVL = insert_last(Len, VL), NewL = vlist_to_list(NewVL), qc(random:uniform(5), NewL, NewVL, Len+1); qc(3, L, VL, Len)-> io:format("reverse~n"), NewL = old_reverse(L), NewVL = reverse(VL), NewL = vlist_to_list(NewVL), qc(random:uniform(5), NewL, NewVL, Len); qc(4, L, VL, Len)-> io:format("nth~n"), N=random:uniform(Len), C=lists:nth(N,L), C=vlists:nth(N,VL), qc(random:uniform(5), L, VL, Len); qc(5, L, VL, Len)-> C=old_length(L), C=vlists:length(VL), io:format("length is ~p~n",[C]), qc(random:uniform(5), L, VL, Len); qc(_, L, VL, Len)-> qc(4, L, VL, Len).