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

Groups > comp.lang.c > #164696

Re: on looking up a word in a table, pointer question

Show all headers | View raw

On 28/01/2022 22:27, Lew Pitcher wrote:
> On Fri, 28 Jan 2022 18:16:15 -0300, Meredith Montgomery wrote:
> 
>> I show the full program at the end of this message, but I bet you don't
>> need the full program.
>>
>> Here's a table of C keywords:
>>
>> --8<---------------cut here---------------start------------->8---
>> struct kw {
>>    char *word;
>>    int count;
>> };
>>
>> struct kw table[] = {
>>    {"break", 0},
>>    {"case", 0},
>>    {"char", 0},
>>    {"const", 0},
>>    {"int", 0},
>>    {"continue", 0},
>>    {"default", 0},
>>    {"unsigned", 0},
>>    {"void", 0},
>>    {"volatile", 0},
>>    {"while", 0}
>> };
>> --8<---------------cut here---------------end--------------->8---
>>
>> Here's a procedure to lookup a word in this table:
>>
>> --8<---------------cut here---------------start------------->8---
>> struct kw * lookup(char *word, struct kw * table, int n) {
>>    struct kw *p;
>>
>>    for ( p = table; p->word != NULL; p++) {
>>      if (strcmp(word, p->word) == 0)
>>        return p;
>>    }
>>
>>    return NULL; /* not found */
>> }
>> --8<---------------cut here---------------end--------------->8---
>>
>> Notice how I'm stopping when p->word is not NULL.  This happens when p
>> gets to the last element of that array, which is terminated with a zero
>> automatically by the compiler.
> 
> Nope. That just does not happen. The table you wrote terminates with the
> last entry you wrote. Nothing (in that table) exists beyond that final
>     {"while", 0}
> and the compiler /does not/ add anything (like a terminating NULL of any
> sort) to the table.
> 
>>   (Just like a c-string.)  (I suppose.)
>>
>> So far so good.
>>
>> But this is not what I wrote first.  I'm stepping p through each element
>> in the table, so I know that eventually p points to the last element of
>> the array which is a certain zero-thing.  So the more natural comparison
>> to me would be something like
>>
>>    *p != NULL
>>
>> but the compiler won't let me because it says that *p has type
>>
>>    struct kw,
>>
>> which cannot be compared with
>>
>>    void *.
>>
>> %make keywords2 cc -x c -g -std=c99 -pedantic-errors   -c -o keywords2.o
>> keywords2.c keywords2.c: In function ‘lookup’:
>> keywords2.c:48:23: error: invalid operands to binary != (have ‘struct
>> kw’ and ‘void *’)
>>     48 |   for ( p = table; *p != NULL; p++) {
>>        |                    ~~ ^~
>>        |                    |
>>        |                    struct kw
>> make: *** [<builtin>: keywords2.o] Error 1 %
>>
>> This makes perfect sense.  But how could I detect that p has reached the
>> end of the table in a more natural way than p->word?  What is the
>> standard way to write this?  Thank you.
> 
> Try
>    for ( p = table; p < (table + sizeof table); p++) {
> 
> The expression
>    (table + sizeof table)
> produces an object that points to the first address /after/ the end of
> the table <<table>>. 

That's not right.  table is a pointer, so sizeof table is the length of a pointer, probably 4 or 8.

Also, adding say 4 to a pointer does not increase the memory address in the pointer by 4.  The 
address will increase by the size of 4 ENTRIES of the size of the table entries.  I.e. when adding 
to a pointer, the value added represents THE NUMBER OF ENTRIES of the pointed-to table by which you 
are advancing the pointer.

So your code would just process a fixed number of entries (probably 4 or 8) regardless of the actual 
size of the table.

Probably you were thinking table was an array, not a pointer.  But that would still be wrong, 
because then "sizeof table" would be the MEMORY SIZE of the table, not the number of entries in the 
table.  What you would actually need for this scenario is
    for ( p = table; p < (table + sizeof table / sizeof table[0]); p++) {
    ...

For Lew, if you have a function which is passed a pointer to a table of data, there are only really 
two options: the number of entries in the table can be explicitly passed to the function as another 
parameter, or you can ensure there is some way to recognise the last entry in the table - that means 
using some "out of normal range" value in the table entry, as Ben suggested.  (Both approaches are 
common.)

Some advice - if documenting a function that receives a "length" field as a parameter, be clear what 
the length means: is it a "number of bytes" length or a "count of entries" length?  Early Microsoft 
API documentation had numerous instances where this was either not clear, or worse on occasions it 
was clear but wrong!

Mike.


> The C language guarantees that
>    [i]f both the pointer operand and the result point to elements of the
>    same array object, or one past the last element of the array object,
>    the evaluation shall not produce an overflow; otherwise, the behavior
>    is undefined. If the result points one past the last element of the
>    array object, it shall not be used as the operand of a unary * operator
>    that is evaluated.
> In this case, the "pointer operand" is <<table>>, and the "result" points
> to "one past the last element of the array object", so the expression has
> a well-defined value, and will not invoke "undefined behaviour".
> 
> But, beware. You can't dereference the results of this expression:
>    *(table + sizeof table)
> is explicitly forbidden (see the last line of the quote above).
> 
> However, you /can/ compare a pointer to the results of this expression
> to determine where the pointer is in relation to the end of the table.
> 
> Specifically, while <<p>> is within the table,
>    p >= table
> and
>    p < (table + sizeof table)
> 
> If <<p>> points outside the table, past the rear end (the last entry) then
>    p >= (table + sizeof table)
> and if <<p>> points outside the table, past the front end (the first
> entry) then
>    p < table
> 
> Now, to your loop:
> 
> <<p>> initially points to the first element of the table, so
> it points at entry {"break", 0}.
> 
> With each iteration of the for() loop, the code increments <<p>> by the
> length of one table entry so that it, in turn, points at each successive
> entry.
> 
> With the last valid entry of the table, <<p>> points to the {"while", 0}
> entry. After processing this entry, your code increments <<p>> by the
> length of one table entry, so that it, now, points outside of the table.
> 
> This makes the expression
>    p < (table + sizeof table)
> false, which terminates the loop.
> 
> 
> [snip]
> 
> HTH
> 

Back to comp.lang.c | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

on looking up a word in a table, pointer question Meredith Montgomery <mmontgomery@levado.to> - 2022-01-28 18:16 -0300
  Re: on looking up a word in a table, pointer question scott@slp53.sl.home (Scott Lurndal) - 2022-01-28 21:29 +0000
  Re: on looking up a word in a table, pointer question Meredith Montgomery <mmontgomery@levado.to> - 2022-01-28 18:49 -0300
  Re: on looking up a word in a table, pointer question Kaz Kylheku <480-992-1380@kylheku.com> - 2022-01-28 22:07 +0000
    Re: on looking up a word in a table, pointer question Meredith Montgomery <mmontgomery@levado.to> - 2022-01-28 22:03 -0300
  Re: on looking up a word in a table, pointer question Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-28 22:23 +0000
    Re: on looking up a word in a table, pointer question Meredith Montgomery <mmontgomery@levado.to> - 2022-01-28 22:05 -0300
    Re: on looking up a word in a table, pointer question James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-01-28 21:10 -0500
  Re: on looking up a word in a table, pointer question Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2022-01-28 22:27 +0000
    Re: on looking up a word in a table, pointer question Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2022-01-28 23:18 +0000
      Re: on looking up a word in a table, pointer question Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-29 02:32 +0000
        Re: on looking up a word in a table, pointer question Meredith Montgomery <mmontgomery@levado.to> - 2022-01-30 10:23 -0300
          Re: on looking up a word in a table, pointer question Bart <bc@freeuk.com> - 2022-01-30 13:44 +0000
    Re: on looking up a word in a table, pointer question Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-01-28 23:23 +0000

csiph-web