lib/etorrent-1.0/src/etorrent_utils.erl

   1 %%%-------------------------------------------------------------------
   2 %%% File    : etorrent_utils.erl
   3 %%% Author  : User Jlouis <jesper.louis.andersen@gmail.com>
   4 %%% License : See COPYING
   5 %%% Description : A selection of utilities used throughout the code
   6 %%%
   7 %%% Created : 17 Apr 2007 by User Jlouis <jesper.louis.andersen@gmail.com>
   8 %%%-------------------------------------------------------------------
   9 -module(etorrent_utils).
  10
  11 %% API
  12 -export([queue_remove/2, queue_remove_with_check/2,
  13          build_encoded_form_rfc1738/1,
  14          shuffle/1, gsplit/2]).
  15
  16 %%====================================================================
  17 %% API
  18 %%====================================================================
  19
  20 %%--------------------------------------------------------------------
  21 %% Function: gsplit(N, L1) -> {L2, L3}
  22 %% Description:
  23 %%    types: N          - integer()
  24 %%           L1, L2, L3 - list()
  25 %%
  26 %%   Graceful split. Works is lists:split, but if N is greater than
  27 %%     length(L1) then L1 =:= L2 and L3 = []
  28 %%--------------------------------------------------------------------
  29 gsplit(N, L) ->
  30     gsplit(N, L, []).
  31
  32 gsplit(_N, [], Rest) ->
  33     {lists:reverse(Rest), []};
  34 gsplit(0, L1, Rest) ->
  35     {lists:reverse(Rest), L1};
  36 gsplit(N, [H|T], Rest) ->
  37     gsplit(N-1, T, [H | Rest]).
  38
  39 %%--------------------------------------------------------------------
  40 %% Function: queue_remove_with_check(Item, Q1) -> {ok, Q2} | false
  41 %% Description: If Item is present in queue(), remove the first
  42 %%   occurence and return it as {ok, Q2}. If the item can not be found
  43 %%   return false.
  44 %%   Note: Inefficient implementation. Converts to/from lists.
  45 %%--------------------------------------------------------------------
  46 queue_remove_with_check(Item, Q) ->
  47     QList = queue:to_list(Q),
  48     case lists:member(Item, QList) of
  49         true ->
  50             List = lists:delete(Item, QList),
  51             {ok, queue:from_list(List)};
  52         false ->
  53             false
  54     end.
  55
  56 %%--------------------------------------------------------------------
  57 %% Function: queue_remove(Item, queue()) -> queue()
  58 %% Description: Remove first occurence of Item in queue() if present.
  59 %%   Note: This function assumes the representation of queue is opaque
  60 %%     and thus the function is quite ineffective. We can build a much
  61 %%     much faster version if we create our own queues.
  62 %%--------------------------------------------------------------------
  63 queue_remove(Item, Q) ->
  64     QList = queue:to_list(Q),
  65     List = lists:delete(Item, QList),
  66     queue:from_list(List).
  67
  68 %%--------------------------------------------------------------------
  69 %% Function: build_encoded_form_rfc1738(list() | binary()) -> String
  70 %% Description: Convert the list into RFC1738 encoding (URL-encoding).
  71 %%--------------------------------------------------------------------
  72 build_encoded_form_rfc1738(List) when is_list(List) ->
  73     Unreserved = rfc_3986_unreserved_characters_set(),
  74     F = fun (E) ->
  75                 case sets:is_element(E, Unreserved) of
  76                     true ->
  77                         E;
  78                     false ->
  79                         lists:concat(
  80                           ["%", io_lib:format("~2.16.0B", [E])])
  81                 end
  82         end,
  83     lists:flatten([F(E) || E <- List]);
  84 build_encoded_form_rfc1738(Binary) when is_binary(Binary) ->
  85     build_encoded_form_rfc1738(binary_to_list(Binary)).
  86
  87 %%--------------------------------------------------------------------
  88 %% Function: shuffle(List1) -> List2
  89 %% Description: Permute List1 randomly. Returns the permuted list.
  90 %%--------------------------------------------------------------------
  91 shuffle(List) ->
  92     merge_shuffle(List).
  93
  94 %%====================================================================
  95 %% Internal functions
  96 %%====================================================================
  97
  98 rfc_3986_unreserved_characters() ->
  99     % jlouis: I deliberately killed ~ from the list as it seems the Mainline
 100     %  client doesn't announce this.
 101     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_./".
 102
 103 rfc_3986_unreserved_characters_set() ->
 104     sets:from_list(rfc_3986_unreserved_characters()).
 105
 106 %%
 107 %% Flip a coin randomly
 108 flip_coin() ->
 109     random:uniform(2) - 1.
 110
 111 %%
 112 %% Merge 2 lists, using a coin flip to choose which list to take the next element from.
 113 merge(A, []) ->
 114     A;
 115 merge([], B) ->
 116     B;
 117 merge([A | As], [B | Bs]) ->
 118     case flip_coin() of
 119         0 ->
 120             [A | merge(As, [B | Bs])];
 121         1 ->
 122             [B | merge([A | As], Bs)]
 123     end.
 124
 125 %%
 126 %% Partition a list into items.
 127 partition(List) ->
 128     partition_l(List, [], []).
 129
 130 partition_l([], A, B) ->
 131     {A, B};
 132 partition_l([Item], A, B) ->
 133     {B, [Item | A]};
 134 partition_l([Item | Rest], A, B) ->
 135     partition_l(Rest, B, [Item | A]).
 136
 137 %%
 138 %% Shuffle a list by partitioning it and then merging it back by coin-flips
 139 merge_shuffle([]) ->
 140     [];
 141 merge_shuffle([Item]) ->
 142     [Item];
 143 merge_shuffle(List) ->
 144     {A, B} = partition(List),
 145     merge(merge_shuffle(A), merge_shuffle(B)).
 146
 147
 148
 149
 150
 151