/**
 * Copyright(c) 2011 Trusted Logic.   All rights reserved.
 *
 * 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.
 *  * Neither the name Trusted Logic nor the names of its
 *    contributors may be used to endorse or promote products derived
 *    from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** Simple implementation of lib_object using doubly-linked lists. This
   implementation should outperform more sophisticated data structures
   like blanced binary trees when the tables have fewer than 10 to 20
   elements.  */

#include <string.h>
#include "s_type.h"

#include "lib_object.h"

/* Generic node */
typedef struct LIB_OBJECT_NODE
{
   struct LIB_OBJECT_NODE* pPrevious;
   struct LIB_OBJECT_NODE* pNext;
   union
   {
      uint16_t nHandle;

      S_STORAGE_NAME sStorageName;

      struct
      {
         /* Public fields */
         uint8_t  sFilename[64];
         uint8_t  nFilenameLength;
      }
      f;
   }
   key;
}
LIB_OBJECT_NODE;

typedef enum
{
   LIB_OBJECT_NODE_TYPE_HANDLE16,
   LIB_OBJECT_NODE_TYPE_STORAGE_NAME,
   LIB_OBJECT_NODE_TYPE_FILENAME,
   LIB_OBJECT_NODE_TYPE_UNINDEXED
}
LIB_OBJECT_NODE_TYPE;

/* -----------------------------------------------------------------------
   Search functions
   -----------------------------------------------------------------------*/
static bool libObjectKeyEqualNode(
   LIB_OBJECT_NODE* pNode,
   uint32_t nKey1,
   void* pKey2,
   LIB_OBJECT_NODE_TYPE eNodeType)
{
   switch (eNodeType)
   {
   default:
   case LIB_OBJECT_NODE_TYPE_HANDLE16:
      return
         nKey1 == pNode->key.nHandle;
   case LIB_OBJECT_NODE_TYPE_STORAGE_NAME:
      return
         memcmp(
            (S_STORAGE_NAME*)pKey2,
            &pNode->key.sStorageName,
            sizeof(S_STORAGE_NAME)) == 0;
   case LIB_OBJECT_NODE_TYPE_FILENAME:
   {
      uint32_t nLength1 = nKey1;
      uint32_t nLength2 = pNode->key.f.nFilenameLength;
      return
         nLength1 == nLength2
         &&
         memcmp(
            pKey2,
            &pNode->key.f.sFilename,
            nLength1) == 0;
   }
   }
}

/* Polymorphic search function */
static LIB_OBJECT_NODE* libObjectSearch(
   LIB_OBJECT_NODE* pRoot,
   uint32_t nKey1,
   void* pKey2,
   LIB_OBJECT_NODE_TYPE eNodeType)
{
   if (pRoot != NULL)
   {
      LIB_OBJECT_NODE* pNode = pRoot;
      do
      {
         if (libObjectKeyEqualNode(pNode, nKey1, pKey2, eNodeType))
         {
            /* Match found */
            return pNode;
         }
         pNode = pNode->pNext;
      }
      while (pNode != pRoot);
   }
   return NULL;
}

LIB_OBJECT_NODE_HANDLE16* libObjectHandle16Search(
               LIB_OBJECT_TABLE_HANDLE16* pTable,
               uint32_t nHandle)
{
   return (LIB_OBJECT_NODE_HANDLE16*)libObjectSearch(
      (LIB_OBJECT_NODE*)pTable->pRoot, nHandle, NULL, LIB_OBJECT_NODE_TYPE_HANDLE16);
}


LIB_OBJECT_NODE_STORAGE_NAME* libObjectStorageNameSearch(
               LIB_OBJECT_TABLE_STORAGE_NAME* pTable,
               S_STORAGE_NAME* pStorageName)
{
   return (LIB_OBJECT_NODE_STORAGE_NAME*)libObjectSearch(
      (LIB_OBJECT_NODE*)pTable->pRoot, 0, pStorageName, LIB_OBJECT_NODE_TYPE_STORAGE_NAME);
}

LIB_OBJECT_NODE_FILENAME* libObjectFilenameSearch(
               LIB_OBJECT_TABLE_FILENAME* pTable,
               uint8_t* pFilename,
               uint32_t  nFilenameLength)
{
   return (LIB_OBJECT_NODE_FILENAME*)libObjectSearch(
      (LIB_OBJECT_NODE*)pTable->pRoot, nFilenameLength, pFilename, LIB_OBJECT_NODE_TYPE_FILENAME);
}

/* -----------------------------------------------------------------------
   Add functions
   -----------------------------------------------------------------------*/

/* Polymorphic add function. Add the node at the end of the linked list */
static bool libObjectAdd(
   LIB_OBJECT_NODE** ppRoot,
   LIB_OBJECT_NODE* pNew,
   LIB_OBJECT_NODE_TYPE eNodeType)
{
   LIB_OBJECT_NODE* pRoot;
   LIB_OBJECT_NODE* pLast;
   if (*ppRoot == NULL)
   {
      *ppRoot = pNew;
      pNew->pNext = pNew;
      pNew->pPrevious = pNew;
      if (eNodeType == LIB_OBJECT_NODE_TYPE_HANDLE16)
      {
         pNew->key.nHandle = 1;
      }
      return true;
   }
   else
   {
      pRoot = *ppRoot;
      pLast = pRoot->pPrevious;
      if (eNodeType == LIB_OBJECT_NODE_TYPE_HANDLE16)
      {
         if (pLast->key.nHandle == LIB_OBJECT_HANDLE16_MAX)
         {
            /* We cannot just assign last handle + 1 because it will
               overflow. So, scan the whole list */
            goto scan_list;
         }
         pNew->key.nHandle = pLast->key.nHandle + 1;
      }
      pLast->pNext = pNew;
      pNew->pPrevious = pLast;
      pNew->pNext = pRoot;
      pRoot->pPrevious = pNew;
      return true;
   }
scan_list:
   {
      LIB_OBJECT_NODE* pNode = pRoot;
      uint32_t nFreeHandle = 1;
      do
      {
         if (pNode->key.nHandle > nFreeHandle)
         {
            /* nMaxHandle+1 is not allocated. Insert pNew just before pNode */
            pNew->key.nHandle = nFreeHandle;
            pNew->pNext = pNode;
            pNew->pPrevious = pNode->pPrevious;
            pNode->pPrevious->pNext = pNew;
            pNode->pPrevious = pNew;
            if (pNode == pRoot)
            {
               /* Special case, pNew is the new root */
               *ppRoot = pNew;
            }
            return true;
         }
         pNode = pNode->pNext;
         nFreeHandle++;
      }
      while (pNode != pRoot);
      /* No free handle */
      return false;
   }
}

bool libObjectHandle16Add(
               LIB_OBJECT_TABLE_HANDLE16* pTable,
               LIB_OBJECT_NODE_HANDLE16* pObject)
{
   return libObjectAdd(
      (LIB_OBJECT_NODE**)&pTable->pRoot,
      (LIB_OBJECT_NODE*)pObject,
      LIB_OBJECT_NODE_TYPE_HANDLE16);
}


void libObjectStorageNameAdd(
               LIB_OBJECT_TABLE_STORAGE_NAME* pTable,
               LIB_OBJECT_NODE_STORAGE_NAME* pObject)
{
   libObjectAdd(
      (LIB_OBJECT_NODE**)&pTable->pRoot,
      (LIB_OBJECT_NODE*)pObject,
      LIB_OBJECT_NODE_TYPE_STORAGE_NAME);
}


void libObjectFilenameAdd(
               LIB_OBJECT_TABLE_FILENAME* pTable,
               LIB_OBJECT_NODE_FILENAME* pObject)
{
   libObjectAdd(
      (LIB_OBJECT_NODE**)&pTable->pRoot,
      (LIB_OBJECT_NODE*)pObject,
      LIB_OBJECT_NODE_TYPE_FILENAME);
}


void libObjectUnindexedAdd(
         LIB_OBJECT_TABLE_UNINDEXED* pTable,
         LIB_OBJECT_NODE_UNINDEXED* pObject)
{
   libObjectAdd(
      (LIB_OBJECT_NODE**)&pTable->pRoot,
      (LIB_OBJECT_NODE*)pObject,
      LIB_OBJECT_NODE_TYPE_UNINDEXED);
}


/* -----------------------------------------------------------------------
   Remove functions
   -----------------------------------------------------------------------*/
static void libObjectRemove(LIB_OBJECT_NODE** ppRoot, LIB_OBJECT_NODE* pObject)
{
   LIB_OBJECT_NODE* pPrevious = pObject->pPrevious;
   LIB_OBJECT_NODE* pNext = pObject->pNext;

   pPrevious->pNext = pNext;
   pNext->pPrevious = pPrevious;

   if (pPrevious == pObject)
   {
      /* Removed the last object in the table */
      *ppRoot = NULL;
   }
   else if (pObject == *ppRoot)
   {
      /* Removed the first object in the list */
      *ppRoot = pNext;
   }
}

static LIB_OBJECT_NODE* libObjectRemoveOne(LIB_OBJECT_NODE** ppRoot)
{
   if (*ppRoot == NULL)
   {
      return NULL;
   }
   else
   {
      LIB_OBJECT_NODE* pObject = *ppRoot;
      libObjectRemove(ppRoot, pObject);
      return pObject;
   }
}

void libObjectHandle16Remove(
               LIB_OBJECT_TABLE_HANDLE16* pTable,
               LIB_OBJECT_NODE_HANDLE16* pObject)
{
   libObjectRemove((LIB_OBJECT_NODE**)&pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
   pObject->nHandle = 0;
}

LIB_OBJECT_NODE_HANDLE16* libObjectHandle16RemoveOne(
               LIB_OBJECT_TABLE_HANDLE16* pTable)
{
   LIB_OBJECT_NODE_HANDLE16* pObject = (LIB_OBJECT_NODE_HANDLE16*)libObjectRemoveOne((LIB_OBJECT_NODE**)&pTable->pRoot);
   if (pObject != NULL)
   {
      pObject->nHandle = 0;
   }
   return pObject;
}

void libObjectStorageNameRemove(
               LIB_OBJECT_TABLE_STORAGE_NAME* pTable,
               LIB_OBJECT_NODE_STORAGE_NAME* pObject)
{
   libObjectRemove((LIB_OBJECT_NODE**)&pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
}

LIB_OBJECT_NODE_STORAGE_NAME* libObjectStorageNameRemoveOne(
               LIB_OBJECT_TABLE_STORAGE_NAME* pTable)
{
   return (LIB_OBJECT_NODE_STORAGE_NAME*)libObjectRemoveOne((LIB_OBJECT_NODE**)&pTable->pRoot);
}

void libObjectFilenameRemove(
               LIB_OBJECT_TABLE_FILENAME* pTable,
               LIB_OBJECT_NODE_FILENAME* pObject)
{
   libObjectRemove((LIB_OBJECT_NODE**)&pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
}

LIB_OBJECT_NODE_FILENAME* libObjectFilenameRemoveOne(
               LIB_OBJECT_TABLE_FILENAME* pTable)
{
   return (LIB_OBJECT_NODE_FILENAME*)libObjectRemoveOne((LIB_OBJECT_NODE**)&pTable->pRoot);
}

void libObjectUnindexedRemove(
         LIB_OBJECT_TABLE_UNINDEXED* pTable,
         LIB_OBJECT_NODE_UNINDEXED* pObject)
{
   libObjectRemove((LIB_OBJECT_NODE**)&pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
}

LIB_OBJECT_NODE_UNINDEXED* libObjectUnindexedRemoveOne(LIB_OBJECT_TABLE_UNINDEXED* pTable)
{
   return (LIB_OBJECT_NODE_UNINDEXED*)libObjectRemoveOne((LIB_OBJECT_NODE**)&pTable->pRoot);
}


/* -----------------------------------------------------------------------
   Get-next functions
   -----------------------------------------------------------------------*/

static LIB_OBJECT_NODE* libObjectNext(LIB_OBJECT_NODE* pRoot, LIB_OBJECT_NODE* pObject)
{
   if (pObject == NULL)
   {
      return pRoot;
   }
   else if (pObject == pRoot->pPrevious)
   {
      return NULL;
   }
   else
   {
      return pObject->pNext;
   }
}


LIB_OBJECT_NODE_HANDLE16* libObjectHandle16Next(
               LIB_OBJECT_TABLE_HANDLE16* pTable,
               LIB_OBJECT_NODE_HANDLE16* pObject)
{
   return (LIB_OBJECT_NODE_HANDLE16*)libObjectNext((LIB_OBJECT_NODE*)pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
}

LIB_OBJECT_NODE_STORAGE_NAME* libObjectStorageNameNext(
               LIB_OBJECT_TABLE_STORAGE_NAME* pTable,
               LIB_OBJECT_NODE_STORAGE_NAME* pObject)
{
   return (LIB_OBJECT_NODE_STORAGE_NAME*)libObjectNext((LIB_OBJECT_NODE*)pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
}

LIB_OBJECT_NODE_FILENAME* libObjectFilenameNext(
               LIB_OBJECT_TABLE_FILENAME* pTable,
               LIB_OBJECT_NODE_FILENAME* pObject)
{
   return (LIB_OBJECT_NODE_FILENAME*)libObjectNext((LIB_OBJECT_NODE*)pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
}

LIB_OBJECT_NODE_UNINDEXED* libObjectUnindexedNext(
               LIB_OBJECT_TABLE_UNINDEXED* pTable,
               LIB_OBJECT_NODE_UNINDEXED* pObject)
{
   return (LIB_OBJECT_NODE_UNINDEXED*)libObjectNext((LIB_OBJECT_NODE*)pTable->pRoot, (LIB_OBJECT_NODE*)pObject);
}