# String compaction algorithm

I've been working on improving my C coding. I wanted to write two string algorithms:

1. to trim white space from the beginning and end of a string
2. to compact a string

I have a few problems with this code that I was hoping to get some advice on:

1. The casts from const char * to char *. Is there a clean and idiomatic way of cleaning those up?
2. The string compaction algorithm requires extra storage and I couldn't think of a clean way to do the compaction in place. Is there a clean way of doing it in place?

I'm looking for a review on algorithmic correctness, code style, design, and any other improvements you can think of. My main concern is performance!

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>

static const char TERMINATOR = '\0';

/* skips space in @param[str] depending on the provided direction
@param[in] -- str -- the string
@param[in] -- direction -- the direction to skip space in
1 -- forward direction
0 -- back direction
@return -- pointer to first non-space character in the string if
@param[direction] and @param[str] are valid or the original
string otherwise
*/
const char *skip_space(const char *str, int direction)
{
if (direction == 1) {
while (isspace(*str)) { ++str; }
} else if (direction == 0) {
while (isspace(*str)) { --str; }
}
return str;
}

const char *ltrim_white(const char *str, size_t len)
{
char *end = (char *)&str[len - 1];
end = (char *)skip_space(end, 0);
*++end = TERMINATOR;
return skip_space(str, 1);
}

const char *trim_white(const char *str)
{
return ltrim_white(str, strlen(str));
}

char *compact_with_mem(char *str)
{
str = (char *)skip_space(str, 1);

size_t len = strlen(str);
if (len == 0) {
char *c = malloc(1);
if (c) {
*c = TERMINATOR;
}
return c;
}

char *back = (char *)skip_space(&str[len - 1], 0);
*++back = TERMINATOR;

char *buf = malloc((back - str) + 1);
printf("Allocated %u memory\n", (back - str) + 1);
char *copy = buf;

while (*str) {
if (isspace(*str) && isspace(*(str + 1))) {
*copy++ = *str;
str = (char *)skip_space(str, 1);
} else {
*copy++ = *str++;
}
}
*copy = TERMINATOR;
return buf;
}

void print(const char *s)
{
const size_t len = strlen(s);
printf("|%s", s);
if (*(s + len) == TERMINATOR) { // redundant but just for testing
putchar('N');
}
puts("|");
}

void test(char *s, char *cmp_str)
{
const size_t blen = strlen(s);
printf("Base string: |%s|\n", s);
print(s);

char *ret = (char *)compact_with_mem(s);
const size_t len = strlen(ret);
printf("Length before compaction: %u\nLength after compaction: %u\n", blen, len);

print(ret);
puts("");
assert(strcmp(ret, cmp_str) == 0);
free(ret);
}

int main()
{
char s1[] = "   hello!";
char s2[] = "   world.   ";
char s3[] = "lol..";
char s4[] = "";
char s5[] = "               ";
char s6[] = "lmfao  ";
char s7[] = "         x";
char s8[] = "ab   ";
char s9[] = "   i am cthulhu   ";
char s10[] = "  all    your    base are belong    to us      ";
char s11[] = "  random    chars \\29289892 *&@ @)!  !*  # $_ ! & # * ! @! ^ *#^ | {]["; char s12[] = "omfgwhyaretherenospaceshere!"; test(s1, "hello!"); test(s2, "world."); test(s3, "lol.."); test(s4, ""); test(s5, ""); test(s6, "lmfao"); test(s7, "x"); test(s8, "ab"); test(s9, "i am cthulhu"); test(s10, "all your base are belong to us"); test(s11, "random chars \\29289892 *&@ @)! !* #$ _ ! & # * ! @! ^ *#^ | {][");
test(s12, "omfgwhyaretherenospaceshere!");
}


The functionality you have implemented in your “compact” is generally known as white-space normalization.

# Get rid of redundant functions

You have a lot of functions. While breaking complicated logic up into manageable bits is a good thing, there is also a point where it becomes too much and hurts maintainability rather than helping it.

For example, the only use of ltrim_white is in trim_white which consists of a single line calling that function. You could have equally well put all the code into trim_white directly. ltrim_white also is a misnomer because unlike its name suggests, it trims white-space from both sides, not just from the left.

const char *skip_space(const char *str, int direction)
{
if (direction == 1) {
while (isspace(*str)) { ++str; }
} else if (direction == 0) {
while (isspace(*str)) { --str; }
}
return str;
}


This function doesn't really buy you anything. Making a function call

s = (char *) skip_space(s, 1);


isn't really simpler than writing

while (isspace(*s)) ++s;


directly. And the latter form saves you the headache figuring out what that 1 as second parameter means. As a bonus, it saves a branch and avoids the const trouble. If you really want a dedicated function, provide skip_space_forward and skip_space_backward instead of introducing the second parameter.

# Make auxiliary functions static

Those auxiliary functions that you determine are in fact useful and should be kept, should still be private to your implementation and not pollute the global name-space. Therefore, you should declare them static. As a nice bonus, this might also make your code run faster (for free).

# Put the standard library to good use

The <string.h> standard library header provides highly optimized functions for dealing with memory. Use them. In particular, memmove and strlen will come in handy.

# Be const-correct

As you have already realized yourself, the adding and removing of const has become a total mess. You should only add const where you can, not at all cost. It is far better to have an internal pointer being not const even if you don't need to modify the pointed-to object than it is to repetitively cast const away. Once you start casting, const doesn't buy you anything in terms of code correctness.

If you have a function like skip_space, that takes a pointer to a buffer and returns a pointer into that buffer without modifying the buffer, it is good to keep the buffer const. Unfortunately, when you call skip_space with a non-const pointer, what you get back is always const and you cannot use the pointer to write through it even though you know it would be safe. This can be solved without a cast while still keeping the buffer skip_space operates on const, though: use the returned pointer to compute an index and use that one!

char buffer[] = "the quick brown fox";         // mutable buffer
const char *const p = skip_space(buffer, 1);   // pointer to const
const ptrdiff_t i = p - buffer;                // just an integer
buffer[i] = 'X';                               // perfectly fine now


If you have a decent compiler, it should be able to optimize the additional arithmetic away while still being able to verify the const-correctness of your code.

# Don't over-generalize

NUL terminated character strings are so prevalent throughout C that you can safely assume the convention is here to stay. By spelling out '\0', you make your code actually more readable than by using a constant like TERMINATOR.

If you really want generality, make the caller pass in a pair of pointers. (If you have ever used the C++ <algorithm> standard library, this will be very familiar to you.) Then your function also works with arrays that are not terminated at all. You can provide a convenience function that only accepts a single pointer (that has to point to a terminated array in this case, of course) and uses rawmemchr (if you have it) or strlen to find the end. Then it calls the generic two-argument version.

Actually, a more useful generalization would probably be to accept a function pointer to use in place of isspace. Such indirect calls can have a performance penalty, though.

# Consider pointer arithmetic

Instead of &p[n - i] you can just write p + n - i. I find this much more readable.

# Modify pointers with care

Your trim_white function trims space from the beginning by simply adding an offset to the pointer. While this is super-fast, there is a big downside. If I call your function with a pointer that I obtained through malloc, I still have to keep the original pointer along with the pointer to the trimmed buffer. I need the former to pass it to free when I no longer need the string. I'm sure I will confuse them all the time.

Instead of advancing the start pointer, you could actually move the bytes of the string to the beginning. While this might seem costly at first, note that it doesn't actually increase the asymptotic complexity of your function. You already do at least one linear traversal (via strlen) and in the worst case (string is all-white-space) a second one finding the cutoff points. So adding a third one is not that bad. Actually, since you only need to move those bytes that are not white-space, the moving cost balances with the testing cost so you traverse the string exactly twice (regardless of its data) and the worst-case cost remains the same.

strlen             |---------------------------------------------------->|
skip_forward       |------------------->                                 |
skip_backward      |                                           <---------|
data               |␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣The␣quick␣brown␣fox␣...␣␣␣␣␣␣␣␣␣␣|
memmove            |                    <----------------------          |


Be sure to move the bytes with memmove rather than memcpy so it will be valid to pass the same buffer as input and output. (memcpy may only be used if the buffers are guaranteed to not overlap.)

# Let the caller decide how to allocate memory

A white-space trimming / normalization function can be useful in a lot of contexts even when dynamic memory is not available or desirable. Allocating memory should not be one of your function's concerns. Instead, have the caller pass in a buffer where you will place the result into.

Since trimming / normalizing white-space can reduce but never enlarge the length of a string, a caller can easily determine the needed size of the buffer upfront by passing a buffer as long as the input string. They can even pass the same pointer twice and trim / normalize the string in-place! If the buffer was dynamically allocated and the string contained a lot of white-space, the caller might decide to realloc it afterwards so to give back the now-unused memory. Or maybe they have other smart options available. Again, your function should not be concerned with this. String manipulation already is a full-time job.

If you let the caller pass in the source and destination buffer, you don't have to return it any more. Instead, you can return something more interesting. For example, a pointer to the end of the result string. This could be useful if the caller wants to know the length of the new string. Having the pointer to its end, they can do so with a single subtraction rather than having to loop over the bytes (aka call strlen).

# Recognize state machines

Some algorithms can be written in a more compact way if you think of them as state machines. Normalizing white-space is such an algorithm. It iterates over all characters of the input from left-to right and performs an action on each character depending on its internal state. There are three states.

• PRE where all we have seen so far is white-space. As long as we continue to see white-space, we do nothing. Once we see a character that is not white-space, we copy it to the output buffer and switch to the
• INTRA state where the last character we have seen was not white-space. If we see another white-space character, we copy it to the output buffer and remain in the INTRA state. If we encounter a white-space character, we transition into the
• INTER state where the last character we have seen was white-space but we have also already seen non-white-space characters before. If we see a white-space character in this state, we do nothing. If we see a non-white-space character, we first append a single blank to the output buffer and then the current character; then we go back into the INTRA state.

Note that the only time we actually do something when we see white-space is in the INTRA state.

Not only is implementing the algorithm as such a state machine simpler and more elegant, it will also be more performant because we only iterate over each (the input and the output) buffer exactly once from left to right. Caching hardware loves such memory access and will honor it with amazing speed.

# Put it all together

Combining all of the advice from this review, I'd suggest you'll end up with an implementation like this.

For trimming…

char *
trim_space(const char *const src, char *const dst)
{
size_t first = 0;
size_t last = strlen(src);
size_t length = last - first;;
if (length > 0)
{
while (isspace(src[first]))
++first;
while ((last > first) && isspace(src[last - 1]))
--last;
length = last - first;
memmove(dst, src + first, length);
}
dst[length] = '\0';
return dst + length;
}


…and for normalizing white-space.

char *
normalize_space(const char * src, char * dst)
{
typedef enum { states_pre, states_intra, states_inter } states;
states state = states_pre;
int c;
while ((c = *src++) != '\0')
{
if (isspace(c))
{
if (state == states_intra)
state = states_inter;
continue;
}
switch (state)
{
case states_pre:
*dst++ = c;
state = states_intra;
break;
case states_intra:
*dst++ = c;
break;
case states_inter:
*dst++ = ' ';
*dst++ = c;
state = states_intra;
break;
}
}
*dst = '\0';
return dst;
}


Simplifying the print function

printf can interpolate strings into a template, and it is powerful enought that your print function may be written as a single call to it:

void print(const char *s)
{
printf("|%sN|\n", s);
}


It removes unnecessary statements and makes the code clearer.

the posted code does not cleanly compile. Therefore, it should not be posted on codereview. When compiling, always enable all the warnings. then fix those warnings.

(for gcc, at a minimum use: -Wall -Wextra -pedantic (I also use: -Wconversion -std=c99) )

It seems that not all the header files in the posted code are needed; however, I left them in this answer.

here is one way to compress out leading spaces, trailing spaces and reduce multiple internal spaces to 1 space and do the work in-place

It also removes the calls to malloc() and free()

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>

static const char TERMINATOR = '\0';
static const char SPACE = ' ';

char *compact_with_mem(char *str)
{
char* source = str;
char* dest = str;

// remove leading spaces, in place
for( ; SPACE == *source; source++ );

// remove internal spaces, in place
int inSpace = 0;
for( ; *source; source++ )
{
if( SPACE == *source && inSpace )
{
;
}
else
{
*dest = *source;
dest++;
}

inSpace = ( SPACE == *source )? 1 : 0;
}

for( ; SPACE == *(dest-1); dest-- );
*dest = TERMINATOR;

//printf( "result str: |%s|\n", str );
return str;
}

void print(const char *s)
{
const size_t len = strlen(s);
printf("|%s", s);
if (*(s + len) == TERMINATOR) { // redundant but just for testing
putchar('N');
}
puts("|");
}

void test(char *s, char *cmp_str)
{
size_t blen = strlen(s);
printf("Base string: |%s|\n", s);

char *ret = compact_with_mem(s);
size_t len = strlen(ret);
printf("Length before compaction: %lu\nLength after compaction: %lu\n", blen, len);

print(ret);
puts("");
assert(strcmp(ret, cmp_str) == 0);
}

int main( void )
{
char s1[] = "   hello!";
char s2[] = "   world.   ";
char s3[] = "lol..";
char s4[] = "";
char s5[] = "               ";
char s6[] = "lmfao  ";
char s7[] = "         x";
char s8[] = "ab   ";
char s9[] = "   i am cthulhu   ";
char s10[] = "  all    your    base are belong    to us      ";
char s11[] = "  random    chars \\29289892 *&@ @)!  !*  # $_ ! & # * ! @! ^ *#^ | {]["; char s12[] = "omfgwhyaretherenospaceshere!"; test(s1, "hello!"); test(s2, "world."); test(s3, "lol.."); test(s4, ""); test(s5, ""); test(s6, "lmfao"); test(s7, "x"); test(s8, "ab"); test(s9, "i am cthulhu"); test(s10, "all your base are belong to us"); test(s11, "random chars \\29289892 *&@ @)! !* #$ _ ! & # * ! @! ^ *#^ | {][");
test(s12, "omfgwhyaretherenospaceshere!");
}


and here is the resulting output

Base string: |   hello!|
Length before compaction: 9
Length after compaction: 6
|hello!N|

Base string: |   world.   |
Length before compaction: 12
Length after compaction: 6
|world.N|

Base string: |lol..|
Length before compaction: 5
Length after compaction: 5
|lol..N|

Base string: ||
Length before compaction: 0
Length after compaction: 0
|N|

Base string: |               |
Length before compaction: 15
Length after compaction: 0
|N|

Base string: |lmfao  |
Length before compaction: 7
Length after compaction: 5
|lmfaoN|

Base string: |         x|
Length before compaction: 10
Length after compaction: 1
|xN|

Base string: |ab   |
Length before compaction: 5
Length after compaction: 2
|abN|

Base string: |   i am cthulhu   |
Length before compaction: 18
Length after compaction: 12
|i am cthulhuN|

Base string: |  all    your    base are belong    to us      |
Length before compaction: 47
Length after compaction: 30
|all your base are belong to usN|

Base string: |  random    chars \29289892 *&@ @)!  !*  # $_ ! & # * ! @! ^ *#^ | {][| Length before compaction: 74 Length after compaction: 64 |random chars \29289892 *&@ @)! !* #$ _ ! & # * ! @! ^ *#^ | {][N|

Base string: |omfgwhyaretherenospaceshere!|
Length before compaction: 28
Length after compaction: 28
|omfgwhyaretherenospaceshere!N|