You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@nuttx.apache.org by xi...@apache.org on 2021/09/21 10:51:13 UTC
[incubator-nuttx] branch master updated:
net/devif/devif_callback.c: made the connection event list doubly linked.
The resulting time complexities are as follows: * devif_callback_alloc()
time complexity is O(1) (i.e. O(n) to fill the whole list). *
devif_callback_free() time complexity is O(1) (i.e. O(n) to empty the whole
list). * devif_conn_event() time complexity is O(n).
This is an automated email from the ASF dual-hosted git repository.
xiaoxiang pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-nuttx.git
The following commit(s) were added to refs/heads/master by this push:
new 4ac7945 net/devif/devif_callback.c: made the connection event list doubly linked. The resulting time complexities are as follows: * devif_callback_alloc() time complexity is O(1) (i.e. O(n) to fill the whole list). * devif_callback_free() time complexity is O(1) (i.e. O(n) to empty the whole list). * devif_conn_event() time complexity is O(n).
4ac7945 is described below
commit 4ac79456767ebf1c0e4c84ae8da518baae35e2be
Author: Alexander Lunev <al...@mail.ru>
AuthorDate: Tue Sep 21 06:43:31 2021 +0300
net/devif/devif_callback.c: made the connection event list doubly linked.
The resulting time complexities are as follows:
* devif_callback_alloc() time complexity is O(1) (i.e. O(n) to fill the whole list).
* devif_callback_free() time complexity is O(1) (i.e. O(n) to empty the whole list).
* devif_conn_event() time complexity is O(n).
---
net/devif/devif.h | 1 +
net/devif/devif_callback.c | 51 +++++++++++++++++++++++++---------------------
2 files changed, 29 insertions(+), 23 deletions(-)
diff --git a/net/devif/devif.h b/net/devif/devif.h
index fc01466..072deb2 100644
--- a/net/devif/devif.h
+++ b/net/devif/devif.h
@@ -260,6 +260,7 @@ typedef CODE uint16_t (*devif_callback_event_t)(FAR struct net_driver_s *dev,
struct devif_callback_s
{
FAR struct devif_callback_s *nxtconn;
+ FAR struct devif_callback_s *prevconn;
FAR struct devif_callback_s *nxtdev;
FAR devif_callback_event_t event;
FAR void *priv;
diff --git a/net/devif/devif_callback.c b/net/devif/devif_callback.c
index 69a8b24..b2bff67 100644
--- a/net/devif/devif_callback.c
+++ b/net/devif/devif_callback.c
@@ -119,42 +119,46 @@ static void devif_callback_free(FAR struct net_driver_s *dev,
if (list_head)
{
- /* Find the callback structure in the connection event list */
-
- for (prev = NULL, curr = *list_head;
- curr && curr != cb;
- prev = curr, curr = curr->nxtconn)
- {
- }
+ prev = cb->prevconn;
/* Remove the structure from the connection event list */
- DEBUGASSERT(curr);
- if (curr)
+ if (prev)
{
- if (prev)
- {
- /* The found item to be removed is not in the head. */
+ /* The item to be removed is not in the head. */
- prev->nxtconn = cb->nxtconn;
- }
- else
+ prev->nxtconn = cb->nxtconn;
+
+ if (cb->nxtconn)
{
- /* The found item to be removed is in the head. */
+ /* The item to be removed is not in the tail. */
- *list_head = cb->nxtconn;
+ cb->nxtconn->prevconn = prev;
}
+ }
+ else
+ {
+ /* The item to be removed is in the head. */
+
+ *list_head = cb->nxtconn;
- if (!cb->nxtconn)
+ if (cb->nxtconn)
{
- /* If the tail item is being removed,
- * update the tail pointer.
- */
+ /* There are more items besides the head item. */
- DEBUGASSERT(list_tail);
- *list_tail = prev;
+ cb->nxtconn->prevconn = NULL;
}
}
+
+ if (!cb->nxtconn)
+ {
+ /* If the tail item is being removed,
+ * update the tail pointer.
+ */
+
+ DEBUGASSERT(list_tail);
+ *list_tail = prev;
+ }
}
/* Put the structure into the free list */
@@ -297,6 +301,7 @@ FAR struct devif_callback_s *
if (list_head && list_tail)
{
ret->nxtconn = NULL;
+ ret->prevconn = *list_tail;
if (*list_tail)
{