path: root/misc/pascal/libpoff/pflineno.c

/**********************************************************************
 * pflineno.c
 * Manage line number information
 *
 *   Copyright (C) 2008-2009 Gregory Nutt. All rights reserved.
 *   Author: Gregory Nutt <gnutt@nuttx.org>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. 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.
 * 3. Neither the name NuttX 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.
 *
 **********************************************************************/

/**********************************************************************
 * Included Files
 **********************************************************************/

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#include "keywords.h"  /* Standard types */
#include "pedefs.h"    /* error code definitions */

#include "perr.h"      /* error() */
#include "pofflib.h"   /* POFF library interface */

/**********************************************************************
 * Pre-processor Definitions
 **********************************************************************/

#define INITIAL_LINENUMBER_TABLE_SIZE 2048*sizeof(poffLibLineNumber_t)
#define LINENUMBER_TABLE_INCREMENT    512*sizeof(poffLibLineNumber_t)

/**********************************************************************
 * Global Variables
 **********************************************************************/

/**********************************************************************
 * Private Variables
 **********************************************************************/

static poffLibLineNumber_t *lineNumberTable;
static uint32_t             nLineNumbers;
static uint32_t             lineNumberTableAlloc;
static uint32_t             prevLineNumberIndex;

/***********************************************************************
 * Private Function Prototypes
 ***********************************************************************/

/***********************************************************************
 * Private Functions
 ***********************************************************************/

static inline void poffCheckLineNumberAllocation(void)
{
  /* Check if we have allocated a line number buffer yet */

  if (!lineNumberTable)
    {
      /* No, allocate it now */

      lineNumberTable = (poffLibLineNumber_t*)
        malloc(INITIAL_LINENUMBER_TABLE_SIZE);

      if (!lineNumberTable)
        {
          fatal(eNOMEMORY);
        }

      lineNumberTableAlloc = INITIAL_LINENUMBER_TABLE_SIZE;
      nLineNumbers         = 0;
    }
}

/***********************************************************************/

static inline void poffCheckLineNumberReallocation(void)
{
  if ((nLineNumbers +1) * sizeof(poffLibLineNumber_t) > lineNumberTableAlloc)
    {
      uint32_t newAlloc = lineNumberTableAlloc + LINENUMBER_TABLE_INCREMENT;
      void *tmp;

      /* Reallocate the line number buffer */

      tmp = realloc(lineNumberTable, newAlloc);
      if (!tmp)
        {
          fatal(eNOMEMORY);
        }

      /* And set the new size */

      lineNumberTableAlloc = newAlloc;
      lineNumberTable      = (poffLibLineNumber_t*)tmp;
    }
}

/***********************************************************************/
/* Add a line number to the line number table. */

static void poffAddLineNumberToTable(poffLibLineNumber_t *lineno)
{
  /* Verify that the line number table has been allocated */

  poffCheckLineNumberAllocation();

  /* Verify that the line number table is large enough to hold
   * information about another line.
   */

  poffCheckLineNumberReallocation();

  /* Save the line number information in the line number table */

  memcpy(&lineNumberTable[nLineNumbers], lineno, sizeof(poffLibLineNumber_t));
  nLineNumbers++;
}

/***********************************************************************/
/* Discard any unused memory */

static void poffDiscardUnusedAllocation(void)
{
  uint32_t newAlloc = nLineNumbers * sizeof(poffLibLineNumber_t);
  void *tmp;

  /* Was a line number table allocated? And, if so, are there unused
   * entries?
   */

  if ((lineNumberTable) && (nLineNumbers < lineNumberTableAlloc))
    {
      /* Reallocate the line number buffer */

      tmp = realloc(lineNumberTable, newAlloc);
      if (!tmp)
        {
          fatal(eNOMEMORY);
        }

      /* And set the new size */

      lineNumberTableAlloc = newAlloc;
      lineNumberTable      = (poffLibLineNumber_t*)tmp;
    }
}

/***********************************************************************/
/* "The comparison function must return an integer less than, equal to,
 * or greater than zero if the first argument is considered to be
 * respectively less than, equal to, or greater than the second. If two
 * members compare as equal, their order in the sorted array is undefined."
 */

static int poffCompareLineNumbers(const void *pv1, const void *pv2)
{
  register poffLibLineNumber_t *ln1 = (poffLibLineNumber_t*)pv1;
  register poffLibLineNumber_t *ln2 = (poffLibLineNumber_t*)pv2;

  if (ln1->offset < ln2->offset) return -1;
  else if (ln1->offset > ln2->offset) return 1;
  else return 0;
}

/***********************************************************************
 * Public Functions
 ***********************************************************************/

void poffReadLineNumberTable(poffHandle_t handle)
{
  poffLibLineNumber_t lineno;
  int32_t offset;

  /* Initialize global variables */

  prevLineNumberIndex = 0;

  /* Create a table of line number information */

  do
    {
      offset = poffGetLineNumber(handle, &lineno);
      if (offset >= 0)
        {
          poffAddLineNumberToTable(&lineno);
        }
    }
  while (offset >= 0);

  /* Discard any memory that is not being used */

  poffDiscardUnusedAllocation();

  /* Sort the table by offset */

  qsort(lineNumberTable, nLineNumbers,
        sizeof(poffLibLineNumber_t), poffCompareLineNumbers);
}

/***********************************************************************/

poffLibLineNumber_t *poffFindLineNumber(uint32_t offset)
{
  uint32_t firstLineNumberIndex;
  uint32_t lastLineNumberIndex;
  uint32_t lineNumberIndex;

  /* Was a line number table allocated? */

  if (!lineNumberTable) return NULL;

  /* We used the last returned line number entry as a hint to speed
   * up the next search.  We don't know how the line numbers will
   * be searched but most likely, they will be searched ina a sequence
   * of ascending offsets.  In that case, a dumb linear search
   * would be better than what we are trying to do here. we are
   * trying to support fast random access.
   */

  if (lineNumberTable[prevLineNumberIndex].offset <= offset)
    {
      firstLineNumberIndex = prevLineNumberIndex;
      lastLineNumberIndex  = nLineNumbers - 1;
    }
  else
    {
      firstLineNumberIndex = 0;
      lastLineNumberIndex  = prevLineNumberIndex;
    }

  /* Search until firstLineNumberIndex and firstLineNumberIndex+1
   * contain the searched for offset.  Exact matches may or may
   * not occur.
   */

  lineNumberIndex = firstLineNumberIndex;
  while (firstLineNumberIndex != lastLineNumberIndex)
    {
      /* Look at the midpoint index.  This will be biased toward
       * the lower index due to truncation.  This means that
       * can always be assured that as long as firstLineNumberIndex !=
       * lastLineNumberIndex, then lineNumberIndex+1 is valid.  We
       * exploit this fact below.
       */

      lineNumberIndex = (firstLineNumberIndex + lastLineNumberIndex) >> 1;

      /* If the offset at the midpoint is greater than the sought
       * for offset, then we can safely set the upper search index
       * to the midpoint.
       */
      
      if (lineNumberTable[lineNumberIndex].offset > offset)
        lastLineNumberIndex = lineNumberIndex;

      /* If we have an exact match, we break out of the loop now */

      else if (lineNumberTable[lineNumberIndex].offset == offset)
        break;

      /* If the next entry is an offset greater then the one we
       * are searching for, then we can break out of the loop now.
       * We know that lineNumberIndex+1 is a valid index (see above).
       */

      else if (lineNumberTable[lineNumberIndex + 1].offset > offset)
        break;

      /* Otherwise, we safely do the following */

      else
        firstLineNumberIndex = lineNumberIndex + 1;
    }

  /* Check that we terminated the loop with a valid line number
   * match.  This should only fail if all of the line numbers in the
   * table have offsets greater than the one in the table.  If we
   * could not find a match, return NULL.
   */

  if (lineNumberTable[lineNumberIndex].offset > offset)
    {
      prevLineNumberIndex = 0;
      return NULL;
    }
  else
    {
      prevLineNumberIndex = lineNumberIndex;
      return &lineNumberTable[lineNumberIndex];
    }
}

/***********************************************************************/

void poffReleaseLineNumberTable(void)
{
  if (lineNumberTable)
    free(lineNumberTable);

  lineNumberTable      = NULL;
  nLineNumbers         = 0;
  lineNumberTableAlloc = 0;
  prevLineNumberIndex  = 0;
}

/***********************************************************************/