2
\$\begingroup\$

In the process of writing a compiler, I wrote this dynamic string library to help with keeping track of heap allocated strings and to have an easy way to format them.

Note:
The macros ALLOC(), CALLOC(), and REALLOC() used in the implementation are equivalent to the C stdlib functions malloc(), calloc(), and realloc(). They expand to the memory allocator used in the compiler that also does NULL checking, that is why the implementation doesn't check for NULL after allocating. They are declared in the header memory.h.

Interface (Strings.h):

#ifndef STRINGS_H
#define STRINGS_H

#include <stddef.h> // size_t
#include <stdbool.h>

// NOTES
// =====
// The 'String' type is equivalent to a C string ('char *'), and therefore can
// be used with the regular C string functions.
// In this API, the String type is used when a string created by this library is expected,
// and 'char *' is used when both types can be used.
// 'const char *' is used when ONLY C strings are expected.

typedef char *String;

/***
 * Create a new empty string 'length' long
 * NOTE: strings returned by stringNew() can ONLY be freed with stringFree()
 *
 * @param length The length of the new string.
 * @return A pointer to a new heap allocated string.
 ***/
String stringNew(size_t length);

/***
 * Free a string created by stringNew() or stringCopy();
 *
 * @param s A string created with stringNew() or stringCopy().
 ***/
void stringFree(String s);

/***
 * Check if a string was created by stringNew(), stringCopy(), or stringDuplicate().
 *
 * @param s A string.
 * @return true if valid, false if not.
 ***/
bool stringIsValid(String s);

/***
 * Return the length of a string allocated with stringNew() or stringCopy().
 * 
 * @param s A string allocated by stringNew() or stringCopy().
 * @return The length of the string.
 ***/
size_t stringLength(String s);

/***
 * Resize a string allocated by stringNew() or stringCopy().
 * NOTE: if 'newSize' is smaller than the current length, data will be lost!
 *
 * @param s A string allocated by stringNew() or stringCopy().
 * @param newLength The new length. can't be 0.
 * @return A new string of length 'newLength'.
 ***/
String stringResize(String s, size_t newLength);

/***
 * Copy 'length' characters from 's' into a new string.
 *
 * @param s A string to copy.
 * @param length How much characters to copy.
 * @return A new copy of 'length' characters of 's'.
 ***/
String stringNCopy(const char *s, int length);

/***
 * Copy a string into a new string.
 *
 * @param s A string to copy.
 * @return A new copy of the string.
 ***/
String stringCopy(const char *s);

/***
 * Duplicate a string allocated with stringNew() or stringCopy().
 *
 * @param s A string allocated by stringNew() or stringCopy().
 * @return A new copy of the string.
 ***/
String stringDuplicate(String s);

/***
 * Check if 2 strings are equal.
 * The strings can be regular C strings as well.
 *
 * @param s1 A string
 * @param s2 Another string
 * @return true if equal, false if not
 ***/
bool stringEqual(char *s1, char *s2);

/***
 * Format a string (using printf-like format specifiers) and return it.
 * 
 * @param format The format string.
 * @return A new String containing the formatted format string.
 ***/
String stringFormat(const char *format, ...);

/***
 * Append format to dest (printf-like formatting supported)
 * NOTE: the string might be reallocated.
 *
 * @param dest the destination string.
 * @param format the string to append (printf-like format specifiers supported).
 ***/
void stringAppend(String *dest, const char *format, ...);

#endif // STRINGS_H

Implementation (Strings.c):

#include <stdio.h>
#include <string.h> // memcpy(), memset()
#include <stdarg.h>
#include <assert.h>
#include <stdbool.h>
#include "memory.h"
#include "Strings.h"

// C = capacity
// L = length
// M = magic number
// D = data
// ________________________
// |   |   |   |   |   |   | ...
// | C | L | M | D | D | D | ...
// |___|___|___|___|___|___| ...
//

enum slots {
    CAPACITY   = 0,
    LENGTH     = 1,
    MAGIC      = 2,
    SLOT_COUNT = 3
};

static inline size_t *from_str(char *s) {
    return ((size_t *)s) - SLOT_COUNT;
}

static inline char *to_str(size_t *ptr) {
    return (char *)(ptr + SLOT_COUNT);
}

String stringNew(size_t capacity) {
    assert(capacity > 0);
    size_t *ptr = CALLOC(sizeof(size_t) * SLOT_COUNT + sizeof(char) * (capacity + 1));
    ptr[CAPACITY] = capacity + 1; // capacity
    ptr[LENGTH] = 0; // length
    ptr[MAGIC] = 0xDEADC0DE; // magic
    return to_str(ptr);
}

void stringFree(String s) {
    assert(stringIsValid(s));
    // Remove the magic number in case the string is used again accidentally.
    from_str(s)[MAGIC] = 0;
    FREE(from_str(s));
}

bool stringIsValid(String s) {
    return from_str(s)[MAGIC] == 0xDEADC0DE;
}

size_t stringLength(String s) {
    return from_str(s)[LENGTH];
}

String stringResize(String s, size_t newCapacity) {
    assert(newCapacity > 0);
    size_t *ptr = from_str(s);
    size_t oldCap = ptr[CAPACITY];
    ptr = REALLOC(ptr, newCapacity);
    memset(to_str(ptr) + oldCap, 0, labs(((ssize_t)oldCap) - ((ssize_t)newCapacity)));
    ptr[CAPACITY] = newCapacity;
    return to_str(ptr);
}

String stringNCopy(const char *s, int length) {
    String str = stringNew(length);
    memcpy(str, s, length);
    from_str(str)[LENGTH] = length;
    return str;
}

String stringCopy(const char *s) {
    return stringNCopy(s, strlen(s));
}

String stringDuplicate(String s) {
    assert(stringIsValid(s));
    return stringNCopy((const char *)s, stringLength(s));
}

bool stringEqual(char *s1, char *s2) {
    size_t length1, length2;
    if(stringIsValid(s1)) {
        length1 = stringLength(s1);
    } else {
        length1 = strlen(s1);
    }
    if(stringIsValid(s2)) {
        length2 = stringLength(s2);
    } else {
        length2 = strlen(s2);
    }

    if(length1 != length2) {
        return false;
    }
    return memcmp(s1, s2, length1) == 0;
}

static String vformat(const char *format, va_list ap) {
    va_list copy;
    va_copy(copy, ap);
    // Get the total length of the formatted string.
    // see man 3 printf.
    int needed_length = vsnprintf(NULL, 0, format, copy);
    va_end(copy);

    String s = stringNew(needed_length + 1);
    vsnprintf(s, needed_length + 1, format, ap);
    from_str(s)[LENGTH] = needed_length;
    return s;
}

String stringFormat(const char *format, ...) {
    va_list ap;

    va_start(ap, format);
    String s = vformat(format, ap);
    va_end(ap);
    return s;
}

void stringAppend(String *dest, const char *format, ...) {
    assert(stringIsValid(*dest));
    va_list ap;

    va_start(ap, format);
    String buffer = vformat(format, ap);
    va_end(ap);

    if((size_t)(stringLength(buffer) + 1) > from_str(*dest)[CAPACITY]) {
        *dest = stringResize(*dest, stringLength(*dest) + stringLength(buffer) + 1);
    }
    strncat(*dest, buffer, stringLength(buffer));
    // *dest is zeroed by stringNew() & stringResize(), so no need to terminate the string.
    from_str(*dest)[LENGTH] += stringLength(buffer);
    stringFree(buffer);
}
```
\$\endgroup\$
1
  • \$\begingroup\$ The code looks reasonable overall, but I think you lack good unit tests \$\endgroup\$
    – frozenca
    Jul 25, 2022 at 12:20

1 Answer 1

3
\$\begingroup\$

A word of warning. Writing yet another string library is a goo programming exercise, but if your goal is to write a compiler, concentrate on the compilation tasks (grammar, optimization , code generation..), and don't get sidetracked. Use c++; std::string offers everything you need out of the box.

That said,

  • typedef char *String; means that the library accepts any char * as String. This is a ticket to disaster. Pass an unaligned char * to, say, stringResize, and enjoy an unaligned access exception on any arch but x86. Consider declaring

      typedef struct {
          size_t capacity;
          // etc
          ....
      } String;
    

    and let your library distinguish String * from char *.

  • MAGIC is only used in stringIsValid, and most uses of stringIsValid are hidden behind assert. Recall that in the production code assert compiles to nothing, so it becomes a dead code indeed.

    The only non-assert use is in stringEqual, and it is much more dangerous. If the magic field is corrupted, God knows what length1 and/or lenght2 evaluate to.

  • Using strncat in stringAppend is suboptimal. You already know where the buffer shall be copied to; there is no need to recompute this position.

\$\endgroup\$
1
  • \$\begingroup\$ I don't understand why it is dangerous using stringIsValid in stringEqual. all Strings are null terminated unless manually changed, so strlen will give the correct size. \$\endgroup\$ Jul 26, 2022 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.