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 */ 42 typedef 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 } 62 LIB_OBJECT_NODE; 63 64 typedef 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 } 71 LIB_OBJECT_NODE_TYPE; 72 73 /* ----------------------------------------------------------------------- 74 Search functions 75 -----------------------------------------------------------------------*/ 76 static 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 */ 110 static 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 133 LIB_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 142 LIB_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 150 LIB_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 */ 164 static 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 } 202 scan_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 232 bool 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 243 void 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 254 void 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 265 void 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 -----------------------------------------------------------------------*/ 279 static 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 299 static 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 313 void 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 321 LIB_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 332 void 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 339 LIB_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 345 void 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 352 LIB_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 358 void 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 365 LIB_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 375 static 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 392 LIB_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 399 LIB_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 406 LIB_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 413 LIB_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
