structs and malloc

[Lars Tackmann]

Hi, i have the following type and struct defined

typedef struct hNode {
unsigned char name[1024];
unsigned long hVal;
struct hNode *next;
} HashNode;

what i want, is to ensure that when doing:

HashNode aNode = malloc(sizeof(HashNode));

i can be sure of the value of "next" in the aNode (eg. later in the
program i want to compare the value of "next" in aNode to see if it has
been linked to another HashNode) --- can i do this in
some easy way or do i need to write my own memory allocator ???.


Thanks.

 

[Alexander Bartolich]

begin followup to Lars Tackmann:

what i want, is to ensure that when doing:

HashNode aNode = malloc(sizeof(HashNode));

^
Something is missing here.

i can be sure of the value of "next" in the aNode

Well, you can use calloc instead of malloc to set all bytes of the
allocated memory to zero. On most platforms that will get you a
null-pointer (and on the one that uses a different representation
you will get a horrible, hard to track runtime error).

[...] can i do this in some easy way or do i need to write my own
memory allocator ???.

Well, you need to do two things:

HashNode* aNode = malloc(sizeof(*aNode));
aNode->next = 0;

If you want to group these two lines into one function, fine with me.

HashNode* new_HashNode(void)
{
HashNode* aNode = malloc(sizeof(*aNode));
aNode->next = 0;
return aNode;
}

 

[nrk]

begin followup to Lars Tackmann:

what i want, is to ensure that when doing:

HashNode aNode = malloc(sizeof(HashNode));

^
Something is missing here.

i can be sure of the value of "next" in the aNode

Well, you can use calloc instead of malloc to set all bytes of the
allocated memory to zero. On most platforms that will get you a
null-pointer (and on the one that uses a different representation
you will get a horrible, hard to track runtime error).

[...] can i do this in some easy way or do i need to write my own
memory allocator ???.

Well, you need to do two things:

HashNode* aNode = malloc(sizeof(*aNode));
aNode->next = 0;

If you want to group these two lines into one function, fine with me.

HashNode* new_HashNode(void)
{
HashNode* aNode = malloc(sizeof(*aNode));
aNode->next = 0;

ITYM:
if ( aNode ) aNode->next = 0;

return aNode;
}

-nrk.

 

[Lars Tackmann]

I think that my example was bad - i need a to be able to allocate a entire
array of hash nodes and be sure that all of the nodes has a sane value
from the start.

eg.

HashNode *hashTable = malloc(sizeof(hashNode) * 100);

Thanks

 

[Tobias Oed]

I think that my example was bad - i need a to be able to allocate a entire
array of hash nodes and be sure that all of the nodes has a sane value
from the start.

eg.

HashNode *hashTable = malloc(sizeof(hashNode) * 100);

I'm confused. If you want an array why do you use a linked list?
Tobias.

 

[Malcolm]

i need a to be able to allocate a entire array of hash nodes and be sure
that all of the nodes has a sane value from the start.

eg.

HashNode *hashTable = malloc(sizeof(hashNode) * 100);

malloc() returns a pointer to memory containing garbage. To help makes bugs
more trackable, some implementations set this to a definite bit-pattern,
whilst others don't.

calloc() returns memory set to all bits zero. It is a false friend. On 99%
of systems a pointer with all bits zero is NULL, but there are a few
implementations where this is not true.

What you need to do is to call malloc(), then iterate over the array. For
instance, to create a linked list.

for(i=0;i<99;i++)
hashTable.next = &hashtable[i+1];
hashTable[99].next = NULL;

 

[Lars Tackmann]

Yep this is what i need - thanks.

i need a to be able to allocate a entire array of hash nodes and be sure
that all of the nodes has a sane value from the start.

eg.

HashNode *hashTable = malloc(sizeof(hashNode) * 100);

malloc() returns a pointer to memory containing garbage. To help makes bugs
more trackable, some implementations set this to a definite bit-pattern,
whilst others don't.

calloc() returns memory set to all bits zero. It is a false friend. On 99%
of systems a pointer with all bits zero is NULL, but there are a few
implementations where this is not true.

What you need to do is to call malloc(), then iterate over the array. For
instance, to create a linked list.

for(i=0;i<99;i++)
hashTable.next = &hashtable[i+1];
hashTable[99].next = NULL;

 

[Lars Tackmann]

Lars Tackmann wrote:

I'm confused. If you want an array why do you use a linked list?
Tobias.

In a hash table you usaly have the problem that more than one items hashes
to the same value -. If this happens you link the ones toghter that have
the same hash value (creating a bucket - that you end up searching linary).

That is why i need an array of items that also can be linked to other items.

 

[The Real OS/2 Guy]

Hi, i have the following type and struct defined

typedef struct hNode {
unsigned char name[1024];
unsigned long hVal;
struct hNode *next;
} HashNode;

what i want, is to ensure that when doing:

HashNode aNode = malloc(sizeof(HashNode));

change to

if (!(aNode = malloc(sizeof(*aNode)) {
/* as malloc returns a pointer to undetermied memory */
/* initialise the struct members to meaningfull values */
/* to prevent unspezified or in worst case undefined behavior */
aNode->name[0] = 0; /* name is empty */
aNode->hVal = 0ul; /* no value */
aNode->next = NULL /* no pointer assigned */
} else {
/* malloc was unable to give enough memory for a new HashNode */
/* do the needed error handling */
}

 

[Toni Uusitalo]

In a hash table you usaly have the problem that more than one items hashes
to the same value -. If this happens you link the ones toghter that have
the same hash value (creating a bucket - that you end up searching linary).

That is why i need an array of items that also can be linked to other items.

You may have misunderstood how hashtable is usually put together:

horisontally it's an array, vertically items (duplicate hash values/keys)
are
usually implemented as linked list.

See my post in thread "Hash Function". It contains a link to snippets
collection
hashtable implementation - you can take some ideas from there I guess.

with respect,
Toni Uusitalo

 

[Toni Uusitalo]

horisontally it's an array, vertically items (duplicate hash values/keys)
are
usually implemented as linked list.

sorry, I'm confused myself: of course I meant vertically it's an array,
horisontally items etc.

with respect,
Toni Uusitalo

 

[Christian Bau]

Hi, i have the following type and struct defined

typedef struct hNode {
unsigned char name[1024];
unsigned long hVal;
struct hNode *next;
} HashNode;

what i want, is to ensure that when doing:

HashNode aNode = malloc(sizeof(HashNode));

change to

if (!(aNode = malloc(sizeof(*aNode)) {

Two closing parentheses missing.

/* as malloc returns a pointer to undetermied memory */
/* initialise the struct members to meaningfull values */
/* to prevent unspezified or in worst case undefined behavior */
aNode->name[0] = 0; /* name is empty */
aNode->hVal = 0ul; /* no value */
aNode->next = NULL /* no pointer assigned */
} else {
/* malloc was unable to give enough memory for a new HashNode */
/* do the needed error handling */
}

You just gave a perfect demonstration why experienced programmers write

if ((aNode = malloc(sizeof(*aNode))) != NULL)

 

[CBFalconer]

I think that my example was bad - i need a to be able to allocate
a entire array of hash nodes and be sure that all of the nodes
has a sane value from the start.

eg.

HashNode *hashTable = malloc(sizeof(hashNode) * 100);

No, you want to allocate an array of pointers to hash nodes. For
an example, see hashlib.zip, which can be found at:

<http://cbfalconer.home.att.net/download/>

 

[Sean Kenwrick]

malloc() returns a pointer to memory containing garbage. To help makes bugs
more trackable, some implementations set this to a definite bit-pattern,
whilst others don't.

calloc() returns memory set to all bits zero. It is a false friend. On 99%
of systems a pointer with all bits zero is NULL, but there are a few
implementations where this is not true.

calloc() returns a block of memory where each byte of the memory block is
initialised to 0. The pointer returned by calloc() is never set to NULL
unless the function failed to allocate the block. I think you are
confusing the pointer to the memory block with the memory itself here.

Therefore you can use calloc() with 100% confidece that it will work as
described on all systems...

Sean

 

[Kevin Goodsell]

calloc() returns a block of memory where each byte of the memory block is
initialised to 0. The pointer returned by calloc() is never set to NULL
unless the function failed to allocate the block. I think you are
confusing the pointer to the memory block with the memory itself here.

No, he's right. I think you misunderstood his post.

Therefore you can use calloc() with 100% confidece that it will work as
described on all systems...

Sure, it will work as described. But there's no guarantee that the
memory you get back will have a correct, non-trap representation for the
type you intend to use it as. In particular, if you intend to allocate
pointers, the allocated pointers will not be initialized to NULL on some
systems where NULL is not represented with all-bits-zero.

-Kevin

 

[John Bode]

Hi, i have the following type and struct defined

typedef struct hNode {
unsigned char name[1024];
unsigned long hVal;
struct hNode *next;
} HashNode;

what i want, is to ensure that when doing:

HashNode aNode = malloc(sizeof(HashNode));

i can be sure of the value of "next" in the aNode (eg. later in the
program i want to compare the value of "next" in aNode to see if it has
been linked to another HashNode) --- can i do this in
some easy way or do i need to write my own memory allocator ???.


Thanks.

If you're relying members of your struct to be initialized to a known
value, you're best off writing your own allocator function. Heck, for
dynamically allocating *any* abstract data type, you're best off
writing your own allocator function.

HashNode *newHashNode (char *name, long hval)
{
HashNode *tmp;

tmp = malloc (sizeof *tmp);
if (tmp)
{
tmp->next = NULL;
tmp->hval = hval;
if (name)
{
if (strlen (name) < sizeof tmp->name)
strcpy (tmp->name, name);
else
{
/*
** Input name is too long to store in data type.
** Several ways to deal with this:
** 1. Report an error, abort the operation (free tmp)
** 2. Report an error, continue operation but
** don't store name
** 3. Report an error, store truncated name
**
** This code reports an error and attempts to
** store a truncated name.
*/
my_log_error (DATA_ERROR, NAME_TOO_LONG);
strncpy (tmp->name, sizeof tmp->name, name);
tmp->name[sizeof tmp->name - 1] = 0;
}
}
else
{
/* no name passed, initialize name buffer to 0 */
memset (tmp->name, 0, sizeof tmp->name);
}
}
else
{
/* report memory allocation error */
my_log_error (SYSTEM_ERROR, MALLOC_FAILED);
}
return tmp;
}

int main (void)
{
HashNode *node = newHashNode ("test", 0);
...
}