Writing Your Own String Functions

Part I · Module 8 · Chapter 8.3 · Writing Your Own String Functions

1. Why Write What Already Exists

Chapter 8.4 covers the library versions and you should prefer them — they are correct, tested and often faster than anything you would write.

This chapter exists because the three functions below are the smallest complete exercise of the array-and-pointer relationship there is. Each one is five or six lines. Between them they use the conversion rule from Chapter 7.6, the arithmetic from Chapter 7.8, the parameter adjustment from Chapter 7.7, the qualifier from Chapter 7.11, and the terminator convention from Chapter 8.1 — and none of them works unless you have all five right.

The output of this chapter is not three functions. It is the ability to read any string code without stopping to work out what the pointers are doing.

2. Length

The length of a string is not stored — Chapter 8.1 — so it must be counted by walking to the terminator. Chapter 7.8 §6 said the pointer-walking form belongs where the end is marked rather than counted, and this is precisely that case, so both forms are worth writing.

size_t my_strlen_index(const char *text)
{
    size_t n = 0;
    while (text[n] != '\0') {
        n++;
    }
    return n;
}

size_t my_strlen_walk(const char *text)
{
    const char *p = text;
    while (*p != '\0') {
        p++;
    }
    return (size_t)(p - text);
}

Both return 11 for "calibration".

The two are the same computation written two ways, which Chapter 7.8 §2 established when it showed that a[i] is *(a + i). The index form keeps a counter; the walking form moves a pointer and recovers the count at the end by subtracting two pointers — Chapter 7.8 §5, where the result is a count of elements, here converted to size_t because a length cannot be negative.

Three details of the signature are deliberate and all of them are earned:

const char * — the function only reads, so Chapter 7.11's habit applies, and Chapter 8.2 §5 showed that this parameter type accepts an array, a const char * and an inline literal alike.

No length parameter. Chapter 7.7 required one for arrays in general; strings are the exception precisely because the terminator supplies the extent. That is the whole trade Chapter 8.1 §1 described.

size_t return. A length is a count, which is what size_t is for — Chapter 2.12.

3. Copy

void my_strcpy(char *destination, const char *source)
{
    size_t i = 0;

    while (source[i] != '\0') {
        destination[i] = source[i];
        i++;
    }

    destination[i] = '\0';
}

Two things about that function carry the whole chapter.

The loop stops at the terminator and does not copy it. The condition is source[i] != '\0', so when the terminator is reached the loop exits with it uncopied.

The line after the loop is not optional. destination[i] = '\0'; puts the terminator in. Without it the destination holds the right characters and is not a string — exactly Chapter 8.1 §5's distinction, and the single most common way the terminator goes missing in code people actually write.

Trace it for "hi":

                      i    source[i]   action                    destination so far
before the loop       0    'h'         —                          (unknown)
pass 1                0    'h'         destination[0] = 'h'       h
pass 2                1    'i'         destination[1] = 'i'       hi
test                  2    '\0'        loop ends                  hi
after the loop        2    —           destination[2] = '\0'      hi   <- now a string

Three bytes written for two characters. The asymmetry between the parameters is also worth reading: char *destination says the function will write there, and const char *source says it will not — Chapter 7.11's contract, visible in the signature.

4. Compare

int my_strcmp(const char *a, const char *b)
{
    size_t i = 0;

    while (a[i] != '\0' && a[i] == b[i]) {
        i++;
    }

    return (unsigned char)a[i] - (unsigned char)b[i];
}

The loop advances while both of two things hold: the first string has not ended, and the characters match. Chapter 3.6's short-circuit guarantee matters here — if a[i] is the terminator the loop stops without evaluating b[i], which is what keeps a shorter first string from running past its own end.

When the loop stops, the two characters at i are either different, or one of them is a terminator, or both are. Subtracting them answers all three cases at once.

The return value is where the surprise is

    printf("cmp(abc,abc) %d\n", my_strcmp("abc", "abc"));
    printf("cmp(abc,abd) %d\n", my_strcmp("abc", "abd"));
    printf("cmp(abd,abc) %d\n", my_strcmp("abd", "abc"));
    printf("cmp(ab, abc) %d\n", my_strcmp("ab", "abc"));
    printf("cmp(abc, ab) %d\n", my_strcmp("abc", "ab"));

Predict these five numbers before reading on.

cmp(abc,abc) 0
cmp(abc,abd) -1
cmp(abd,abc) 1
cmp(ab, abc) -99
cmp(abc, ab) 99

The last two are −99 and 99, not −1 and 1.

The reason is arithmetic: the loop stopped where a had its terminator (0) and b had 'c' (99), and 0 - 99 is −99. There was never a promise of −1.

Why the unsigned char cast

That cast is not noise. Chapter 2.8 established that plain char's signedness is implementation-defined — it may behave as signed or unsigned, and the standard does not say which.

For bytes above 127 that matters. On an implementation where char is signed, such a byte is a negative number, and subtracting two of them can produce a sign that disagrees with the ordering an implementation with unsigned char would give. The same program would sort the same data differently on two machines.

The standard specifies that string comparison behaves as though the characters were unsigned char, and casting makes this implementation match that. For plain ASCII text you would never notice; the cast costs nothing and removes a platform dependency, which is the right trade.

5. The Three Contracts

Chapter 5.9 established that a contract is larger than a signature. Here are all three, in that format:

size_t my_strlen(const char *text);
  needs:      a pointer to a null-terminated string
  gives back: the number of characters before the terminator
  assumes:    a terminator exists within the storage
  does not:   modify anything, or check that the terminator is there

void my_strcpy(char *destination, const char *source);
  needs:      a writable destination and a null-terminated source
  gives back: nothing
  promises:   destination holds a copy of source, terminator included
  assumes:    destination has at least my_strlen(source) + 1 bytes
  does not:   check the destination's size — it cannot

int my_strcmp(const char *a, const char *b);
  needs:      two null-terminated strings
  gives back: negative, zero or positive — the SIGN only
  assumes:    both have terminators
  does not:   modify anything; the magnitude is not part of the contract

Every one of them has the same unverifiable assumption: a terminator exists. That is the cost Chapter 8.1 §1 described when C chose to mark the end rather than carry a count, and it is why Chapter 8.5 exists.

6. Putting Them Together

#include <stdio.h>
#include <stddef.h>

size_t my_strlen(const char *text)
{
    size_t n = 0;
    while (text[n] != '\0') {
        n++;
    }
    return n;
}

void my_strcpy(char *destination, const char *source)
{
    size_t i = 0;
    while (source[i] != '\0') {
        destination[i] = source[i];
        i++;
    }
    destination[i] = '\0';
}

int my_strcmp(const char *a, const char *b)
{
    size_t i = 0;
    while (a[i] != '\0' && a[i] == b[i]) {
        i++;
    }
    return (unsigned char)a[i] - (unsigned char)b[i];
}

int main(void)
{
    const char *source = "calibration";

    printf("length        %zu\n", my_strlen(source));

    char buffer[32];
    my_strcpy(buffer, source);
    printf("copied        [%s]\n", buffer);
    printf("same ?        %d\n", my_strcmp(buffer, source) == 0);

    my_strcpy(buffer, "short");
    printf("recopied      [%s]  length %zu\n", buffer, my_strlen(buffer));

    return 0;
}

Output:

length        11
copied        [calibration]
same ?        1
recopied      [short]  length 5

The last two lines are worth a sentence. buffer is 32 bytes and held "calibration"; copying "short" into it wrote six bytes and left the rest of the old text sitting in the array after the new terminator. my_strlen reports 5, because the string ends where the terminator is — Chapter 8.1 §6's point that the array and the string are different extents, now produced by ordinary code rather than a contrived literal.

7. What You Should Be Able to Say Now

1. These three functions exercise every rule Module 7 established, which is why writing them is worth an hour.
2. Length is counted by walking to the terminator — there is nothing stored to read.
3. The index form and the pointer-walking form are the same computation; the walking form recovers the count by subtracting two pointers.
4. String functions take no length parameter, because the terminator supplies the extent.
5. Copy must write the terminator itself — the loop stops before it.
6. my_strcpy has a precondition it cannot check: the destination must be large enough.
7. Comparison advances while both strings match and the first has not ended — Chapter 3.6's short-circuit.
8. The return value is a sign, not a value — cmp("ab", "abc") is −99.
9. Compare against zero, never against 1 or −1.
10. The unsigned char cast removes a platform dependency, because plain char's signedness is implementation-defined.

8. Exercises

Exercise 1 — predict the lengths. Give what my_strlen returns for each.

my_strlen("")        my_strlen("a")       my_strlen("a\tb")
my_strlen("ab\0cd")  my_strlen("\\")

The fourth is the interesting one — explain it using Chapter 8.1 §6.

Exercise 2 — trace the copy. Write the table, in §3's style, for my_strcpy(dest, "ok"). Give the number of bytes written and the final contents.

Exercise 3 — predict the comparisons. Give the sign of each, and say which ones you can predict the exact value of.

my_strcmp("apple", "apple")
my_strcmp("apple", "apply")
my_strcmp("apple", "app")
my_strcmp("", "a")
my_strcmp("A", "a")

Exercise 4 — fix the comparison. This is meant to detect equality and has two faults. Name both and repair them.

if (my_strcmp(name, "reset") == 1) {
    printf("match\n");
}

Exercise 5 — find the missing terminator. This copy produces a destination that is not a string. Say which line is missing, what the symptom would be, and which chapter classifies the behaviour of printing the result.

void broken_copy(char *destination, const char *source)
{
    size_t i = 0;
    while (source[i] != '\0') {
        destination[i] = source[i];
        i++;
    }
}

Exercise 6 — convert the form. Rewrite my_strcpy in the pointer-walking style, using *d++ = *s++, and say which chapter's rule makes that expression work. Then say which version you would ship and why.

Exercise 7 — write a fourth. Implement const char *my_strchr(const char *text, char wanted) returning a pointer to the first occurrence or NULL. State its contract in §5's format, and say what it should return when wanted is '\0'.

Exercise 8 — justify the cast. Explain, in terms of Chapter 2.8, why my_strcmp casts to unsigned char, what could differ between two platforms without it, and why plain ASCII text would never reveal the problem.

9. Summary

• Writing these three turns Module 7's rules into fluency; the library's versions are what you ship.
• Length is walked, not read — nothing stores it.
• Index and pointer-walking forms are the same computation; the latter ends with a pointer subtraction.
• String functions need no length parameter — that is the terminator's job.
• Copy must write the terminator after the loop.
• Copy's destination-size precondition cannot be checked, by this function or by the library's.
• Comparison relies on short-circuit evaluation to avoid running past a shorter string.
• The result is a sign — cmp("ab", "abc") is −99. Compare against zero.
• The unsigned char cast matches the standard's specification and removes a platform dependency.

The library versions of these three functions exist, have the same contracts, and are what production code calls. There are also a dozen more alongside them — joining strings, searching for a character or a substring, and a family of length-limited variants whose names suggest safety and whose behaviour is more subtle than the names imply. The next chapter covers the ones worth knowing, with the preconditions of each stated precisely, because every one of them assumes something the compiler will not check.