Creating a struct on the heap?

Question

I've been instructed to write a model strdup by creating a String struct on the heap the holds a copy of the source. I think I have successfully coded the strdup, but I'm not sure if I've created a Struct on the heap...

typedef 
struct String {
    int length;
    int capacity;
    unsigned check;
    char ptr[0];
} String;

char* modelstrdup(char* src){
    int capacity =0, length=0, i = 0 ;
    char *string;
    while ( src[length] != '\0'){
        length++;
    }
    capacity = length;
    string = malloc(sizeof(String) + capacity + 1);
    while ( i < length ){
        string[i] = src[i];
        i++;
    }
    string[i+1] = '\0';

    return string;
}   

Solution 1

Yes, you've created a struct on the heap. You haven't populated it correctly, and you are going to face problems deleting it - I'm not sure whether the homework covered that or not. As it stands, you're more likely to get memory corruption or, if you're lucky, a memory leak than to release one of these strings.

Code that works with standard C89 and C99

Your code, somewhat fixed up...

typedef 
struct String {
    int length;
    int capacity;
    char *ptr;
} String;

char* modelstrdup(char* src){
    int length = strlen(src);
    char *space = malloc(sizeof(String) + length + 1);
    //String *string = space;  // Original code - compilers are not keen on it
    String *string = (String *)space;
    assert(space != 0);
    string->ptr = space + sizeof(String);  // or sizeof(*string)
    string->length = length;
    string->capacity = length + 1;
    strcpy(string->ptr, src);
    return string->ptr;
}

This code will work in C89 as well as C99 (except for the C99/C++ comments). You can probably optimize it to work with the 'struct hack' (saves a pointer in the structure - but only if you have a C99 compiler). The assert is sub-optimal error handling. The code doesn't defend itself against a null pointer for input. In this context, neither the length nor the capacity provides any benefit - there must be other functions in the suite that will be able to make use of that information.

As already intimated, you are going to face problems deleting the string structure when the value handed back is not a pointer to the string. You have some delicate pointer adjustments to make.

---

Code that works with standard C99 only

In C99, section 6.7.2.1 paragraph 16 describes 'flexible array members':

As a special case, the last element of a structure with more than one named member may have an incomplete array type; this is called a flexible array member. With two exceptions, the flexible array member is ignored. First, the size of the structure shall be equal to the offset of the last element of an otherwise identical structure that replaces the flexible array member with an array of unspecified length.¹⁰⁶⁾ Second, when a . (or ->) operator has a left operand that is (a pointer to) a structure with a flexible array member and the right operand names that member, it behaves as if that member were replaced with the longest array (with the same element type) that would not make the structure larger than the object being accessed; the offset of the array shall remain that of the flexible array member, even if this would differ from that of the replacement array. If this array would have no elements, it behaves as if it had one element but the behavior is undefined if any attempt is made to access that element or to generate a pointer one past it.

¹⁰⁶ The length is unspecified to allow for the fact that implementations may give array members different alignments according to their lengths.

Using a 'flexible array member', your code could become:

typedef 
struct String {
    int length;
    int capacity;
    char ptr[];
} String;

char* modelstrdup(char* src){
    int length = strlen(src);
    String *string = malloc(sizeof(String) + length + 1);
    assert(string != 0);
    string->length = length;
    string->capacity = length + 1;
    strcpy(string->ptr, src);
    return string->ptr;
}

This code was accepted as clean by GCC 4.0.1 apart from a declaration for the function (options -Wall -Wextra). The previous code needs a cast on 'String *string = (String *)space;' to tell the compiler I meant what I said; I've now fixed that and left a comment to show the original.

---

Using the 'struct hack'

Before C99, people often used the 'struct hack' to handle this. It is very similar to the code shown in the question, except the dimension of the array is 1, not 0. Standard C does not allow array dimensions of size zero.

typedef struct String {
    size_t length;
    size_t capacity;
    char ptr[1];
} String;

char* modelstrdup(char* src)
{
    size_t length = strlen(src);
    String *string = malloc(sizeof(String) + length + 1);
    assert(string != 0);
    string->length = length;
    string->capacity = length + 1;
    strcpy(string->ptr, src);
    return string->ptr;
}

---

Code that uses a GCC non-standard extension to C89 and C99

The zero-size array notation is accepted by GCC unless you poke it hard - specify the ISO C standard and request pedantic accuracy. This code, therefore, compiles OK unless you get to use gcc -Wall -Wextra -std=c99 -pedantic:

#include <assert.h>
#include <stdlib.h>
#include <string.h>

typedef
struct String {
    int length;
    int capacity;
    char ptr[0];
} String;

char* modelstrdup(char* src){
    int length = strlen(src);
    String *string = malloc(sizeof(String) + length + 1);
    assert(string != 0);
    string->length = length;
    string->capacity = length + 1;
    strcpy(string->ptr, src);
    return string->ptr;
}

However, you should not be being trained in non-standard extensions to the C language before you have a thorough grasp of the basics of standard C. That is simply unfair to you; you can't tell whether what you're being told to do is sensible, but your tutors should not be misguiding you by forcing you to use non-standard stuff. Even if they alerted you to the fact that it is non-standard, it is not fair to you. C is hard enough to learn without learning tricksy stuff that is somewhat compiler specific.

Solution 2

You have allocated some memory on the heap, but you're not using it as if it were your structure. The string variable in your function is of type char *, not of type struct String. I think you're duplicating the functionality of strdup() reasonably enough, but I don't understand the reason for the structure.

Note: You should probably check your call to malloc() for failure, and return appropriately. The man page for strdup() should explains exactly what your function should be doing.

Comments

[Phil Miller]

If by new, you meant the operator in C++, no, it doesn't. It uses the "free store", which might be the same as C's heap, or might be entirely unrelated. Unfortunately, computers are dumb and demand precision.

[Greg Hewgill]

@metashockwave: a->b is exactly the same as (*a).b. It's just shorthand which reads better and doesn't need as many parentheses.

[Jonathan Leffler]

(*ptr).member <===> ptr->member. I saw that lack of understanding in the x-ref'd question. You need to get used to it if you wish to write idiomatic C or C++.

[user133466]

x-ref'd question would be...? sorry, I'm very new to programming. I'm taking intro to C programming for the first time =)

[Jonathan Leffler]

The x-ref'd question would be SO 1622416 (stackoverflow.com/questions/1622416) which you asked earlier.

[user133466]

there an incompatible error at statement String *string = space; types - from 'char *' to 'String *'

[Jonathan Leffler]

Yeah - I noted that in my last addition (without fixing it).

[Admin]

@metashockwave, you are forgetting to initialize check. Also if you watch xref closely capacity should be always the actual capacity -sizeof(struct)-1(in this case == length) as it returns the capacity for non-0 characters. Seriously are you supposed to work that out by yourself when you don't even know ->, or you forgot to mention that you had failed to attend any class until today.

[Jonathan Leffler]

Did you notice that I changed the definition of ptr in the structure? You had 'char ptr[0];' - which is illegal in C; you can't have size zero arrays. I have 'char *ptr;' which is a perfectly good lvalue - and it is why I mentioned that the 'struct hack' saves you a pointer in the structure. When I take the first block of code, as amended, and include <stdlib.h>, <string.h> and <assert.h>, it compiles cleanly under 'gcc -Wall -Wextra'.

[user133466]

yes, I saw the changes made on the pointer. And thank you for your detailed explanation. But my project explicitly states all members of the struct. So "ptr[0]" must stay... I tried to compile what's written in the second code block and that's when I got the lvalue error =( also the "->" notation was never mentioned in class, our professor told us to use "." but for some reason, if I substitute -> with . , the compiler would tell me to switch back to ->

[Jonathan Leffler]

GCC does allow the 'ptr[0]' notation; I had to kick it with '-std=c89 -pedantic' (or '-std=c99 -pedantic') to get it to 'fess up that "ISO C forbids zero-size array 'ptr'". It is a non-standard extension; you should not be learning such at this stage in your education.

[Jonathan Leffler]

@scape: Sorta. The way I view it is: there is a block of memory allocated that is as big as a sizeof(String) plus length + 1. The first bytes of that space will be treated as a String; the remainder will contain a string (null-terminated array of char). The start offset of the remainder is the start address of the structure plus the size of the structure. The expression string->ptr = space + sizeof(String); assigns the pointer to the string storage area to the pointer in the String, so when you subsequently write string->ptr[0], it accesses the first byte of the string.