qcacmn: Remove membership check from list APIs

Getting the next node of a linked list should be a O(1) operation.
qdf_list_peek_next, however, iterates though the list first, checking
for node membership, before returning the next node. This makes the O(1)
operation a O(n) operation instead. Code that uses this API for list
traversal inadvertently performs a O(n^2) operation, causing unexpected
performance issues. Similar problems exist for qdf_list_remove_node as
well. Remove the membership checks in qdf_list_peek_next and
qdf_list_remove_node to prevent unexpected performance penalties.

Change-Id: If20825690ad861815c8164caebbf75318e572f0a
CRs-Fixed: 2091815

1 files changed, 5 insertions, 24 deletions

diff --git a/qdf/linux/src/qdf_list.c b/qdf/linux/src/qdf_list.c
index 09157f25dfdb..d6363685ff5c 100644
--- a/qdf/linux/src/qdf_list.c
+++ b/qdf/linux/src/qdf_list.c
@@ -173,10 +173,6 @@ QDF_STATUS qdf_list_remove_node(qdf_list_t *list,
 	if (list_empty(&list->anchor))
 		return QDF_STATUS_E_EMPTY;
 
-	/* verify that node_to_remove is indeed part of list list */
-	if (!qdf_list_has_node(list, node_to_remove))
-		return QDF_STATUS_E_INVAL;
-
 	list_del(node_to_remove);
 	list->count--;
 
@@ -212,35 +208,20 @@ qdf_export_symbol(qdf_list_peek_front);
  *
  * Return: QDF status
  */
-QDF_STATUS qdf_list_peek_next(qdf_list_t *list, qdf_list_node_t *node,
+QDF_STATUS qdf_list_peek_next(qdf_list_t *list,
+			      qdf_list_node_t *node,
 			      qdf_list_node_t **node2)
 {
-	struct list_head *listptr;
-	int found = 0;
-	qdf_list_node_t *tmp;
-
-	if ((list == NULL) || (node == NULL) || (node2 == NULL))
+	if (!list || !node || !node2)
 		return QDF_STATUS_E_FAULT;
 
 	if (list_empty(&list->anchor))
 		return QDF_STATUS_E_EMPTY;
 
-	/* verify that node is indeed part of list list */
-	list_for_each(tmp, &list->anchor) {
-		if (tmp == node) {
-			found = 1;
-			break;
-		}
-	}
-
-	if (found == 0)
-		return QDF_STATUS_E_INVAL;
-
-	listptr = node->next;
-	if (listptr == &list->anchor)
+	if (node->next == &list->anchor)
 		return QDF_STATUS_E_EMPTY;
 
-	*node2 = listptr;
+	*node2 = node->next;
 
 	return QDF_STATUS_SUCCESS;
 }