b52a362e62
For memory savings it is sometimes desirable to use a single-linked list instead of a double-linked list. However, the Linux kernel does not provide a default implementation of a single-linked list. Add a very simple single-linked list implementation to WLAN for general use. Change-Id: I2959f34649a0d8e0b312d9d67c81de17753b9b6c CRs-Fixed: 2418493
127 line
3.0 KiB
C
127 line
3.0 KiB
C
/*
|
|
* Copyright (c) 2019 The Linux Foundation. All rights reserved.
|
|
*
|
|
* Permission to use, copy, modify, and/or distribute this software for
|
|
* any purpose with or without fee is hereby granted, provided that the
|
|
* above copyright notice and this permission notice appear in all
|
|
* copies.
|
|
*
|
|
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
|
|
* WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
|
|
* WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
|
|
* AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
|
|
* DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
|
|
* PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
|
|
* TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
|
|
* PERFORMANCE OF THIS SOFTWARE.
|
|
*/
|
|
|
|
#include "qdf_slist.h"
|
|
#include "qdf_slist_test.h"
|
|
#include "qdf_trace.h"
|
|
|
|
struct qdf_slist_test_item {
|
|
uint32_t id;
|
|
struct qdf_slist_node node;
|
|
};
|
|
|
|
#define qdf_slist_node_count 10
|
|
|
|
static uint32_t qdf_slist_test_empty(void)
|
|
{
|
|
struct qdf_slist list;
|
|
struct qdf_slist_test_item *item;
|
|
|
|
/* a new list should ... */
|
|
qdf_slist_init(&list);
|
|
|
|
/* ... be empty */
|
|
QDF_BUG(qdf_slist_empty(&list));
|
|
|
|
/* ... return NULL when pop()'d */
|
|
QDF_BUG(!qdf_slist_pop(&list, item, node));
|
|
|
|
qdf_slist_deinit(&list);
|
|
|
|
return 0;
|
|
}
|
|
|
|
static uint32_t qdf_slist_test_push_pop(void)
|
|
{
|
|
struct qdf_slist list;
|
|
struct qdf_slist_test_item items[qdf_slist_node_count];
|
|
struct qdf_slist_test_item *item;
|
|
int i;
|
|
|
|
qdf_slist_init(&list);
|
|
|
|
/* a list with items should ... */
|
|
for (i = 0; i < qdf_slist_node_count; i++)
|
|
qdf_slist_push(&list, &items[i], node);
|
|
|
|
/* ... not be empty */
|
|
QDF_BUG(!qdf_slist_empty(&list));
|
|
|
|
/* ... be able to pop() all items previously push()'d */
|
|
for (i = 0; i < qdf_slist_node_count; i++)
|
|
QDF_BUG(qdf_slist_pop(&list, item, node));
|
|
|
|
/* ... be empty after pop()'ing all items */
|
|
QDF_BUG(qdf_slist_empty(&list));
|
|
|
|
qdf_slist_deinit(&list);
|
|
|
|
return 0;
|
|
}
|
|
|
|
static uint32_t qdf_slist_test_for_each(void)
|
|
{
|
|
struct qdf_slist list;
|
|
struct qdf_slist_test_item items[qdf_slist_node_count];
|
|
struct qdf_slist_test_item *prev;
|
|
struct qdf_slist_test_item *item;
|
|
int i;
|
|
|
|
qdf_slist_init(&list);
|
|
|
|
/* a list with items should ... */
|
|
for (i = 0; i < qdf_slist_node_count; i++)
|
|
qdf_slist_push(&list, &items[i], node);
|
|
|
|
/* ... be able to iterate over each item */
|
|
i = 0;
|
|
qdf_slist_for_each(&list, item, node) {
|
|
item->id = i++;
|
|
}
|
|
QDF_BUG(i == qdf_slist_node_count);
|
|
|
|
/* ... be able to remove each item in the same order */
|
|
i = 0;
|
|
qdf_slist_for_each_del(&list, prev, item, node) {
|
|
QDF_BUG(item);
|
|
QDF_BUG(item->id == i++);
|
|
QDF_BUG(qdf_slist_remove(&list, prev, node)->id == item->id);
|
|
}
|
|
QDF_BUG(i == qdf_slist_node_count);
|
|
|
|
/* ... be empty after all items are removed */
|
|
QDF_BUG(!qdf_slist_pop(&list, item, node));
|
|
QDF_BUG(qdf_slist_empty(&list));
|
|
|
|
qdf_slist_deinit(&list);
|
|
|
|
return 0;
|
|
}
|
|
|
|
uint32_t qdf_slist_unit_test(void)
|
|
{
|
|
uint32_t errors = 0;
|
|
|
|
errors += qdf_slist_test_empty();
|
|
errors += qdf_slist_test_push_pop();
|
|
errors += qdf_slist_test_for_each();
|
|
|
|
return errors;
|
|
}
|
|
|