From 797544333ca9c40eb4e8b36fb58aefff9b0ebe02 Mon Sep 17 00:00:00 2001
From: Alexey Shchepin <alexey@process-one.net>
Date: Tue, 22 Apr 2008 21:51:32 +0000
Subject: * src/mod_register.erl: Restrict registration frequency per IP or
 user * src/ejabberd_c2s.erl: Pass IP to the c2s_unauthenticated_iq hook *
 src/ejabberd_config.erl: Added registration_timeout option * src/treap.erl:
 Treaps implementation

SVN Revision: 1299
---
 src/treap.erl | 164 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 164 insertions(+)
 create mode 100644 src/treap.erl

(limited to 'src/treap.erl')

diff --git a/src/treap.erl b/src/treap.erl
new file mode 100644
index 000000000..d7b070b9e
--- /dev/null
+++ b/src/treap.erl
@@ -0,0 +1,164 @@
+%%%----------------------------------------------------------------------
+%%% File    : treap.erl
+%%% Author  : Alexey Shchepin <alexey@process-one.net>
+%%% Purpose : Treaps implementation
+%%% Created : 22 Apr 2008 by Alexey Shchepin <alexey@process-one.net>
+%%%
+%%%
+%%% ejabberd, Copyright (C) 2002-2008   Process-one
+%%%
+%%% This program is free software; you can redistribute it and/or
+%%% modify it under the terms of the GNU General Public License as
+%%% published by the Free Software Foundation; either version 2 of the
+%%% License, or (at your option) any later version.
+%%%
+%%% This program is distributed in the hope that it will be useful,
+%%% but WITHOUT ANY WARRANTY; without even the implied warranty of
+%%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+%%% General Public License for more details.
+%%%
+%%% You should have received a copy of the GNU General Public License
+%%% along with this program; if not, write to the Free Software
+%%% Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+%%% 02111-1307 USA
+%%%
+%%%----------------------------------------------------------------------
+
+-module(treap).
+
+-export([empty/0,
+	 insert/4,
+	 delete/2,
+	 delete_root/1,
+	 get_root/1,
+	 lookup/2,
+	 is_empty/1]).
+
+empty() ->
+    nil.
+
+insert(Key, Priority, Value, Tree) ->
+    HashKey = {erlang:phash2(Key), Key},
+    insert1(Tree, HashKey, Priority, Value).
+
+insert1(nil, HashKey, Priority, Value) ->
+    {HashKey, Priority, Value, nil, nil};
+insert1({HashKey1, Priority1, Value1, Left, Right},
+	HashKey, Priority, Value) ->
+    if
+	HashKey < HashKey1 ->
+	    heapify({HashKey1, Priority1, Value1,
+		     insert1(Left, HashKey, Priority, Value),
+		     Right});
+	HashKey > HashKey1 ->
+	    heapify({HashKey1, Priority1, Value1,
+		     Left,
+		     insert1(Right, HashKey, Priority, Value)});
+	true ->
+	    erlang:error(key_exists)
+    end.
+
+heapify(nil) ->
+    nil;
+heapify({_HashKey, _Priority, _Value, nil, nil} = Tree) ->
+    Tree;
+heapify({HashKey, Priority, Value,
+	 nil = Left,
+	 {HashKeyR, PriorityR, ValueR, LeftR, RightR}} = Tree) ->
+    if
+	PriorityR > Priority ->
+	    {HashKeyR, PriorityR, ValueR,
+	     {HashKey, Priority, Value, Left, LeftR},
+	     RightR};
+	true ->
+	    Tree
+    end;
+heapify({HashKey, Priority, Value,
+	 {HashKeyL, PriorityL, ValueL, LeftL, RightL},
+	 nil = Right} = Tree) ->
+    if
+	PriorityL > Priority ->
+	    {HashKeyL, PriorityL, ValueL,
+	     LeftL,
+	     {HashKey, Priority, Value, RightL, Right}};
+	true ->
+	    Tree
+    end;
+heapify({HashKey, Priority, Value,
+	 {HashKeyL, PriorityL, ValueL, LeftL, RightL} = Left,
+	 {HashKeyR, PriorityR, ValueR, LeftR, RightR} = Right} = Tree) ->
+    if
+	PriorityR > Priority ->
+	    {HashKeyR, PriorityR, ValueR,
+	     {HashKey, Priority, Value, Left, LeftR},
+	     RightR};
+	PriorityL > Priority ->
+	    {HashKeyL, PriorityL, ValueL,
+	     LeftL,
+	     {HashKey, Priority, Value, RightL, Right}};
+	true ->
+	    Tree
+    end.
+
+
+delete(Key, Tree) ->
+    HashKey = {erlang:phash2(Key), Key},
+    delete1(Tree, HashKey).
+
+delete1(HashKey, {HashKey1, Priority1, Value1, Left, Right} = Tree) ->
+    if
+	HashKey < HashKey1 ->
+	    {HashKey1, Priority1, Value1, delete1(HashKey, Left), Right};
+	HashKey > HashKey1 ->
+	    {HashKey1, Priority1, Value1, Left, delete1(HashKey, Right)};
+	true ->
+	    delete_root(Tree)
+    end.
+
+delete_root({HashKey, Priority, Value, Left, Right}) ->
+    case {Left, Right} of
+	{nil, nil} ->
+	    nil;
+	{_, nil} ->
+	    Left;
+	{nil, _} ->
+	    Right;
+	{{HashKeyL, PriorityL, ValueL, LeftL, RightL},
+	 {HashKeyR, PriorityR, ValueR, LeftR, RightR}} ->
+	    if
+		PriorityL > PriorityR ->
+		    {HashKeyL, PriorityL, ValueL,
+		     LeftL,
+		     delete_root({HashKey, Priority, Value, RightL, Right})};
+		true ->
+		    {HashKeyR, PriorityR, ValueR,
+		     delete_root({HashKey, Priority, Value, Left, LeftR}),
+		     RightR}
+	    end
+    end.
+
+is_empty(nil) ->
+    true;
+is_empty({_HashKey, _Priority, _Value, _Left, _Right}) ->
+    false.
+
+get_root({{_Hash, Key}, Priority, Value, _Left, _Right}) ->
+    {Key, Priority, Value}.
+
+
+lookup(Key, Tree) ->
+    HashKey = {erlang:phash2(Key), Key},
+    lookup1(Tree, HashKey).
+
+lookup1(nil, _HashKey) ->
+    error;
+lookup1({HashKey1, Priority1, Value1, Left, Right}, HashKey) ->
+    if
+	HashKey < HashKey1 ->
+	    lookup1(Left, HashKey);
+	HashKey > HashKey1 ->
+	    lookup1(Right, HashKey);
+	true ->
+	    {ok, Priority1, Value1}
+    end.
+
-- 
cgit v1.2.3