I don’t much like the C programming language, but as part of my Internet anti-bullying campaign (including the campaign against the anti-Schildt swift-boating campaign mentioned elsewhere here in my blog), I am relearning it in order to make my points more effectively at the usenet/Google Group comp.lang.c.
This is where the instigator of the anti-Schildt swift boating (Peter Seebach) resides. He’d posted a piece of code purporting to replace %s by strings, but I noticed that in using the C library string.H, he’d been blinded by the poor implementation of strings in C.
He’d used a character find to locate the percent sign in two different places, and hadn’t bothered, by his own admission, to check for the following s. This meant that correcting the code involved making the same clumsy change in two separate places, guaranteeing further problems.
I discussed a real string replacement program, but actually thinking about “strings” independent of “character arrays with a Nul at the right” is beyond the day to day ken of many C programmers due to the subtle ways in which string.H blinds the soul.
I then demonstrated a straightforward replace() function, working collaboratively online with a few well-intentioned posters who were willing to find bugs.
In Swift Boat mode, Seebach of course interpreted this as “posting buggy software”. Since I don’t take shit, the fun was on at the link below.
It amused me to get back up to speed in C after many years (having helped John “A Beautiful Mind” Nash with C at Princeton in 1991) in order to prove my point: that today’s corporate programmers rarely program, are unqualified, and tend to be bullies, who see in others “the secret contour” of their own weakness, incompetence and fear.
See this link for the Google Group discussions. Warning: drink deep or drink not from this Pieran spring, for the discussion is a real free for all, and it is a big mistake to make conclusions after reading only a few posts. Indeed, the Thugs rely on superficial readings absent any sort of moral grammar, so that their favorite argument, the criminal’s tu quoque, can be used.
Here is the code of a replace() function. It is raising for me some interesting questions of theory and method which I shall pursue primarily in the thread from hell with updates here. In particular, C is strongly biased towards Western languages read left to right, and the VERY interesting problem of a string like “banana” and a replacement of ana by omo (bomona or banono?) needs to be addressed.
Even more interesting would be the relationship of the straightforward-if-crude algorithm used below and the Boyer Moore algorithm.
Also, an argument, germane to some possible real-world applications, could be made that “banana” contains TWO partly overlapping occurences of ana, and could be converted to bonono! Boyer Moore may anticipate this: I need to recheck this source.
But: the Google Groups discussion is why I’m delighted to be a teacher today. My father asked me what would happen when all the code was written. The answer seems to me to be that a eunuch priesthood of machine tenders, without qualifications, courage, spirit, or heart, would then tear at each other for sinecures maintained only because someone needs to hold down the null function in the corporation.
Here is the code.
// ***************************************************************
// * *
// * replace() demo *
// * *
// * Demonstrates how to replace non-NUL-defined strings in C *
// * using a simple function, and bypassing string.h. *
// * *
// * C H A N G E R E C O R D --------------------------------- *
// * DATE PROGRAMMER DESCRIPTION OF CHANGE *
// * -------- ---------- --------------------------------- *
// * 02 07 10 Nilges Version 1.0 *
// * *
// * 02 07 10 Nilges Bug: partial matches not handled *
// * correctly: need to iterate search *
// * for match. *
// * *
// * 02 07 10 Nilges 1. Santosh suggested tests *
// * 2. Heathfield put the boot in re *
// * including malloc *
// * *
// * 02 07 10 Nilges 1. Remove string.h use and code *
// * strlen by hand *
// * 2. Add comment block and comments*
// * inline. *
// * 3. free() storage *
// * 4. Use macro for testing *
// * 5. Bug: calculation of *
// * lngNewLength used incorrect *
// * index (intIndex3 instead of 2)*
// * which caused a memory leak. *
// * *
// * 02 07 10 Nilges 1. Bug: Ike Naar test failed. *
// * At end of scan loop, main *
// * string pointer was not *
// * correctly updated from index3 *
// * *
// * 02 07 10 Nilges Added new Santosh test *
// * *
// * 02 07 10 Nilges Added new Ike Naar test *
// * *
// * 02 08 10 Nilges 1. Added some new comments *
// * 2. Make "check for a complete *
// * match "structured" by means *
// * of a tested assignment *
// * 3. Get rid of "replace at end" *
// * evilness: the only time this *
// * flag is meaningful is in the *
// * LAST segment. *
// * 4. Return replace count *
// * 5. TESTER macro assertion added *
// * *
// * 02 10 10 Nilges 1. Bug fix: in a partial match, *
// * the main scan index is set to *
// * one past the end, which misses*
// * full matches that start *
// * between the first character of*
// * the partial match and its end.*
// * *
// * No longer updating the main *
// * scan index (ptrIndex1) to the *
// * point of partial match *
// * failure: setting it one past *
// * the first character of the *
// * partial match. *
// * *
// * 2. Line up expected & actual *
// * results per excellent *
// * suggestion (who made this?) *
// * *
// * 3. After a partial match, update *
// * the main handle search index *
// * (ptrIndex1) to the first *
// * occurrence of the handle *
// * character after the start of *
// * the partial match, or to the *
// * index of the unmatched char. *
// * *
// * 021310 Nilges Bug: failed to handle a one-char *
// * replace (of a by x in b) since *
// * we set ptrIndex2 to point to NUL *
// * which made it appear that there *
// * was a match. When the main index *
// * to the master string (ptrIndex1) *
// * goes off the end of a cliff, we *
// * needed to break out of the search *
// * loop. *
// * *
// * This also entailed setting the *
// * target index ptrIndex2 to 0 at the*
// * beginning of each search so that *
// * it is not erroneously used to *
// * indicate that there's an insert *
// * needed at the end. *
// * *
// * I have also added additional tests*
// * to verify that the code works *
// * when the string and target end *
// * at the same time. *
// * ----------------------------------------------------------- *
// * *
// * "In the near future we shall have to live with the *
// * superstition that programming is 'so easy that even a *
// * Republican can do it!'" *
// * *
// * - E. W. Dijkstra *
// * *
// * *
// ***************************************************************
#include <stdio.h>
#include <stdlib.h>
// ***** Segmentation *****
struct TYPsegmentstruct
{ char * strSegment;
long lngSegmentLength;
struct TYPsegmentstruct * ptrNext; };
// ---------------------------------------------------------------
// Calculate string length
//
//
long strLength(char *strInstring)
{
char *ptrInstring;
for (ptrInstring = strInstring; *ptrInstring; ptrInstring++);
return ptrInstring - strInstring;
}
// ---------------------------------------------------------------
// Replace target by replacement string in master string
//
//
// Caution: the string returned by this function should be freed.
//
//
char * replace(char * strMaster,
char * strTarget,
char * strReplacement,
long * ptrReplacements)
{
char * ptrIndex0;
char * ptrIndex1;
char * ptrIndex2;
char * ptrIndex3;
char * ptrIndex4;
char * strNew;
char * strNewStart;
long lngNewLength;
long lngCount;
long lngReplacementLength;
struct TYPsegmentstruct * ptrSegmentStructStarts;
struct TYPsegmentstruct * ptrSegmentStruct;
struct TYPsegmentstruct * ptrSegmentStructPrev;
lngReplacementLength = strLength(strReplacement);
if (!*strTarget)
{
printf("Error in calling replace(): target can't be null");
abort();
}
ptrIndex1 = strMaster;
ptrSegmentStructPrev = 0;
lngNewLength = 0;
*ptrReplacements = 0;
while(*ptrIndex1)
{
ptrIndex0 = ptrIndex1;
ptrIndex2 = 0;
while (-1)
{
// --- Check for (one character) handle
for(;
*ptrIndex1 && *ptrIndex1 != *strTarget;
ptrIndex1++);
if (!*ptrIndex1) break;
// --- Check for complete match while remembering the
// --- last position of the handle
ptrIndex4 = 0;
for(ptrIndex2 = strTarget + 1,
ptrIndex3 = ptrIndex1 + 1;
*ptrIndex3
&&
*ptrIndex2
&&
*ptrIndex3 == *ptrIndex2;
ptrIndex3++, ptrIndex2++)
{
if (*ptrIndex3 == *strTarget
&&
ptrIndex4 == 0) ptrIndex4 = ptrIndex3;
}
// End test: check complete match, update main ptr past
// partial match while checking for end of loop
if ((!*ptrIndex2 ? ((*ptrReplacements)++, -1) : 0)
||
(!*ptrIndex3 ? (ptrIndex1 = ptrIndex3, -1) : 0))
break;
// Update the main search pointer
ptrIndex1 = (ptrIndex4 == 0 ? ptrIndex3 : ptrIndex4);
}
// --- Create new segment
if (!(ptrSegmentStruct =
malloc(sizeof(struct TYPsegmentstruct))))
abort();
ptrSegmentStruct->strSegment = ptrIndex0;
ptrSegmentStruct->lngSegmentLength =
ptrIndex1 - ptrIndex0;
ptrSegmentStruct->ptrNext = 0;
if (ptrSegmentStructPrev != 0)
ptrSegmentStructPrev->ptrNext = ptrSegmentStruct;
else
ptrSegmentStructStarts = ptrSegmentStruct;
ptrSegmentStructPrev = ptrSegmentStruct;
// --- Update mallocation length
lngNewLength += ptrSegmentStruct->lngSegmentLength +
(ptrIndex2 && !*ptrIndex2
?
lngReplacementLength
:
0);
// --- Get past end of target string & iterate
if (*ptrIndex1) ptrIndex1 = ptrIndex3;
}
// --- Allocate just enough storage for the new string
if (!(strNewStart = malloc(lngNewLength + 1))) abort();
// --- Build the new string whilst freeing the list
strNew = strNewStart;
ptrSegmentStruct = ptrSegmentStructStarts;
while (ptrSegmentStruct)
{
for (ptrIndex1 = ptrSegmentStruct->strSegment,
lngCount = 0;
lngCount < ptrSegmentStruct->lngSegmentLength;
ptrIndex1++, lngCount++, strNew++)
*strNew = *ptrIndex1;
if (ptrSegmentStruct->ptrNext
||
ptrIndex2 != 0 && !*ptrIndex2)
for (ptrIndex1 = strReplacement;
*ptrIndex1;
ptrIndex1++, ++strNew)
*strNew = *ptrIndex1;
ptrSegmentStructPrev = ptrSegmentStruct;
ptrSegmentStruct = ptrSegmentStruct->ptrNext;
free(ptrSegmentStructPrev);
}
*strNew = '\0';
return strNewStart;
}
// ---------------------------------------------------------------
// Statement-format test macro
//
//
#define TESTER(resultPtr, master, target, replacement, expected,
expectedReplacements, replacements) \
{ \
printf("Replace \"%s\" by \"%s\" in \"%s\"\n", \
(target), (replacement), (master)); \
printf("Expect \"%s\":\n \"%s\"\n", \
(expected), \
resultPtr = replace((master), \
(target), \
(replacement), \
&(replacements))); \
printf("Replacements expected: %d: replacements: %d\n", \
(expectedReplacements), \
(replacements)); \
if (!(strLength(resultPtr) \
== \
strLength(master) \
+ \
(strLength(replacement)-strLength(target)) \
* \
replacements)) \
printf("Assertion failed\n"); \
printf("\n\n"); \
free(resultPtr); \
}
// ---------------------------------------------------------------
// Main procedure
//
//
int main()
{
char *ptrResult;
long lngReplacements;
printf("\nReplace\n\n\n");
TESTER(ptrResult,
"1111123bbb1111123bbb11123bb11111231111112111111123",
"111123",
"ono",
"1onobbb1onobbb11123bb1ono1111112111ono",
4,
lngReplacements)
TESTER(ptrResult,
"bbb1111123bbbbb",
"111123",
"ono",
"bbb1onobbbbb",
1,
lngReplacements)
TESTER(ptrResult,
"a stupid error",
"stupid error",
"miracle",
"a miracle",
1,
lngReplacements)
TESTER(ptrResult,
"a stupid error",
"stupid",
"miracle",
"a miracle error",
1,
lngReplacements)
TESTER(ptrResult,
"the stupid error",
"the stupid error",
"a miracle",
"a miracle",
1,
lngReplacements)
TESTER(ptrResult,
"the miracle",
"the",
"a",
"a miracle",
1,
lngReplacements)
TESTER(ptrResult,
"a miraclsnirpKamunkle",
"snirpKamunkle",
"e",
"a miracle",
1,
lngReplacements)
TESTER(ptrResult,
"a miraclesnirpKamunkle",
"a miracle",
"",
"snirpKamunkle",
1,
lngReplacements)
TESTER(ptrResult,
" a miraclesnirpKamunkle",
"a miracle",
"",
" snirpKamunkle",
1,
lngReplacements)
TESTER(ptrResult,
" a miraclesnirpKamunklea miraclea miracle",
"a miracle",
"",
" snirpKamunkle",
3,
lngReplacements)
TESTER(ptrResult,
"a miracle a miraclesnirpKamunkle a Miraclea miraclea
miracle",
"a miracle",
"",
" snirpKamunkle a Miracle",
4,
lngReplacements)
TESTER(ptrResult,
"a stupid errord",
"stupid error",
"miracle",
"a miracled",
1,
lngReplacements)
TESTER(ptrResult,
"a stupid errod",
"stupid error",
"miracle",
"a stupid errod",
0,
lngReplacements)
TESTER(ptrResult,
"a sstupid error",
"stupid error",
"miracle",
"a smiracle",
1,
lngReplacements)
TESTER(ptrResult,
"a stupid errorstupid error",
"stupid error",
"miracle",
"a miraclemiracle",
2,
lngReplacements)
TESTER(ptrResult,
"a stupid error stupiderror",
"stupid error",
"miracle",
"a miracle stupiderror",
1,
lngReplacements)
TESTER(ptrResult,
"bbbbbbbbbb",
"b",
"a",
"aaaaaaaaaa",
10,
lngReplacements)
TESTER(ptrResult,
"In the halls of R'yleh great %s lies dreaming",
"%s",
"Cthulu",
"In the halls of R'yleh great Cthulu lies dreaming",
1,
lngReplacements)
TESTER(ptrResult,
"%s%s%s%s%s%s",
"%s",
"Cthulu",
"CthuluCthuluCthuluCthuluCthuluCthulu",
6,
lngReplacements)
TESTER(ptrResult,
"banana",
"ana",
"oat",
"boatna",
1,
lngReplacements)
TESTER(ptrResult,
" a stupid errorstupid errorHeystupid errors",
"stupid error",
"+",
" a ++Hey+s",
3,
lngReplacements)
TESTER(ptrResult,
"foo barfoo barf",
"foo bar",
"bas",
"basbasf",
2,
lngReplacements)
TESTER(ptrResult,
"abab",
"ba",
"ba",
"abab",
1,
lngReplacements)
TESTER(ptrResult,
"abab",
"bab",
"boop",
"aboop",
1,
lngReplacements)
TESTER(ptrResult,
"banana",
"ana",
"ono",
"bonona",
1,
lngReplacements)
TESTER(ptrResult,
"a",
"x",
"b",
"a",
0,
lngReplacements)
TESTER(ptrResult,
"x",
"x",
"b",
"b",
1,
lngReplacements)
TESTER(ptrResult,
"egregious",
"egregious",
"egregious",
"egregious",
1,
lngReplacements)
TESTER(ptrResult,
"egregious",
"egregious",
"x",
"x",
1,
lngReplacements)
printf("\n\nTesting complete: check output carefully: \"Assertion
failed\" should not occur!\n\n");
return 0;
}
