view release on metacpan or  search on metacpan

Vec.xs  view on Meta::CPAN

/*-*- Mode: C -*-*/
#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"
#include <inttypes.h>
/*#include "ppport.h"*/

#ifndef uchar
typedef unsigned char uchar;
#endif

#ifdef U64TYPE
#define ABSV_HAVE_QUAD
#define ABSV_UINT U64TYPE
#define ABSV_PRI  "%" PRIu64
#else
#undef ABSV_HAVE_QUAD
#define ABSV_UINT U32
#define ABSV_PRI  "%" PRIu32
#endif /* U64TYPE */

//const ABSV_UINT KEY_NOT_FOUND = (ABSV_UINT)-1;
const ABSV_UINT KEY_NOT_FOUND = 0xffffffff; /*-- still always just 32-bit --*/

/*==============================================================================
 * Utils
 */

//--------------------------------------------------------------
static inline int absv_cmp(ABSV_UINT a, ABSV_UINT b)
{
  if      (a<b) return -1;
  else if (a>b) return  1;
  return 0;
}

//--------------------------------------------------------------
static inline ABSV_UINT absv_vget(const uchar *v, ABSV_UINT i, ABSV_UINT nbits)
{
  //fprintf(stderr, "DEBUG: absv_vget() called with INDEX=%lu, NBITS=%lu\n", i, nbits);
  switch (nbits) {
  case 1:	return (v[i>>3] >>  (i&7)    ) &  1;
  case 2:	return (v[i>>2] >> ((i&3)<<1)) &  3;
  case 4:	return (v[i>>1] >> ((i&1)<<2)) & 15;
  case 8:	return (v[i]);
  case 16:	i <<= 1; return (v[i]<<8)  | (v[i+1]);
  case 32:	i <<= 2; return (v[i]<<24) | (v[i+1]<<16) | (v[i+2]<<8) | (v[i+3]);
#ifdef ABSV_HAVE_QUAD
  case 64:
    i <<= 3;
    return ((ABSV_UINT)(v[i]  )<<56) | ((ABSV_UINT)(v[i+1])<<48) | ((ABSV_UINT)(v[i+2])<<40) | ((ABSV_UINT)(v[i+3])<<32)
          |((ABSV_UINT)(v[i+4])<<24) | ((ABSV_UINT)(v[i+5])<<16) | ((ABSV_UINT)(v[i+6])<< 8) | ((ABSV_UINT)(v[i+7])    );
#endif
  default: break;
  }
  croak("absv_vget() cannot handle NBITS=" ABSV_PRI " for INDEX=" ABSV_PRI, nbits, i);
  return KEY_NOT_FOUND;
}

//--------------------------------------------------------------
static inline void absv_vset(uchar *v, ABSV_UINT i, ABSV_UINT nbits, ABSV_UINT val)
{
  ABSV_UINT b;
  switch (nbits) {
  case 1:	b=i&7;      i>>=3; v[i] = (v[i]&~( 1<<b)) | ((val& 1)<<b); break;
  case 2:	b=(i&3)<<1; i>>=2; v[i] = (v[i]&~( 3<<b)) | ((val& 3)<<b); break;
  case 4:	b=(i&1)<<2; i>>=1; v[i] = (v[i]&~(15<<b)) | ((val&15)<<b); break;
  case 8:	v[i] = (val & 255); break;
  case 16:	v += (i<<1); *v++=(val>> 8)&0xff; *v=(val&0xff); break;
  case 32:	v += (i<<2); *v++=(val>>24)&0xff; *v++=(val>>16)&0xff; *v++=(val>>8)&0xff; *v=val&0xff; break;
#ifdef ABSV_HAVE_QUAD
  case 64:
    v += (i<<3);
    *v++=(val>>56)&0xff; *v++=(val>>48)&0xff; *v++=(val>>40)&0xff; *v++=(val>>32)&0xff;
    *v++=(val>>24)&0xff; *v++=(val>>16)&0xff; *v++=(val>> 8)&0xff; *v  =val      &0xff;
    break;
#endif
  default:
    croak("absv_vset() cannot handle NBITS=" ABSV_PRI " for INDEX=" ABSV_PRI, nbits, i);
    break;
  }
}

//--------------------------------------------------------------
static ABSV_UINT absv_bsearch(const uchar *v, ABSV_UINT key, ABSV_UINT ilo, ABSV_UINT ihi, ABSV_UINT nbits)
{
  while (ilo < ihi) {
    ABSV_UINT imid = (ilo+ihi) >> 1;
    if (absv_vget(v, imid, nbits) < key)
      ilo = imid + 1;
    else
      ihi = imid;
  }
  if ((ilo == ihi) && (absv_vget(v,ilo,nbits) == key))
    return ilo;
  else
    return KEY_NOT_FOUND;
}

//--------------------------------------------------------------