heap.c

Stack-based sequential decoder for M-QAM modulated MIMO-type problems, i.e., of fixed tree depth.

/*
 * heap.c
 *
 * C code file for an implementation of a heap to be used by the accompanying
 * Matlab lattice decoders. Can be compiled into a standalone library or using
 * mex into a Matlab library. Pre-compiled for Matlab 7.0.1 R14SP1 (Linux) and
 * Matlab 6.5 R13 (Windows); for best effect, re-compile for other releases.
 *
 * Version 1.0, copyright 2006 by Karen Su ([e-mail]).
 * Version 1.1
 *   Fixed heapDelMin; added heapGetMaxSize, heapGetDim and appropriate interfaces.
 * Version 1.2
 *   Fixed heapInsert; added heap.pLastDel to replace global pLastDelNode;
 *   modified heapGetMin to return key == -1 (invalid value) if heap is empty.
 */

#include "stdlib.h"
#include "stdio.h"
#include "malloc.h"
#include "memory.h"
#include "heap.h"
#include "math.h"
#include "string.h"

/* #define DEBUG */
/* #define VER65 */
#define VER7R14
#define MAXNODES 32768
#define COMPILEFORMATLAB
/* #define MSVC */

#ifdef VER65
#define mycreatedoublescalar mxCreateDoubleScalar
#define mystrncasecmp strncasecmp
#else
#define mycreatedoublescalar mxCreateScalarDouble
#define mystrncasecmp strncasecmp
#endif

#ifdef VER7R14
#define myprintf printf
#define myerrmsg(str) { printf(str); return; }
#else
#define myprintf mexPrintf
#define myerrmsg mexErrMsgTxt
#endif

#ifdef MSVC
#define strncasecmp strnicmp
#endif

#ifdef COMPILEFORMATLAB
#include "mex.h"
#define mymalloc mxCalloc
#define myfree mxFree
#else
#define mymalloc calloc
#define myfree free
#endif

struct heap *heapInit(int spdim, int type) {
  return heapInitT(spdim, MAXNODES, type);
}

struct heap *heapInitT(int spdim, int T, int type) {
  struct heap *pH = (struct heap*)mymalloc(1, sizeof(struct heap));
  pH->nNodes   = 0;
  pH->pRoot    = NULL;
  pH->spdim    = spdim;
  pH->maxNodes = T;
  pH->type     = type;
  pH->pLastDel = NULL;

#ifdef COMPILEFORMATLAB
  /* Ensure that matlab doesn't erase this */
  mexMakeMemoryPersistent((void*)pH);
#endif

  return pH;
}

struct hNode *heapNewNode(double       key,
                          double      *pY,
                          double      *pZ,
                          int          dim,
                          struct heap *pH) {
  struct hNode *pNewNode;

  if (pH->pLastDel) {
    pNewNode     = pH->pLastDel;
    pH->pLastDel = NULL;
  } else {
    switch (pH->type) {
      case BASIC:
        pNewNode = (struct hNode *)mymalloc(1, sizeof(struct hNode));
        break;
      case LATTICE:
        pNewNode = (struct hNode *)mymalloc(1, sizeof(struct hNodeI));
        break;
      case LAST:
        pNewNode = (struct hNode *)mymalloc(1, sizeof(struct hNodeL));
        break;
      default:
        break;
    }

    if (pNewNode) {  /* mxCalloc didn't fail */
#ifdef COMPILEFORMATLAB
      mexMakeMemoryPersistent((void *)pNewNode);
#endif
    } else {
      return NULL;
    }

    pNewNode->pY      = (double *)mymalloc(pH->spdim, sizeof(double));

    if (pNewNode->pY) {  /* mxCalloc didn't fail */
#ifdef COMPILEFORMATLAB
      mexMakeMemoryPersistent((void *)pNewNode->pY);
#endif
    } else {
      myfree(pNewNode);
      return NULL;
    }
  }

  pNewNode->key     = key;
  if (pY) { memcpy(pNewNode->pY, pY, dim*sizeof(double)); }
  pNewNode->pZ      = pNewNode->pY+dim;
  if (pZ) { memcpy(pNewNode->pZ, pZ, (pH->spdim-dim)*sizeof(double)); }
  pNewNode->dim     = dim;

  pNewNode->pLCh    = NULL;
  pNewNode->pRCh    = NULL;

  return pNewNode;
}

int heapInsertB(double       key, 
                double      *pY, 
                double      *pZ, 
                int          dim, 
                struct heap *pH) {
  struct hNode *pNewNode = heapNewNode(key, pY, pZ, dim, pH);

  if (pNewNode) { 
    return heapInsert(pNewNode, pH);
  } else {
    return -1;
  }
}

int heapInsertI(double       key, 
                double      *pY, 
                double      *pZ, 
                int          dim, 
                int          cnum, 
                double       pweight, 
                double       utarget, 
                double       delta, 
                struct heap *pH) {
  struct hNodeI *pNewNode = (struct hNodeI *)heapNewNode(key, pY, pZ, dim, pH);

  if (pNewNode) {
    pNewNode->cnum    = cnum;
    pNewNode->pweight = pweight;
    pNewNode->utarget = utarget;
    pNewNode->delta   = delta;

    return heapInsert((struct hNode *)pNewNode, pH);
  } else {
    return -1;
  }
}

int heapInsertL(double       key, 
                double      *pY, 
                double      *pZ, 
                int          dim, 
                int          cnum, 
                double       pweight, 
                double       utarget, 
                double       delta, 
                double      *pA,
                double       sqradius,
                int          lbound,
                int          ubound,
                double       uoffset,
                struct heap *pH) {
  struct hNodeL *pNewNode = (struct hNodeL *)heapNewNode(key, pY, pZ, dim, pH);

  if (pNewNode) {
    pNewNode->cnum    = cnum;
    pNewNode->pweight = pweight;
    pNewNode->utarget = utarget;
    pNewNode->delta   = delta;

    if (dim>0) {
      pNewNode->pA = (double *)mymalloc(dim, sizeof(double));

      if (pNewNode->pA) {  /* mxCalloc didn't fail */
#ifdef COMPILEFORMATLAB
        mexMakeMemoryPersistent((void *)pNewNode->pA);
#endif
      } else {
        hNodeFree((struct hNode *)pNewNode);
        return -1;
      }
      if (pA) { memcpy(pNewNode->pA, pA, dim*sizeof(double)); }
    }
    pNewNode->sqradius = sqradius;
    pNewNode->lbound   = lbound;
    pNewNode->ubound   = ubound;
    pNewNode->uoffset  = uoffset;
  
    return heapInsert((struct hNode *)pNewNode, pH);
  } else {
    return -1;
  }
}

int heapInsert(struct hNode *pNewNode, struct heap *pH) {
  struct hNode  *pParentNode, *pLastParNode;
  int            nextNodeIndex, ii, nSwaps = 0;

  pH->nNodes++;
  nextNodeIndex = pH->nNodes;

#ifdef DEBUG
  printf("InsertIng node %i: ",nextNodeIndex); 
#endif

  if (pH->pRoot) { /* find where to append new node, bubble */
    pParentNode = pH->pRoot;

    for (ii = (int)floor(log(nextNodeIndex)/log(2)-1); ii > 0; ii--) {
      if (nextNodeIndex&(1<<ii)) {       /* follow right child path */

#ifdef DEBUG
        printf("Right "); 
#endif 

        pParentNode = pParentNode->pRCh; 
      } else {                           /* follow left child path */

#ifdef DEBUG
        printf("Left "); 
#endif 

        pParentNode = pParentNode->pLCh; 
      }
    }
    if (nextNodeIndex&1) {           /* append new node as right child */

#ifdef DEBUG
      printf("InsertasRight\n"); 
#endif

      pParentNode->pRCh = pNewNode; 
    } else {                         /* append new node as left child */

#ifdef DEBUG
      printf("InsertasLeft\n"); 
#endif

      pParentNode->pLCh = pNewNode; 
    }
    pNewNode->pPar = pParentNode; 

#ifdef DEBUG
    printf("Intermediate heap:\n");
    heapPrintContents(pH);
#endif

    pLastParNode = pNewNode->pPar;      /* this node may be it... */
    nSwaps = heapBubbleUp(pH, pNewNode); 

    if (pH->nNodes > pH->maxNodes) {    /* delete last node, can only save T */
                                        /* note that this is not the largest */
                                        /* weight node. */

      if (pNewNode->pPar != pLastParNode) {  /* pLastParNode was bubbled last*/
        if (pLastParNode->pPar->pLCh == pLastParNode) {
          pLastParNode->pPar->pLCh = NULL;
        } else if (pLastParNode->pPar->pRCh == pLastParNode) {
          pLastParNode->pPar->pRCh = NULL;
        }
        pH->pLastDel = pLastParNode; /* we do not delete because this fragments */
                                     /* memory, instead we will reuse the space */

      } else {                       /* pNewNode not bubbled and is still last  */
        if (pLastParNode->pLCh == pNewNode) {
          pLastParNode->pLCh = NULL;
        } else if (pLastParNode->pRCh == pNewNode) {
          pLastParNode->pRCh = NULL;
        }
        pH->pLastDel = pNewNode; 
      }
      pH->nNodes--;
    }
    
  } else { 

#ifdef DEBUG
    printf("InsertasRoot\n"); 
#endif

    pH->pRoot      = pNewNode;
    pNewNode->pPar = NULL;
  } 

  return nSwaps;
}

struct hNode *heapGetMin(struct heap *pH) {
  return pH->pRoot;
}

int heapReplaceMinb(double       key, 
                    double      *pY, 
                    double      *pZ, 
                    int          dim, 
                    struct heap *pH) {
  struct hNode *pMinNode;
  int           nSwaps = 0;

  pMinNode = heapGetMin(pH);
  if (pMinNode) {                      
    pMinNode->key     = key;
    if (pY) { memcpy(pMinNode->pY, pY, dim*sizeof(double)); }
    pMinNode->pZ      = pMinNode->pY+dim;
    if (pZ) { memcpy(pMinNode->pZ, pZ, (pH->spdim-dim)*sizeof(double)); }
    pMinNode->dim     = dim;

#ifdef DEBUG
    printf("Intermediate heap:\n");
    heapPrintContents(pH);
#endif

    if (pH->pRoot->pLCh) { nSwaps = heapBubbleDown(pH); }

  } else { nSwaps = heapInsertB(key, pY, pZ, dim, pH); }
  
  return nSwaps;
}

int heapReplaceMini(double       key, 
                    double      *pY, 
                    double      *pZ, 
                    int          dim, 
                    int          cnum,