Signed-off-by: Tomek Grabiec <[email protected]>
---
Makefile | 3 +-
include/vm/list.h | 41 ++++++++++++++++++
test/vm/Makefile | 1 +
test/vm/list-test.c | 46 ++++++++++++++++++++
vm/list.c | 115 +++++++++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 205 insertions(+), 1 deletions(-)
create mode 100644 vm/list.c
diff --git a/Makefile b/Makefile
index ef99405..2006636 100644
--- a/Makefile
+++ b/Makefile
@@ -93,7 +93,8 @@ VM_OBJS = \
vm/string.o \
vm/types.o \
vm/zalloc.o \
- vm/class.o
+ vm/class.o \
+ vm/list.o
JAMVM_OBJS = \
vm/jato.o \
diff --git a/include/vm/list.h b/include/vm/list.h
index b94e737..e723fb3 100644
--- a/include/vm/list.h
+++ b/include/vm/list.h
@@ -4,6 +4,7 @@
#include <vm/system.h>
#include <stdbool.h>
+#include <memory.h>
/*
* This doubly-linked list is shamelessly stolen from Linux kernel.
@@ -190,4 +191,44 @@ static inline struct list_head *list_last(struct list_head
*head)
return head->prev;
}
+/**
+ * list_move_all - move one list to another
+ * @to: list head that elements from @from will be linked to
+ * @from: source list
+ */
+static inline void list_move_all(struct list_head *to, struct list_head *from)
+{
+ to->next = from->next;
+ to->prev = from->prev;
+ to->prev->next = to;
+ to->next->prev = to;
+}
+
+/**
+ * __list_sort - sort the list using given comparator with merge-sort algorithm
+ * @head: is a head of the list to be sorted
+ * @member_offset: is machine offset inside the list entry structure to the
+ * field of type struct list_head which links that entry with
+ * the list.
+ */
+extern void __list_sort(struct list_head * head,
+ int member_offset,
+ int (*comparator)(void*,void*));
+
+/**
+ * list_sort - wrapper for __list_sort
+ * @head: is a head of the list to be sorted
+ * @type: is the type of list entry
+ * @member: is the name of the field inside entry that links that entry with
+ * other entries in the list.
+ * @comaprator: function comparing two entries, should return value lesser
+ * than 0 when the first argument is lesser than the second one.
+ */
+#define list_sort(head,type,member,comparator) \
+ ({ \
+ __list_sort(head, \
+ offsetof(type, member), \
+ (int (*)(void*, void*)) comparator); \
+ })
+
#endif
diff --git a/test/vm/Makefile b/test/vm/Makefile
index f3480db..9e065ad 100644
--- a/test/vm/Makefile
+++ b/test/vm/Makefile
@@ -14,6 +14,7 @@ OBJS = \
../../vm/string.o \
../../vm/zalloc.o \
../../vm/types.o \
+ ../../vm/list.o \
bitset-test.o \
buffer-test.o \
bytecodes-test.o \
diff --git a/test/vm/list-test.c b/test/vm/list-test.c
index 455a57f..a10698f 100644
--- a/test/vm/list-test.c
+++ b/test/vm/list-test.c
@@ -63,3 +63,49 @@ void test_list_entry(void)
assert_ptr_equals(&foo, list_entry(&foo.node, struct foo, node));
}
+
+struct test_list_el {
+ int value;
+ struct list_head test_list_node;
+};
+
+int test_list_sort_comparator(struct test_list_el *e1, struct test_list_el *e2)
+{
+ return e1->value - e2->value;
+}
+
+void test_list_sort(void)
+{
+ struct list_head test_list;
+ struct test_list_el *el, *next;
+ struct test_list_el te1 = {.value = 1};
+ struct test_list_el te2 = {.value = 2};
+ struct test_list_el te3 = {.value = 3};
+ struct test_list_el te4 = {.value = 4};
+ struct test_list_el te5 = {.value = 5};
+ struct test_list_el te6 = {.value = 6};
+ struct test_list_el te7 = {.value = 7};
+
+ const int expected[] = {1, 2, 3, 4, 5, 6, 7};
+ int i;
+
+ INIT_LIST_HEAD(&test_list);
+ list_add_tail(&te2.test_list_node, &test_list);
+ list_add_tail(&te6.test_list_node, &test_list);
+ list_add_tail(&te4.test_list_node, &test_list);
+ list_add_tail(&te5.test_list_node, &test_list);
+ list_add_tail(&te7.test_list_node, &test_list);
+ list_add_tail(&te1.test_list_node, &test_list);
+ list_add_tail(&te3.test_list_node, &test_list);
+
+ list_sort(&test_list,
+ struct test_list_el,
+ test_list_node,
+ test_list_sort_comparator);
+
+ i = 0;
+ list_for_each_entry_safe(el, next, &test_list, test_list_node) {
+ assert_int_equals(el->value, expected[i]);
+ i++;
+ }
+}
diff --git a/vm/list.c b/vm/list.c
new file mode 100644
index 0000000..b239509
--- /dev/null
+++ b/vm/list.c
@@ -0,0 +1,115 @@
+/*
+ * Copyright (c) 2009 Tomasz Grabiec
+ *
+ * This file is released under the GPL version 2 with the following
+ * clarification and special exception:
+ *
+ * Linking this library statically or dynamically with other modules is
+ * making a combined work based on this library. Thus, the terms and
+ * conditions of the GNU General Public License cover the whole
+ * combination.
+ *
+ * As a special exception, the copyright holders of this library give you
+ * permission to link this library with independent modules to produce an
+ * executable, regardless of the license terms of these independent
+ * modules, and to copy and distribute the resulting executable under terms
+ * of your choice, provided that you also meet, for each linked independent
+ * module, the terms and conditions of the license of that module. An
+ * independent module is a module which is not derived from or based on
+ * this library. If you modify this library, you may extend this exception
+ * to your version of the library, but you are not obligated to do so. If
+ * you do not wish to do so, delete this exception statement from your
+ * version.
+ *
+ * Please refer to the file LICENSE for details.
+ */
+
+#include "vm/list.h"
+
+void __list_sort(struct list_head * head,
+ int member_offset,
+ int (*comparator)(void*, void*))
+{
+ struct list_head output_list;
+ struct list_head *input;
+ struct list_head *tmp;
+ struct list_head *output;
+ struct list_head *p, *q;
+ int i;
+ int k;
+ int pcount;
+ int qcount;
+ int nmerge;
+
+ input = head;
+ output = &output_list;
+ INIT_LIST_HEAD(output);
+ k = 1;
+
+ do {
+ p = input->next;
+ q = p;
+ nmerge = 0;
+
+ while (p != input) {
+ nmerge++;
+ pcount = 0;
+ qcount = k;
+
+ for (i=0; i<k && q!=input; i++) {
+ q = q->next;
+ pcount++;
+ }
+
+ while (pcount && qcount && q!=input) {
+ struct list_head *sel;
+ void *p_entry;
+ void *q_entry;
+
+ p_entry = (void*)p - member_offset;
+ q_entry = (void*)q - member_offset;
+
+ if (comparator(p_entry, q_entry) <= 0) {
+ sel = p;
+ pcount--;
+ p = p->next;
+ } else {
+ sel = q;
+ qcount--;
+ q = q->next;
+ }
+
+ list_del(sel);
+ list_add_tail(sel, output);
+ }
+
+ while (pcount--) {
+ struct list_head *next;
+
+ next = p->next;
+ list_del(p);
+ list_add_tail(p, output);
+ p = next;
+ }
+
+ while (qcount-- && q != input) {
+ struct list_head *next;
+
+ next = q->next;
+ list_del(q);
+ list_add_tail(q, output);
+ q = next;
+ }
+
+ p = q;
+ }
+
+ tmp = input;
+ input = output;
+ output = tmp;
+
+ k *= 2;
+ } while (nmerge > 1);
+
+ list_move_all(head, input);
+}
--
1.6.0.6
------------------------------------------------------------------------------
Stay on top of everything new and different, both inside and
around Java (TM) technology - register by April 22, and save
$200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
300 plus technical and hands-on sessions. Register today.
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
Jatovm-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jatovm-devel
