tags:

views:

260

answers:

6
typedef struct dict_pair {
  void *key;
  void *value;
  struct dict_pair *head;
  struct dict_pair *tail;
} dict;

dict* NewDictionary(void) {
  dict *dictionary = malloc(sizeof(dict_pair));
  dictionary->head = null;
  dictionary->tail = null;
}

int main(void) {
  dict *dictionary = NewDictionary();
}

I had initially planned to set the structs as null but the compiler does not allow it. How can I check if a struct is assigned or not?

Also, can I refer recursively declare the same struct inside the struct?

A: 

typedef struct dict_pair {
  void *key;
  void *value;
  struct dict_pair *head;
  struct dict_pair *tail;
} dict;

dict* NewDictionary(void) {
  dict *dictionary = malloc(sizeof(dict_pair));
  if (dictionary) {
      dictionary->head = NULL;
      dictionary->tail = NULL;
  }
  return dictionary;
}

int main(void) {
  dict *dictionary = NewDictionary();
  if (!dictionary) {
        printf("oom!\n");
        exit(1);
  }
  printf("dictionary is ok!\n");
  return 0;
}

Jon
-1 for missing `null` vs. `NULL`
Chris Lutz
You are absolutely right. Fixed it.
Jon
you didnt even test the code did you.
nubela
i said this because you can't sizeof(dict_pair), i had to change it to sizeof(dict) or sizeof(struct dict_pair)
nubela
A: 

You can set them as NULL, but not as null. C is case-sensitive, and the NULL constant is all caps.

And to answer your second question, yes, struct definitions can be recursive in a sense. The internal reference has to be a pointer to the struct, instead of a straight definition of the struct. If the latter was allowed, you would end up with an infinitely recursing struct definition, which would be a bad thing. See Chris Lutz's answer for more details.

Ed Carrel
A: 

@Chris is right -

#include <stddef.h> 

dictionary->head = NULL;
dictionary->tail = NULL;
Avi
+1  A: 

You may want to consider calloc rather than malloc.

calloc fills the memory it allocates with 0s, so you'll have your head and tail as NULL w/o explicit assignment.

Arkadiy
wow, interesting, THANKS!
nubela
+1 for John Wayne here.
Chris Lutz
This is wrong; do not do this.
Cirno de Bergerac
@sgm - How is it wrong?
Chris Lutz
calloc() set memory to all-bits-zero, such that if you looked at the RAM with a magnifying glass you would see "00000000…". This is fine for integers, but does not at all mean you'll get floating-point zeros or null pointers.
Cirno de Bergerac
@sgm - That's tricky. I know `void *p = 0;` _is_ identical to a null pointer by the standard, but I don't know about `calloc()` because it says "all-bits zero" rather than just "assigned to zero."
Chris Lutz
@Chris: casting `0` to `void*` might involve conversions, so it's indeed true that a pointer with bit representation `0` (as returned by `calloc()`) isn't guaranteed to be a null pointer
Christoph
If you dig through some museums, you may find a machine where 0 address is not same as NULL, but I doubt even that. Same applies to floating point numbers, even more so, as there is a standard for those. For all practical purposes, calloc does what it's expected to do.
Arkadiy
+7  A: 

C doesn't have null, it has NULL. So try this:

dict* NewDictionary(void) {
  return calloc(sizeof(dict)); 
}

This fixes a few problems:

  1. You were leaving value and key uninitialized, so they could hold random garbage. Using calloc() will initialize everything to 0, which in pointer context is NULL. It won't even take that much more processing time.
  2. You weren't returning anything. This is undefined behavior. If you function ends without a return statement, it's only by sheer luck that anything will be returned.
  3. You were using dict_pair instead of struct dict_pair. In C++, struct names are in the regular type namespace, i.e. t x = { 0 }; is valid C++, but in C you'd need to say struct t x = { 0 };.
  4. You weren't checking the return value of malloc() (now calloc() but same rules apply). If there isn't enough memory, calloc() returns NULL. I'd hate to dereference a NULL pointer on accident. We don't have to check the return value here because I've done away with all the intermediate steps - calloc() is enough for us.

Note that calloc() is slightly less portable. Even though the standard does require that void *p = 0 sets the pointer to a null pointer, it doesn't require that the null pointer be "all bits set to zero", which is what calloc() technically does. If you don't want to use calloc() for this reason, here's a version that does the same thing with malloc():

dict* NewDictionary(void) {
  dict *dictionary = malloc(sizeof(dict)); 
  if(dictionary) {
    dictionary->head  = NULL;
    dictionary->tail  = NULL;
    dictionary->value = NULL;
    dictionary->key   = NULL;
  }
  return dictionary;
}

Or:

dict* NewDictionary(void) {
  dict *dictionary = malloc(sizeof(dict)); 
  if(dictionary == NULL) return NULL;
  dictionary->head  = NULL;
  dictionary->tail  = NULL;
  dictionary->value = NULL;
  dictionary->key   = NULL;
  return dictionary;
}

See how much nicer the calloc() version is?

As to your second question:

Also, can I refer recursively declare the same struct inside the struct?

No, you can't do this:

struct t {
  struct t x;
}

But you can do this (which is what you're doing, and what you want):

struct t {
  struct t *x;
}

You can have a pointer to a struct inside the struct itself, but you can't have the actual struct inside the struct itself. What you're doing is perfectly legal, because you're using pointers.

Chris Lutz
The `calloc` version might be nicer, but it's technically not portable. It sets the underlying representation of the pointers to all-bits-zero, but that's *not* necessarily the same thing as `NULL` (even though the value `0` when converted to a pointer compares equal to the null pointer). (Not that I'm aware of any place where all-bits-zero pointers aren't equal to `NULL`, but something to bear in mind).
caf
@caf - I was just made aware of that point. I've checked and, though I thought the wording was just "calloc sets stuff to zero" it does specify "all bits zero" which means that, yes, I do believe this super-edge-case is valid.
Chris Lutz
Yes, it's worded that way because it's not reasonable for implementation to know how you're going to treat the returned memory. The same applies to using `calloc` to allocate floating point values - all-bits-zero is not necessarily `0.0f`
caf
+1  A: 

I'd use a statically allocated variable for initialization:

dict* NewDictionary(void) {
  static dict null_dict; // no initializer, so zero by default
  dict *dictionary = malloc(sizeof *dictionary);
  *dictionary = null_dict;
  return dictionary;
}

This guarantees that member are correctly zeroed, regardless whether they're pointers, floating point or integer types.

Christoph
+1 for extreme cleverness.
Chris Lutz