1/**
2 * Copyright(c) 2011 Trusted Logic.   All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 *  * Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 *  * Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in
12 *    the documentation and/or other materials provided with the
13 *    distribution.
14 *  * Neither the name Trusted Logic nor the names of its
15 *    contributors may be used to endorse or promote products derived
16 *    from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31/** Simple implementation of lib_object using doubly-linked lists. This
32   implementation should outperform more sophisticated data structures
33   like blanced binary trees when the tables have fewer than 10 to 20
34   elements.  */
35
36#include <string.h>
37#include "s_type.h"
38
39#include "lib_object.h"
40
41/* Generic node */
42typedef struct LIB_OBJECT_NODE
43{
44   struct LIB_OBJECT_NODE* pPrevious;
45   struct LIB_OBJECT_NODE* pNext;
46   union
47   {
48      uint16_t nHandle;
49
50      S_STORAGE_NAME sStorageName;
51
52      struct
53      {
54         /* Public fields */
55         uint8_t  sFilename[64];
56         uint8_t  nFilenameLength;
57      }
58      f;
59   }
60   key;
61}
62LIB_OBJECT_NODE;
63
64typedef enum
65{
66   LIB_OBJECT_NODE_TYPE_HANDLE16,
67   LIB_OBJECT_NODE_TYPE_STORAGE_NAME,
68   LIB_OBJECT_NODE_TYPE_FILENAME,
69   LIB_OBJECT_NODE_TYPE_UNINDEXED
70}
71LIB_OBJECT_NODE_TYPE;
72
73/* -----------------------------------------------------------------------
74   Search functions
75   -----------------------------------------------------------------------*/
76static bool libObjectKeyEqualNode(
77   LIB_OBJECT_NODE* pNode,
78   uint32_t nKey1,
79   void* pKey2,
80   LIB_OBJECT_NODE_TYPE eNodeType)
81{
82   switch (eNodeType)
83   {
84   default:
85   case LIB_OBJECT_NODE_TYPE_HANDLE16:
86      return
87         nKey1 == pNode->key.nHandle;
88   case LIB_OBJECT_NODE_TYPE_STORAGE_NAME:
89      return
90         memcmp(
91            (S_STORAGE_NAME*)pKey2,
92            &pNode->key.sStorageName,
93            sizeof(S_STORAGE_NAME)) == 0;
94   case LIB_OBJECT_NODE_TYPE_FILENAME:
95   {
96      uint32_t nLength1 = nKey1;
97      uint32_t nLength2 = pNode->key.f.nFilenameLength;
98      return
99         nLength1 == nLength2
100         &&
101         memcmp(
102            pKey2,
103            &pNode->key.f.sFilename,
104            nLength1) == 0;
105   }
106   }
107}
108
109/* Polymorphic search function */
110static LIB_OBJECT_NODE* libObjectSearch(
111   LIB_OBJECT_NODE* pRoot,
112   uint32_t nKey1,
113   void* pKey2,
114   LIB_OBJECT_NODE_TYPE eNodeType)
115{
116   if (pRoot != NULL)
117   {
118      LIB_OBJECT_NODE* pNode = pRoot;
119      do
120      {
121         if (libObjectKeyEqualNode(pNode, nKey1, pKey2, eNodeType))
122         {
123            /* Match found */
124            return pNode;
125         }
126         pNode = pNode->pNext;
127      }
128      while (pNode != pRoot);
129   }
130   return NULL;
131}
132
133LIB_OBJECT_NODE_HANDLE16* libObjectHandle16Search(
134               LIB_OBJECT_TABLE_HANDLE16* pTable,
135               uint32_t nHandle)
136{
137   return (LIB_OBJECT_NODE_HANDLE16*)libObjectSearch(
138      (LIB_OBJECT_NODE*)pTable->pRoot, nHandle, NULL, LIB_OBJECT_NODE_TYPE_HANDLE16);
139}
140
141
142LIB_OBJECT_NODE_STORAGE_NAME* libObjectStorageNameSearch(
143               LIB_OBJECT_TABLE_STORAGE_NAME* pTable,
144               S_STORAGE_NAME* pStorageName)
145{
146   return (LIB_OBJECT_NODE_STORAGE_NAME*)libObjectSearch(
147      (LIB_OBJECT_NODE*)pTable->pRoot, 0, pStorageName, LIB_OBJECT_NODE_TYPE_STORAGE_NAME);
148}
149
150LIB_OBJECT_NODE_FILENAME* libObjectFilenameSearch(
151               LIB_OBJECT_TABLE_FILENAME* pTable,
152               uint8_t* pFilename,
153               uint32_t  nFilenameLength)
154{
155   return (LIB_OBJECT_NODE_FILENAME*)libObjectSearch(
156      (LIB_OBJECT_NODE*)pTable->pRoot, nFilenameLength, pFilename, LIB_OBJECT_NODE_TYPE_FILENAME);
157}
158
159/* -----------------------------------------------------------------------
160   Add functions
161   -----------------------------------------------------------------------*/
162
163/* Polymorphic add function. Add the node at the end of the linked list */
164static bool libObjectAdd(
165   LIB_OBJECT_NODE** ppRoot,
166   LIB_OBJECT_NODE* pNew,
167   LIB_OBJECT_NODE_TYPE eNodeType)
168{
169   LIB_OBJECT_NODE* pRoot;
170   LIB_OBJECT_NODE* pLast;
171   if (*ppRoot == NULL)
172   {
173      *ppRoot = pNew;
174      pNew->pNext = pNew;
175      pNew->pPrevious = pNew;
176      if (eNodeType == LIB_OBJECT_NODE_TYPE_HANDLE16)
177      {
178         pNew->key.nHandle = 1;
179      }
180      return true;
181   }
182   else
183   {
184      pRoot = *ppRoot;
185      pLast = pRoot->pPrevious;
186      if (eNodeType == LIB_OBJECT_NODE_TYPE_HANDLE16)
187      {
188         if (pLast->key.nHandle == LIB_OBJECT_HANDLE16_MAX)
189         {
190            /* We cannot just assign last handle + 1 because it will
191               overflow. So, scan the whole list */
192            goto scan_list;
193         }
194         pNew->key.nHandle = pLast->key.nHandle + 1;
195      }
196      pLast->pNext = pNew;
197      pNew->pPrevious = pLast;
198      pNew->pNext = pRoot;
199      pRoot->pPrevious = pNew;
200      return true;
201   }
202scan_list:
203   {
204      LIB_OBJECT_NODE* pNode = pRoot;
205      uint32_t nFreeHandle = 1;
206      do
207      {
208         if (pNode->key.nHandle > nFreeHandle)
209         {
210            /* nMaxHandle+1 is not allocated. Insert pNew just before pNode */
211            pNew->key.nHandle = nFreeHandle;
212            pNew->pNext = pNode;
213            pNew->pPrevious = pNode->pPrevious;
214            pNode->pPrevious->pNext = pNew;
215            pNode->pPrevious = pNew;
216            if (pNode == pRoot)
217            {
218               /* Special case, pNew is the new root */
219               *ppRoot = pNew;
220            }
221            return true;
222         }
223         pNode = pNode->pNext;
224         nFreeHandle++;
225      }
226      while (pNode != pRoot);
227      /* No free handle */
228      return false;
229   }
230}
231
232bool libObjectHandle16Add(
233               LIB_OBJECT_TABLE_HANDLE16* pTable,
234               LIB_OBJECT_NODE_HANDLE16* pObject)
235{
236   return libObjectAdd(
237      (LIB_OBJECT_NODE**)&pTable->pRoot,
238      (LIB_OBJECT_NODE*)pObject,
239      LIB_OBJECT_NODE_TYPE_HANDLE16);
240}
241
242
243void libObjectStorageNameAdd(
244               LIB_OBJECT_TABLE_STORAGE_NAME* pTable,
245               LIB_OBJECT_NODE_STORAGE_NAME* pObject)
246{
247   libObjectAdd(
248      (LIB_OBJECT_NODE**)&pTable->pRoot,
249      (LIB_OBJECT_NODE*)pObject,
250      LIB_OBJECT_NODE_TYPE_STORAGE_NAME);
251}
252
253
254void libObjectFilenameAdd(
255               LIB_OBJECT_TABLE_FILENAME* pTable,
256               LIB_OBJECT_NODE_FILENAME* pObject)
257{
258   libObjectAdd(
259      (LIB_OBJECT_NODE**)&pTable->pRoot,
260      (LIB_OBJECT_NODE*)pObject,
261      LIB_OBJECT_NODE_TYPE_FILENAME);
262}
263
264
265void libObjectUnindexedAdd(
266         LIB_OBJECT_TABLE_UNINDEXED* pTable,
267         LIB_OBJECT_NODE_UNINDEXED* pObject)
268{
269   libObjectAdd(
270      (LIB_OBJECT_NODE**)&pTable->pRoot,
271      (LIB_OBJECT_NODE*)pObject,
272      LIB_OBJECT_NODE_TYPE_UNINDEXED);
273}
274
275
276/* -----------------------------------------------------------------------
277   Remove functions
278   -----------------------------------------------------------------------*/
279static void libObjectRemove(LIB_OBJECT_NODE** ppRoot, LIB_OBJECT_NODE* pObject)
280{
281   LIB_OBJECT_NODE* pPrevious = pObject->pPrevious;
282   LIB_OBJECT_NODE* pNext = pObject->pNext;
283
284   pPrevious->pNext = pNext;
285   pNext->pPrevious = pPrevious;
286
287   if (pPrevious == pObject)
288   {
289      /* Removed the last object in the table */
290      *ppRoot = NULL;
291   }
292   else if (pObject == *ppRoot)
293   {
294      /* Removed the first object in the list */
295      *ppRoot = pNext;
296   }
297}
298
299static LIB_OBJECT_NODE* libObjectRemoveOne(LIB_OBJECT_NODE** ppRoot)
300{
301   if (*ppRoot == NULL)
302   {
303      return NULL;
304   }
305   else
306   {
307      LIB_OBJECT_NODE* pObject = *ppRoot;
308      libObjectRemove(ppRoot, pObject);
309      return pObject;
310   }
311}
312
313void libObjectHandle16Remove(
314               LIB_OBJECT_TABLE_HANDLE16* pTable,
315               LIB_OBJECT_NODE_HANDLE16* pObject)
316{
317   libObjectRemove((LIB_OBJECT_NODE**)&pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
318   pObject->nHandle = 0;
319}
320
321LIB_OBJECT_NODE_HANDLE16* libObjectHandle16RemoveOne(
322               LIB_OBJECT_TABLE_HANDLE16* pTable)
323{
324   LIB_OBJECT_NODE_HANDLE16* pObject = (LIB_OBJECT_NODE_HANDLE16*)libObjectRemoveOne((LIB_OBJECT_NODE**)&pTable->pRoot);
325   if (pObject != NULL)
326   {
327      pObject->nHandle = 0;
328   }
329   return pObject;
330}
331
332void libObjectStorageNameRemove(
333               LIB_OBJECT_TABLE_STORAGE_NAME* pTable,
334               LIB_OBJECT_NODE_STORAGE_NAME* pObject)
335{
336   libObjectRemove((LIB_OBJECT_NODE**)&pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
337}
338
339LIB_OBJECT_NODE_STORAGE_NAME* libObjectStorageNameRemoveOne(
340               LIB_OBJECT_TABLE_STORAGE_NAME* pTable)
341{
342   return (LIB_OBJECT_NODE_STORAGE_NAME*)libObjectRemoveOne((LIB_OBJECT_NODE**)&pTable->pRoot);
343}
344
345void libObjectFilenameRemove(
346               LIB_OBJECT_TABLE_FILENAME* pTable,
347               LIB_OBJECT_NODE_FILENAME* pObject)
348{
349   libObjectRemove((LIB_OBJECT_NODE**)&pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
350}
351
352LIB_OBJECT_NODE_FILENAME* libObjectFilenameRemoveOne(
353               LIB_OBJECT_TABLE_FILENAME* pTable)
354{
355   return (LIB_OBJECT_NODE_FILENAME*)libObjectRemoveOne((LIB_OBJECT_NODE**)&pTable->pRoot);
356}
357
358void libObjectUnindexedRemove(
359         LIB_OBJECT_TABLE_UNINDEXED* pTable,
360         LIB_OBJECT_NODE_UNINDEXED* pObject)
361{
362   libObjectRemove((LIB_OBJECT_NODE**)&pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
363}
364
365LIB_OBJECT_NODE_UNINDEXED* libObjectUnindexedRemoveOne(LIB_OBJECT_TABLE_UNINDEXED* pTable)
366{
367   return (LIB_OBJECT_NODE_UNINDEXED*)libObjectRemoveOne((LIB_OBJECT_NODE**)&pTable->pRoot);
368}
369
370
371/* -----------------------------------------------------------------------
372   Get-next functions
373   -----------------------------------------------------------------------*/
374
375static LIB_OBJECT_NODE* libObjectNext(LIB_OBJECT_NODE* pRoot, LIB_OBJECT_NODE* pObject)
376{
377   if (pObject == NULL)
378   {
379      return pRoot;
380   }
381   else if (pObject == pRoot->pPrevious)
382   {
383      return NULL;
384   }
385   else
386   {
387      return pObject->pNext;
388   }
389}
390
391
392LIB_OBJECT_NODE_HANDLE16* libObjectHandle16Next(
393               LIB_OBJECT_TABLE_HANDLE16* pTable,
394               LIB_OBJECT_NODE_HANDLE16* pObject)
395{
396   return (LIB_OBJECT_NODE_HANDLE16*)libObjectNext((LIB_OBJECT_NODE*)pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
397}
398
399LIB_OBJECT_NODE_STORAGE_NAME* libObjectStorageNameNext(
400               LIB_OBJECT_TABLE_STORAGE_NAME* pTable,
401               LIB_OBJECT_NODE_STORAGE_NAME* pObject)
402{
403   return (LIB_OBJECT_NODE_STORAGE_NAME*)libObjectNext((LIB_OBJECT_NODE*)pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
404}
405
406LIB_OBJECT_NODE_FILENAME* libObjectFilenameNext(
407               LIB_OBJECT_TABLE_FILENAME* pTable,
408               LIB_OBJECT_NODE_FILENAME* pObject)
409{
410   return (LIB_OBJECT_NODE_FILENAME*)libObjectNext((LIB_OBJECT_NODE*)pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
411}
412
413LIB_OBJECT_NODE_UNINDEXED* libObjectUnindexedNext(
414               LIB_OBJECT_TABLE_UNINDEXED* pTable,
415               LIB_OBJECT_NODE_UNINDEXED* pObject)
416{
417   return (LIB_OBJECT_NODE_UNINDEXED*)libObjectNext((LIB_OBJECT_NODE*)pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
418}
419