From 558023e9b0423ab444d77f18350661957c779098 Mon Sep 17 00:00:00 2001
From: Tee Teoh <tty.erlang@gmail.com>
Date: Mon, 11 Jun 2007 22:43:58 -0400
Subject: [PATCH] Added Fisher-Yates/Knuth fair shuffle to lists module.
Relies on srandom/random
---
 erts/emulator/beam/beam_emu.c      |    1 +
 erts/emulator/beam/bif.tab         |    2 +
 erts/emulator/beam/erl_bif_lists.c |   63 ++++++++++++++++++++++++++++++++++++
 3 files changed, 66 insertions(+), 0 deletions(-)

diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c
index 9a47602..9b460eb 100644
--- a/erts/emulator/beam/beam_emu.c
+++ b/erts/emulator/beam/beam_emu.c
@@ -1180,6 +1180,7 @@ static int init_done;
 void
 init_emulator(void)
 {
+    srandom((unsigned int)time(NULL));
 #if defined(_OSE_) || defined(VXWORKS)
     init_done = 0;
 #endif
diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index 2c0cb0c..7e611bf 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -603,6 +603,8 @@ bif lists:keymember/3
 bif 'erl.lang.list.keylist':is_element/3 ebif_keylist_is_element_3 lists_keymember_3
 bif lists:keysearch/3
 bif 'erl.lang.list.keylist':search/3	ebif_keylist_search_3 lists_keysearch_3
+bif lists:shuffle/1
+bif 'erl.lang.list':shuffle/1	        ebif_list_shuffle_1 lists_shuffle_1
 
 #
 # Bifs for debugging.
diff --git a/erts/emulator/beam/erl_bif_lists.c b/erts/emulator/beam/erl_bif_lists.c
index 132b5b0..7f87484 100644
--- a/erts/emulator/beam/erl_bif_lists.c
+++ b/erts/emulator/beam/erl_bif_lists.c
@@ -203,6 +203,69 @@ BIF_RETTYPE lists_member_2(BIF_ALIST_2)
     BIF_RET2(am_false, CONTEXT_REDS - max_iter/10);
 }
 
+BIF_RETTYPE lists_shuffle_1(BIF_ALIST_1)
+{
+    Eterm  list;
+    Eterm* hp;
+    Uint  need;
+    Eterm  res;
+    Eterm* vec_p;
+    Eterm* vp;
+    int     i;
+    int     n;
+    
+    if ((n = list_length(BIF_ARG_1)) < 0) {
+	BIF_ERROR(BIF_P, BADARG);
+    }
+    
+    if (n == 0)
+	BIF_RET(NIL);
+    
+    vec_p = (Eterm*) erts_alloc(ERTS_ALC_T_TMP, n * sizeof(Eterm));
+    
+    /* PUT ALL ELEMENTS IN VP */
+    vp = vec_p;
+    list = BIF_ARG_1;
+    i = n;
+    while(i--) {
+	Eterm* listp = list_val(list);
+	*vp++ = CAR(listp);
+	list = CDR(listp);
+    }
+
+    shuffle(vec_p, n);
+    
+    /* REBUILD LIST */
+    res = NIL;
+    need = 2*n;
+    hp = HAlloc(BIF_P, need);
+    vp = vec_p + n - 1;
+    while(vp >= vec_p) {
+      if (is_value(*vp)) {
+	res = CONS(hp, *vp, res);
+	hp += 2;
+      }
+      vp--;
+    }
+
+    erts_free(ERTS_ALC_T_TMP, (void *) vec_p);
+    BIF_RET(res);
+}
+
+void shuffle(Eterm* l, int n) 
+{
+    int i;
+    Eterm tmp;
+    int j;
+
+    for(j = (n - 1); j > 0; j--) {
+      i = (int)((random()) % j);
+      tmp = l[j];
+      l[j] = l[i];
+      l[i] = tmp;
+    }    
+}
+
 BIF_RETTYPE lists_reverse_2(BIF_ALIST_2)
 {
     Eterm list;
-- 
1.5.2