@@ -132,6 +132,7 @@ noinst_HEADERS = \
${srcdir}/include/odp_timer_internal.h \
${srcdir}/include/odp_name_table_internal.h \
${srcdir}/include/odp_pkt_queue_internal.h \
+ ${srcdir}/include/odp_sorted_list_internal.h \
${srcdir}/Makefile.inc
__LIB__libodp_la_SOURCES = \
@@ -145,6 +146,7 @@ __LIB__libodp_la_SOURCES = \
odp_init.c \
odp_name_table.c \
odp_pkt_queue.c \
+ odp_sorted_list.c \
odp_impl.c \
odp_packet.c \
odp_packet_flags.c \
new file mode 100644
@@ -0,0 +1,58 @@
+/* Copyright 2015 EZchip Semiconductor Ltd. All Rights Reserved.
+ *
+ * Copyright (c) 2015, Linaro Limited
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+#ifndef ODP_INT_SORTED_LIST_H_
+#define ODP_INT_SORTED_LIST_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <stdint.h>
+
+typedef uint64_t odp_int_sorted_pool_t;
+typedef uint32_t odp_int_sorted_list_t;
+
+#define ODP_INT_SORTED_POOL_INVALID 0
+#define ODP_INT_SORTED_LIST_INVALID 0
+
+odp_int_sorted_pool_t odp_sorted_pool_create(uint32_t max_sorted_lists);
+
+odp_int_sorted_list_t odp_sorted_list_create(odp_int_sorted_pool_t sorted_pool,
+ uint32_t max_entries);
+
+/* Enters the pair <sort_key, user_ptr> into a list of such entries, all
+ * sorted by sort_key (lowest value first with ties going to the oldest
+ * entry). The user_ptr is an arbitrary/opaque value. It is returned later
+ * (along with the associated sort_key) when a odp_int_sorted_list_remove()
+ * call is made.
+ */
+int odp_sorted_list_insert(odp_int_sorted_pool_t sorted_pool,
+ odp_int_sorted_list_t sorted_list,
+ uint64_t sort_key,
+ void *user_ptr);
+
+/* Removes and returns the list entry with the smallest sort_key. The
+ * sort_key is returned via the out ptr sort_key_ptr, and the opaque user ptr
+ * is the return value of odp_int_sorted_list_remove(). Returns NULL if the
+ * sorted_list is empty (or upon an error), in which case the value pointed to
+ * by sort_key_ptr remains unchanged.
+ */
+void *odp_sorted_list_remove(odp_int_sorted_pool_t sorted_pool,
+ odp_int_sorted_list_t sorted_list,
+ uint64_t *sort_key_ptr);
+
+void odp_sorted_list_stats_print(odp_int_sorted_pool_t sorted_pool);
+
+void odp_sorted_pool_destroy(odp_int_sorted_pool_t sorted_pool);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
new file mode 100644
@@ -0,0 +1,184 @@
+/* Copyright 2015 EZchip Semiconductor Ltd. All Rights Reserved.
+ *
+ * Copyright (c) 2015, Linaro Limited
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+#include <stdint.h>
+#include <string.h>
+#include <malloc.h>
+#include <stdio.h>
+#include <odp.h>
+#include <odp_sorted_list_internal.h>
+
+typedef struct sorted_list_item_s sorted_list_item_t;
+
+struct sorted_list_item_s {
+ sorted_list_item_t *next_item;
+ uint64_t sort_key;
+ uint64_t user_data;
+};
+
+typedef struct {
+ sorted_list_item_t *first_item;
+ uint32_t sorted_list_len;
+ uint32_t pad;
+} sorted_list_desc_t;
+
+typedef struct {
+ sorted_list_desc_t descs[0];
+} sorted_list_descs_t;
+
+typedef struct {
+ uint64_t total_inserts;
+ uint64_t total_removes;
+ uint32_t max_sorted_lists;
+ uint32_t next_list_idx;
+ sorted_list_descs_t *list_descs;
+} sorted_pool_t;
+
+odp_int_sorted_pool_t odp_sorted_pool_create(uint32_t max_sorted_lists)
+{
+ sorted_list_descs_t *list_descs;
+ sorted_pool_t *pool;
+ uint32_t malloc_len;
+
+ pool = malloc(sizeof(sorted_pool_t));
+ memset(pool, 0, sizeof(sorted_pool_t));
+ pool->max_sorted_lists = max_sorted_lists;
+ pool->next_list_idx = 1;
+
+ malloc_len = max_sorted_lists * sizeof(sorted_list_desc_t);
+ list_descs = malloc(malloc_len);
+ memset(list_descs, 0, malloc_len);
+ pool->list_descs = list_descs;
+ return (odp_int_sorted_pool_t)pool;
+}
+
+odp_int_sorted_list_t odp_sorted_list_create(odp_int_sorted_pool_t sorted_pool,
+ uint32_t max_entries ODP_UNUSED)
+{
+ sorted_pool_t *pool;
+ uint32_t list_idx;
+
+ pool = (sorted_pool_t *)sorted_pool;
+ list_idx = pool->next_list_idx++;
+ return (odp_int_sorted_list_t)list_idx;
+}
+
+int odp_sorted_list_insert(odp_int_sorted_pool_t sorted_pool,
+ odp_int_sorted_list_t sorted_list,
+ uint64_t sort_key,
+ void *user_ptr)
+{
+ sorted_list_desc_t *list_desc;
+ sorted_list_item_t *new_list_item, *list_item, *prev_list_item;
+ sorted_pool_t *pool;
+ uint32_t list_idx;
+
+ pool = (sorted_pool_t *)sorted_pool;
+ list_idx = (uint32_t)sorted_list;
+ if ((pool->next_list_idx <= list_idx) ||
+ (pool->max_sorted_lists <= list_idx))
+ return -1;
+
+ list_desc = &pool->list_descs->descs[list_idx];
+ new_list_item = malloc(sizeof(sorted_list_item_t));
+ memset(new_list_item, 0, sizeof(sorted_list_item_t));
+ new_list_item->next_item = NULL;
+ new_list_item->sort_key = sort_key;
+ new_list_item->user_data = (uint64_t)user_ptr;
+
+ /* Now insert the new_list_item according to the sort_key (lowest
+ * value first).
+ */
+ list_item = list_desc->first_item;
+ prev_list_item = NULL;
+ while ((list_item) && (list_item->sort_key <= sort_key)) {
+ prev_list_item = list_item;
+ list_item = list_item->next_item;
+ }
+
+ new_list_item->next_item = list_item;
+ if (!prev_list_item)
+ list_desc->first_item = new_list_item;
+ else
+ prev_list_item->next_item = new_list_item;
+
+ list_desc->sorted_list_len++;
+ pool->total_inserts++;
+ return 0;
+}
+
+void *odp_sorted_list_remove(odp_int_sorted_pool_t sorted_pool,
+ odp_int_sorted_list_t sorted_list,
+ uint64_t *sort_key_ptr)
+{
+ sorted_list_desc_t *list_desc;
+ sorted_list_item_t *list_item;
+ sorted_pool_t *pool;
+ uint64_t user_data;
+ uint32_t list_idx;
+
+ pool = (sorted_pool_t *)sorted_pool;
+ list_idx = (uint32_t)sorted_list;
+ if ((pool->next_list_idx <= list_idx) ||
+ (pool->max_sorted_lists <= list_idx))
+ return NULL;
+
+ list_desc = &pool->list_descs->descs[list_idx];
+ if ((list_desc->sorted_list_len == 0) ||
+ (!list_desc->first_item))
+ return NULL;
+
+ list_item = list_desc->first_item;
+ list_desc->first_item = list_item->next_item;
+ list_desc->sorted_list_len--;
+
+ if (sort_key_ptr)
+ *sort_key_ptr = list_item->sort_key;
+
+ user_data = list_item->user_data;
+ free(list_item);
+ pool->total_removes++;
+ return (void *)user_data;
+}
+
+void odp_sorted_list_stats_print(odp_int_sorted_pool_t sorted_pool)
+{
+ sorted_pool_t *pool;
+
+ pool = (sorted_pool_t *)sorted_pool;
+ printf("sorted_pool=0x%lX\n", sorted_pool);
+ printf(" max_sorted_lists=%u next_list_idx=%u\n",
+ pool->max_sorted_lists, pool->next_list_idx);
+ printf(" total_inserts=%lu total_removes=%lu\n",
+ pool->total_inserts, pool->total_removes);
+}
+
+void odp_sorted_pool_destroy(odp_int_sorted_pool_t sorted_pool)
+{
+ sorted_list_descs_t *list_descs;
+ sorted_list_desc_t *list_desc;
+ sorted_list_item_t *list_item, *next_list_item;
+ sorted_pool_t *pool;
+ uint32_t list_idx;
+
+ pool = (sorted_pool_t *)sorted_pool;
+ list_descs = pool->list_descs;
+
+ for (list_idx = 0; list_idx < pool->next_list_idx; list_idx++) {
+ list_desc = &list_descs->descs[list_idx];
+ list_item = list_desc->first_item;
+ while (list_item) {
+ next_list_item = list_item->next_item;
+ free(list_item);
+ list_item = next_list_item;
+ }
+ }
+
+ free(list_descs);
+ free(pool);
+}