u32Table.c

// Copyright 2018, Kevin Lang, Oath Research

#include "common.h"
#include "u32Table.h"
#include "fm85Util.h"

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

u32Table * u32TableMake (Short lgSize, Short numValidBits) {
  assert (lgSize >= 2);
  Long numSlots = (1LL << lgSize);
  u32Table * self = (u32Table *) malloc (sizeof(u32Table));
  U32 * arr = (U32 *) malloc ((size_t) (numSlots * sizeof(U32)));
  assert (self != NULL);
  assert (arr != NULL);
  Long i = 0;
  for (i = 0; i < numSlots; i++) { arr[i] = ALL32BITS; }
  assert (numValidBits > 0 && numValidBits <= 32);
  self->validBits = numValidBits;
  self->lgSize = lgSize;
  self->numItems = 0;
  self->slots = arr;
  return (self);
}

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

u32Table * u32TableCopy (u32Table * self) {
  assert (self != NULL && self->slots != NULL);
  Long numSlots = (1LL << self->lgSize);
  u32Table * newObj = (u32Table *) shallowCopy ((void *) self, sizeof(u32Table));
  newObj->slots = (U32 *) shallowCopy ((void *) self->slots, ((size_t) numSlots) * sizeof(U32));
  return (newObj);
}

//  newObj->validBits = self->validBits;
//  newObj->lgSize    = self->lgSize;
//  newObj->numItems  = self->numItems;

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

void u32TableFree (u32Table * self) {
  if (self != NULL) {
    if (self->slots != NULL) free (self->slots);
    free (self);
  }
}

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

void u32TableShow (u32Table * self) {
  Long tableSize = 1LL << self->lgSize;
  printf ("\nu32Table (%d valid bits; %lld of %lld slots occupied)\n",
	  self->validBits, self->numItems, tableSize);
  //  U32 * arr = self->slots;
  //  Long i;
  //  for (i = 0; i < tableSize; i++) {
  //    if (arr[i] == ALL32BITS) printf ("%d:\tempty\n", (int) i);
  //    else printf ("%d:\t%8X\n", (int) i, arr[i]);
  //  }
  fflush (stdout);
}

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

void u32TableClear (u32Table * self) { // clear the table without resizing it
  Long tableSize = 1LL << self->lgSize;
  U32 * arr = self->slots;
  Long i;
  for (i = 0; i < tableSize; i++) { arr[i] = ALL32BITS; }
  self->numItems = 0;
}

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

void printU32Array (U32 * array, Long arrayLength) {
  Long i = 0;
  printf ("\nu32Array [%lld]\n", arrayLength);
  for (i = 0; i < arrayLength; i++) {
    printf ("%d:\t%8X\n", (int) i, array[i]);    
  }
  fflush (stdout);
}

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

#define U32_TABLE_LOOKUP_SHARED_CODE_SECTION \
  Long tableSize = 1LL << self->lgSize; \
  Long mask = tableSize - 1LL; \
  Short shift = self->validBits - self->lgSize; \
  Long probe = ((Long) item) >> shift; \
  assert (probe >= 0 && probe <= mask); \
  U32 * arr = self->slots; \
  U32 fetched = arr[probe]; \
  while (fetched != item && fetched != ALL32BITS) { \
    probe = (probe + 1) & mask; \
    fetched = arr[probe]; \
  }

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

void u32TableMustInsert (u32Table * self, U32 item) {
  U32_TABLE_LOOKUP_SHARED_CODE_SECTION;
  if (fetched == item) { FATAL_ERROR("u32TableMustInsert"); }
  else {
    assert (fetched == ALL32BITS);
    arr[probe] = item;
    // counts and resizing must be handled by the caller.
  }
}

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

// This one is specifically tailored to be part of our fm85 decompression scheme.

u32Table * makeU32TableFromPairsArray (U32 * pairs, Long numPairs, Short sketchLgK) {
  Short lgNumSlots = 2;
  while (u32TableUpsizeDenom * numPairs > u32TableUpsizeNumer * (1LL << lgNumSlots)) { lgNumSlots++; }
  u32Table * table = u32TableMake (lgNumSlots, 6 + sketchLgK); // Already filled with the "Empty" value which is ALL32BITS.
  Long i = 0;
  // Note: there is a possible "snowplow effect" here because the caller is passing in a sorted pairs array.
  // However, we are starting out with the correct final table size, so the problem might not occur.
  for (i = 0; i < numPairs; i++) {
    u32TableMustInsert (table, pairs[i]);
  }
  table->numItems = numPairs;
  return (table);
}

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

void privateU32TableRebuild (u32Table * self, Short newLgSize) {
  assert (newLgSize >= 2);
  Long newSize = (1LL << newLgSize);
  Long oldSize = (1LL << self->lgSize);
  //  printf ("rebuilding: %lld -> %lld; %lld items in table\n", oldSize, newSize, self->numItems); fflush (stdout);
  assert (newSize > self->numItems); // TODO
  U32 * oldSlots = self->slots;
  U32 * newSlots = (U32 *) malloc ((size_t) (newSize * sizeof(U32)));
  assert (newSlots != NULL);
  Long i;
  for (i = 0; i < newSize; i++) { 
    newSlots[i] = ALL32BITS;
  }  
  self->slots = newSlots;
  self->lgSize = newLgSize;
  for (i = 0; i < oldSize; i++) {
    U32 item = oldSlots[i];
    if (item != ALL32BITS) {
      u32TableMustInsert (self, item);
    }
  }
  free (oldSlots);
  return;
}

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

// Returns true iff the item was new and was therefore added to the table.

Boolean u32TableMaybeInsert (u32Table * self, U32 item) {
  U32_TABLE_LOOKUP_SHARED_CODE_SECTION;
  if (fetched == item) { return 0; }
  else {
    assert (fetched == ALL32BITS);
    arr[probe] = item;
    self->numItems += 1;
    while (u32TableUpsizeDenom * self->numItems > u32TableUpsizeNumer * (1LL << self->lgSize)) {
      privateU32TableRebuild(self, self->lgSize + 1);
    }
    return 1;
  }
}

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

// Returns true iff the item was present and was therefore removed from the table.

Boolean u32TableMaybeDelete (u32Table * self, U32 item) {
  U32_TABLE_LOOKUP_SHARED_CODE_SECTION;
  if (fetched == ALL32BITS) { return 0; }
  else {
    assert (fetched == item);
    // delete the item
    arr[probe] = ALL32BITS;
    self->numItems -= 1; assert (self->numItems >= 0);

    // re-insert all items between the freed slot and the next empty slot
    probe = (probe + 1) & mask; fetched = arr[probe];
    while (fetched != ALL32BITS) {
      arr[probe] = ALL32BITS;
      u32TableMustInsert (self, fetched);
      probe = (probe + 1) & mask; fetched = arr[probe];      
    }

    // shrink if necessary
    while (u32TableDownsizeDenom * self->numItems < u32TableDownsizeNumer * (1LL << self->lgSize) && self->lgSize > 2) {
      privateU32TableRebuild(self, self->lgSize - 1);
    }
    return 1;
  }
}

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

// While extracting the items from a linear probing hashtable,
// this will usually undo the wrap-around provided that the table 
// isn't too full. Experiments suggest that for sufficiently large tables 
// the load factor would have to be over 90 percent before this would fail frequently, 
// and even then the subsequent sort would fix things up.

U32 * u32TableUnwrappingGetItems (u32Table * self, Long * returnNumItems) {
  *returnNumItems = self->numItems;
  if (self->numItems < 1) { return (NULL); }
  U32 * slots = self->slots;
  Long tableSize = (1LL << self->lgSize);
  U32 * result = (U32 *) malloc ((size_t) (self->numItems * sizeof(U32)));  
  assert (result != NULL);
  Long i = 0;
  Long l = 0;
  Long r = self->numItems - 1;

  // Special rules for the region before the first empty slot.
  U32 hiBit = 1 << (self->validBits - 1);
  while (i < tableSize && slots[i] != ALL32BITS) {
    U32 item = slots[i++];
    if (item & hiBit) { result[r--] = item; } // This item was probably wrapped, so move to end.
    else              { result[l++] = item; }
  }

  // The rest of the table is processed normally.
  while (i < tableSize) {
    U32 look = slots[i++];
    if (look != ALL32BITS) { result[l++] = look; }
  }
  assert (l == r + 1);
  return (result);
}


/*******************************************************/
// The Java version won't need this, because it provides a good array sort.

void u32KnuthShellSort3(U32 a[], Long l, Long r)
{ Long i, h;
  for (h = 1; h <= (r-l)/9; h = 3*h+1) ;
  for ( ; h > 0; h /= 3) {
    for (i = l+h; i <= r; i++) {
      Long j = i; U32 v = a[i]; 
      while (j >= l+h && v < a[j-h])
	{ a[j] = a[j-h]; j -= h; }
      a[j] = v; 
    } 
  }
  Long bad = 0;
  for (i = l; i < r-1; i++) {
    if (a[i] > a[i+1]) bad++;
  };
  assert (bad == 0);
}

/*******************************************************/
// In applications where the input array is already nearly sorted,
// insertion sort runs in linear time with a very small constant.
// This introspective version of insertion sort protects against
// the quadratic cost of sorting bad input arrays.
// It keeps track of how much work has been done, and if that exceeds a
// constant times the array length, it switches to a different sorting algorithm.

void introspectiveInsertionSort(U32 a[], Long l, Long r) // r points AT the rightmost element
{ Long i;
  Long length = r - l + 1;
  Long cost = 0;
  Long costLimit = 8 * length;
  for (i = l+1; i <= r; i++) {
    Long j = i; 
    U32 v = a[i]; 
    while (j >= l+1 && v < a[j-1]) { 
      a[j] = a[j-1]; 
      j -= 1; 
    }
    a[j] = v; 
    cost += (i - j); // distance moved is a measure of work
    if (cost > costLimit) {
      fprintf (stderr, "switching to the other sorting algorithm\n"); fflush (stderr);
      u32KnuthShellSort3(a, l, r); // In the Java version, this should be the system's array sort.
      return;
    }
  } 
  // The following sanity check can eventually go away, but it seems like a
  // good idea to perform it while the code is under development.
  //  Long bad = 0;
  //  for (i = l; i < r-1; i++) {
  //    if (a[i] > a[i+1]) bad++;
  //  };
  //  assert (bad == 0);
}


//  printf ("cost was %lld (arrlen=%lld)\n", cost, length); fflush (stdout);


/******************************************************/
// This merge is safe to use in carefully designed overlapping scenarios.

void u32Merge (U32 * arrA, Long startA, Long lengthA, // input
	       U32 * arrB, Long startB, Long lengthB, // input
	       U32 * arrC, Long startC) { // output
  Long lengthC = lengthA + lengthB;
  Long limA = startA + lengthA;
  Long limB = startB + lengthB;
  Long limC = startC + lengthC;
  Long a = startA;
  Long b = startB;
  Long c = startC;
  for ( ; c < limC ; c++) {
    if      (b >= limB)         { arrC[c] = arrA[a++]; }
    else if (a >= limA)         { arrC[c] = arrB[b++]; }
    else if (arrA[a] < arrB[b]) { arrC[c] = arrA[a++]; }
    else                        { arrC[c] = arrB[b++]; }
  }
  assert (a == limA);
  assert (b == limB);
}



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

#ifdef TOKUDA

Long tokudaIncrements [48] = 
  { 1LL, 4LL, 9LL, 20LL, 46LL, 103LL, 233LL, 525LL, 1182LL, 2660LL, 5985LL, 13467LL, 30301LL, 68178LL,
    153401LL, 345152LL, 776591LL, 1747331LL, 3931496LL, 8845866LL, 19903198LL, 44782196LL,
    100759940LL, 226709866LL, 510097200LL, 1147718700LL, 2582367076LL, 5810325920LL,
    13073233321LL, 29414774973LL, 66183243690LL, 148912298303LL, 335052671183LL,
    753868510162LL, 1696204147864LL, 3816459332694LL, 8587033498562LL,
    19320825371765LL, 43471857086472LL, 97811678444563LL, 220076276500268LL,
    495171622125603LL, 1114136149782608LL, 2506806337010868LL, 5640314258274455LL,
    12690707081117524LL, 28554090932514432LL };

// Call with r pointing AT the rightmost element of the subarray.

void u32TokudaShellSort(U32 a[], Long l, Long r)
{ Long i, h, k;
  for (k = 0; tokudaIncrements[k] <= (r-l)/5; k++) ;
  for (; k >= 0; k--) {
    h = tokudaIncrements[k];
    for (i = l+h; i <= r; i++) {
      Long j = i; U32 v = a[i]; 
      while (j >= l+h && v < a[j-h])
	{ a[j] = a[j-h]; j -= h; }
      a[j] = v; 
    } 
  }
  //  Long bad = 0;
  //  for (i = l; i < r-1; i++) {
  //    if (a[i] > a[i+1]) bad++;
  //  };
  //  assert (bad == 0);
}

#endif