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

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

on looking up a word in a table, pointer question

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

Contents

  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

#164680 — on looking up a word in a table, pointer question

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

(*) Full program

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

#define NKEYS ((sizeof table) / (sizeof table[0]))
#define MAXWORD 100

int getword(char *, int);
struct kw * lookup(char *, struct kw *, int);

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

int main() {
  int n; char word[MAXWORD]; struct kw * p;

  while (getword(word, MAXWORD) != EOF)
    if (isalpha(word[0]))
      if ((p = lookup(word, table, NKEYS)) != NULL)
        p->count++;

  for (p = table; p < table + NKEYS; p++)
    if (p->count > 0)
      printf("%4d %s\n", p->count, p->word);

  return 0;
}

struct kw * lookup(char *word, struct kw * table, int n) {
  struct kw *p;

  for ( p = table; *p != NULL; p++) {
    if (strcmp(word, p->word) == 0)
      return p;
  }

  return NULL; /* not found */
}

int getword(char *word, int lim) {
  int getch(void);
  void ungetch(int);

  int c; 
  char *w = word;

  while (isspace(c = getch()))
    ;

  if (c != EOF)
    *w++ = c;

  if (!isalpha(c)) {
    *w = '\0';
    return c;
  }

  for ( ; --lim > 0; w++)
    if (!isalnum(*w = getch())) {
      ungetch(*w);
      break;
    }

  *w = '\0';
  return word[0];
}

[toc] | [next] | [standalone]

#164684

Meredith Montgomery <mmontgomery@levado.to> writes:
>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.  (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.
>
>(*) Full program
>
>#include <ctype.h>
>#include <string.h>
>#include <stdio.h>
>
>#define NKEYS ((sizeof table) / (sizeof table[0]))
>#define MAXWORD 100
>
>int getword(char *, int);
>struct kw * lookup(char *, struct kw *, int);
>
>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}
>};
>
>int main() {
>  int n; char word[MAXWORD]; struct kw * p;
>
>  while (getword(word, MAXWORD) != EOF)
>    if (isalpha(word[0]))
>      if ((p = lookup(word, table, NKEYS)) != NULL)
>        p->count++;
>
>  for (p = table; p < table + NKEYS; p++)
>    if (p->count > 0)
>      printf("%4d %s\n", p->count, p->word);
>
>  return 0;
>}
>
>struct kw * lookup(char *word, struct kw * table, int n) {
>  struct kw *p;
>
>  for ( p = table; *p != NULL; p++) {
>    if (strcmp(word, p->word) == 0)
>      return p;
>  }
>
>  return NULL; /* not found */
>}
>
>int getword(char *word, int lim) {
>  int getch(void);
>  void ungetch(int);
>
>  int c; 
>  char *w = word;
>
>  while (isspace(c = getch()))
>    ;
>
>  if (c != EOF)
>    *w++ = c;
>
>  if (!isalpha(c)) {
>    *w = '\0';
>    return c;
>  }
>
>  for ( ; --lim > 0; w++)
>    if (!isalnum(*w = getch())) {
>      ungetch(*w);
>      break;
>    }
>
>  *w = '\0';
>  return word[0];
>}


   for(tp=commands, i=0; i < MAX_COMMAND_INTERP_COMMANDS; i++,tp++) {
        if (tp->name[0] != '\0') {
            /*
             * If this command is allowed to be abbreviated,
             * check to see if this is it.
             */

            if (tp->minlen
             && (strlen(argv[0]) <= tp->minlen)) {
                if (strncmp(argv[0],
                            tp->name,
                            tp->minlen) == 0) {
                    break;
                }
            }

            if (strcmp(argv[0], tp->name)==0) {
                break;
            }
        }
    }

    if (i < MAX_COMMAND_INTERP_COMMANDS) {
        if (tp->thisarg) {
            return (*tp->thisfunc)(tp->thisarg, argc, (const char **)argv, env);
        } else {
            return (*tp->func)(argc, (const char **)argv, env);
        }
    }

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

#164687

Sorry.  This post turned out to be a case of being tired.

> 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 */
> }

The reason the argument n is there is precisely to be the size of the
table so that we can write the for loop's test as 

  p < table + n

Here's a revise version of lookup():

--8<---------------cut here---------------start------------->8---
struct kw * lookup(char *word, struct kw * table, int n) {
  struct kw *p;
  for (p = table; p < table + n; p++) {
    if (strcmp(word, p->word) == 0)
      return p;
  }

  return NULL; /* not found */
}
--8<---------------cut here---------------end--------------->8---

This loop is pretty natural to me.  I was being bitten, too, by the fact
that in main() I had an array and in lookup() I had just a pointer to an
element of the table.  The NKEYS macro, therefore, doesn't work as I
expected inside lookup().  I was bitten there.

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

#164690

On 2022-01-28, Meredith Montgomery <mmontgomery@levado.to> 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.

So you need an entry for that in the array

    {"while", 0},
    {NULL, 0}
  };

> };
> This happens when p gets to the last element.

"gets" is deprecated in C, please say "moves" or "mosies on over to" or
some other more precise word. :)

> to the last element of that array, which is terminated with a zero
> automatically by the compiler.  (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.

The last element of the array is the {"while", 0} entry.

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

That could be arrangd, but provides no benefit:

  int null_kw(struct kw kw)
  {
     return kw.word == NULL && kw.count == 0;
  }

So then, provided you have the {NULL, 0} entry in the table. the loop
could terminate like this:

  for (p = table; !null_kw(*p); p++)

That's a lot of ceremony for something simple. Or even

  struct kw NULL_kw = { NULL, 0 };

  for (p = table; !kw_compare(*p, NULL_kw); p++)

where we have this:

  int kw_compare(struct kw left, struct kw right)
  {
     return ((left.word == NULL && right.word == NULL) ||
             (left.word != NULL && right.word != NULL &&
              strcmp(left.word, right.word) == 0)) &&
            left.count == right.count;
  }

All these kinds of idioms have their right time and place; probably
not here though in the simple loop through a table of keywords.

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

Comparing p->word to NULL and ensuring there such an entry at the end
of the array is natural.

Another way is this:

  /* caution: this macro invites an array_size(pointer) bug */

  #define num_elements(array) (sizeof array / sizeof array[0])

  /* ... */

  for (i = 0; i < num_elements(table); i++) {
     if (strcmp(table[i], word) == 0)
        return &table[i];
  }

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

#164699

Kaz Kylheku <480-992-1380@kylheku.com> writes:

> On 2022-01-28, Meredith Montgomery <mmontgomery@levado.to> 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.
>
> So you need an entry for that in the array
>
>     {"while", 0},
>     {NULL, 0}
>   };

Aha!  That's what I had not realized.

>> };
>> This happens when p gets to the last element.
>
> "gets" is deprecated in C, please say "moves" or "mosies on over to" or
> some other more precise word. :)

Lol.  Will do.  :-) 

>> to the last element of that array, which is terminated with a zero
>> automatically by the compiler.  (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.
>
> The last element of the array is the {"while", 0} entry.

Yes, I was bitten there.  Thanks for pointing it out.

> 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 *.  
>
> That could be arrangd, but provides no benefit:
>
>   int null_kw(struct kw kw)
>   {
>      return kw.word == NULL && kw.count == 0;
>   }
>
> So then, provided you have the {NULL, 0} entry in the table. the loop
> could terminate like this:
>
>   for (p = table; !null_kw(*p); p++)

Lol.  I've done this once.  Lol.  It's really such a bad solution.  Let
me see if I can look up when I did this.  Here.

typedef struct Pair {
  uint64_t p;
  uint64_t q;
} Pair;

#define IS_NOT_NIL_PAIR(P) (P.p != 0 && P.q != 0)

int main() {
  Pair N;
  for (N = composites(); IS_NOT_NIL_PAIR(N); N = composites()) {
    printf("Pair (%ld, %ld) produces N = %ld\n", N.p, N.q, N.p * N.q);
  }
  printf("Done\n");
  return 0;
}

Pair composites(void) {
  static unsigned int i = 0;
  static unsigned int j = 1;
  
  Pair N;
  N.p = primes(i);
  N.q = primes(j);

  if (i == (primes_size() - 1) && j == primes_size()) {
    return (Pair) {0, 0};
  }

  j = j + 1;

  if (j == (primes_size())) { 
    i = i + 1; 
    j = i + 1; 
  }
  
  return N;
}

Oh, boy.  I really didn't know any better at that time.  

My case up there wasn't quite a table, but I wanted to somehow specify
that at some point I wasn't going to generate more composites and,
because I didn't want to work with pointers, I had to return a struct.
I guess I still don't know how to do any better here.  (It's not a
table.)

I think I should improve this a by creating a nullPair --- like Kaz
Kylheku was doing.  So in case of termination or error, I just return
this nullPair.

[...]

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

#164692

Meredith Montgomery <mmontgomery@levado.to> writes:

> 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:
>
> 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}
> };
>
>
> Here's a procedure to lookup a word in this table:
>
> 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 */
> }
>
> 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.  (Just like a c-string.)  (I suppose.)

Eek!  No, that does not happen.  You will be tricked by the fact that
your code will often work because zeros are so common, but you need to
add a final

  { 0, 0 }

entry to the table.

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

There is nothing wrong with using p->word.  You could add a line

  { "", -1 }

and test for p->count >= 0 because any impossible value like a negative
count can be used as a sentinel (as these things are known), but using a
null pointer where a string is expected will be recognised for what it
is by everyone reading your code.

You can, just about, test for *p being "all zeros" but it's not worth
trying.  For one thing structs can have padding that might be non-zero!

-- 
Ben.

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

#164700

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Meredith Montgomery <mmontgomery@levado.to> writes:
>
>> 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:
>>
>> 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}
>> };
>>
>>
>> Here's a procedure to lookup a word in this table:
>>
>> 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 */
>> }
>>
>> 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.  (Just like a c-string.)  (I suppose.)
>
> Eek!  No, that does not happen.  You will be tricked by the fact that
> your code will often work because zeros are so common, but you need to
> add a final
>
>   { 0, 0 }
>
> entry to the table.

That's right.  Lesson learned!

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

#164704

On 1/28/22 17:23, Ben Bacarisse wrote:
> Meredith Montgomery <mmontgomery@levado.to> writes:
...
>> 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}
>> };
...
>> 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. (Just like a c-string.) (I suppose.)
>
> Eek! No, that does not happen. You will be tricked by the fact that
> your code will often work because zeros are so common, but you need to
> add a final
>
> { 0, 0 }

Note, however, that something similar can happen. If he had specified
that table has 12 or more elements, "all subobjects that are not
initialized explicitly shall be initialized implicitly the same as
objects that have static storage duration." (6.7.9p19). For pointers,
that means a null pointer (6.7.9p10).

Of course, explicitly adding a {0,0} at the end is a better solution, as
it works regardless of the number of initializers.

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

#164693

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>>. 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
-- 
Lew Pitcher
"In Skills, We Trust"

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

#164694

On Fri, 28 Jan 2022 22:27:22 +0000, 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++) {

Gawd, I shouldn't post on an empty stomach. And, I'm too used to using 
char pointers that I forgot about array entry length computations.
(Excuses, excuses... mea culpa)

I meant
  for ( p = table; p < (struct kw *)((char *)table + sizeof table); p++) {
because
  1) pointers increment by the size of the thing they are pointing to
     so, here, we have to make (table + sizeof table) increment in
     char rather than struct kw, so we coerce <<table>> into char
  2) pointers compare to pointers of the same type, so we must coerce
     the results of ((char *)table + sizeof table) /back/ into a
     struct kw * before we compare to <<p>>

Yah. I'll shut up now.
-- 
Lew Pitcher
"In Skills, We Trust"

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

#164706

Lew Pitcher <lew.pitcher@digitalfreehold.ca> writes:

> On Fri, 28 Jan 2022 22:27:22 +0000, Lew Pitcher wrote:
>
>> On Fri, 28 Jan 2022 18:16:15 -0300, Meredith Montgomery wrote:

>>> 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 */
>>> }

> Gawd, I shouldn't post on an empty stomach. And, I'm too used to using 
> char pointers that I forgot about array entry length computations.
> (Excuses, excuses... mea culpa)
>
> I meant
>   for ( p = table; p < (struct kw *)((char *)table + sizeof table); p++) {
> because
>   1) pointers increment by the size of the thing they are pointing to
>      so, here, we have to make (table + sizeof table) increment in
>      char rather than struct kw, so we coerce <<table>> into char
>   2) pointers compare to pointers of the same type, so we must coerce
>      the results of ((char *)table + sizeof table) /back/ into a
>      struct kw * before we compare to <<p>>

But, as has been pointed out, table is a pointer here, not an array, so
sizeof table is of no use at all, no matter how you scale it.

However, when you really /do/ have an array called table, the usual way
to get its size is to write sizeof table / sizeof *table.  That's
clearer, in my opinion, than casting pointer types.

Second however, since I'm a bit odd, I would write (&table)[1] to get a
pointer just past the end of the array:

  for (struct kw *p = table; p < (&table)[1]; p++) ...

To the OP: remember, this does not work inside a function where you
have a pointer to the first element, rather than an array proper: table
is the name of an array outside the lookup function, but it's a pointer
inside it.

I've been caught out by this, so I always avoid parameter names that
shadow array names.  gcc even has a warning you can turn on for this,
though it is more general than I'd like.

-- 
Ben.

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

#164735

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Lew Pitcher <lew.pitcher@digitalfreehold.ca> writes:
>
>> On Fri, 28 Jan 2022 22:27:22 +0000, Lew Pitcher wrote:
>>
>>> On Fri, 28 Jan 2022 18:16:15 -0300, Meredith Montgomery wrote:
>
>>>> 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 */
>>>> }
>
>> Gawd, I shouldn't post on an empty stomach. And, I'm too used to using 
>> char pointers that I forgot about array entry length computations.
>> (Excuses, excuses... mea culpa)
>>
>> I meant
>>   for ( p = table; p < (struct kw *)((char *)table + sizeof table); p++) {
>> because
>>   1) pointers increment by the size of the thing they are pointing to
>>      so, here, we have to make (table + sizeof table) increment in
>>      char rather than struct kw, so we coerce <<table>> into char
>>   2) pointers compare to pointers of the same type, so we must coerce
>>      the results of ((char *)table + sizeof table) /back/ into a
>>      struct kw * before we compare to <<p>>
>
> But, as has been pointed out, table is a pointer here, not an array, so
> sizeof table is of no use at all, no matter how you scale it.
>
> However, when you really /do/ have an array called table, the usual way
> to get its size is to write sizeof table / sizeof *table.  That's
> clearer, in my opinion, than casting pointer types.
>
> Second however, since I'm a bit odd, I would write (&table)[1] to get a
> pointer just past the end of the array:
>
>   for (struct kw *p = table; p < (&table)[1]; p++) ...

You taught me this already in previous threads --- one where I had a
pointer to an array of 13 chars.  (You showed this solution then.  I
then commented on the terminology of ``end of the array''.)  I was
bitten there that by adding one to that pointer it advanced 13 chars and
I couldn't see why.  The lesson there was that a pointer has a type that
must be noticed.  Pointer arithmetic is dependent upon the type of the
pointer.  My intuition of what a pointer is improved immensely.

> To the OP: remember, this does not work inside a function where you
> have a pointer to the first element, rather than an array proper: table
> is the name of an array outside the lookup function, but it's a pointer
> inside it.

That's right --- I was bitten by that in this case.  The macro

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

happens to do 8/16 == 0 in that procedure where table is a pointer.
That /struct kw/ happens to occupy 16 bytes in my system.  Alignment
reasons, I suppose.  The members themselves should occupy 8 + 4 bytes
in my system because I have a pointer to char and an int.

struct kw {
  char *word; 
  int count;
};

> I've been caught out by this, so I always avoid parameter names that
> shadow array names.  gcc even has a warning you can turn on for this,
> though it is more general than I'd like.

I might just start doing the same because I did fall for the same and it
probably took me over an hour to realize the trouble.  (Learning
immensely lately.)

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

#164736

On 30/01/2022 13:23, Meredith Montgomery wrote:
> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> 
>> Lew Pitcher <lew.pitcher@digitalfreehold.ca> writes:
>>
>>> On Fri, 28 Jan 2022 22:27:22 +0000, Lew Pitcher wrote:
>>>
>>>> On Fri, 28 Jan 2022 18:16:15 -0300, Meredith Montgomery wrote:
>>
>>>>> 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 */
>>>>> }
>>
>>> Gawd, I shouldn't post on an empty stomach. And, I'm too used to using
>>> char pointers that I forgot about array entry length computations.
>>> (Excuses, excuses... mea culpa)
>>>
>>> I meant
>>>    for ( p = table; p < (struct kw *)((char *)table + sizeof table); p++) {
>>> because
>>>    1) pointers increment by the size of the thing they are pointing to
>>>       so, here, we have to make (table + sizeof table) increment in
>>>       char rather than struct kw, so we coerce <<table>> into char
>>>    2) pointers compare to pointers of the same type, so we must coerce
>>>       the results of ((char *)table + sizeof table) /back/ into a
>>>       struct kw * before we compare to <<p>>
>>
>> But, as has been pointed out, table is a pointer here, not an array, so
>> sizeof table is of no use at all, no matter how you scale it.
>>
>> However, when you really /do/ have an array called table, the usual way
>> to get its size is to write sizeof table / sizeof *table.  That's
>> clearer, in my opinion, than casting pointer types.
>>
>> Second however, since I'm a bit odd, I would write (&table)[1] to get a
>> pointer just past the end of the array:
>>
>>    for (struct kw *p = table; p < (&table)[1]; p++) ...
> 
> You taught me this already in previous threads --- one where I had a
> pointer to an array of 13 chars.  (You showed this solution then.  I
> then commented on the terminology of ``end of the array''.)  I was
> bitten there that by adding one to that pointer it advanced 13 chars and
> I couldn't see why.

It /is/ difficult to see why. I believe that if you have to stop and 
think about something, then you ought to find a different way of doing 
it. Others may be confused too.

Or at least, use a macro:

   #define ENDOF(table) ((&table)[1])   // address of last+1 element

Then it can be used like this:

#include <stdio.h>

   int main(void) {
       int table[] = {10,20,30,40};

       for (int* p = table; p < ENDOF(table); ++p) {
           printf("%d\n", *p);
       }
   }

Although I would personally avoid one past the last element business, 
and do it like this:

   #define ENDOF(table) (&table[(sizeof(table)/sizeof(table[0])-1)])

   int main(void) {
       int table[] = {10,20,30,40};

       for (int* p = table; p <= ENDOF(table); ++p) {
           printf("%d\n", *p);
       }
   }

Now ENDOF is the actual last element, not the following one. (This 
requires 'table' to be a proper, dimensioned array; probably the first 
does too, but that's harder to see.)

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

#164696

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
> 

[toc] | [prev] | [standalone]

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

csiph-web