stbllist.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
 *
 * 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----------------------------------------------------
// compiler library header files

#include <stdlib.h>

// third party header files

// Ocean Blue Software header files

#include <techtype.h>
#include <dbgfuncs.h>

#include "stbllist.h"
#include "stbheap.h"


//---constant definitions for this file----------------------------------------

//---local typedef structs for this file---------------------------------------

//---local (static) variable declarations for this file------------------------
//   (internal variables declared static to make them local)

//---local function prototypes for this file-----------------------------------
//   (internal functions declared static to make them local)

static void InsertBlkInList(LINK_LIST_PTR_BLK *prev_blk, LINK_LIST_PTR_BLK *new_blk,
   LINK_LIST_PTR_BLK *next_blk, LINK_LIST_PTR_BLK **prev_blk_next_ptr,
   LINK_LIST_PTR_BLK **next_blk_prev_ptr);

static void quick_sort(void *blocks_array, size_t num_blocks, size_t block_size, short int (*cmp_func)(const void *, const void *));
static void rec_quick_sort(void *blocks_array[], U16BIT left, U16BIT right, short int (*cmp_func)(const void *, const void *));

//---local function definitions------------------------------------------------

static void InsertBlkInList(LINK_LIST_PTR_BLK *prev_blk,
   LINK_LIST_PTR_BLK *new_blk,
   LINK_LIST_PTR_BLK *next_blk,
   LINK_LIST_PTR_BLK **prev_blk_next_ptr,
   LINK_LIST_PTR_BLK **next_blk_prev_ptr)
{
//   FUNCTION_START(InsertBlkInList);

   // make new blk point forward to next blk and back to prev blk
   new_blk->next = next_blk;
   new_blk->prev = prev_blk;

   // make prev blk point forward to new blk
   *prev_blk_next_ptr = new_blk;

   // make next blk point backwards to new blk
   *next_blk_prev_ptr = new_blk;

//   FUNCTION_FINISH(InsertBlkInList);
}

//---global function definitions-----------------------------------------------
void STB_LLInitialiseHeader(LINK_LIST_HEADER *hdr)
{
//   FUNCTION_START(STB_LLInitialiseHeader);

   hdr->null_next = NULL;
   hdr->first = hdr;
   hdr->last = hdr;

//   FUNCTION_FINISH(STB_LLInitialiseHeader);
}

BOOLEAN STB_LLSort(LINK_LIST_HEADER *ll_hdr, S16BIT (*cmp_func)(LINK_LIST_PTR_BLK **, LINK_LIST_PTR_BLK **))
{
   LINK_LIST_PTR_BLK **blocks_array;   //ptr to a buffer of LINK_LIST_PTR_BLK ptrs
   LINK_LIST_PTR_BLK *ll_block;
   U32BIT num_blocks;
   U32BIT block_size;
   U16BIT i;
   BOOLEAN success;

//   FUNCTION_START(STB_LLSort);

   ASSERT(cmp_func != NULL);
   ASSERT(ll_hdr != NULL);

   success = TRUE;

   num_blocks = STB_LLGetNumBlocks(ll_hdr);

   if (num_blocks > 1)
   {
      blocks_array = (LINK_LIST_PTR_BLK **)STB_GetMemory(num_blocks * sizeof(LINK_LIST_PTR_BLK *));

      if (blocks_array == NULL)
      {
         success = FALSE;
      }
      else
      {
         // copy linked list block pointers from database to block array
         ll_block = STB_LLGetFirstBlock(ll_hdr);
         for (i = 0; i < num_blocks; i++)
         {
            ASSERT(ll_block != NULL);
            blocks_array[i] = ll_block;
            if (ll_block)
            {
               ll_block = STB_LLGetNextBlock(ll_block);
            }
         }

         ASSERT(ll_block == NULL);

         ASSERT(sizeof(size_t) == sizeof(U32BIT));

         block_size = sizeof(LINK_LIST_PTR_BLK *);
         // run qsort on block array
         // cast is used here to match required format of qsort

         // "quick sort" function to sort unicode name strings
         quick_sort((void *)blocks_array, (size_t)num_blocks, (size_t)block_size, (short int (*)(const void *, const void *))cmp_func);

         // restore sorted array of block pointers to database linked list
         for (i = 0; i < num_blocks; i++) //move each item in the array to last position in the linked list
         {
            STB_LLRemoveBlock(blocks_array[i]);
            STB_LLAddBlockToEnd(ll_hdr, blocks_array[i]);
         }

         STB_FreeMemory(blocks_array);
      }
   }

//   FUNCTION_FINISH(STB_LLSort);
   return success;
}

static void quick_sort(void *blocks_array, size_t num_blocks, size_t block_size, short int (*cmp_func)(const void *, const void *))
{
//   FUNCTION_START(quick_sort);
   USE_UNWANTED_PARAM(block_size);

   // cast as (void**) to allow dereferencing as void* in array form:
   rec_quick_sort((void **)blocks_array, 0, (U16BIT)(num_blocks - 1), cmp_func);

//   FUNCTION_FINISH(quick_sort);
}

static void rec_quick_sort(void *blocks_array[], U16BIT left, U16BIT right, short int (*cmp_func)(const void *, const void *))
{
   register U16BIT i, j;
   void *temp;


//   FUNCTION_START(rec_quick_sort);

   while (right > left)
   {
      i = left;
      j = right;
      temp = blocks_array[left];

      // split array in two
      while (i < j)
      {
         for (; ((j > left) && (cmp_func(&blocks_array[j], &temp) > 0)); j--)
            ;

         for (blocks_array[i] = blocks_array[j]; ((i < j) && cmp_func(&blocks_array[i], &temp) <= 0); i++)
            ;
         // swap items
         blocks_array[j] = blocks_array[i];
      }
      blocks_array[i] = temp;

      // sort recursively, the smallest first
      if ((i - left) < (right - i))
      {
         rec_quick_sort(blocks_array, left, (U16BIT)i, cmp_func);
         left = i + 1;
      }
      else
      {
         rec_quick_sort(blocks_array, (U16BIT)(i + 1), right, cmp_func);
         right = i - 1;
      }
   }

//   FUNCTION_FINISH(rec_quick_sort);
}

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

void STB_LLAddBlockToEnd(LINK_LIST_HEADER *hdr, LINK_LIST_PTR_BLK *new_blk)
{
   LINK_LIST_PTR_BLK *prev_blk;
   LINK_LIST_PTR_BLK **prev_blk_next_ptr;

//   FUNCTION_START(STB_LLAddBlockToEnd);

   ASSERT(hdr != NULL);
   ASSERT(new_blk != NULL);

   // get pointer to the last block in the list   - this becomes the previous block to new_blk
   prev_blk = hdr->last;

   // check if prev_blk is the header - if so there are no entries in the list yet and
   // prev_blk_next_ptr must point to hdr->first. Otherwise it points to prev_blk->next
   if (prev_blk->next == NULL)
      prev_blk_next_ptr = (LINK_LIST_PTR_BLK **)&(hdr->first);
   else
      prev_blk_next_ptr = (LINK_LIST_PTR_BLK **)&(prev_blk->next);

   // add new_blk between prev_blk and hdr
   InsertBlkInList(prev_blk, new_blk, (LINK_LIST_PTR_BLK *)hdr, prev_blk_next_ptr, (LINK_LIST_PTR_BLK **)&(hdr->last));

//   FUNCTION_FINISH(STB_LLAddBlockToEnd);
}

void STB_LLAddBlockToStart(LINK_LIST_HEADER *hdr, LINK_LIST_PTR_BLK *new_blk)
{
   LINK_LIST_PTR_BLK *next_blk;
   LINK_LIST_PTR_BLK **next_blk_prev_ptr;

//   FUNCTION_START(STB_LLAddBlockToStart);

   ASSERT(hdr != NULL);
   ASSERT(new_blk != NULL);

   // get pointer to the next block in the list   - this becomes the next block to new_blk
   next_blk = hdr->first;

   // check if next_blk is the header - if so there are no entries in the list yet and
   // next_blk_prev_ptr must point to hdr->prev. Otherwise it points to next_blk->prev
   if (next_blk->next == NULL)
      next_blk_prev_ptr = (LINK_LIST_PTR_BLK **)&(hdr->last);
   else
      next_blk_prev_ptr = (LINK_LIST_PTR_BLK **)&(next_blk->prev);

   // add new_blk between hdr and next_blk
   InsertBlkInList((LINK_LIST_PTR_BLK *)hdr, new_blk, next_blk, (LINK_LIST_PTR_BLK **)&(hdr->first), next_blk_prev_ptr);

//   FUNCTION_FINISH(STB_LLAddBlockToStart);
}

void STB_LLAddBlockBefore(LINK_LIST_PTR_BLK *next_blk, LINK_LIST_PTR_BLK *new_blk)
{
   LINK_LIST_PTR_BLK *prev_blk;
   LINK_LIST_PTR_BLK **prev_blk_next_ptr;

//   FUNCTION_START(STB_LLAddBlockBefore);

   ASSERT(next_blk != NULL);
   ASSERT(new_blk != NULL);

   // get pointer to the previous block from next_blk - this block will become the one previous
   // to new_blk
   prev_blk = next_blk->prev;

   // if prev_blk's next ptr is NULL then it is the list header - we must therefore be at the start
   // of the list. Set prev_blk_next_ptr accordingly.
   if (prev_blk->next == NULL)
   {
      prev_blk_next_ptr = (LINK_LIST_PTR_BLK **)&(((LINK_LIST_HEADER *)prev_blk)->first);
   }
   else
   {
      prev_blk_next_ptr = (LINK_LIST_PTR_BLK **)&(prev_blk->next);
   }

   // add new_blk between prev_blk and next_blk
   InsertBlkInList(prev_blk, new_blk, next_blk, prev_blk_next_ptr, (LINK_LIST_PTR_BLK **)&(next_blk->prev));

//   FUNCTION_FINISH(STB_LLAddBlockBefore);
}

void STB_LLAddBlockAfter(LINK_LIST_PTR_BLK *prev_blk, LINK_LIST_PTR_BLK *new_blk)
{
   LINK_LIST_PTR_BLK *next_blk;
   LINK_LIST_PTR_BLK **next_blk_prev_ptr;

//   FUNCTION_START(STB_LLAddBlockAfter);

   ASSERT(prev_blk != NULL);
   ASSERT(new_blk != NULL);

   // get pointer to the next block from prev_blk - this block will become the one after new_blk
   next_blk = prev_blk->next;

   // if next_blk's next ptr is NULL then it is the list header - we must therefore be at the end
   // of the list. Set next_blk_prev_ptr accordingly
   if (next_blk->next == NULL)
   {
      next_blk_prev_ptr = (LINK_LIST_PTR_BLK **)&(((LINK_LIST_HEADER *)next_blk)->last);
   }
   else
   {
      next_blk_prev_ptr = (LINK_LIST_PTR_BLK **)&(next_blk->prev);
   }

   // add new_blk between prev_blk and next_blk
   InsertBlkInList(prev_blk, new_blk, next_blk, (LINK_LIST_PTR_BLK **)&(prev_blk->next), next_blk_prev_ptr);

//   FUNCTION_FINISH(STB_LLAddBlockAfter);
}

void STB_LLRemoveBlock(LINK_LIST_PTR_BLK *blk)
{
   LINK_LIST_PTR_BLK *prev_blk;
   LINK_LIST_PTR_BLK **prev_blk_next_ptr;
   LINK_LIST_PTR_BLK *next_blk;
   LINK_LIST_PTR_BLK **next_blk_prev_ptr;

//   FUNCTION_START(STB_LLRemoveBlock);

   ASSERT(blk != NULL);

   // get pointer to the previous block to blk.
   prev_blk = blk->prev;
   if (prev_blk != NULL)
   {
      // if prev_blk's next ptr is NULL then it is the list header - we must therefore be at the start
      // of the list. Set prev_blk_next_ptr accordingly.
      if (prev_blk->next == NULL)
      {
         prev_blk_next_ptr = (LINK_LIST_PTR_BLK **)&(((LINK_LIST_HEADER *)prev_blk)->first);
      }
      else
      {
         prev_blk_next_ptr = (LINK_LIST_PTR_BLK **)&(prev_blk->next);
      }
   }
   else
   {
      prev_blk_next_ptr = NULL;
   }

   // get pointer to the next block to blk
   next_blk = blk->next;
   if (next_blk != NULL)
   {
      // if next_blk's next ptr is NULL then it is the list header - we must therefore be at the end
      // of the list. Set next_blk_prev_ptr accordingly
      if (next_blk->next == NULL)
      {
         next_blk_prev_ptr = (LINK_LIST_PTR_BLK **)&(((LINK_LIST_HEADER *)next_blk)->last);
      }
      else
      {
         next_blk_prev_ptr = (LINK_LIST_PTR_BLK **)&(next_blk->prev);
      }
   }
   else
   {
      next_blk_prev_ptr = NULL;
   }

   if (prev_blk_next_ptr != NULL)
   {
      // set prev_blk_next_ptr to point at next_blk
      *prev_blk_next_ptr = next_blk;
   }

   if (next_blk_prev_ptr != NULL)
   {
      // set next_blk_prev_ptr to point at prev_blk
      *next_blk_prev_ptr = prev_blk;
   }

//   FUNCTION_FINISH(STB_LLRemoveBlock);
}

LINK_LIST_PTR_BLK* STB_LLGetNextBlock(LINK_LIST_PTR_BLK *blk)
{
   LINK_LIST_PTR_BLK *next_blk;

//   FUNCTION_START(STB_LLGetNextBlock);

   ASSERT(blk != NULL);

   // get pointer to next block
   next_blk = blk->next;

   // check if next_blk is the header (next pointer will be NULL). If it is the header then we are
   // at the end of the list so set next_blk to NULL.
   if (next_blk->next == NULL)
      next_blk = NULL;

//   FUNCTION_FINISH(STB_LLGetNextBlock);

   // return next_blk
   return(next_blk);
}

LINK_LIST_PTR_BLK* STB_LLGetPrevBlock(LINK_LIST_PTR_BLK *blk)
{
   LINK_LIST_PTR_BLK *prev_blk;

//   FUNCTION_START(STB_LLGetPrevBlock);

   ASSERT(blk != NULL);

   // get pointer to prev block
   prev_blk = blk->prev;

   // check if prev_blk is the header (next pointer will be NULL). If it is the header then we are
   // at the start of the list so set prev_blk to NULL.
   if (prev_blk->next == NULL)
      prev_blk = NULL;

//   FUNCTION_FINISH(STB_LLGetPrevBlock);

   // return prev_blk
   return(prev_blk);
}

LINK_LIST_PTR_BLK* STB_LLGetFirstBlock(LINK_LIST_HEADER *hdr)
{
   LINK_LIST_PTR_BLK *next_blk;

//   FUNCTION_START(STB_LLGetFirstBlock);

   ASSERT(hdr != NULL);

   // get pointer to the next block
   next_blk = hdr->first;

   // if next_blk is pointing to the header then the list is empty - set next_blk to null
   if (next_blk->next == NULL)
      next_blk = NULL;

//   FUNCTION_FINISH(STB_LLGetFirstBlock);

   // return next_blk pointer
   return(next_blk);
}

LINK_LIST_PTR_BLK* STB_LLGetLastBlock(LINK_LIST_HEADER *hdr)
{
   LINK_LIST_PTR_BLK *prev_blk;

//   FUNCTION_START(STB_LLGetLastBlock);

   ASSERT(hdr != NULL);

   // get pointer to the previous block
   prev_blk = hdr->last;

   // if prev_blk is pointing to the header itself then the list is empty - set prev_blk to null
   if (prev_blk->next == NULL)
      prev_blk = NULL;

//   FUNCTION_FINISH(STB_LLGetLastBlock);

   // return prev_blk pointer
   return(prev_blk);
}

LINK_LIST_PTR_BLK* STB_LLGetBlock(LINK_LIST_HEADER *hdr, U16BIT num)
{
   LINK_LIST_PTR_BLK *next_blk;
   U16BIT i;

//   FUNCTION_START(STB_LLGetBlock);

   ASSERT(hdr != NULL);

   // get pointer to the first_block
   next_blk = STB_LLGetFirstBlock(hdr);
   i = 0;

   // count blocks along list until we reach the number required
   while ((next_blk != NULL) && (i < num))
   {
      next_blk = STB_LLGetNextBlock(next_blk);
      i++;
   }

//   FUNCTION_FINISH(STB_LLGetBlock);

   // return pointer found - it may be null
   return(next_blk);
}

U16BIT STB_LLGetNumBlocks(LINK_LIST_HEADER *hdr)
{
   LINK_LIST_PTR_BLK *next_blk;
   U16BIT i;

//   FUNCTION_START(STB_LLGetNumBlocks);

   ASSERT(hdr != NULL);

   // get pointer to the first_block
   next_blk = STB_LLGetFirstBlock(hdr);
   i = 0;

   // step along list counting blocks
   while (next_blk != NULL)
   {
      i++;
      next_blk = STB_LLGetNextBlock(next_blk);
   }

//   FUNCTION_FINISH(STB_LLGetNumBlocks);

   // return the count
   return(i);
}

BOOLEAN STB_LLCheckBlockInList(LINK_LIST_HEADER *hdr, LINK_LIST_PTR_BLK *blk)
{
   LINK_LIST_PTR_BLK *next_blk;

//   FUNCTION_START(STB_LLCheckBlockInList);

   ASSERT(hdr != NULL);
   ASSERT(blk != NULL);

   // get pointer to the first_block
   next_blk = STB_LLGetFirstBlock(hdr);

   // step along list looking for specified block
   while (next_blk != NULL)
   {
      // if next_blk == blk then found block so return TRUE
      if (next_blk == blk)
         return(TRUE);

      // move on to next block in list


      next_blk = STB_LLGetNextBlock(next_blk);
   }

//   FUNCTION_FINISH(STB_LLCheckBlockInList);

   // not found so return false
   return(FALSE);
}

//*****************************************************************************
// End of file
//*****************************************************************************