linkList.c

Go to the documentation of this file.

/*******************************************************************************
 * Copyright © 2014 The DTVKit Open Software Foundation Ltd (www.dtvkit.org)
 * Copyright © 2004 Ocean Blue Software Ltd
 * Copyright © 2001 Koninklijke Philips Electronics N.V
 *
 * This file is part of a DTVKit Software Component
 * You are permitted to copy, modify or distribute this file subject to the terms
 * of the DTVKit 1.0 Licence which can be found in licence.txt or at www.dtvkit.org
 *
 * THIS CODE AND INFORMATION ARE PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND,
 * EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND/OR FITNESS FOR A PARTICULAR PURPOSE.
 *
 * If you or your organisation is not a member of DTVKit then you have access
 * to this source code outside of the terms of the licence agreement
 * and you are expected to delete this and any associated files immediately.
 * Further information on DTVKit, membership and terms can be found at www.dtvkit.org
 *******************************************************************************/
/*---includes for this file--------------------------------------------------*/
#include "clDsmSystem.h"
#include "linkList.h"

#include "cacheMgr.h"


/*------------------------------- Local Macros -------------------------------*/



/*------------------------------  Exported Data  -----------------------------*/



/*--------------------------------Local Types --------------------------------*/



/*------------------------------- Local Statics ------------------------------*/



/*------------------- local prototypes/forward declarations ------------------*/
/* eg static void myLocalFunction(); */


/*---------------------------- Exported Functions ----------------------------*/

/**** LINK LIST CONTROL BLOCK FUNCTIONS ****/

/* /////////////////////////////////////////////////////////////////////////////
// LLCtrlBlockInit
// Initialises a new, empty Control Block.
void LLCtrlBlockInit( P_LLControl pCtrl, ListId_t listId, H_Object hParent )
{
   dsmAssert((pCtrl != NULL));

   pCtrl->pHead = pCtrl->pTail = NULL;
   pCtrl->count = 0;
   pCtrl->listId = listId;
   pCtrl->hParent = hParent;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLCreate
// Creates a linked list Control block, and returns a handle to it.
E_DscError LLCreate( P_DsmCoreInst idp,
   H_Object hParent, ListId_t listId, P_LLControl *phLlCtrl )
{
   E_DscError err;

   dsmAssert((idp != NULL));
   dsmAssert((phLlCtrl != NULL));

   *phLlCtrl = (P_LLControl)DSC_CmMemGet( idp, sizeof(S_LLControl) );
   if (*phLlCtrl == NULL)
   {
      err = CLDSM_ERR_MEM_HEAP_FULL;
   }
   else
   {
      err = CLDSM_OK;
      LLCtrlBlockInit( *phLlCtrl, listId, hParent );
   }

   DEBUG_CHK( err == CLDSM_OK, dsmDP1(("ERROR: LLCreate %u\n", err)));
   return err;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLDestroy
// Destroys a linked list Control block, and sets the handle to NULL.
void LLDestroy( P_DsmCoreInst idp, P_LLControl *phLlCtrl )
{
   dsmAssert((idp != NULL));
   dsmAssert((phLlCtrl != NULL));
   dsmAssert((*phLlCtrl != NULL));

   if (!memValidate( *phLlCtrl ))
   {
      dsmDP1(("ERROR: LLDestroy mem invalid %p\n", *phLlCtrl));
   }
   else
   {
   #ifndef NDEBUG
      dsmAssert(((*phLlCtrl)->count == 0));
   #endif
      DSC_CmMemRelease( idp, *phLlCtrl );
      *phLlCtrl = NULL;
   }
}

/* /////////////////////////////////////////////////////////////////////////////
// RemoveItem
// Removes an object from list given by control block.
// returns TRUE if this was the last object in the list
void RemoveItem( P_LLControl pLLCtrl, P_LLObject pLL )
{
   dsmAssert((pLL != NULL));
   dsmAssert((pLLCtrl != NULL));
   dsmAssert((pLL->pLLCtrl == pLLCtrl));
   if (pLL->pNext)
   {
      P_LLObject pLLNext = pLL->pNext + pLLCtrl->listId;
      pLLNext->pPrev = pLL->pPrev;
   }
   else
   {
      dsmAssert((pLLCtrl->pTail == (pLL - pLLCtrl->listId)));
      pLLCtrl->pTail = pLL->pPrev;
   }
   if (pLL->pPrev)
   {
      P_LLObject pLLPrev = pLL->pPrev + pLLCtrl->listId;
      pLLPrev->pNext = pLL->pNext;
   }
   else
   {
      dsmAssert((pLLCtrl->pHead == (pLL - pLLCtrl->listId)));
      pLLCtrl->pHead = pLL->pNext;
   }
   pLLCtrl->count--;
   pLL->pLLCtrl = NULL;
   pLL->pPrev = pLL->pNext = NULL;
}

/* /////////////////////////////////////////////////////////////////////////////
// llRemoveFromAll
// Removes an object from all lists it is currently in.
// The object becomes a floating object.
void LLRemoveFromAll( H_Object hListObj, U16BIT numLists )
{
   P_LLObject pLL = (P_LLObject)hListObj;
   dsmAssert((pLL != NULL));
   for (; numLists--; pLL++)
   {
      if (pLL->pLLCtrl != NULL)
      {
         RemoveItem( pLL->pLLCtrl, pLL );
      }
   }
}

/* /////////////////////////////////////////////////////////////////////////////
// LLHead
// Returns a handle to the head object. The object is not removed.
H_Object LLHead( P_LLControl pCtrlObj )
{
   return (pCtrlObj->count) ? pCtrlObj->pHead : NULL;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLTail
// Returns a handle to the head object. The object is not removed.
H_Object LLTail( P_LLControl pCtrlObj )
{
   return (pCtrlObj && pCtrlObj->count) ? pCtrlObj->pTail : NULL;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLInsertHead
// Inserts an object into the head of the list.
// If the object exists already in the list, then it is moved to the head.
// returns TRUE if the object was not previously in the list.
BOOLEAN LLInsertHead( P_LLControl pCtrlObj, H_Object hNewObj )
{
   P_LLObject pNewObj;
   P_LLObject pHead;
   ListId_t listId;
   BOOLEAN added;

   dsmAssert((pCtrlObj != NULL));
   dsmAssert((hNewObj != NULL));

   listId = pCtrlObj->listId;
   pNewObj = (P_LLObject)hNewObj;
   pNewObj += listId;

   /* If in list already, then remove it ready for re-insertion at the head */
   if (pNewObj->pLLCtrl != NULL)
   {
      added = FALSE;
      if (pNewObj->pLLCtrl != pCtrlObj)
      {
         /* Module is in a different list. This can happen when we have two
          * DIIs with the same ModuleId. It shouldn't happen under normal
          * circumstances, but it *can* happen. In this case we just give
          * up (we don't know which DII it belongs to).
          */
         return FALSE;
      }
      /* Already in list */
      RemoveItem( pCtrlObj, pNewObj );
   }
   else
   {
      added = TRUE;
   }

   pNewObj->pNext = pCtrlObj->pHead;
   pNewObj->pLLCtrl = pCtrlObj;
   if (pCtrlObj->count++)
   {
      pHead = pCtrlObj->pHead + listId;
      pHead->pPrev = (P_LLObject)hNewObj;
   }
   else
   {
      pCtrlObj->pTail = (P_LLObject)hNewObj;
   }
   pCtrlObj->pHead = (P_LLObject)hNewObj;

   return added;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLInsertTail
// Appends an object onto the tail of the list
// If the object exists already in the list, then it is moved to the tail.
// returns TRUE if the object was not previously in the list.
BOOLEAN LLInsertTail( P_LLControl pCtrlObj, H_Object hNewObj )
{
   P_LLObject pNewObj;
   P_LLObject pTail = NULL;
   ListId_t listId;
   BOOLEAN added;

   dsmAssert((pCtrlObj != NULL));
   dsmAssert((hNewObj != NULL));

   listId = pCtrlObj->listId;
   pNewObj = (P_LLObject)hNewObj;
   pNewObj += listId;

   /* Assert if object is in another list with same listId */
   dsmAssert(((pNewObj->pLLCtrl == NULL) || (pNewObj->pLLCtrl == pCtrlObj)));

   /* If in list already, then remove it ready for re-insertion at the head */
   if (pNewObj->pLLCtrl != NULL)
   {
      /* Already in list */
      RemoveItem( pCtrlObj, pNewObj );
      added = FALSE;
   }
   else
   {
      added = TRUE;
   }
   pNewObj->pPrev = pCtrlObj->pTail;
   pNewObj->pLLCtrl = pCtrlObj;
   if (pCtrlObj->count++)
   {
      pTail = pCtrlObj->pTail + listId;
      pTail->pNext = (P_LLObject)hNewObj;
   }
   else
   {
      pCtrlObj->pHead = (P_LLObject)hNewObj;
   }
   pCtrlObj->pTail = (P_LLObject)hNewObj;

   return added;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLRemoveHead
// Disconnects the first object in the list and returns a handle to it.
// Handle is NULL if the list contained no objects.
H_Object LLRemoveHead( P_LLControl pCtrlObj )
{
   P_LLObject obj;
   dsmAssert((pCtrlObj != NULL));
   if (pCtrlObj->count)
   {
      obj = pCtrlObj->pHead;
      RemoveItem( pCtrlObj, obj + pCtrlObj->listId );
   }
   else
   {
      obj = NULL;
   }
   return (H_Object)obj;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLRemoveTail
// Disconnects the last object in the list and returns a handle to it.
// Handle is NULL if the list contained no objects.
H_Object LLRemoveTail( P_LLControl pCtrlObj )
{
   P_LLObject obj;
   dsmAssert((pCtrlObj != NULL));
   if (pCtrlObj->count)
   {
      obj = pCtrlObj->pTail;
      RemoveItem( pCtrlObj, obj + pCtrlObj->listId );
   }
   else
   {
      obj = NULL;
   }
   return (H_Object)obj;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLCount
// returns number of objects in the specified list.
U16BIT LLCount( P_LLControl pCtrlObj )
{
   return pCtrlObj->count;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLListId
// returns number of objects in the specified list.
U16BIT LListId( P_LLControl pCtrlObj )
{
   return pCtrlObj->listId;
}

/**** LINK LIST FUNCTIONS ****/
/* /////////////////////////////////////////////////////////////////////////////
// llLinkInit
// Initialises a new, empty list object's list parameters
void llLinkInit( P_LLObject pLL, U32BIT numLists )
{
   S32BIT loop;

   dsmAssert((pLL != NULL));
   dsmAssert((numLists != 0));

   /* Init pointers */
   for (loop = 0; loop != numLists; loop++)
   {
      pLL->pLLCtrl = NULL;
      pLL->pNext = pLL->pPrev = NULL;
      pLL++;
   }
}

/* /////////////////////////////////////////////////////////////////////////////
// LLRemove
// Removes an object from the specified list.
// returns TRUE if this was the last object in the list
BOOLEAN LLRemove( H_Object hListObj, ListId_t listId )
{
   P_LLObject pLL = (P_LLObject)hListObj;
   P_LLControl pCtrlObj;
   BOOLEAN islast = FALSE;

   dsmAssert((hListObj != NULL));

   pLL += listId;
   pCtrlObj = pLL->pLLCtrl;

   if (pCtrlObj != NULL)
   {
      RemoveItem( pCtrlObj, pLL );
      if (pCtrlObj->count == 0)
      {
         islast = TRUE;
      }
   }
   return islast;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLNext
// Returns the handle to the next object in the list
H_Object LLNext( H_Object obj, ListId_t listId )
{
   P_LLObject pLLs = (P_LLObject)obj;
   return pLLs[listId].pNext;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLPrev
// Returns the handle to the previous object in the list
H_Object LLPrev( H_Object obj, ListId_t listId )
{
   P_LLObject pLLs = obj;
   return pLLs[listId].pPrev;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLCheckInListCtrl
//
BOOLEAN LLCheckInListCtrl( P_LLControl pCtrlBlk, H_Object obj )
{
   P_LLObject pLL = obj;

   dsmAssert((pCtrlBlk != NULL));
   dsmAssert((obj != NULL));

   pLL += pCtrlBlk->listId;
   return (pLL->pLLCtrl == pCtrlBlk) ? TRUE : FALSE;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLCheckInListId
//
BOOLEAN LLCheckInListId( ListId_t listId, H_Object obj )
{
   P_LLObject pLL = obj;

   dsmAssert((obj != NULL));

   pLL += listId;
   return pLL->pLLCtrl ? TRUE : FALSE;
}

/* /////////////////////////////////////////////////////////////////////////////
// llGetParent
//
H_Object LLParent( H_Object obj, ListId_t listId )
{
   P_LLObject pLL = obj;
   P_LLControl pLLCtrl;
   dsmAssert((obj != NULL));
   pLL += listId;
   pLLCtrl = pLL->pLLCtrl;
   return (pLLCtrl == NULL) ? NULL : pLLCtrl->hParent;
}

/* /////////////////////////////////////////////////////////////////////////////
// LLReplaceAll
//
void LLReplaceAll( H_Object oldobj, H_Object newobj, U16BIT numLists )
{
   P_LLObject pLLOld = oldobj;
   P_LLObject pLLNew = newobj;
   P_LLControl pLLCtrl;
   P_LLObject pNext;
   P_LLObject pPrev;
   ListId_t listId;

   dsmAssert((pLLOld != NULL));
   dsmAssert((pLLNew != NULL));

   for (listId = 0; listId != numLists; listId++)
   {
      pLLCtrl = pLLOld[listId].pLLCtrl;
      if (pLLCtrl != NULL)
      {
         pLLNew[listId].pLLCtrl = pLLCtrl;
         pLLOld[listId].pLLCtrl = NULL;
         pNext = pLLOld[listId].pNext;
         pPrev = pLLOld[listId].pPrev;
         pLLNew[listId].pNext = pNext;
         pLLNew[listId].pPrev = pPrev;
         pLLOld[listId].pNext = NULL;
         pLLOld[listId].pPrev = NULL;
         if (pNext)
         {
            pNext += listId;
            pNext->pPrev = pLLNew;
         }
         if (pPrev)
         {
            pPrev += listId;
            pPrev->pNext = pLLNew;
         }
         if (pLLCtrl->pHead == pLLOld)
            pLLCtrl->pHead = pLLNew;
         if (pLLCtrl->pTail == pLLOld)
            pLLCtrl->pTail = pLLNew;
      }
   }
}

BOOLEAN LLIsObjectInList( P_LLControl pCtrlBlk, H_Object obj )
{
   H_Object object;
   ListId_t listId;
   BOOLEAN bFound = FALSE;
   dsmAssert((pCtrlBlk != NULL));
   listId = pCtrlBlk->listId;
   object = pCtrlBlk->pHead;
   while (object)
   {
      /* Is this the OC we want? */
      if (obj == object)
      {
         /* Found the OC */
         bFound = TRUE;
         break;
      }
      object = LLNext( object, listId );
   }
   return(bFound);
}

/*------------------------------ Local Functions -----------------------------*/


/*----------------------------------------------------------------------------*/