summaryrefslogtreecommitdiff
path: root/drivers/alsa_midi/list.c
diff options
context:
space:
mode:
Diffstat (limited to 'drivers/alsa_midi/list.c')
-rw-r--r--drivers/alsa_midi/list.c261
1 files changed, 134 insertions, 127 deletions
diff --git a/drivers/alsa_midi/list.c b/drivers/alsa_midi/list.c
index 438066c..d646878 100644
--- a/drivers/alsa_midi/list.c
+++ b/drivers/alsa_midi/list.c
@@ -1,22 +1,22 @@
/* -*- Mode: C ; c-basic-offset: 2 -*- */
/*****************************************************************************
- *
- * list_sort() adapted from linux kernel.
- *
- * 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; version 2 of the License
- *
- * 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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- *****************************************************************************/
+*
+* list_sort() adapted from linux kernel.
+*
+* 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; version 2 of the License
+*
+* 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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+*
+*****************************************************************************/
#include <assert.h>
@@ -24,124 +24,131 @@
/* list sort from Mark J Roberts (mjr@znex.org) */
void
-__list_sort(
- struct list_head *head,
- int member_offset,
- int (*cmp)(void * a, void * b))
+__list_sort (
+ struct list_head *head,
+ int member_offset,
+ int (*cmp)(void * a, void * b))
{
- struct list_head *p, *q, *e, *list, *tail, *oldhead;
- int insize, nmerges, psize, qsize, i;
-
- list = head->next;
- list_del(head);
- insize = 1;
- for (;;) {
- p = oldhead = list;
- list = tail = NULL;
- nmerges = 0;
-
- while (p) {
- nmerges++;
- q = p;
- psize = 0;
- for (i = 0; i < insize; i++) {
- psize++;
- q = q->next == oldhead ? NULL : q->next;
- if (!q)
- break;
- }
-
- qsize = insize;
- while (psize > 0 || (qsize > 0 && q)) {
- if (!psize) {
- e = q;
- q = q->next;
- qsize--;
- if (q == oldhead)
- q = NULL;
- } else if (!qsize || !q) {
- e = p;
- p = p->next;
- psize--;
- if (p == oldhead)
- p = NULL;
- } else if (cmp((void *)p - member_offset, (void *)q - member_offset) <= 0) {
- e = p;
- p = p->next;
- psize--;
- if (p == oldhead)
- p = NULL;
- } else {
- e = q;
- q = q->next;
- qsize--;
- if (q == oldhead)
- q = NULL;
- }
- if (tail)
- tail->next = e;
- else
- list = e;
- e->prev = tail;
- tail = e;
- }
- p = q;
- }
-
- tail->next = list;
- list->prev = tail;
-
- if (nmerges <= 1)
- break;
-
- insize *= 2;
- }
-
- head->next = list;
- head->prev = list->prev;
- list->prev->next = head;
- list->prev = head;
+ struct list_head *p, *q, *e, *list, *tail, *oldhead;
+ int insize, nmerges, psize, qsize, i;
+
+ list = head->next;
+ list_del (head);
+ insize = 1;
+ for (;; ) {
+ p = oldhead = list;
+ list = tail = NULL;
+ nmerges = 0;
+
+ while (p) {
+ nmerges++;
+ q = p;
+ psize = 0;
+ for (i = 0; i < insize; i++) {
+ psize++;
+ q = q->next == oldhead ? NULL : q->next;
+ if (!q) {
+ break;
+ }
+ }
+
+ qsize = insize;
+ while (psize > 0 || (qsize > 0 && q)) {
+ if (!psize) {
+ e = q;
+ q = q->next;
+ qsize--;
+ if (q == oldhead) {
+ q = NULL;
+ }
+ } else if (!qsize || !q) {
+ e = p;
+ p = p->next;
+ psize--;
+ if (p == oldhead) {
+ p = NULL;
+ }
+ } else if (cmp ((void*)p - member_offset, (void*)q - member_offset) <= 0) {
+ e = p;
+ p = p->next;
+ psize--;
+ if (p == oldhead) {
+ p = NULL;
+ }
+ } else {
+ e = q;
+ q = q->next;
+ qsize--;
+ if (q == oldhead) {
+ q = NULL;
+ }
+ }
+ if (tail) {
+ tail->next = e;
+ } else {
+ list = e;
+ }
+ e->prev = tail;
+ tail = e;
+ }
+ p = q;
+ }
+
+ tail->next = list;
+ list->prev = tail;
+
+ if (nmerges <= 1) {
+ break;
+ }
+
+ insize *= 2;
+ }
+
+ head->next = list;
+ head->prev = list->prev;
+ list->prev->next = head;
+ list->prev = head;
}
struct test_list_el {
- int value;
- struct list_head test_list_node;
+ int value;
+ struct list_head test_list_node;
};
-int test_list_sort_comparator(struct test_list_el * e1, struct test_list_el * e2)
+int test_list_sort_comparator (struct test_list_el * e1, struct test_list_el * e2)
{
- return e1->value - e2->value;
+ return e1->value - e2->value;
}
-void test_list_sort(void)
+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(el->value == expected[i]);
- i++;
- }
+ 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 (el->value == expected[i]);
+ i++;
+ }
}
View Lorry Controller Status