Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #9220 > unrolled thread

Hash table implementation.

Back to article view | Back to comp.lang.c

Contents

  Hash table implementation. lolzy@live.nl - 2011-08-11 10:43 -0700
    Re: Hash table implementation. China Blue Tip Wrench <chine.bleu@yahoo.com> - 2011-08-11 11:25 -0700
    Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-11 11:49 -0700
      Re: Hash table implementation. Ralf Damaschke <rwspam@gmx.de> - 2011-08-11 20:02 +0000
    Re: Hash table implementation. Ike Naar <ike@sverige.freeshell.org> - 2011-08-11 22:02 +0000
    Re: Hash table implementation. "Scott Fluhrer" <sfluhrer@ix.netcom.com> - 2011-08-11 18:14 -0400
      Re: Hash table implementation. lolzy@live.nl - 2011-08-11 23:55 -0700
        Re: Hash table implementation. lolzy@live.nl - 2011-08-12 01:38 -0700
        Re: Hash table implementation. Nobody <nobody@nowhere.com> - 2011-08-12 09:47 +0100
          Re: Hash table implementation. tom st denis <tom@iahu.ca> - 2011-08-12 06:15 -0700
            Re: Hash table implementation. James Kuyper <jameskuyper@verizon.net> - 2011-08-12 11:34 -0400
              Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-12 08:50 -0700
                Re: Hash table implementation. James Kuyper <jameskuyper@verizon.net> - 2011-08-12 12:24 -0400
            Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-12 08:38 -0700
              Re: Hash table implementation. tom st denis <tom@iahu.ca> - 2011-08-12 10:17 -0700
                Re: Hash table implementation. James Kuyper <jameskuyper@verizon.net> - 2011-08-12 13:54 -0400
                  Re: Hash table implementation. tom st denis <tom@iahu.ca> - 2011-08-12 11:30 -0700
                    Re: Hash table implementation. Seebs <usenet-nospam@seebs.net> - 2011-08-12 20:39 +0000
                      Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-12 14:08 -0700
              Re: Hash table implementation. gordonb.4sxmx@burditt.org (Gordon Burditt) - 2011-08-12 20:04 -0500
                Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-12 18:40 -0700
                  Re: Hash table implementation. Harald van Dijk <truedfx@gmail.com> - 2011-08-13 12:59 -0700
                Re: Hash table implementation. Seebs <usenet-nospam@seebs.net> - 2011-08-13 02:34 +0000
        Re: Hash table implementation. Ike Naar <ike@iceland.freeshell.org> - 2011-08-12 11:13 +0000
        Re: Hash table implementation. Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-08-12 07:24 -0400
        Re: Hash table implementation. Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-08-12 09:27 -0600
        Re: Hash table implementation. Seebs <usenet-nospam@seebs.net> - 2011-08-12 18:37 +0000
        Re: Hash table implementation. Jens Gustedt <Jens.Gustedt@loria.fr> - 2011-08-13 00:08 +0200
          Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-12 15:26 -0700
            Re: Hash table implementation. Jens Gustedt <Jens.Gustedt@loria.fr> - 2011-08-13 15:11 +0200
              Re: Hash table implementation. Keith Thompson <kst-u@mib.org> - 2011-08-13 11:38 -0700
                Re: Hash table implementation. Jens Gustedt <Jens.Gustedt@loria.fr> - 2011-08-13 21:03 +0200
          Re: Hash table implementation. "Herbert Rosenau" <os2guy@pc-rosenau.de> - 2011-08-19 08:17 +0000
            Re: Hash table implementation. Jens Gustedt <jens.gustedt@loria.fr> - 2011-08-19 13:29 +0200
            Re: Hash table implementation. Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-08-19 14:35 +0300
    Re: Hash table implementation. Michael Angelo Ravera <maravera@prodigy.net> - 2011-08-12 02:54 -0700
    Re: Hash table implementation. Rui Maciel <rui.maciel@gmail.com> - 2011-08-13 23:11 +0100
      Re: Hash table implementation. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-08-14 00:56 +0100
        Re: Hash table implementation. lolzy@live.nl - 2011-08-14 00:11 -0700
          Re: Hash table implementation. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-08-14 11:57 +0100

Page 1 of 2  [1] 2  Next page →

#9220 — Hash table implementation.

Hello comp.lang.c,

This is a hash table implementation I wrote, please comment. Thanks in
advance.


# START CODE

/*
 * Hash table demo.
 * (C) Jori Koolstra - 19:40 11-8-2011
*/


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


#define		HASH_TABLE_SIZE							100


#define		HASH_TABLE_DELETE_ELEMENT_CHECK_FOR_ERRORS(t, n)		if
(hash_table_delete_element(t, n) == 0) hash_table_fatal_error(0, n)

#define		HASH_TABLE_GET_STRING_FROM_TABLE_CHECK_FOR_ERRORS(t, n, z)	if
((z = hash_table_get_string_from_table(t, n)) == NULL)
hash_table_fatal_error(1, n)


struct table_data
{
	char *uid;
	char *d;
};


typedef struct table_data table_data;



struct hash_table
{
	table_data data;
	struct hash_table *x;
};


typedef struct hash_table hash_table;



hash_table ** hash_table_create_table(int);
hash_table * hash_table_get_string_from_table(hash_table **, char *);
int hash_table_hash(char *);
void hash_table_add_element(hash_table **, char *, char *);
int hash_table_delete_element(hash_table **, char *);
void hash_table_fatal_error(int, char *);



int main(void)
{
	hash_table **table;
	hash_table *y;

	table = hash_table_create_table(HASH_TABLE_SIZE);

	hash_table_add_element(table, "John", "Hello John!");
	hash_table_add_element(table, "Kim", "Hello Kim!");
	hash_table_add_element(table, "Jori", "Hello Jori!");
	hash_table_add_element(table, "Jack", "Hello Jack!");

	HASH_TABLE_DELETE_ELEMENT_CHECK_FOR_ERRORS(table, "Kim");

	HASH_TABLE_GET_STRING_FROM_TABLE_CHECK_FOR_ERRORS(table, "Jack", y);

	printf("%s\n", y->data.d);




	return 0;
}



/*
 * Print error and quit.
*/
void hash_table_fatal_error(int t, char *el)
{
	switch (t)
	{
		case 0:
			printf("ERROR: Could not delete element '%s' from hash table.\n",
el);
			break;
		case 1:
			printf("ERROR: Could not find key '%s' in hash table.\n", el);
			break;
	}


	exit(0);
}



/*
 * Create a hash table with size 'size' and return a hash table array.
*/
hash_table ** hash_table_create_table(int size)
{
	register int i = 0;
	hash_table **x;


	x = (hash_table **) calloc(size, sizeof(hash_table *));

	for (; i <= size; ++i)
	{
		x[i] = (hash_table *) calloc(1, sizeof(hash_table));
	}

	return x;
}



/*
 * Returns a specified hash table element from table 't' with key 's',
 * or NULL on failure.
*/
hash_table * hash_table_get_string_from_table(hash_table **t, char *s)
{
	int id = hash_table_hash(s);
	hash_table *q;

	if (t[id]->data.uid != NULL && strcmp(t[id]->data.uid, s) != 0)
	{
		if (t[id]->x != NULL)
		{
			/* Move trough linked list */
			for (q = t[id]->x; ; q = q->x)
			{
				if (strcmp(q->data.uid, s) == 0)
				{
					/* Found */
					return q;
				}


				if (q->x == NULL)
				{
					break;
				}
			}
		}

		return NULL;
	}

	return (t[id]->data.uid == NULL ? NULL : t[id]);
}



/*
 * Add 'data' to table 't' with key 'uid'.
*/
void hash_table_add_element(hash_table **t, char *uid, char *data)
{
	int hash = hash_table_hash(uid);
	hash_table *q = (hash_table *) calloc(1, sizeof(hash_table));
	hash_table *c;

	q->data.uid = strdup(uid);
	q->data.d = strdup(data);
	q->x = NULL;


	c = t[hash];


	if (c->data.uid != NULL)
	{
		while (c->x != NULL)
		{
			c = c->x;
		}

		c->x = q;
	}
	else
	{
		t[hash]->data.uid = strdup(uid);
		t[hash]->data.d = strdup(data);
	}
}



/*
 * Delete element identified by 'uid' from hash table 't'.
 * Returns: 1 on success, 0 on failure.
*/
int hash_table_delete_element(hash_table **t, char *uid)
{
	int id = hash_table_hash(uid);
	hash_table *q;


	if (t[id]->data.uid == NULL)
	{
		return 0;
	}


	if (t[id]->data.uid != NULL && strcmp(t[id]->data.uid, uid) != 0)
	{
		/* Move trough linked list */
		for (q = t[id]; ; q = q->x)
		{
			if (strcmp(q->x->data.uid, uid) == 0)
			{
				if (q->x->x != NULL)
				{
					free(q->x);
					q->x = q->x->x;
				}
				else
				{
					free(q->x);
					q->x = NULL;
				}

				return 1;
			}


			if (q->x == NULL)
			{
				break;
			}
		}

		return 0;
	}


	if (t[id]->x == NULL)
	{
		t[id]->data.uid = NULL;
	}
	else
	{
		t[id]->data.uid = t[id]->x->data.uid;
		t[id]->data.d = t[id]->x->data.d;
		t[id]->x = t[id]->x->x;
	}

	return 1;
}




/***** NOT UNDER MY COPYRIGHT *****/
/*
 * UNIX ELF hash.
 * Published hash algorithm used in the UNIX ELF format for object
files.
 */
int hash_table_hash(char *data)
{
	int h = 0, g;

	while (*data)
	{
		h = (h << 4) + *data++;

		if (g = h & 0xF0000000)
		{
			h ^= g >> 24;
		}

		h &= ~g;
	}

	return h % HASH_TABLE_SIZE;
}

# END CODE

[toc] | [next] | [standalone]

#9222

In article <0c914904-6a93-4354-94a2-2bbeb6a53ddb@a17g2000yqk.googlegroups.com>,
 lolzy@live.nl wrote:

> Hello comp.lang.c,
> 
> This is a hash table implementation I wrote, please comment. Thanks in
> advance.

It's not that much more complicated to make a resizable hash table H.

H fields:
    n: number of entries
    a: number of allocated entries
    t: pointer to entries of type table_data

deleted: variable of type table_data

initialise H:
    H.n = 8
    H.a = 0
    H.t = calloc(H.n,sizeof table_data)

probe H for uid returning matching and firstfree:
    matching = -1
    firstfree = -1
    for (h=hash_table_hash(h) % H.n; H.t[h].uid!=NULL; h=(h+3) % H.n)
        if H.t[h].uid==deleted.uid and firstfree<0,
            firstfree = h
        else if strcmp(uid, H.t[h].uid)==0,
            matching = h
    if matching<0 then firstfree = h

reorganise H to size m:
    n = H.n
    t = H.t
    H.n = m
    H.a = 0
    H.t = calloc(H.n,sizeof table_data)
    for (k=0; k<n; k++)
        if t[k].uid!=NULL and t[k].uid!=deleted.uid,
            add table_data t[k] to H
    free t

find uid in H returning data d:
    matching, firstfree = probe H for uid
    if matching>=0,
        return H.t[h].d
    if matching<0,
        return NULL

add table_data e to H:
    matching, firstfree = probe H for e.uid
    if matching>=0,
        H.t[matching].d = copy of e.d
    if matching<0,
        H.t[matching].uid = copy of e.uid
        H.t[matching].d = copy of e.d
        H.a++
        if H.a/H.n >= 0.75,
            reorganise H to size 2*H.n

delete uid from H:
    matching, firstfree = probe H for uid
    if matching>=0,
        free H.t[matching].uid
        free H.t[matching].d
        H.t[matching] = deleted
        H.a--
        if H.a/H.n <= 0.25 and H.n > 8,
            reorganise H to size H.n/2


> # START CODE
> 
> /*
>  * Hash table demo.
>  * (C) Jori Koolstra - 19:40 11-8-2011
> */
> 
> 
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> 
> 
> #define		HASH_TABLE_SIZE							100
> 
> 
> #define		HASH_TABLE_DELETE_ELEMENT_CHECK_FOR_ERRORS(t, n)		if
> (hash_table_delete_element(t, n) == 0) hash_table_fatal_error(0, n)
> 
> #define		HASH_TABLE_GET_STRING_FROM_TABLE_CHECK_FOR_ERRORS(t, n, z)	if
> ((z = hash_table_get_string_from_table(t, n)) == NULL)
> hash_table_fatal_error(1, n)
> 
> 
> struct table_data
> {
> 	char *uid;
> 	char *d;
> };
> 
> 
> typedef struct table_data table_data;
> 
> 
> 
> struct hash_table
> {
> 	table_data data;
> 	struct hash_table *x;
> };
> 
> 
> typedef struct hash_table hash_table;
> 
> 
> 
> hash_table ** hash_table_create_table(int);
> hash_table * hash_table_get_string_from_table(hash_table **, char *);
> int hash_table_hash(char *);
> void hash_table_add_element(hash_table **, char *, char *);
> int hash_table_delete_element(hash_table **, char *);
> void hash_table_fatal_error(int, char *);
> 
> 
> 
> int main(void)
> {
> 	hash_table **table;
> 	hash_table *y;
> 
> 	table = hash_table_create_table(HASH_TABLE_SIZE);
> 
> 	hash_table_add_element(table, "John", "Hello John!");
> 	hash_table_add_element(table, "Kim", "Hello Kim!");
> 	hash_table_add_element(table, "Jori", "Hello Jori!");
> 	hash_table_add_element(table, "Jack", "Hello Jack!");
> 
> 	HASH_TABLE_DELETE_ELEMENT_CHECK_FOR_ERRORS(table, "Kim");
> 
> 	HASH_TABLE_GET_STRING_FROM_TABLE_CHECK_FOR_ERRORS(table, "Jack", y);
> 
> 	printf("%s\n", y->data.d);
> 
> 
> 
> 
> 	return 0;
> }
> 
> 
> 
> /*
>  * Print error and quit.
> */
> void hash_table_fatal_error(int t, char *el)
> {
> 	switch (t)
> 	{
> 		case 0:
> 			printf("ERROR: Could not delete element '%s' from hash table.\n",
> el);
> 			break;
> 		case 1:
> 			printf("ERROR: Could not find key '%s' in hash table.\n", el);
> 			break;
> 	}
> 
> 
> 	exit(0);
> }
> 
> 
> 
> /*
>  * Create a hash table with size 'size' and return a hash table array.
> */
> hash_table ** hash_table_create_table(int size)
> {
> 	register int i = 0;
> 	hash_table **x;
> 
> 
> 	x = (hash_table **) calloc(size, sizeof(hash_table *));
> 
> 	for (; i <= size; ++i)
> 	{
> 		x[i] = (hash_table *) calloc(1, sizeof(hash_table));
> 	}
> 
> 	return x;
> }
> 
> 
> 
> /*
>  * Returns a specified hash table element from table 't' with key 's',
>  * or NULL on failure.
> */
> hash_table * hash_table_get_string_from_table(hash_table **t, char *s)
> {
> 	int id = hash_table_hash(s);
> 	hash_table *q;
> 
> 	if (t[id]->data.uid != NULL && strcmp(t[id]->data.uid, s) != 0)
> 	{
> 		if (t[id]->x != NULL)
> 		{
> 			/* Move trough linked list */
> 			for (q = t[id]->x; ; q = q->x)
> 			{
> 				if (strcmp(q->data.uid, s) == 0)
> 				{
> 					/* Found */
> 					return q;
> 				}
> 
> 
> 				if (q->x == NULL)
> 				{
> 					break;
> 				}
> 			}
> 		}
> 
> 		return NULL;
> 	}
> 
> 	return (t[id]->data.uid == NULL ? NULL : t[id]);
> }
> 
> 
> 
> /*
>  * Add 'data' to table 't' with key 'uid'.
> */
> void hash_table_add_element(hash_table **t, char *uid, char *data)
> {
> 	int hash = hash_table_hash(uid);
> 	hash_table *q = (hash_table *) calloc(1, sizeof(hash_table));
> 	hash_table *c;
> 
> 	q->data.uid = strdup(uid);
> 	q->data.d = strdup(data);
> 	q->x = NULL;
> 
> 
> 	c = t[hash];
> 
> 
> 	if (c->data.uid != NULL)
> 	{
> 		while (c->x != NULL)
> 		{
> 			c = c->x;
> 		}
> 
> 		c->x = q;
> 	}
> 	else
> 	{
> 		t[hash]->data.uid = strdup(uid);
> 		t[hash]->data.d = strdup(data);
> 	}
> }
> 
> 
> 
> /*
>  * Delete element identified by 'uid' from hash table 't'.
>  * Returns: 1 on success, 0 on failure.
> */
> int hash_table_delete_element(hash_table **t, char *uid)
> {
> 	int id = hash_table_hash(uid);
> 	hash_table *q;
> 
> 
> 	if (t[id]->data.uid == NULL)
> 	{
> 		return 0;
> 	}
> 
> 
> 	if (t[id]->data.uid != NULL && strcmp(t[id]->data.uid, uid) != 0)
> 	{
> 		/* Move trough linked list */
> 		for (q = t[id]; ; q = q->x)
> 		{
> 			if (strcmp(q->x->data.uid, uid) == 0)
> 			{
> 				if (q->x->x != NULL)
> 				{
> 					free(q->x);
> 					q->x = q->x->x;
> 				}
> 				else
> 				{
> 					free(q->x);
> 					q->x = NULL;
> 				}
> 
> 				return 1;
> 			}
> 
> 
> 			if (q->x == NULL)
> 			{
> 				break;
> 			}
> 		}
> 
> 		return 0;
> 	}
> 
> 
> 	if (t[id]->x == NULL)
> 	{
> 		t[id]->data.uid = NULL;
> 	}
> 	else
> 	{
> 		t[id]->data.uid = t[id]->x->data.uid;
> 		t[id]->data.d = t[id]->x->data.d;
> 		t[id]->x = t[id]->x->x;
> 	}
> 
> 	return 1;
> }
> 
> 
> 
> 
> /***** NOT UNDER MY COPYRIGHT *****/
> /*
>  * UNIX ELF hash.
>  * Published hash algorithm used in the UNIX ELF format for object
> files.
>  */
> int hash_table_hash(char *data)
> {
> 	int h = 0, g;
> 
> 	while (*data)
> 	{
> 		h = (h << 4) + *data++;
> 
> 		if (g = h & 0xF0000000)
> 		{
> 			h ^= g >> 24;
> 		}
> 
> 		h &= ~g;
> 	}
> 
> 	return h % HASH_TABLE_SIZE;
> }
> 
> # END CODE

-- 
I remember finding out about you,  | How to loosen bolts with a hammer.
Everyday my mind is all around you,|      I'm whoever you want me to be.
Looking out from my lonely room    | Annoying Usenet one post at a time.
Day after day.                     |   At least I can stay in character.

[toc] | [prev] | [next] | [standalone]

#9225

ram@zedat.fu-berlin.de (Stefan Ram) writes:
> lolzy@live.nl writes:
>>x = (hash_table **) calloc(size, sizeof(hash_table *));
>> for (; i <= size; ++i)
>> {
>>  x[i] = (hash_table *) calloc(1, sizeof(hash_table));
>
>   x might be 0 here.

And if x isn't null, the elements of x might not be null pointers;
there's no guarantee that a null pointer is represented as
all-bits-zero.  If you're satisfied with portability only to
systems where null pointers *are* all-bits-zero, you can do that,
but I'd suggest at least documenting it.  Or you can use malloc()
and then set each element to NULL in a loop.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <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"

[toc] | [prev] | [next] | [standalone]

#9227

Keith Thompson <kst-u@mib.org> wrote:

> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>> lolzy@live.nl writes:
>>>x = (hash_table **) calloc(size, sizeof(hash_table *));
>>> for (; i <= size; ++i)
>>> {
>>>  x[i] = (hash_table *) calloc(1, sizeof(hash_table));
>>
>>   x might be 0 here.
> 
> And if x isn't null, the elements of x might not be null pointers;

You are right, at the place marked "here" for a non-null x these
pointers are either null pointers or point to an object
sufficiently large to hold an instance of hash_table.

-- Ralf

[toc] | [prev] | [next] | [standalone]

#9233

On 2011-08-11, lolzy@live.nl <lolzy@live.nl> wrote:
> hash_table ** hash_table_create_table(int size)
> {
> 	register int i = 0;

It's probably a good idea to drop the 'register' qualification
and leave this kind of optimization to the compiler.
I'd prefer to make 'size' and 'i' of type size_t.

> 	hash_table **x;
>
>
> 	x = (hash_table **) calloc(size, sizeof(hash_table *));

The cast is unnecessary; the recommended idiom is

        x = calloc(size, sizeof *x);

calloc can fail, and return NULL; you should check for that.
It's not necessary to set the elements of the array to all-bits-zero,
because you immediately overwrite each element in the for loop below.
So you might as well allocate the array using

        x = malloc(size * sizeof *x);

> 	for (; i <= size; ++i)
> 	{
> 		x[i] = (hash_table *) calloc(1, sizeof(hash_table));
> 	}

This looks like an off-by-error; x has only 'size' elements,
numbered 0 to size-1. The last iteration of the for loop assigns
to the nonexisting element x[size].
>
> 	return x;
> }

[toc] | [prev] | [next] | [standalone]

#9234

More comments...

<lolzy@live.nl> wrote in message 
news:0c914904-6a93-4354-94a2-2bbeb6a53ddb@a17g2000yqk.googlegroups.com...
> Hello comp.lang.c,
>
> This is a hash table implementation I wrote, please comment. Thanks in
> advance.
>
>
> # START CODE
>
>
> /*
> * Print error and quit.
> */
> void hash_table_fatal_error(int t, char *el)
> {
> switch (t)
> {
> case 0:
> printf("ERROR: Could not delete element '%s' from hash table.\n",
> el);

In case this is used in a utility which produces output which is used in a 
pipeline, you might want to make this:
fprintf( stderr, "Error message\n" );

> break;
> case 1:
> printf("ERROR: Could not find key '%s' in hash table.\n", el);
> break;
> }
>
>
> exit(0);
> }
>
>
>
> /*
> * Create a hash table with size 'size' and return a hash table array.
> */
> hash_table ** hash_table_create_table(int size)

What's the point in having the caller specify a hash table size, given that 
your hash function always returns values between 0 and 99?  If the caller 
specifies a value less that 100, you have a potential array overwrite when 
you add an element; if the caller specifies a value greater than 100, that's 
just wasted space.

> {
> register int i = 0;
> hash_table **x;
>
>
> x = (hash_table **) calloc(size, sizeof(hash_table *));
>
> for (; i <= size; ++i)

Array overflow!  You want:
   for (; i < size; ++i)

> {
> x[i] = (hash_table *) calloc(1, sizeof(hash_table));
> }

I see you have the convention that you represent an empty list with a dummy 
element.  While this is neither unethical nor immoral, it is a bit 
fattening, as it makes your search/insert/delete code more complex than it 
needs to be.  Why not represent an empty list with a NULL?

>
> return x;
> }
>
>
>
> /*
> * Returns a specified hash table element from table 't' with key 's',
> * or NULL on failure.
> */
> hash_table * hash_table_get_string_from_table(hash_table **t, char *s)
> {
> int id = hash_table_hash(s);
> hash_table *q;
>
> if (t[id]->data.uid != NULL && strcmp(t[id]->data.uid, s) != 0)
> {
> if (t[id]->x != NULL)
> {
> /* Move trough linked list */
> for (q = t[id]->x; ; q = q->x)
> {
> if (strcmp(q->data.uid, s) == 0)
> {
> /* Found */
> return q;
> }
>
>
> if (q->x == NULL)
> {
> break;
> }
> }
> }
>
> return NULL;
> }
>
> return (t[id]->data.uid == NULL ? NULL : t[id]);
> }

Sigh, this is rather more complex that it really needs to be:

    for (q = t[hash_table_hash(s)]; q; q = q->link) {
        if (q->data.uid && 0 == strcmp( q->data.uid, s ))
            return s;
    }
    return NULL;

The insert/remove functions can also be simplified a good bit.

>
>
>
> /*
> * Add 'data' to table 't' with key 'uid'.
> */
> void hash_table_add_element(hash_table **t, char *uid, char *data)
> {
> int hash = hash_table_hash(uid);
> hash_table *q = (hash_table *) calloc(1, sizeof(hash_table));
> hash_table *c;
>
> q->data.uid = strdup(uid);
> q->data.d = strdup(data);
> q->x = NULL;
>
>
> c = t[hash];
>
>
> if (c->data.uid != NULL)
> {
> while (c->x != NULL)
> {
> c = c->x;
> }
>
> c->x = q;
> }
> else
> {
> t[hash]->data.uid = strdup(uid);
> t[hash]->data.d = strdup(data);
Don't you leak the q element (and the strings it points to) here?

> }
> }
>
>
>
> /*
> * Delete element identified by 'uid' from hash table 't'.
> * Returns: 1 on success, 0 on failure.
> */
> int hash_table_delete_element(hash_table **t, char *uid)
> {
> int id = hash_table_hash(uid);
> hash_table *q;
>
>
> if (t[id]->data.uid == NULL)
> {
> return 0;
> }
>
>
> if (t[id]->data.uid != NULL && strcmp(t[id]->data.uid, uid) != 0)
> {
> /* Move trough linked list */
> for (q = t[id]; ; q = q->x)
> {
> if (strcmp(q->x->data.uid, uid) == 0)
> {
> if (q->x->x != NULL)
> {
> free(q->x);
> q->x = q->x->x;
> }
> else
> {
> free(q->x);
> q->x = NULL;
> }
>
> return 1;
> }
>
>
> if (q->x == NULL)
> {
> break;
> }
> }
>
> return 0;
> }
>
>
> if (t[id]->x == NULL)
> {
> t[id]->data.uid = NULL;
> }
> else
> {
> t[id]->data.uid = t[id]->x->data.uid;
> t[id]->data.d = t[id]->x->data.d;
> t[id]->x = t[id]->x->x;
> }
>
> return 1;
> }
>
>
>
>
> /***** NOT UNDER MY COPYRIGHT *****/
> /*
> * UNIX ELF hash.
> * Published hash algorithm used in the UNIX ELF format for object
> files.
> */
> int hash_table_hash(char *data)

This hash function has the property that the lower 2 bits of the result will 
always be the lower 2 bits of the last character of the string being hashed. 
Because the hash table is depending on the hashes to be well distributed 
(even if the strings might not be uniformly random), this is less than 
desirable.

Also, more generally, if this hash function were for general use as a 
utility, it's probably desirable for the user to be able to specify his own 
hash function.  The best that a generic hash function can do is act 
randomly; if the user knows about nonrandomness in his strings being hashed, 
he can often exploit that to create a hash function that actually works 
(generates a more uniform distribution) better than random (!).


> {
> int h = 0, g;
>
> while (*data)
> {
> h = (h << 4) + *data++;
>
> if (g = h & 0xF0000000)
> {
> h ^= g >> 24;
> }
>
> h &= ~g;
> }
>
> return h % HASH_TABLE_SIZE;
> }

>
> # END CODE 

[toc] | [prev] | [next] | [standalone]

#9247

Thanks for all your comments. I still have some questions :) :

* Why do you prefer malloc() over calloc() ?
* Why not cast for C++ compatibility?
* Why shouldn't I use the register keyword for loop variables?

[toc] | [prev] | [next] | [standalone]

#9249

I took a look at the code, and I optimized it to:
(Still looking for answers for my question 1 post up)
Thanks in advance.

/*
 * Hash table demo.
 * (C) Jori Koolstra - 19:40 11-8-2011
*/


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


#define		HASH_TABLE_SIZE							100


#define		HASH_TABLE_DELETE_ELEMENT_CHECK_FOR_ERRORS(t, n)		if
(hash_table_delete_element(t, n) == 0) hash_table_fatal_error(0, n)

#define		HASH_TABLE_GET_STRING_FROM_TABLE_CHECK_FOR_ERRORS(t, n, z)	if
((z = hash_table_get_string_from_table(t, n)) == NULL)
hash_table_fatal_error(1, n)


struct table_data
{
	char *uid;
	char *d;
};


typedef struct table_data table_data;



struct hash_table
{
	table_data data;
	struct hash_table *x;
};


typedef struct hash_table hash_table;



hash_table ** hash_table_create_table(int);
hash_table * hash_table_get_string_from_table(hash_table **, char *);
int hash_table_hash(char *);
void hash_table_add_element(hash_table **, char *, char *);
int hash_table_delete_element(hash_table **, char *);
void hash_table_fatal_error(int, char *);
void * hash_table_safe_calloc(size_t, size_t);


int main(void)
{
	hash_table **table;
	hash_table *y;

	table = hash_table_create_table(HASH_TABLE_SIZE);

	hash_table_add_element(table, "John", "Hello John!");
	hash_table_add_element(table, "Kim", "Hello Kim!");
	hash_table_add_element(table, "Jori", "Hello Jori!");
	hash_table_add_element(table, "Jack", "Hello Jack!");

	HASH_TABLE_DELETE_ELEMENT_CHECK_FOR_ERRORS(table, "Kim");

	HASH_TABLE_GET_STRING_FROM_TABLE_CHECK_FOR_ERRORS(table, "Jack", y);

	printf("%s\n", y->data.d);




	return 0;
}



/*
 * Print error and quit.
*/
void hash_table_fatal_error(int t, char *el)
{
	switch (t)
	{
		case 0:
			printf("ERROR: Could not delete element '%s' from hash table.\n",
el);
			break;
		case 1:
			printf("ERROR: Could not find key '%s' in hash table.\n", el);
			break;
		case 2:
			printf("ERROR: Could not allocate memory.\n");
			break;
	}


	exit(0);
}



/*
 * Create a hash table with size 'size' and return a hash table array.
*/
hash_table ** hash_table_create_table(int size)
{
	register int i = 0;
	hash_table **x;


	x = (hash_table **) hash_table_safe_calloc(size, sizeof(hash_table
*));

	for (; i < size; ++i)
	{
		x[i] = (hash_table *) hash_table_safe_calloc(1, sizeof(hash_table));
	}

	return x;
}



/*
 * Returns a specified hash table element from table 't' with key 's',
 * or NULL on failure.
*/
hash_table * hash_table_get_string_from_table(hash_table **t, char *s)
{
	hash_table *q;

	for (q = t[hash_table_hash(s)]; q; q = q->x)
	{
		if (q->data.uid && 0 == strcmp(q->data.uid, s))
		{
			return q;
		}
	}

	return NULL;
}



/*
 * Add 'data' to table 't' with key 'uid'.
*/
void hash_table_add_element(hash_table **t, char *uid, char *data)
{
	int h = hash_table_hash(uid);
	hash_table *q, *c = t[h];


	if (c->data.uid != NULL)
	{
		q = (hash_table *) hash_table_safe_calloc(1, sizeof(hash_table));
		q->data.uid = strdup(uid);
		q->data.d = strdup(data);

		for (; c->x != NULL; c = c->x)

		c->x = q;
	}
	else
	{
		t[h]->data.uid = strdup(uid);
		t[h]->data.d = strdup(data);
	}
}



/*
 * Delete element identified by 'uid' from hash table 't'.
 * Returns: 1 on success, 0 on failure.
*/
int hash_table_delete_element(hash_table **t, char *uid)
{
	int h = hash_table_hash(uid);
	hash_table *q;


	if (t[h]->data.uid != NULL && strcmp(t[h]->data.uid, uid) != 0)
	{
		/* Move trough linked list */
		for (q = t[h]; q; q = q->x)
		{
			if (strcmp(q->x->data.uid, uid) == 0)
			{
				free(q->x);
				q->x = q->x->x;

				return 1;
			}
		}

		return 0;
	}


	if (t[h]->x == NULL)
	{
		if (t[h]->data.uid == NULL)
		{
			return 0;
		}
		else
		{
			t[h]->data.uid = NULL;
		}
	}
	else
	{
		t[h]->data.uid = t[h]->x->data.uid;
		t[h]->data.d = t[h]->x->data.d;
		t[h]->x = t[h]->x->x;
	}

	return 1;
}



/*
 * Allocate space with error checking.
*/
void * hash_table_safe_calloc(size_t num, size_t size)
{
	void *p;

	if ((p = calloc(num, size)) == NULL)
	{
		hash_table_fatal_error(2, "");
	}

	return p;
}




/***** NOT UNDER MY COPYRIGHT *****/
/*
 * UNIX ELF hash.
 * Published hash algorithm used in the UNIX ELF format for object
files.
 */
int hash_table_hash(char *data)
{
	int h = 0, g;

	while (*data)
	{
		h = (h << 4) + *data++;

		if (g = h & 0xF0000000)
		{
			h ^= g >> 24;
		}

		h &= ~g;
	}

	return h % HASH_TABLE_SIZE;
}

[toc] | [prev] | [next] | [standalone]

#9250

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.

> * Why not cast for C++ compatibility?

There are arguments for and against casting. The main argument against is
that casting can prevent a diagnostic being issued if the prototype isn't
in scope.

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

At best, it's a waste of both keystrokes and bytes; the compiler will
probably ignore it when deciding where to store the variable (i.e. the
only effect of a "register" qualifier is likely to be that you get an
error if you attempt to take the variable's address). At worst, the
compiler might actually pay attention to it, and you get less efficient
code than the compiler would have generated without it.

The "register" qualifier originated in an era where compilers performed a
fairly direct translation from source code to object code, without any
significant optimisation. It is somewhere between useless and worse than
useless with a modern compiler.

[toc] | [prev] | [next] | [standalone]

#9256

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

[toc] | [prev] | [next] | [standalone]

#9259

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.

[toc] | [prev] | [next] | [standalone]

#9263

James Kuyper <jameskuyper@verizon.net> 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-u@mib.org  <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"

[toc] | [prev] | [next] | [standalone]

#9267

On 08/12/2011 11:50 AM, Keith Thompson wrote:
> James Kuyper <jameskuyper@verizon.net> 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.

[toc] | [prev] | [next] | [standalone]

#9261

tom st denis <tom@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.  8-)}

> 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-u@mib.org  <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"

[toc] | [prev] | [next] | [standalone]

#9269

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.  8-)}

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

[toc] | [prev] | [next] | [standalone]

#9271

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.
    }

[toc] | [prev] | [next] | [standalone]

#9274

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

[toc] | [prev] | [next] | [standalone]

#9291

On 2011-08-12, tom st denis <tom@iahu.ca> wrote:
> 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.

Chances are good, yes, but...

There are reasons, even on such hardware, to prefer some non-all-bits-zero
pointer as "null".

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

I don't think so.  I honestly think we would all probably be better off
if most modern systems had used 0xFFFFFFFF (or more Fs on 64-bit) as the
C "NULL".

-s
-- 
Copyright 2011, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.

[toc] | [prev] | [next] | [standalone]

#9295

Seebs <usenet-nospam@seebs.net> writes:
> On 2011-08-12, tom st denis <tom@iahu.ca> wrote:
>> 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.
>
> Chances are good, yes, but...
>
> There are reasons, even on such hardware, to prefer some non-all-bits-zero
> pointer as "null".

I've worked on a system where a null pointer has the value 1, because
the CPU trapped on word access to odd addresses.  It was Pascal, not C,
but the same thing could apply to a C implementation.

On the other hand, modern systems are more likely to do this by
unmapping the appropriate address range (as I recall the system didn't
have virtual memory).

>> ISO C would do well by just dropping such nonsense...
>
> I don't think so.  I honestly think we would all probably be better off
> if most modern systems had used 0xFFFFFFFF (or more Fs on 64-bit) as the
> C "NULL".

We don't know what seemingly odd decisions might be made for future
architectures.  A lot of code had to be re-written when some system
started trapping on references to address 0; prior to that, *(char*)0
would quietly give you 0, and a lot of software took advantage of that.

Avoiding undefined behavior in C can make your code portable both to
systems that are so old that you've never heard of them, and to systems
that haven't been invented yet.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <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"

[toc] | [prev] | [next] | [standalone]

#9316

IEEE floating point numbers have at least two different representations
for zero and negative zero.  They can't *BOTH* be represented by
all-bits-zero.  That's a very large chunk of implementations that
have at least one representation for zero that isn't all-bits-zero.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web