4

I thought I understood this stuff, but I'm stumped here.

Given a struct declared as:

typedef struct _Thing {
  uint32_t type;
  struct _Thing *children;
  unsigned long childCount;
  char *description;

  union {
    uint32_t thirtyTwoBitValue;
    char *nameValue;
  } data;

} Thing;

I have a method that re allocates an array to accommodate adding a new Thing object. It looks like this:

void AddTopLevelThing(Thing *thing)
{
  Thing *oldThings = things;
  things = malloc(sizeof(Thing) * thingCount +1);

  // Add any existing things to the new array
  for (int i = 0; i < thingCount; ++i) {
    things[i] = oldThings[i];
  }

  // Add the newest thing to the new array
  things[thingCount] = *thing;

  // Increment the thing count
  thingCount++;
}

Note: things and thingCount are globals. Don't freak. ;-) Oh, and I also realize this is leaking. One problem at a time...

In order to create my Thing objects, I've created an initializer function. It looks like this:

Thing* CreateThingWithDescription(char *description)
{
  Thing *thing = malloc(sizeof(Thing));
  if (thing == NULL) {
    printf("Bad thing!, Bad!\n");
    return NULL;
  }

  // Initialize everything in the structure to 0
  memset(thing, 0, sizeof(Thing));

  thing->children = NULL;
  thing->description = strdup(description);

  return thing;
}

To complicate things (no pun intended), a Thing object has an array of children that gets reallocated (grown) when new objects are added to it. It looks like this:

void AddChildThingToThing(Thing *parent, Thing *child)
{
  Thing *oldChildren = parent->children;
  parent->children = malloc(sizeof(Thing) * parent->childCount + 1);
  if (parent->children == NULL) {
    printf("Couldn't allocate space for thing children.\n");
    parent->children = oldChildren;
    return;
  }

  // Add any existing child things to the new array
  for (int i = 0; i < parent->childCount; ++i) {
    parent->children[i] = oldChildren[i];
  }

  // Add the newest child thing to the new array
  parent->children[parent->childCount] = *child;  

  // Increment the child count
  parent->childCount = parent->childCount + 1;
}

Anyhow, I'm having a tough time figuring out why when I'm finished creating my structures and adding child structures that they are often zeroed out even though I validated their creation (in the debugger) when they were created. When the code in my main finishes running, I should have a tree structure, but instead it's just a mangled mess of values that I don't recognize or understand--which is why I believe things are getting overwritten.

Anyhow, I'm hoping I'm just overlooking something simple.

Here is my main if you want to see how I build my object hierarchy:

int main(int argc, const char * argv[])
{
  things = NULL;
  thingCount = 0;

  Thing *thing = CreateThingWithDescription("This is thing 1");
  SetThingName(thing, "Willy Johnson");
  AddTopLevelThing(thing);
  Thing *child = CreateThingWithDescription("This is child thing 1");
  SetThingName(child, "Willy's Son");
  AddChildThingToThing(thing, child);
  child = CreateThingWithDescription("This is child thing 2");
  SetThingName(child, "Willy's Daughter");
  AddChildThingToThing(thing, child);

  thing = CreateThingWithDescription("This is thing 2");
  SetThingValue(thing, 700);
  AddTopLevelThing(thing);
  child = CreateThingWithDescription("This is child thing 3");
  SetThingValue(child, 1024);
  AddChildThingToThing(thing, child);

  for (int i = 0; i < thingCount; ++i) {
    PrintThing(&things[i]);
  }
  return 0;
}

Note: this is just a demo project to figure out what's going on.

3
  • 1
    Identifiers starting with two underscores, or with an underscore followed by an uppercase letter, are reserved to the implementation; you should not define them in your own code (see _Thing). In fact, there's no particular reason not to use the same identifier for a struct tag and typedef; you can just write typedef struct Thing { ... } Thing; -- or, my own preference, omit the typedef and refer to the type by its proper name, struct Thing. Commented Jun 6, 2013 at 18:03
  • Nice Keith. So what's the philosophy there? Is it just for greater readability that you'd remove the typedef and just always declare struct Thing instead? Commented Jun 6, 2013 at 19:28
  • 1
    IMHO struct Thing already has a perfectly good name; little is gained by giving it another one. On the other hand, plenty of smart people disagree with me on this point, and think that it's worthwhile to have a name that's a single identifier. But even then, using distinct identifiers for the tag and the typedef is generally unnecessary. Or at least use a consistent convention (foo_t and struct foo_s, or whatever.) (Note that C++ cuts this particular Gordian knot by letting you define a type struct Thing and then refer to it as Thing without the need for a typedef.) Commented Jun 6, 2013 at 19:37

1 Answer 1

6

You need to allocate one struct more, not one byte more in your AddTopLevelThing function:

things = malloc(sizeof(Thing) * (thingCount+1));

Also, you do not free the old memory block after reallocating. And it's better to use realloc ('realloc' cares for copying old data and freeing old memory; it also can sometimes to perform reallocation 'in place' which is much more efficient):

void AddTopLevelThing(Thing *thing) {
    thingCount++;
    things = realloc(things, sizeof(Thing) * thingCount);
    things[thingCount-1] = *thing;
}
Sign up to request clarification or add additional context in comments.

4 Comments

Good catch, same problem here: malloc(sizeof(Thing) * parent->childCount + 1).
Also for the record, when doing this type of array expansion, the most efficient approach is to double the size of the array rather than adding one. You store maxThings in addition to thingCount and resize using maxThings *= 2; realloc(things, sizeof(Thing) * maxThings); things[++thingCount] = *thing;
@Chris good advice. I'd also add a switch to linear growth after some reasonable maxThings value, e.g. if (maxThings < 4096) maxThings *= 2; else maxThings += 4096; realloc(...);.
When I had implemented realloc (which I did first) it seemed like it wasn't copying everything over. Character strings would be empty after the realloc so I tried this other approach instead. Apparently the problem there was the same problem I am having here. Your answer was what I was looking for--something simple/stupid that I am missing. Thanks!

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.