K&R chapter 6.3 Question 'how to calculate the number of array elements'

[Herrcho]

in K&R Chapter 6.3

it mentions two methods to calculate NKEYS.

and points out the first one which is to terminate the list of
initializers with a null pointer, then loop along keytab until the end
is found is less efficient than using sizeof operator , since size of
the array is completely determined at compile time.

i don't quite understand this. Could anyone explain to me in detail ?

Thanks in advance..

[Mark Shelor]

Herrcho wrote:

in K&R Chapter 6.3

it mentions two methods to calculate NKEYS.

and points out the first one which is to terminate the list of
initializers with a null pointer, then loop along keytab until the end
is found is less efficient

Yes, the first method would need to be performed at runtime, with
initialization code such as:

#include <stdlib.h>

unsigned int nkeys;

for (nkeys = 0; keytab[nkeys].word != NULL; nkeys++)
;

than using sizeof operator , since size of
the array is completely determined at compile time.

The second method requires no runtime code, and leaves all the work up
to the compiler:

#define NKEYS (sizeof keytab / sizeof keytab[0])

The latter is much simpler, n'est-ce pas?

Mark

[Mike Wahler]

"Herrcho" <he*********@kornet.net> wrote in message
news:76**************************@posting.google.c om...

in K&R Chapter 6.3

it mentions two methods to calculate NKEYS.

and points out the first one which is to terminate the list of
initializers with a null pointer,
Or more generally, a value which has been specified to
mean 'terminator'. E.g. an array of integer values which
are defined as 'valid' data if nonnegative. A 'terminator'
value for this could be e.g. -1.
then loop along keytab until the end
is found
This would be 'manual' counting. It happens at run time,
so it consumes processor time. It also is 'fragile' since
it depends upon the array's elements being properly initialized.

It's also not very flexible, since it disallows storing (in
any array element, intentionally or inadvertently) any possible
value the array's element type could represent (a 'terminator'
value would belong to this set.)
is less efficient
Because 'sizeof' provides the value at compile-time. Thus
the value is already known at program startup. No need for the
program to consume processor time to calculate it.
than using sizeof operator , since size of
the array is completely determined at compile time.

i don't quite understand this. Could anyone explain to me in detail ?
I hope I did.

A caveat:

'sizeof' will only correctly report the size of an array if
that array is in the same scope where the 'sizeof' operator
is used. Passed as an argument to a function, an array's
type is 'demoted' to a pointer type (the value is the address
of the array's first element).

#include <stdio.h>

int g_array[] = {1,2,3,-1}; /* using -1 as 'terminator' for */
/* array of non-negative value */

size_t size(int arg[10]) /* the [10] is ignored, 'arg's type is really */
/* 'int*' ('pointer to int') */
{
return sizeof arg;
}

void other_stuff(int *arg) /* note that we can pass either a 'real' */
/* pointer, or an array of ints as the */
/* parameter */
{
--arg[2]; /* decrement element 2 (imagine this is part of a */
/* larger algorithm, e.g. where the 2 is replaced */
/* by the value of some other variable. IOW we */
/* don't know by looking at this statment what */
/* that value is) */
}

void more_stuff(void)
{
++g_array[3]; /* increment element 3 (imagine this is part of a */
/* larger algorithm, e.g. where the 3 is replaced */
/* by the value of some other variable. IOW we */
/* don't know by looking at this statment what */
/* that value is) */
}

/* 'Manually' counts array elements, */
/* uses -1 as terminator value */
size_t count_em(int arg[]) /* yet another possible syntax for */
/* a pointer or array argument */
{
size_t count = 0;
size_t i = 0;

while(arg[i++] >= 0)
count += sizeof *arg; /* '*arg' means same thing as 'arg[0]' */

return count;
}

int main()
{
int m_array[] = { 2, 6, 0, 7, 5, -1}; /* using -1 as 'terminator' for
*/
/* array of non-negative value */

printf("size of g_array as reported by sizeof operator :"
" %2lu bytes\n",
(unsigned long)sizeof g_array); /* prints sizeof(int) * 4, */
/* e.g. 16 on a Win32 platform */

printf("size of g_array as reported by size() function :"
" %2lu bytes\n",
(unsigned long)size(g_array)); /* prints the size of type 'int*' */
/* e.g. 4 on a Win32 platform */

putchar('\n');

printf("size of m_array as reported by sizeof operator :"
" %2lu bytes\n",
(unsigned long)sizeof m_array); /* prints sizeof(int) * 5, */
/* e.g. 24 on a Win32 platform */

printf("size of m_array as reported by size() function :"
" %2lu bytes\n",
(unsigned long)size(m_array)); /* prints the size of type 'int*' */
/* e.g. 4 on a Win32 platform */

putchar('\n');

/* Hereafter, size values stated in comments
are those obtained on Win32 platform */

printf("size of g_array as reported by count_em() function :"
" %2lu bytes\n",
(unsigned long)count_em(g_array)); /* prints size of the portion */
/* of array preceding element */
/* with value -1 (here, 12) */

printf("size of m_array as reported by count_em() function :"
" %2lu bytes\n",
(unsigned long)count_em(m_array)); /* prints size of the portion */
/* of array preceding element */
/* with value -1 (here, 20) */

putchar('\n');

other_stuff(m_array); /* do some stuff with 'm_array' */
printf("%s\n\n", "other_stuff(m_array) called");

printf("size of m_array as reported by count_em() function :"
" %2lu bytes\n",
(unsigned long)count_em(m_array)); /* prints the number of array */
/* of array preceding element */
/* with value -1 (here, 8) */
/* -- because m_array[2] was */
/* 'accidentally' set to -1. */
/* OOPS! :-) */

putchar('\n');

more_stuff();
printf("%s\n\n", "more_stuff() called (touches g_array)");

puts("Better not call count_em(g_array) !!!");

#if 0
printf("size of g_array as reported by count_em() function :"
" %2lu bytes\n",
(unsigned long)count_em(g_array)); /* prints the number of array */
/* of array preceding element */
/* with value -1. But WAIT!! */
/* there's no element with a */
/* value of -1!! (due to what */
/* 'more_stuff()' did) */
/* execution of this statment */
/* would produce 'undefined' */
/* behavior (wich is why I */
/* "#if-d" it out */

/* this last issue is why we should always provide an array's size */
/* (typically expressed as number of elements) as an extra paramter */
/* to functions to which arrays are passed. It provides a 'hard limit */
/* on how many elements can be accessed, regardless of their values. */
/* And again, remember that sizeof will only report correct size for */
/* arrays in same scope (of course some other mechanism for determining */
/* size might be used instead, e.g. a #define for the size of the array) */

/* recommended syntax for calcuating count of array elements using sizeof:
*/
/*
/* sizeof array_name / sizeof *array_name
*/

#endif

return 0;
}
Output:
-------------------------------------------------------------
size of g_array as reported by sizeof operator : 16 bytes
size of g_array as reported by size() function : 4 bytes

size of m_array as reported by sizeof operator : 24 bytes
size of m_array as reported by size() function : 4 bytes

size of g_array as reported by count_em() function : 12 bytes
size of m_array as reported by count_em() function : 20 bytes

other_stuff(m_array) called

size of m_array as reported by count_em() function : 8 bytes

more_stuff() called (touches g_array)

Better not call count_em(g_array) !!!
-------------------------------------------------------------

Hope I didn't foul all that up. If I did, we'll hear about
it soon enough! :-)

Thanks in advance..

You're welcome after the fact. :-)

-Mike

[Kelsey Bjarnason]

On Mon, 09 Feb 2004 22:38:19 -0800, Herrcho wrote:

in K&R Chapter 6.3

it mentions two methods to calculate NKEYS.

and points out the first one which is to terminate the list of
initializers with a null pointer, then loop along keytab until the end
is found is less efficient than using sizeof operator , since size of
the array is completely determined at compile time.

i don't quite understand this. Could anyone explain to me in detail ?

Thanks in advance..

Don't have the book handy, but it seems simpl enough. Here's the first
case:

char *array[100] = { val1, val2, ... NULL };

Now you can loop through the array until you reach the NULL; if you've
filled in all the values array[0] ... array[98] with values and array[99]
with NULL, you'll get your count. Like so:

int i;

for ( i = 1; i <= 100; i++ )
if ( array[i-1] == NULL )
break;

Thing is, that requires 100 loops and comparisons. Now try this:

char *array[100];

size_t n = sizeof(array)/sizeof(array[0]);

Assuming a char * takes, say, 4 bytes, then the size of the array will be
400 bytes, the size of array[0] will be 4 bytes, and 400/4 == 100, which
is the number of elements. Better yet, since sizeof is a compile-time
thing, this works out to a simple assignment: size_t n = 100;

[pete]

Kelsey Bjarnason wrote:

On Mon, 09 Feb 2004 22:38:19 -0800, Herrcho wrote:

in K&R Chapter 6.3

it mentions two methods to calculate NKEYS.

and points out the first one which is to terminate the list of
initializers with a null pointer, then loop along keytab
until the end is found is less efficient than using sizeof
operator , since size of the array is completely
determined at compile time.

i don't quite understand this.
Could anyone explain to me in detail ?

Thanks in advance..

Don't have the book handy, but it seems simpl enough.
Here's the first case:

char *array[100] = { val1, val2, ... NULL };

Now you can loop through the array until you reach the NULL; if you've
filled in all the values array[0] ... array[98]
with values and array[99] with NULL, you'll get your count.
Like so:

int i;

for ( i = 1; i <= 100; i++ )
if ( array[i-1] == NULL )
break;

Thing is, that requires 100 loops and comparisons.

char *ptr;

for (ptr = array; ptr != NULL; ++ptr);

--
pete

[pete]

pete wrote:

Kelsey Bjarnason wrote:

char *array[100] = { val1, val2, ... NULL };

char *ptr;
char **ptr;
for (ptr = array; ptr != NULL; ++ptr);

--
pete

[Peter Pichler]

"pete" <pf*****@mindspring.com> wrote in message
news:40***********@mindspring.com...

Kelsey Bjarnason wrote:

char *array[100] = { val1, val2, ... NULL }; .... int i;

for ( i = 1; i <= 100; i++ )
if ( array[i-1] == NULL )
break;

Thing is, that requires 100 loops and comparisons.

char *ptr;

for (ptr = array; ptr != NULL; ++ptr);

Two questions:
1. How many loops would this execute in your opinion, given the
initialization above? (I admit, I assume the NULL is the *last* element in
the array.)
2. How does it calculate the number of elements? ;-)