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