git-svn-id: svn://openib.tc.cornell.edu/gen1/branches/WOF2-0@1528 ad392aa1-c5ef-ae45...
[mirror/winof/.git] / etc / kernel / index_list.c
1 /*\r
2  * Copyright (c) 2008 Intel Corporation. All rights reserved.\r
3  *\r
4  * This software is available to you under the OpenIB.org BSD license\r
5  * below:\r
6  *\r
7  *     Redistribution and use in source and binary forms, with or\r
8  *     without modification, are permitted provided that the following\r
9  *     conditions are met:\r
10  *\r
11  *      - Redistributions of source code must retain the above\r
12  *        copyright notice, this list of conditions and the following\r
13  *        disclaimer.\r
14  *\r
15  *      - Redistributions in binary form must reproduce the above\r
16  *        copyright notice, this list of conditions and the following\r
17  *        disclaimer in the documentation and/or other materials\r
18  *        provided with the distribution.\r
19  *\r
20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
21  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\r
22  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AWV\r
23  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS\r
24  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN\r
25  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
26  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
27  * SOFTWARE.\r
28  */\r
29 \r
30 #include "index_list.h"\r
31 \r
32 INDEX_ENTRY EmptyList;\r
33 \r
34 static BOOLEAN IndexListGrow(INDEX_LIST *pIndexList)\r
35 {\r
36         INDEX_ENTRY     *array;\r
37         SIZE_T          size, i;\r
38 \r
39         size = pIndexList->Size + (PAGE_SIZE / sizeof(INDEX_ENTRY));\r
40         array = ExAllocatePoolWithTag(PagedPool, size * sizeof(INDEX_ENTRY), 'xdni');\r
41         if (array == NULL) {\r
42                 return FALSE;\r
43         }\r
44 \r
45         i = size;\r
46         while (i-- > pIndexList->Size) {\r
47                 array[i].pItem = NULL;\r
48                 array[i].Next = pIndexList->FreeList;\r
49                 pIndexList->FreeList = i;\r
50         }\r
51 \r
52         if (pIndexList->pArray != &EmptyList) {\r
53                 RtlCopyMemory(array, pIndexList->pArray, pIndexList->Size * sizeof(INDEX_ENTRY));\r
54                 ExFreePool(pIndexList->pArray);\r
55         } else {\r
56                 array[0].Next = 0;\r
57                 array[0].Prev = 0;\r
58                 pIndexList->FreeList = 1;\r
59         }\r
60 \r
61         pIndexList->Size = size;\r
62         pIndexList->pArray = array;\r
63         return TRUE;\r
64 }\r
65 \r
66 SIZE_T IndexListInsertHead(INDEX_LIST *pIndexList, void *pItem)\r
67 {\r
68         INDEX_ENTRY     *entry;\r
69         SIZE_T          index;\r
70 \r
71         if (pIndexList->FreeList == 0 && !IndexListGrow(pIndexList)) {\r
72                 return 0;\r
73         }\r
74 \r
75         index = pIndexList->FreeList;\r
76         entry = &pIndexList->pArray[index];\r
77         pIndexList->FreeList = entry->Next;\r
78 \r
79         entry->pItem = pItem;\r
80         entry->Next = pIndexList->pArray[0].Next;\r
81         pIndexList->pArray[0].Next = index;\r
82         entry->Prev = 0;\r
83         pIndexList->pArray[entry->Next].Prev = index;\r
84 \r
85         return index;\r
86 }\r
87 \r
88 void *IndexListRemove(INDEX_LIST *pIndexList, SIZE_T Index)\r
89 {\r
90         INDEX_ENTRY     *entry;\r
91         void            *item;\r
92 \r
93         if (Index >= pIndexList->Size) {\r
94                 return NULL;\r
95         }\r
96 \r
97         entry = &pIndexList->pArray[Index];\r
98         if (entry->pItem == NULL) {\r
99                 return NULL;\r
100         }\r
101 \r
102         pIndexList->pArray[entry->Next].Prev = entry->Prev;\r
103         pIndexList->pArray[entry->Prev].Next = entry->Next;\r
104 \r
105         item = entry->pItem;\r
106         entry->pItem = NULL;\r
107         entry->Next = pIndexList->FreeList;\r
108         pIndexList->FreeList = Index;\r
109         return item;\r
110 }\r