circular array implementation

Question

This is my implementation of a circular array so far. It is supposed to store the last 5 commands entered, by entering the 6th command in the place of the 5th and discarding the 1st. What I have managed to do so far is, to able to store the 5 commands and print them out. On the 6th command, I noticed that it goes in the 2nd position (k=1) of the historyArray, but when debugging, k was equal to 0 which would at least push the last command at the top. If you can put me in the right track again, I would appreciate it. Here is part of the code.

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

int main (int argc, char *argv[])
{
    int i=0; 
    int j=0; 
    int k=0;
    int tempIndex = 0;
    int elementCounter = 0;

    char inputString[100];
    char *result=NULL;
    char delims[] = " ";
    char historyArray[5][20] = {0};
    char tokenArray[20][20] ;
    char hCommand[1][20];

    do
    {
         j = 0;

         printf("hshell>");
         gets(inputString);

         //skip writing "history" in historyArray
         if (strcmp(inputString,"history")!= 0)
         {
             strcpy (historyArray[k], inputString);
         }

         k = (k+1) % 5;
         if (elementCounter <= 5)
             elementCounter++;

         // Break the string into parts
         result = strtok(inputString, delims);

         while (result!=NULL)
         {
             strcpy(tokenArray[j], result);
             j++;
             result= strtok(NULL, delims);                  
         }

         if (strcmp(tokenArray[0], "exit") == 0)
             return 0;

         if (strcmp(tokenArray[0], "history") ==  0)
         {
             if (j>1)
             {
                 tempIndex = atoi(tokenArray[j]);
                 puts(tempIndex);
             }
             else
             {
                 for (i=0; i<elementCounter-1;i++)
                     printf("%i. %s\n", i+1, historyArray[i]);
             }
         }
         else
         {
             printf("Command not found\n");
         }
    } while (1);
}

After suggestions (still incomplete):

         j = 0;
         //elementCounter = 0;
         printf("327>");
         gets(inputString);

         strcpy (historyArray[k], inputString);
         k = (k+1) % 5;

        if (elementCounter <= 5)
         {         
          elementCounter++;                
         }

Indigenous

This may or may not be related, but are you confident that your buffers are big enough for any string you'll encounter? If not, then gets and strcpy will lead to overflows. You should investigate fgets and strncpy as "safe" alternatives. – Acidforming

Also, I'm sceptical about the if (elementCounter <= 5); why do you need that? – Acidforming

@OliCharlesworth You are right. I plan on fixing those later on. The if (elementCounter <= 5) is used to count the elements in the array and I used it in the array printing further down the code. It is there so that it does not print more than 5 values. – Indigenous

But what happens when elementCounter reaches 6? Then k will never be updated ever again. – Acidforming

Seems to me that if you were to remove the conditional and do the modular arithmetic when doing the copy, things would be a bit simpler. I.e., you always write to historyArray[k % 5] (incrementing k each time around), k + 1 is always the total number of "commands" entered, and MIN(k + 1, 5) is the number of jobs currently in the array. – Cruiserweight

@OliCharlesworth I also tried putting k = (k+1) % 5; just above if (elementCounter <= 5) but then the value change occurs after position 1 – Indigenous

Updated answer based on expanded code. – Apparition

Answer 1

The bug you describe is occurring because of the lines:

k = (k + 1) % 5;
elementCounter++;

What I see happening:

k initial | calculation | k result  | elementCounter
0           (0 + 1) % 5   1 % 5 = 1   1
1           (1 + 1) % 5   2 % 5 = 2   2
...
4           (4 + 1) % 5   5 % 5 = 0   5
0           (0 + 1) % 5   1 % 5 = 1   5

k is behaving as it's supposed to, as far as I can see. However, when elementCounter is 5, k = 1.

EDIT: The problem that I see is that the latest command is being added at position k, not position 0, which based on your implementation is the most recent command entered (based on the various if clauses, like the one that processes the "exit" and "history" commands). Try this set of commands, using your current algorithm. I expect that the contents of the [Command List] column are what you'll see...

Command # | Command Text | [Command List]
0           (null)         []
1           Login          [Login]
2           History        [Login,History]
3           Skynet         [Login,History,Skynet]
4           ps -al         [Login,History,Skynet,ps -al]
5           Skynet         [Login,History,Skynet,ps -al,Skynet]
6           Exit           [Exit,History,Skynet,ps -al,Skynet]

What you would want to do, is copy elements 0-3, and move them to elements 1-4. Then, insert the new command at position 0 in the historyArray. Thus, your history should look like this after adjusting your algorithm appropriately:

Command # | Command Text | [Command List]
0           (null)         []
1           Login          [Login]
2           History        [History,Login]
3           Skynet         [Skynet,History,Login]
4           ps -al         [ps -al,Skynet,History,Login]
5           Skynet         [Skynet,ps -al,Skynet,History,Login]
6           Exit           [Exit,Skynet,ps -al,Skynet,History]

Apparition

I have posted the full code so you can get a better view at what's happening. – Indigenous

I removed the if clauses and it works as shown in your first table. The thing that strikes me though, is the copying. You say "copy elements 0-3, and move them to elements 1-4", but from what I understand, this should be the opposite, as in, copy the values from index 1-4 in index 0-3 and insert the new command in index 4 (position 5). Which is what you showed in your last table, correct? – Indigenous

If position 4 is going to be the most recent element in the history queue, yes. It will resemble my second table, just the order would be inverted, as new members would always be added to the final position. Of course, that will also complicate your implementation when your array has fewer than five members. – Apparition

please check my answer below and tell me what do you think. – Indigenous

Answer 2

This is I tried and it seems to be working as expected:

             j = 0;
             //elementCounter = 0;
             printf("hshell>");
             gets(inputString);

             strcpy (historyArray[k], inputString);
             k = (k+1) % 5;

            if (elementCounter <= 5)
             {         
              elementCounter++;                
             }

             if (elementCounter ==6)
             {
                k = 5;
                for (i=0; i<5; i++)
                {
                    strcpy(historyArray[i], historyArray[i+1]);
                }
                 strcpy (historyArray[4], inputString);                 
             }

This, basically, checks if the elementCounter becomes 6 (meaning that a 6th command has been entered). If so, it sets k=5 so that the command will be entered at the last position of the array, and then shift the first 4 values up one position leaving index 4 blank. The final step fills the position with the command. It is not the most elegant piece of code but seems to do the trick.

Indigenous

Answer 3

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    long n; 
    long k; 
    long q; 
    scanf("%ld %ld %ld",&n,&k,&q);
    long *a = malloc(sizeof(long) * n);
    long *b = malloc(sizeof(long) * n);
    for(long a_i = 0; a_i < n; a_i++)
    {
       scanf("%ld",&a[a_i]);
    }
    for(long i = 0; i < k; i++)
    {
        b[0] = a[n-1];
        for(long a_i = 1; a_i < n; a_i++)
        {
        b[a_i] = a[a_i-1];
        }
        for(long a_i = 0; a_i < n; a_i++) 
             a[a_i] = b[a_i];
    }
    for(long a0 = 0; a0 < q; a0++) 
   {
    long m; 
    scanf("%ld",&m);
    printf("%ld\n", b[m]);
    }
    return 0;
}

Maiden