From patchwork Sat Jul 18 20:03:43 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bill Fischofer X-Patchwork-Id: 51259 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-wg0-f71.google.com (mail-wg0-f71.google.com [74.125.82.71]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 1ED2B22A28 for ; Sat, 18 Jul 2015 20:16:34 +0000 (UTC) Received: by wgal16 with SMTP id l16sf5617718wga.2 for ; Sat, 18 Jul 2015 13:16:33 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:delivered-to:from:to:date :message-id:in-reply-to:references:cc:subject:precedence:list-id :list-unsubscribe:list-archive:list-post:list-help:list-subscribe :mime-version:content-type:content-transfer-encoding:errors-to :sender:x-original-sender:x-original-authentication-results :mailing-list; bh=VafIb+EkGlxb55PjTVjhu8FOAe8W0FBp9lUSg8bj9+0=; b=ibJaWvBOmUl+vB//gCVBYbzQ1eP4sDo9zLjC7+8lIT/el1bKw2aT56bNmispdtODOp wRGI9cxsk1HEUPnC7T0saPppAKrWmpgPmSjDzjJ30aTRMIzYqm+peY4YvBHvX3v8SXGs w6oW2ZoAuKBx8923OmtQWXkx696wtMceySr6zqK8GUzfOkcCI630ngmgAMPhbIWl1lm7 dea3B/I/QA9lEoicvmhbxLJx8Zc6Yfhy3UvapAyaMHKsPk/KK6fqgFGgMXPSyxbexMUz y6IwQpyJUArgQTxPj2qHWdLiJdZZKRQgH8V6BxcMYvcL1xzm6rfpcEscbpf/bMvBjMm9 +hYg== X-Gm-Message-State: ALoCoQnvI3ijaiVpI0cSTERwi701rww/gtl6CgQqG1FHfqk1eFrM64nk52UN8Er4O78RIV3xn3Ne X-Received: by 10.112.54.166 with SMTP id k6mr10854132lbp.0.1437250593067; Sat, 18 Jul 2015 13:16:33 -0700 (PDT) X-BeenThere: patchwork-forward@linaro.org Received: by 10.152.179.171 with SMTP id dh11ls557747lac.47.gmail; Sat, 18 Jul 2015 13:16:32 -0700 (PDT) X-Received: by 10.112.35.229 with SMTP id l5mr20750913lbj.0.1437250592914; Sat, 18 Jul 2015 13:16:32 -0700 (PDT) Received: from mail-lb0-f171.google.com (mail-lb0-f171.google.com. [209.85.217.171]) by mx.google.com with ESMTPS id l7si13403603lae.121.2015.07.18.13.16.32 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 18 Jul 2015 13:16:32 -0700 (PDT) Received-SPF: pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.217.171 as permitted sender) client-ip=209.85.217.171; Received: by lblf12 with SMTP id f12so76788718lbl.2 for ; Sat, 18 Jul 2015 13:16:32 -0700 (PDT) X-Received: by 10.152.5.228 with SMTP id v4mr20323951lav.36.1437250592725; Sat, 18 Jul 2015 13:16:32 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.112.108.230 with SMTP id hn6csp537291lbb; Sat, 18 Jul 2015 13:16:31 -0700 (PDT) X-Received: by 10.140.237.214 with SMTP id i205mr30498646qhc.31.1437250591327; Sat, 18 Jul 2015 13:16:31 -0700 (PDT) Received: from lists.linaro.org (lists.linaro.org. [54.225.227.206]) by mx.google.com with ESMTP id l18si18662511qgd.62.2015.07.18.13.16.30; Sat, 18 Jul 2015 13:16:31 -0700 (PDT) Received-SPF: pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.225.227.206 as permitted sender) client-ip=54.225.227.206; Received: by lists.linaro.org (Postfix, from userid 109) id 35DFB61D12; Sat, 18 Jul 2015 20:16:30 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on ip-10-142-244-252.ec2.internal X-Spam-Level: X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, URIBL_BLOCKED autolearn=disabled version=3.4.0 Received: from ip-10-142-244-252.ec2.internal (localhost [127.0.0.1]) by lists.linaro.org (Postfix) with ESMTP id B0F0E61843; Sat, 18 Jul 2015 20:05:55 +0000 (UTC) X-Original-To: lng-odp@lists.linaro.org Delivered-To: lng-odp@lists.linaro.org Received: by lists.linaro.org (Postfix, from userid 109) id 8A3F861D03; Sat, 18 Jul 2015 20:04:40 +0000 (UTC) Received: from mail-ob0-f176.google.com (mail-ob0-f176.google.com [209.85.214.176]) by lists.linaro.org (Postfix) with ESMTPS id 4B98E61B80 for ; Sat, 18 Jul 2015 20:04:06 +0000 (UTC) Received: by obbgp5 with SMTP id gp5so82854264obb.0 for ; Sat, 18 Jul 2015 13:04:05 -0700 (PDT) X-Received: by 10.202.182.65 with SMTP id g62mr6100472oif.85.1437249845881; Sat, 18 Jul 2015 13:04:05 -0700 (PDT) Received: from localhost.localdomain (cpe-24-28-70-239.austin.res.rr.com. [24.28.70.239]) by smtp.gmail.com with ESMTPSA id y5sm8537998oes.15.2015.07.18.13.04.05 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sat, 18 Jul 2015 13:04:05 -0700 (PDT) From: Bill Fischofer To: lng-odp@lists.linaro.org Date: Sat, 18 Jul 2015 15:03:43 -0500 Message-Id: <1437249827-578-9-git-send-email-bill.fischofer@linaro.org> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1437249827-578-1-git-send-email-bill.fischofer@linaro.org> References: <1437249827-578-1-git-send-email-bill.fischofer@linaro.org> X-Topics: patch Cc: Barry Spinney Subject: [lng-odp] [RFC API-NEXT PATCH 08/12] linux-generic: tm: add sorted_list support routines X-BeenThere: lng-odp@lists.linaro.org X-Mailman-Version: 2.1.16 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: , List-Help: , List-Subscribe: , MIME-Version: 1.0 Errors-To: lng-odp-bounces@lists.linaro.org Sender: "lng-odp" X-Removed-Original-Auth: Dkim didn't pass. X-Original-Sender: bill.fischofer@linaro.org X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.217.171 as permitted sender) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org X-Google-Group-Id: 836684582541 Signed-off-by: Barry Spinney Signed-off-by: Mike Holmes Signed-off-by: Bill Fischofer --- platform/linux-generic/Makefile.am | 2 + .../include/odp_sorted_list_internal.h | 58 +++++++ platform/linux-generic/odp_sorted_list.c | 184 +++++++++++++++++++++ 3 files changed, 244 insertions(+) create mode 100644 platform/linux-generic/include/odp_sorted_list_internal.h create mode 100644 platform/linux-generic/odp_sorted_list.c diff --git a/platform/linux-generic/Makefile.am b/platform/linux-generic/Makefile.am index 2eb271a..358a478 100644 --- a/platform/linux-generic/Makefile.am +++ b/platform/linux-generic/Makefile.am @@ -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 \ diff --git a/platform/linux-generic/include/odp_sorted_list_internal.h b/platform/linux-generic/include/odp_sorted_list_internal.h new file mode 100644 index 0000000..7e730c2 --- /dev/null +++ b/platform/linux-generic/include/odp_sorted_list_internal.h @@ -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 + +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 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 diff --git a/platform/linux-generic/odp_sorted_list.c b/platform/linux-generic/odp_sorted_list.c new file mode 100644 index 0000000..7df89c3 --- /dev/null +++ b/platform/linux-generic/odp_sorted_list.c @@ -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 +#include +#include +#include +#include +#include + +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); +}