[ofw] [RFC] [PATCH 3/4] index list: new component to map quickly from an index to a pointer

[Sean Hefty]

Implement an 'index list'.  An index list allows storing pointers into
a dynamically growing array for fast lookups.  The index maintains a list
of all free and allocated array entries for quick insertion, and the
ability to walk through all allocated entries.  The lists are tracked
using indices, in order to allow copying the index list in memory.

Signed-off-by: Sean Hefty <sean.hefty at intel.com>
---
Conceptually, this is similar to complib ptr vector, but maintains the
free and allocated lists.  Currently, this is part of the winverbs build
only and was not added to complib, since it does not use abstracted
complib data types or syntax.

Index: index_list.c
===================================================================
--- index_list.c	(revision 0)
+++ index_list.c	(revision 0)
@@ -0,0 +1,108 @@
+/*
+ * Copyright (c) 2008 Intel Corporation. All rights reserved.
+ *
+ * This software is available to you under the OpenIB.org BSD license
+ * below:
+ *
+ *     Redistribution and use in source and binary forms, with or
+ *     without modification, are permitted provided that the following
+ *     conditions are met:
+ *
+ *      - Redistributions of source code must retain the above
+ *        copyright notice, this list of conditions and the following
+ *        disclaimer.
+ *
+ *      - Redistributions in binary form must reproduce the above
+ *        copyright notice, this list of conditions and the following
+ *        disclaimer in the documentation and/or other materials
+ *        provided with the distribution.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AWV
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include "index_list.h"
+
+static BOOLEAN IndexListGrow(INDEX_LIST *pIndexList)
+{
+	INDEX_ENTRY	*array;
+	SIZE_T		size, i;
+
+	size = pIndexList->Size + (PAGE_SIZE / sizeof(INDEX_ENTRY));
+	array = ExAllocatePoolWithTag(PagedPool, size * sizeof(INDEX_ENTRY), 'xdni');
+	if (array == NULL) {
+		return FALSE;
+	}
+
+	i = size;
+	while (i-- > pIndexList->Size) {
+		array[i].pItem = NULL;
+		array[i].Entry.Next = pIndexList->FreeList;
+		pIndexList->FreeList = i;
+	}
+
+	if (pIndexList->pArray != NULL) {
+		RtlCopyMemory(array, pIndexList->pArray, pIndexList->Size * sizeof(INDEX_ENTRY));
+		ExFreePool(pIndexList->pArray);
+	} else {
+		array[0].Entry.Next = 0;
+		array[0].Entry.Prev = 0;
+		pIndexList->FreeList = 1;
+	}
+
+	pIndexList->Size = size;
+	pIndexList->pArray = array;
+	return TRUE;
+}
+
+SIZE_T IndexListInsert(INDEX_LIST *pIndexList, void *pItem)
+{
+	INDEX_ENTRY	*entry;
+	SIZE_T		index;
+
+	if (pIndexList->FreeList == 0 && !IndexListGrow(pIndexList)) {
+		return 0;
+	}
+
+	index = pIndexList->FreeList;
+	entry = &pIndexList->pArray[index];
+	pIndexList->FreeList = entry->Entry.Next;
+
+	entry->pItem = pItem;
+	entry->Entry.Next = pIndexList->pArray[0].Entry.Next;
+	pIndexList->pArray[0].Entry.Next = index;
+	entry->Entry.Prev = 0;
+	pIndexList->pArray[entry->Entry.Next].Entry.Prev = index;
+
+	return index;
+}
+
+void *IndexListRemove(INDEX_LIST *pIndexList, SIZE_T Index)
+{
+	INDEX_ENTRY	*entry;
+	void		*item;
+
+	if (Index >= pIndexList->Size) {
+		return NULL;
+	}
+
+	entry = &pIndexList->pArray[Index];
+	if (entry->pItem == NULL) {
+		return NULL;
+	}
+
+	pIndexList->pArray[entry->Entry.Next].Entry.Prev = entry->Entry.Prev;
+	pIndexList->pArray[entry->Entry.Prev].Entry.Next = entry->Entry.Next;
+
+	item = entry->pItem;
+	entry->pItem = NULL;
+	entry->Entry.Next = pIndexList->FreeList;
+	pIndexList->FreeList = Index;
+	return item;
+}
Index: index_list.h
===================================================================
--- index_list.h	(revision 0)
+++ index_list.h	(revision 0)
@@ -0,0 +1,89 @@
+/*
+ * Copyright (c) 2008 Intel Corporation. All rights reserved.
+ *
+ * This software is available to you under the OpenIB.org BSD license
+ * below:
+ *
+ *     Redistribution and use in source and binary forms, with or
+ *     without modification, are permitted provided that the following
+ *     conditions are met:
+ *
+ *      - Redistributions of source code must retain the above
+ *        copyright notice, this list of conditions and the following
+ *        disclaimer.
+ *
+ *      - Redistributions in binary form must reproduce the above
+ *        copyright notice, this list of conditions and the following
+ *        disclaimer in the documentation and/or other materials
+ *        provided with the distribution.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AWV
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#pragma once
+
+#ifndef _INDEX_LIST_H_
+#define _INDEX_LIST_H_
+
+#include <ntddk.h>
+
+typedef struct _INDEX_LIST_ENTRY
+{
+	SIZE_T				Next;
+	SIZE_T				Prev;
+
+}	INDEX_LIST_ENTRY;	
+
+typedef struct _INDEX_ENTRY
+{
+	INDEX_LIST_ENTRY	Entry;
+	void				*pItem;
+
+}	INDEX_ENTRY;
+
+typedef struct _INDEX_LIST
+{
+	INDEX_ENTRY			*pArray;
+	SIZE_T				FreeList;
+	SIZE_T				Size;
+
+}	INDEX_LIST;
+
+static void IndexListInit(INDEX_LIST *pIndexList)
+{
+	RtlZeroMemory(pIndexList, sizeof(INDEX_LIST));
+}
+
+static void IndexListDestroy(INDEX_LIST *pIndexList)
+{
+	if (pIndexList->pArray != NULL) {
+		ExFreePool(pIndexList->pArray);
+	}
+}
+
+SIZE_T IndexListInsert(INDEX_LIST *pIndexList, void *pItem);
+
+static void *IndexListAt(INDEX_LIST *pIndexList, SIZE_T Index)
+{
+	return (Index < pIndexList->Size) ? pIndexList->pArray[Index].pItem : NULL;
+}
+
+void *IndexListRemove(INDEX_LIST *pIndexList, SIZE_T Index);
+
+static void *IndexListRemoveFirst(INDEX_LIST *pIndexList)
+{
+	return IndexListRemove(pIndexList, pIndexList->pArray[0].Entry.Next);
+}
+
+#define IndexListForEach(pIndexList, Index)						\
+	for (Index = (pIndexList)->pArray[0].Entry.Next; Index != 0;	\
+		 Index = (pIndexList)->pArray[Index].Entry.Next)
+
+#endif // _INDEX_LIST_H_