Keyword counting with structures

Good morning. I have two problems: The program isn't printing the members of the key structure and I don't know how exactly the for below works because keytab + NKEYS is a bit strange to me (iterating with the condition that the pointer has to be less than the structure array + the nkeys ? how's that?)

Code:

---

  for(p = keytab; p < keytab + NKEYS; p++)

---

Code:

---

struct key {
 
  char* word;
  int count;   
   
} keytab[] = {
   
    "auto", 0,
    "break", 0,
    "case", 0,
    "char", 0,
    "const", 0,
    "continue", 0,
    "default", 0,
    "unsigned", 0,
    "void", 0,
    "volatile", 0,
    "while", 0
 };
 
  #include <stdio.h>
  #include <ctype.h>
  #include <string.h>
 
 #define MAXWORD 100
 #define NKEYS (sizeof keytab / sizeof keytab[0])
 #define BUFSIZE 100
 
 char buf[BUFSIZE];
 int bufp = 0;
 
 int getword(char*, int);
 struct key* binsearch(char*, struct key*, int);
 int getch(void);
 void ungetch(int);         
 
/* the program counts how many times
    a word from the structure array appears
    and outputs the words and the respective count.
 */

int main()
{
  char word[MAXWORD];
  struct key* p;
  while(getword(word, MAXWORD) != EOF)
    if(isalpha(word[0]))
    if((p = binsearch(word, keytab, NKEYS)) != NULL)
      p->count++;
  for(p = keytab; p < keytab + NKEYS; p++)
    if(p->count > 0)
        printf("%4d %s\n", p->count, p->word);     
  return 0;
}               

/* binsearch: find word in tab[0]...tab[n-1] */
struct key* binsearch(char* word, struct key* tab, int n)
{
  int cond;
  struct key* low = &tab[0];
  struct key* high = &tab[n];
  struct key* mid;
 
  while(low < mid)
  {
    mid = low + (high-low) / 2; 
    if((cond = strcmp(word, mid->word)) < 0)
      high = mid - 1;
    else if(cond > 0)
      low = mid + 1;
    else
      return mid;   
  }
  return NULL;         
}         

int getch(void) /* get a (possibly pushed back) character */
{
  return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c) /* push character back on input */
{
  if(bufp >= BUFSIZE)
    printf("ungetch: too many characters\n");
  else
    buf[bufp++] = c;
}

/* getword: get next word or character from input */
int getword(char* word, int lim)
{
  int c, getch(void);
  void ungetch(int);
  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];               
}

---

Array names in many uses decay to a pointer to their first element.

So, in the expression p = keytab, p gets assigned the address of the first element of the array;

In the expression keytab + NKEYS, p decays and it's then just pointer arithmetic (the effect is the same as &keytab[NKEYS]).

The third expression in the for, is just plain pointer arithmetic. It gets p to point to each successive member of the array.

Quote:

---

Originally Posted by thames

keytab + NKEYS is a bit strange to me (iterating with the condition that the pointer has to be less than the structure array + the nkeys ? how's that?)

---

It is pointer arithmetic.

p is a pointer to a struct key, right? p = keytab starts the loop by setting it to the start of the keytab array.

p++ advances the pointer p by one structure. Remember, (p + 5) and &p[5] are the exact same thing: pointers to the sixth structure counting from p .

So, keytab + NKEYS is the same as &keytab[NKEYS] and is the pointer to the NKEYS'th element in the array. It is perfectly valid for a pointer to point to just after the array like that in C.

Edit: qny beat me to the explanation.

Quote:

---

Originally Posted by thames

The program isn't printing the members of the key structure

---

The reason is your faulty binary search:

Code:

---

/* binsearch: find word in tab[0]...tab[n-1] */
struct key* binsearch(char* word, struct key* tab, int n)
{
  int cond;
  struct key* low = &tab[0];
  struct key* high = &tab[n];

---

"high" points to an element just outside your array because you call binsearch() with NKEYS. NKEYS is the number of elements in your array and when you start indexing with 0 (as C does), the last valid index is number of elements - 1. Try your program with an input which compares bigger than "while" (e.g. "x") and you will probably get an seg fault.

Code:

---

  struct key* mid;
 
  while(low < mid)

---

At the first iteration, "mid" is uninitialized. But the real problem is, that your condition is wrong. You have to loop as long as low <= high (or high >= low)
See https://en.wikipedia.org/wiki/Binary...ithm#Iterative

Bye, Andreas

You're awesome people. Many thanks.