Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Hash table implementation.

Reply
Thread Tools

Hash table implementation.

 
 
Eric Sosman
Guest
Posts: n/a
 
      08-12-2011
On 8/12/2011 2:55 AM, wrote:
> Thanks for all your comments. I still have some questions :
>
> * Why do you prefer malloc() over calloc() ?


This was explained elsethread.

> * Why not cast for C++ compatibility?


Why not use `#define STOP ;' and write STOP instead of ; at
the end of each statement, so you can change it to `#define STOP .'
for easier conversion to COBOL?

> * Why shouldn't I use the register keyword for loop variables?


Because the compilers know the trade-offs for their particular
machines better than you know them for all machines.

--
Eric Sosman
d
 
Reply With Quote
 
 
 
 
tom st denis
Guest
Posts: n/a
 
      08-12-2011
On Aug 12, 4:47*am, Nobody <nob...@nowhere.com> wrote:
> On Thu, 11 Aug 2011 23:55:45 -0700, lolzy wrote:
> > Thanks for all your comments. I still have some questions :

>
> > * Why do you prefer malloc() over calloc() ?

>
> calloc() zeros the allocated memory, which is inefficient if you don't
> actually need to do so.


Generally, if you're allocating memory for a struct that has pointers
calloc() is your buddy since it'll also NULL the pointers [ya ya
rabble rabble, it's portable, let it go]. If you have char arrays
they're now NUL terminated, etc and so on...

If you're just allocating a buffer and then going to immediately use
it then malloc() is handy.

Tom
 
Reply With Quote
 
 
 
 
Joe Pfeiffer
Guest
Posts: n/a
 
      08-12-2011
writes:

> Thanks for all your comments. I still have some questions :
>
> * Why do you prefer malloc() over calloc() ?


Slightly faster if you're going to initialize the space to anything but
0.

> * Why not cast for C++ compatibility?


Because it isn't C++

> * Why shouldn't I use the register keyword for loop variables?


There's no real reason not to, but every compiler I'm familiar with
ignores it so there's no real point.
 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      08-12-2011
On 08/12/2011 09:15 AM, tom st denis wrote:
> On Aug 12, 4:47 am, Nobody <nob...@nowhere.com> wrote:
>> On Thu, 11 Aug 2011 23:55:45 -0700, lolzy wrote:
>>> Thanks for all your comments. I still have some questions :

>>
>>> * Why do you prefer malloc() over calloc() ?

>>
>> calloc() zeros the allocated memory, which is inefficient if you don't
>> actually need to do so.

>
> Generally, if you're allocating memory for a struct that has pointers
> calloc() is your buddy since it'll also NULL the pointers [ya ya
> rabble rabble, it's portable, let it go].


It will set all there bits zero, which is not necessarily a
representation of a null pointer. So, no, it is NOT portable.

Similarly, a floating point object with all bits zeros does not
necessarily represent 0.0, though that does happen to be the case for
most implementations.

However, you're fine as long as you stick with arithmetic types.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      08-12-2011
tom st denis <> writes:
> On Aug 12, 4:47Â*am, Nobody <nob...@nowhere.com> wrote:
>> On Thu, 11 Aug 2011 23:55:45 -0700, lolzy wrote:
>> > Thanks for all your comments. I still have some questions :

>>
>> > * Why do you prefer malloc() over calloc() ?

>>
>> calloc() zeros the allocated memory, which is inefficient if you don't
>> actually need to do so.

>
> Generally, if you're allocating memory for a struct that has pointers
> calloc() is your buddy since it'll also NULL the pointers [ya ya
> rabble rabble, it's portable, let it go]. If you have char arrays
> they're now NUL terminated, etc and so on...


No, I don't think I will let it go.

The language does not guarantee that either null pointers or
floating-point zero are represented as all-bits-zero.

There wasn't even such a guarantee for integer types until *after*
C99. (As of the C99 standard, an integer representation with padding
bits could in principle require some of those bits to be 1, making
all-bits-zero a trap representation; one of the technical corrigenda
requires all-bits-zero to be a valid representation for 0.)

I don't know of any implementation where all-bits-zero *isn't*
the representation for null pointers, zero-valued integers,
and zero-valued floating-point numbers. So if you use calloc()
and assume that it sets your pointers to NULL, you can almost
certainly get away with it. But your code won't be portable to
any implementations that violate those assumptions.

If you're ok with that, go ahead -- but at least add a comment
exlaining the choice you've made.

*Now* I'll let it go. }

> If you're just allocating a buffer and then going to immediately use
> it then malloc() is handy.


Why allocate a buffer unless you're going to use it? There are
cases where it's convenient to initialize some large data structure
to all zeros, with the possibility that you'll actually use the zero
values before writing some meaningful value. But another approach
is for your program's logic to keep track of which elements you've
set, and refer only to those elements' values. For example, if
a char array is going to contain a string, you don't need to zero
the whole thing; zeroing the first byte makes it an empty string.

--
Keith Thompson (The_Other_Keith) kst- <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      08-12-2011
James Kuyper <> writes:
> On 08/12/2011 09:15 AM, tom st denis wrote:
>> On Aug 12, 4:47 am, Nobody <nob...@nowhere.com> wrote:
>>> On Thu, 11 Aug 2011 23:55:45 -0700, lolzy wrote:
>>>> Thanks for all your comments. I still have some questions :
>>>
>>>> * Why do you prefer malloc() over calloc() ?
>>>
>>> calloc() zeros the allocated memory, which is inefficient if you don't
>>> actually need to do so.

>>
>> Generally, if you're allocating memory for a struct that has pointers
>> calloc() is your buddy since it'll also NULL the pointers [ya ya
>> rabble rabble, it's portable, let it go].

>
> It will set all there bits zero, which is not necessarily a
> representation of a null pointer. So, no, it is NOT portable.
>
> Similarly, a floating point object with all bits zeros does not
> necessarily represent 0.0, though that does happen to be the case for
> most implementations.
>
> However, you're fine as long as you stick with arithmetic types.


You're fine as long as you stick with *integer* types. (Floating-point
types are arithmetic.)

--
Keith Thompson (The_Other_Keith) kst- <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      08-12-2011
On 08/12/2011 11:50 AM, Keith Thompson wrote:
> James Kuyper <> writes:

....
>> Similarly, a floating point object with all bits zeros does not
>> necessarily represent 0.0, though that does happen to be the case for
>> most implementations.
>>
>> However, you're fine as long as you stick with arithmetic types.

>
> You're fine as long as you stick with *integer* types. (Floating-point
> types are arithmetic.)


Yep, I thought about that, just 2 seconds after I sent the message.

 
Reply With Quote
 
tom st denis
Guest
Posts: n/a
 
      08-12-2011
On Aug 12, 11:38*am, Keith Thompson <ks...@mib.org> wrote:
> tom st denis <t...@iahu.ca> writes:
>
> > On Aug 12, 4:47*am, Nobody <nob...@nowhere.com> wrote:
> >> On Thu, 11 Aug 2011 23:55:45 -0700, lolzy wrote:
> >> > Thanks for all your comments. I still have some questions :

>
> >> > * Why do you prefer malloc() over calloc() ?

>
> >> calloc() zeros the allocated memory, which is inefficient if you don't
> >> actually need to do so.

>
> > Generally, if you're allocating memory for a struct that has pointers
> > calloc() is your buddy since it'll also NULL the pointers [ya ya
> > rabble rabble, it's portable, let it go]. *If you have char arrays
> > they're now NUL terminated, etc and so on...

>
> No, I don't think I will let it go.
>
> The language does not guarantee that either null pointers or
> floating-point zero are represented as all-bits-zero.
>
> There wasn't even such a guarantee for integer types until *after*
> C99. *(As of the C99 standard, an integer representation with padding
> bits could in principle require some of those bits to be 1, making
> all-bits-zero a trap representation; one of the technical corrigenda
> requires all-bits-zero to be a valid representation for 0.)
>
> I don't know of any implementation where all-bits-zero *isn't*
> the representation for null pointers, zero-valued integers,
> and zero-valued floating-point numbers. *So if you use calloc()
> and assume that it sets your pointers to NULL, you can almost
> certainly get away with it. *But your code won't be portable to
> any implementations that violate those assumptions.
>
> If you're ok with that, go ahead -- but at least add a comment
> exlaining the choice you've made.
>
> *Now* I'll let it go. *}


While I appreciate the indepth analysis I did put that aside in there
BECAUSE I knew it wasn't 100% portable.

But basically for most developers we have two alternatives

1. calloc the struct and zero all pointers/etc thereby assuring that
you have more coverage and NULL pointers that weren't initialized will
be detected tout-suite

or

2. malloc the struct, try and cover all pointers/etc and run the risk
of missing some that may just randomly behave [or worse, appear to]
and thereby introduce security holes and uptime hazards...

> > If you're just allocating a buffer and then going to immediately use
> > it then malloc() is handy.

>
> Why allocate a buffer unless you're going to use it? *There are
> cases where it's convenient to initialize some large data structure
> to all zeros, with the possibility that you'll actually use the zero
> values before writing some meaningful value. *But another approach
> is for your program's logic to keep track of which elements you've
> set, and refer only to those elements' values. *For example, if
> a char array is going to contain a string, you don't need to zero
> the whole thing; zeroing the first byte makes it an empty string.


What I meant is something like

char *p = malloc(10); // I need some bytes

p[0] = somebuf[5];
// etc and so on

I always use calloc() [or equivs] when allocating structures ... I
just like having known state buffers...

Tom
 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      08-12-2011
On 08/12/2011 01:17 PM, tom st denis wrote:
> On Aug 12, 11:38 am, Keith Thompson <ks...@mib.org> wrote:
>> tom st denis <t...@iahu.ca> writes:

....
>>> Generally, if you're allocating memory for a struct that has pointers
>>> calloc() is your buddy since it'll also NULL the pointers [ya ya
>>> rabble rabble, it's portable, let it go]. If you have char arrays
>>> they're now NUL terminated, etc and so on...

....
> While I appreciate the indepth analysis I did put that aside in there
> BECAUSE I knew it wasn't 100% portable.


Saying "it'll also NULL the pointers" and "it's portable" is not a good
way of communicating the fact that you knew that it will sometimes fail
to create null pointers, and that it's not always portable. You should
be careful about saying things like that; it could give people the
impression that you are unaware of the fact that there are real
implementations where such code won't work.

> But basically for most developers we have two alternatives
>
> 1. calloc the struct and zero all pointers/etc thereby assuring that
> you have more coverage and NULL pointers that weren't initialized will
> be detected tout-suite
>
> or
>
> 2. malloc the struct, try and cover all pointers/etc and run the risk
> of missing some that may just randomly behave [or worse, appear to]
> and thereby introduce security holes and uptime hazards...


You've left out option 3, which is the one I use most often:

3. malloc() the struct, and then fill in it's members only when I have
actual values to fill them in with that I intend to use. Sometimes those
will be the same values that would result from either
zero-initialization, but often they will not be.

Another technique I often use is as follows:

static const struct my_struct empty;
struct my_struct *p = malloc(*p);
if(p)
{
*p = empty;
}
else
{
// error handling.
}
 
Reply With Quote
 
tom st denis
Guest
Posts: n/a
 
      08-12-2011
On Aug 12, 1:54*pm, James Kuyper <jameskuy...@verizon.net> wrote:
> On 08/12/2011 01:17 PM, tom st denis wrote:
>
> > On Aug 12, 11:38 am, Keith Thompson <ks...@mib.org> wrote:
> >> tom st denis <t...@iahu.ca> writes:

> ...
> >>> Generally, if you're allocating memory for a struct that has pointers
> >>> calloc() is your buddy since it'll also NULL the pointers [ya ya
> >>> rabble rabble, it's portable, let it go]. *If you have char arrays
> >>> they're now NUL terminated, etc and so on...

> ...
> > While I appreciate the indepth analysis I did put that aside in there
> > BECAUSE I knew it wasn't 100% portable.

>
> Saying "it'll also NULL the pointers" and "it's portable" is not a good
> way of communicating the fact that you knew that it will sometimes fail
> to create null pointers, and that it's not always portable. You should
> be careful about saying things like that; it could give people the
> impression that you are unaware of the fact that there are real
> implementations where such code won't work.


It's portable that in if you were born after the fall of the wall, and
develop software used on machines after the fall of indoor smoking at
shopping centres ... chances are highly good that you're on a machine
with[out] a MMU where there are no tag bits, no funkyness, and
pointers are just 16, 32, and/or 64 bit words where NULL is just all
zeroes.

For the 7 people out there who work on their PDP-11 slowly calculating
the value of 'e' or whatever you do with those machines ... they can
take heed of your warning.

ISO C would do well by just dropping such nonsense...


> > But basically for most developers we have two alternatives

>
> > 1. *calloc the struct and zero all pointers/etc thereby assuring that
> > you have more coverage and NULL pointers that weren't initialized will
> > be detected tout-suite

>
> > or

>
> > 2. *malloc the struct, try and cover all pointers/etc and run the risk
> > of missing some that may just randomly behave [or worse, appear to]
> > and thereby introduce security holes and uptime hazards...

>
> You've left out option 3, which is the one I use most often:
>
> 3. malloc() the struct, and then fill in it's members only when I have
> actual values to fill them in with that I intend to use. Sometimes those
> will be the same values that would result from either
> zero-initialization, but often they will not be.


Sometimes you initialize [or alloc] a structure in one routine and
don't fill in all of the values [or can't just yet] but it's later
used by code that CAN make use of the additional members. So not
having a default value in the pointer means that it creates UB.

> Another technique I often use is as follows:
>
> * * static const struct my_struct empty;
> * * struct my_struct *p = malloc(*p);
> * * if(p)
> * * {
> * * * * **p = empty;
> * * }
> * * else
> * * {
> * * * * *// error handling.
> * * }


typo aside (not pointing out because I'm not a jackass, I'll assume
you know C hehehehe), that is nice and portable, and sure if people
used that all the power to them. It does waste a bit of BSS segment
space though.

All I'm advocating is that if people cut corners they cut them so
they're less likely to cause UB than more. Your last solution is the
most ideal of them all [that you presented] but I'm still ok with just
simply using calloc() over malloc() if all else fails.

Tom
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
hash of hash of hash of hash in c++ rp C++ 1 11-10-2011 04:45 PM
Hash#select returns an array but Hash#reject returns a hash... Srijayanth Sridhar Ruby 19 07-02-2008 12:49 PM
Table/table rows/table data tag question? Rio HTML 4 11-05-2004 08:11 AM
standard library for hash table storage and hash algorithm Pieter Claassen C Programming 1 08-04-2004 03:11 AM
Could not load type VTFixup Table from assembly Invalid token in v-table fix-up table. David Williams ASP .Net 2 08-12-2003 07:55 AM



Advertisments
 



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57