+/** ============================================================ **/
+
+static int VECTOR_BITS[4] = { 8, 4, 2, 64 };
+
+typedef struct {
+ unsigned int a:2;
+ unsigned int b:2;
+ unsigned int c:2;
+ unsigned int d:2;
+} bitpair;
+
+typedef struct {
+ unsigned int a:4;
+ unsigned int b:4;
+} nibble;
+
+typedef struct {
+ unsigned int a:8;
+} byte;
+
+/**
+ * Return the index part for the given level of the vector's leveling
+ * variant.
+ *
+ * The vector variant indicates whether indexing uses 8, 4, or 2 bits
+ * per level.
+ */
+unsigned long VECTOR_INDEX_PART(vector *pv,vector_index *index, int level) {
+ unsigned char *px = (unsigned char *) index;
+ switch ( pv->variant ) {
+ case 0: {
+ byte *pp = (byte*)(px + level);
+ return pp->a;
+ }
+ case 1: {
+ nibble *pp = (nibble*)( px + ( level / 2 ) );
+ switch ( level & 1 ) {
+ case 0: return pp->a;
+ case 1: return pp->b;
+ }
+ break;
+ }
+ case 2: {
+ bitpair *pp = (bitpair*)( px + ( level / 4 ) );
+ switch ( level & 3 ) {
+ case 0: return pp->a;
+ case 1: return pp->b;
+ case 2: return pp->c;
+ case 3: return pp->d;
+ }
+ break;
+ }
+ case 3:
+ return (*index);
+ }
+ return 0;
+}
+
+/**
+ * Increment the index part at the indivated level, cyclic but not
+ * carrying over to the upper level. Returns the new level index.
+ */
+static unsigned long VECTOR_INDEX_PART_INC(
+ vector *pv,vector_index *index, int level)
+{
+ unsigned char *px = (unsigned char *) index;
+ switch ( pv->variant ) {
+ case 0: {
+ byte *pp = (byte*)( px + level );
+ return ++(pp->a);
+ }
+ case 1: {
+ nibble *pp = (nibble*)( px + ( level / 2 ) );
+ switch ( level & 1 ) {
+ case 0: return ++(pp->a);
+ case 1: return ++(pp->b);
+ }
+ break;
+ }
+ case 2: {
+ bitpair *pp = (bitpair*)( px + level / 4 );
+ switch ( level & 3 ) {
+ case 0: return ++(pp->a);
+ case 1: return ++(pp->b);
+ case 2: return ++(pp->c);
+ case 3: return ++(pp->d);
+ }
+ break;
+ }
+ case 3:
+ return ++(*index);
+ }
+ return 0;
+}
+
+/**
+ * Decrement the index part at the indicated level, cyclic but not
+ * carrying over to the upper level. Returns the prior level index.
+ */
+static unsigned long VECTOR_INDEX_PART_DEC(
+ vector *pv,vector_index *index, int level)
+{
+ unsigned char *px = (unsigned char *) index;
+ switch ( pv->variant ) {
+ case 0: {
+ byte *pp = (byte*)( px + level );
+ return (pp->a)--;
+ }
+ case 1: {
+ nibble *pp = (nibble*)( px + ( level / 2 ) );
+ switch ( level & 1 ) {
+ case 0: return (pp->a)--;
+ case 1: return (pp->b)--;
+ }
+ break;
+ }
+ case 2: {
+ bitpair *pp = (bitpair*)( px + level / 4 );
+ switch ( level & 0xf ) {
+ case 0: return (pp->a)--;
+ case 1: return (pp->b)--;
+ case 2: return (pp->c)--;
+ case 3: return (pp->d)--;
+ }
+ break;
+ }
+ case 3:
+ return (*index)--;
+ }
+ return 0;
+}
+
+#define ONES (~((vector_index) 0))
+
+// Set index to first value for all index parts at level and lower.
+static void VECTOR_INDEX_FIRST(vector *pv,vector_index *index, int level) {
+ (*index) &= ONES << ( VECTOR_BITS[ pv->variant ] * level );
+}
+
+// Set index to last value for all index parts at level and lower.
+static void VECTOR_INDEX_LAST(vector *pv,vector_index *index, int level) {
+ static unsigned long ones[] = { 255, 15, 3 };
+ unsigned long x = ones[ pv->variant ];
+ while ( level-- ) {
+ (*index) |= x;
+ x <<= VECTOR_BITS[ pv->variant ];
+ }
+ // 255, 25, 3
+ //(*index) |= ONES >> ( 64 - ( VECTOR_BITS[ pv->variant ] * level ) );
+}
+
+// Return number of slots for a vector variant.
+unsigned long VECTOR_SLOTS(vector *pv) {
+ switch ( pv->variant ) {
+ case 0: return 256;
+ case 1: return 16;
+ case 2: return 4;
+ case 3: return pv->size;
+ }
+ return 0;
+}
+
+// The number of levels to span vector pv wrt its size and variant
+static unsigned int vector_levels(vector *pv,unsigned int size) {
+ if ( size < 4 ) {
+ return 1;
+ }
+ switch ( pv->variant ) {
+ case 0: return ((int)(log2( size - 1 ) / 8)) + 1;
+ case 1: return ((int)(log2( size - 1 ) / 4)) + 1;
+ case 2: return ((int)(log2( size - 1 ) / 2)) + 1;
+ case 3: return 1;
+ }
+ return 0;
+}
+
+/** ============================================================ **/
+