Title: The Wall

Dear Francis,

Since you asked for an implementation of the eliminate function which used neither break nor a function, I thought I would try my hand at my first letter to ACCU. I initially sketched this out on the train, but lost the piece of paper in dashing for a connection.

The obvious efficient implementation of this function was suggested by Pete Disdale, using a 256-element array, building it up.

I chose to use 32-bit words rather than bytes so that I could erase the discard array easily using the initialiser. With memory so cheap, it would have been quicker to just allocate 256 bytes of memory and use the char as a location in that array. I chose to be space efficient and use a mask and shift method to get the word and bit indices.

I also used unsigned char internally to allow the function to cope with any extended ASCII characters it may be given. To make this code really portable, I should be generating the constants (i.e. num_elements, index_shift and mask_bits) according to sizeof (unsigned long) but I could not think of a way to generate the latter two at compile time.

As is so often the case, the code to test the function to my satisfaction ended up being larger than the code I was writing.

/* ACCU_eliminate.cpp
   Function to eliminate characters within one string from another string, returning a pointer to the eliminated string. Note that this is a destructive function, i.e. it destroys the source string in generating the result.
   Also included is my rough and ready tests, these test the obvious boundary conditions of the parts of the function. Also tested is the high bit handling.
*/
#include "stdafx.h"
char * eliminate(const char these[],
                 char from[]);
void testme(const char these[], 
              char from[]);
int main(){
  char teststring1[] = 
    "This test removes all vowels and spaces.";
  char removeme1[] = "aeiou ";
  char teststring2[] = 
          "This test removes all of self.";
  char teststring3[] =
             "This test removes nothing.";
  char teststring4[] = 
     "This test removes the first character.";
  char removeme4[] = "T";
  char teststring5[] = 
      "This test removes the last character.";
  char removeme5[] = ".";
  unsigned char teststringA[] = { 0x01, 0x1f,   
    0x20, 0x44, 0x80, 0x81, 0xc0, 0xff, 0x00};
  unsigned char removemeA[] = { 0x01, 0x1f, 
          0x44, 0x80, 0x81, 0xff, 0x00};
  unsigned char teststringB[] = { 0x01, 0x1f, 
    0x20, 0x44, 0x80, 0x81, 0xc0, 0xff ,0x00};
  testme(removeme1, teststring1);
  testme(teststring2, teststring2);
  testme("", teststring3);
  testme(removeme4, teststring4);
  testme(removeme5, teststring5);
  testme((char*)removemeA, (char*)teststringA);
  testme((char*)teststringB, (char*)teststringB);
  return 0;
}
void testme(char const *these, char *from) {
  char *teststring;
  printf("eliminate \"%s\" from \"%s\"\n",
                 these, from);
  teststring = eliminate(these, from);
  printf(" = \"%s\"\n", teststring);
}
char *eliminate(char const *these, char *from) {
  unsigned char *src, *dst;
/* Assume a 32-bit minimum size unsigned long */
  int const num_elements = 8; /* 256 / 32 = 8 */
  unsigned long discard[num_elements] = {0};
  int const index_shift = 5; /* 2^5 = 32 *8 */
  int const mask_bits = 0x1F;
  int i;
/* Bits 0-4 index into word, 5-7 into array. */
/* Set up discard */
  for (src=(unsigned char*)these; *src; src++){
/* Add char to discard. Find the word */
    i = (*src) >> index_shift;
/* and set the correct bit */
    discard[i] = discard[i] | 
            1 << (*src & mask_bits);
  }  
/* Do eliminate */
  dst=src=(unsigned char *)from;
  while (*dst = *src++) {
/* Find the discard word */
    i = (*dst) >> index_shift;
/* and test for the correct bit */
    if (!(discard[i] & 
        1 << (*dst & mask_bits))) dst++;
    }
  }
  return from;
}

Thanks. I made a few changes in the code that have no effect on the results. I changed your declarations to meet the house style where cv-qualification is to the right of the thing qualified. I simplified your initialosation of discard.