Current section
8 Versions
Jump to
Current section
8 Versions
Compare versions
5
files changed
+24
additions
-24
deletions
| @@ -1,4 +1,4 @@ | |
| 1 | - Cuckoo [](https://travis-ci.org/gmcabrita/cuckoo) [](https://coveralls.io/r/gmcabrita/cuckoo?branch=master) [](https://github.com/gmcabrita/cuckoo/blob/master/LICENSE) [](https://hex.pm/packages/cuckoo) |
| 1 | + Cuckoo [](https://travis-ci.org/gmcabrita/cuckoo) [](https://coveralls.io/r/gmcabrita/cuckoo?branch=master) [](https://hexdocs.pm/cuckoo) [](https://hex.pm/packages/cuckoo) [](https://github.com/gmcabrita/cuckoo/blob/master/LICENSE) |
| 2 2 | ====== |
| 3 3 | |
| 4 4 | Cuckoo is a pure Elixir implementation of a [Cuckoo Filter](https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf). |
| @@ -9,7 +9,7 @@ Add Cuckoo as a dependency in your mix.exs file. | |
| 9 9 | |
| 10 10 | ```elixir |
| 11 11 | def deps do |
| 12 | - [{:cuckoo, "~> 0.0.1"}] |
| 12 | + [{:cuckoo, "~> 0.2.0"}] |
| 13 13 | end |
| 14 14 | ``` |
| @@ -13,4 +13,4 @@ | |
| 13 13 | {<<"requirements">>, |
| 14 14 | #{<<"array">> => #{<<"app">> => <<"array">>,<<"optional">> => nil,<<"requirement">> => <<"~> 1.0">>}, |
| 15 15 | <<"murmur">> => #{<<"app">> => <<"murmur">>,<<"optional">> => nil,<<"requirement">> => <<"~> 0.2">>}}}. |
| 16 | - {<<"version">>,<<"0.1.0">>}. |
| 16 | + {<<"version">>,<<"0.2.0">>}. |
| @@ -47,13 +47,13 @@ defmodule Cuckoo.Bucket do | |
| 47 47 | Checks if the `bucket` has any room left. |
| 48 48 | |
| 49 49 | Returns `{ :ok, index }` if it finds an empty entry in the bucket, |
| 50 | - otherwise returns `{ :err, :full }`. |
| 50 | + otherwise returns `{ :error, :full }`. |
| 51 51 | """ |
| 52 | - @spec has_room?(t) :: { :ok, pos_integer } | { :err, :full } |
| 52 | + @spec has_room?(t) :: { :ok, pos_integer } | { :error, :full } |
| 53 53 | def has_room?(bucket) do |
| 54 54 | index = Enum.find_index(bucket, fn (x) -> x == nil end) |
| 55 55 | unless index do |
| 56 | - { :err, :full } |
| 56 | + { :error, :full } |
| 57 57 | else |
| 58 58 | { :ok, index } |
| 59 59 | end |
| @@ -72,13 +72,13 @@ defmodule Cuckoo.Bucket do | |
| 72 72 | @doc """ |
| 73 73 | Tries to find the given `element` in the `bucket`. |
| 74 74 | |
| 75 | - Returns `{:ok, index}` if it finds it, otherwise returns `{:err, :inexistent}`. |
| 75 | + Returns `{:ok, index}` if it finds it, otherwise returns `{:error, :inexistent}`. |
| 76 76 | """ |
| 77 | - @spec find(t, pos_integer) :: {:ok, non_neg_integer} | {:err, :inexistent} |
| 77 | + @spec find(t, pos_integer) :: {:ok, non_neg_integer} | {:error, :inexistent} |
| 78 78 | def find(bucket, element) do |
| 79 79 | index = Enum.find_index(bucket, fn (x) -> x == element end) |
| 80 80 | unless index do |
| 81 | - {:err, :inexistent} |
| 81 | + {:error, :inexistent} |
| 82 82 | else |
| 83 83 | {:ok, index} |
| 84 84 | end |
| @@ -85,10 +85,10 @@ defmodule Cuckoo do | |
| 85 85 | @doc """ |
| 86 86 | Tries to insert `element` into the Cuckoo Filter. |
| 87 87 | |
| 88 | - Returns `{:ok, filter}` if successful, otherwise returns `{:err, :full}` from which |
| 88 | + Returns `{:ok, filter}` if successful, otherwise returns `{:error, :full}` from which |
| 89 89 | you should consider the Filter to be full. |
| 90 90 | """ |
| 91 | - @spec insert(Filter.t, any) :: {:ok, Filter.t} | {:err, :full} |
| 91 | + @spec insert(Filter.t, any) :: {:ok, Filter.t} | {:error, :full} |
| 92 92 | def insert(%Filter{ |
| 93 93 | buckets: buckets, |
| 94 94 | fingerprint_size: bits_per_item, |
| @@ -108,7 +108,7 @@ defmodule Cuckoo do | |
| 108 108 | Bucket.set(i1_bucket, index, fingerprint) |
| 109 109 | )}} |
| 110 110 | |
| 111 | - {:err, :full} -> |
| 111 | + {:error, :full} -> |
| 112 112 | i2_bucket = Array.get(buckets, i2) |
| 113 113 | case Bucket.has_room?(i2_bucket) do |
| 114 114 | {:ok, index} -> |
| @@ -119,7 +119,7 @@ defmodule Cuckoo do | |
| 119 119 | Bucket.set(i2_bucket, index, fingerprint) |
| 120 120 | )}} |
| 121 121 | |
| 122 | - {:err, :full} -> |
| 122 | + {:error, :full} -> |
| 123 123 | if :random.uniform(2) == 1 do |
| 124 124 | kickout(filter, i1, fingerprint, fingerprints_per_bucket) |
| 125 125 | else |
| @@ -150,10 +150,10 @@ defmodule Cuckoo do | |
| 150 150 | @doc """ |
| 151 151 | Attempts to delete `element` from the Cuckoo Filter if it contains it. |
| 152 152 | |
| 153 | - Returns `{:err, :inexistent}` if the element doesn't exist in the filter, otherwise |
| 153 | + Returns `{:error, :inexistent}` if the element doesn't exist in the filter, otherwise |
| 154 154 | returns `{:ok, filter}`. |
| 155 155 | """ |
| 156 | - @spec delete(Filter.t, any) :: {:ok, Filter.t} | {:err, :inexistent} |
| 156 | + @spec delete(Filter.t, any) :: {:ok, Filter.t} | {:error, :inexistent} |
| 157 157 | def delete(%Filter{buckets: buckets, fingerprint_size: bits_per_item} = filter, element) do |
| 158 158 | num_buckets = Array.size(buckets) |
| 159 159 | {fingerprint, i1} = fingerprint_and_index(element, num_buckets, bits_per_item) |
| @@ -163,15 +163,15 @@ defmodule Cuckoo do | |
| 163 163 | {:ok, index} -> |
| 164 164 | updated_bucket = Bucket.reset(b1, index) |
| 165 165 | {:ok, %{filter | buckets: Array.set(buckets, i1, updated_bucket)}} |
| 166 | - {:err, :inexistent} -> |
| 166 | + {:error, :inexistent} -> |
| 167 167 | i2 = alt_index(i1, fingerprint, num_buckets) |
| 168 168 | b2 = Array.get(buckets, i2) |
| 169 169 | case Bucket.find(b2, fingerprint) do |
| 170 170 | {:ok, index} -> |
| 171 171 | updated_bucket = Bucket.reset(b2, index) |
| 172 172 | {:ok, %{filter | buckets: Array.set(buckets, i2, updated_bucket)}} |
| 173 | - {:err, :inexistent} -> |
| 174 | - {:err, :inexistent} |
| 173 | + {:error, :inexistent} -> |
| 174 | + {:error, :inexistent} |
| 175 175 | end |
| 176 176 | |
| 177 177 | end |
| @@ -185,7 +185,7 @@ defmodule Cuckoo do | |
| 185 185 | case insert(filter, element) do |
| 186 186 | {:ok, filter} -> |
| 187 187 | filter |
| 188 | - {:err, reason} -> |
| 188 | + {:error, reason} -> |
| 189 189 | raise Cuckoo.Error, reason: reason, action: "insert element", element: element |
| 190 190 | end |
| 191 191 | end |
| @@ -198,7 +198,7 @@ defmodule Cuckoo do | |
| 198 198 | case delete(filter, element) do |
| 199 199 | {:ok, filter} -> |
| 200 200 | filter |
| 201 | - {:err, reason} -> |
| 201 | + {:error, reason} -> |
| 202 202 | raise Cuckoo.Error, reason: reason, action: "delete element", element: element |
| 203 203 | end |
| 204 204 | end |
| @@ -206,9 +206,9 @@ defmodule Cuckoo do | |
| 206 206 | |
| 207 207 | # private helper functions |
| 208 208 | |
| 209 | - @spec kickout(Filter.t, non_neg_integer, pos_integer, pos_integer, pos_integer) :: {:ok, Filter.t} | {:err, :full} |
| 209 | + @spec kickout(Filter.t, non_neg_integer, pos_integer, pos_integer, pos_integer) :: {:ok, Filter.t} | {:error, :full} |
| 210 210 | defp kickout(filter, index, fingerprint, fingerprints_per_bucket, current_kick \\ @max_kicks) |
| 211 | - defp kickout(_, _, _, _, 0), do: {:err, :full} |
| 211 | + defp kickout(_, _, _, _, 0), do: {:error, :full} |
| 212 212 | defp kickout(%Filter{buckets: buckets} = filter, index, fingerprint, fingerprints_per_bucket, current_kick) do |
| 213 213 | bucket = Array.get(buckets, index) |
| 214 214 | |
| @@ -233,7 +233,7 @@ defmodule Cuckoo do | |
| 233 233 | bucket = Bucket.set(bucket, b_index, fingerprint) |
| 234 234 | buckets = Array.set(buckets, index, bucket) |
| 235 235 | {:ok, %{filter | buckets: buckets}} |
| 236 | - {:err, :full} -> |
| 236 | + {:error, :full} -> |
| 237 237 | kickout(%{filter | buckets: buckets}, index, fingerprint, fingerprints_per_bucket, current_kick - 1) |
| 238 238 | end |
| @@ -7,7 +7,7 @@ defmodule Cuckoo.Mixfile do | |
| 7 7 | |
| 8 8 | def project do |
| 9 9 | [app: :cuckoo, |
| 10 | - version: "0.1.0", |
| 10 | + version: "0.2.0", |
| 11 11 | elixir: "~> 1.0", |
| 12 12 | description: @description, |
| 13 13 | package: package, |