Dubbio su strtok

di il
12 risposte

Dubbio su strtok

Parlando di standard c89/90 (scelta obbligata) ho difficoltà a capire il seguente algoritmo che utilizza la funzione strtok dove deve dividere una stringa in linee  e ogni linea a sua volta in parole senza far uso dell'amica strtok_r che aderisce allo standard posix e non rispetterebbe lo standard prima citato.

Mi sono letto un po' di info sulla strtok, credo di aver chiaro come funziona ma nonostante ciò non mi torna questo codice:

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

int main ()
{
  char str[] = "a;b;c;d;e\nf;g;h;i;j\n1;2;3;4;5\n";
  char *line;
  char *token;
  char buf[256];

  for (line = strtok (str, "\n");  line != NULL; line = strtok (line + strlen (line) + 1, "\n"))
  {
      strncpy (buf, line, sizeof (buf));
      printf ("Line: %s\n", buf);
      for (token = strtok (buf, ";");  token != NULL;  token = strtok (token + strlen (token) + 1, ";"))
          printf ("\tToken: %s\n", token);
  }
  return 0;
}

in paarticolare non mi torna in entrambi i for questa porzione di codice:

line = strtok (line + strlen (line) + 1, "\n")
token = strtok (token + strlen (token) + 1, ";")

Se p.e. ci focalizziamo nella primo for, che si occupa di separare le righe utilizzando come delimitatore “\n”, e controlliamo gli effetti della funzione strtok:

1o step del for:

str -  >   "a;b;c;d;e\0f;g;h;i;j\n1;2;3;4;5\n"

line -  >   "a;b;c;d;e\0"

2o step del for:

str -  >   "a;b;c;d;e\0f;g;h;i;j\01;2;3;4;5\n"

line -  >   "f;g;h;i;j\0"

3o step del for:

str -  >   "a;b;c;d;e\0f;g;h;i;j\01;2;3;4;5\0"

line -  >   "1;2;3;4;5\0"

4o step del for:

str -  >   "a;b;c;d;e\0f;g;h;i;j\01;2;3;4;5\0"

line -  >   &str[30]      !?!??!?!

considerando che 

str[28] = ‘5’

str[29] = ‘\0’

line dovrebbe puntare al carattere di str che si trova dopo l'ultimo ‘\0’, per cui quel carattere è indefinito, non sappiamo cosa ci sia in memoria ed il comportamento dell'algoritmo non è prevedibile.

La stessa cosa, a mio avviso, accade quando il secondo for ha terminato di analizzare l'ultima parola della stringa.

Questo codice va bene fintanto non hai completato l'analisi dell'ultimo token.

cosa ne pensate ?' 

12 Risposte

  • Re: Dubbio su strtok

     A str[30] c'è obbligatoriamente uno zero, altrimenti la tua stringa letterale sarebbe senza terminatore.

    Piuttosto è questionabile fare la copia dei token, dato che strtok “sporca” già la stringa di partenza.

    #include <string.h>
    #include <stdio.h>
    
    int main ()
    {
      char str[] = "a;b;c;d;e\nf;g;h;i;j\n1;2;3;4;5\n";
      char *line, *token;
      int  len;
    
      for (line = strtok (str, "\n");  line != NULL; line = strtok (line + len + 1, "\n"))
      {
          len = strlen(line);
          printf ("Line: %s\n", line);
          for (token = strtok (line, ";");  token != NULL;  token = strtok (NULL, ";"))
               printf ("\tToken: %s\n", token);      
      }
      return 0;
    }
  • Re: Dubbio su strtok

    26/06/2023 - Weierstrass ha scritto:


     A str[30] c'è obbligatoriamente uno zero, altrimenti la tua stringa letterale sarebbe senza terminatore.

    Giusto, ho fatto male i conti ma non credo sposti il concetto:

    str[0] = ‘a’   str[1] = ‘;’   str[2] = ‘b’   str[3] = ‘;’   str[4] = ‘c’   str[5] = ‘;’   str[6] = ‘d’   str[7] = ‘;’   str[8] = ‘e’   str[9] = ‘\n’   str[10] = ‘f’   str[11] = ‘;’

    str[12] = ‘g’   str[13] = ‘;’   str[14] = ‘h'’   str[15] = ‘;’   str[16] = ‘i’   str[17] = ‘;’   str[18] = ‘j’   str[19] = ‘\n’   str[20] = ‘1’   str[21] = ‘;’   str[22] = ‘2’

    str[23] = ‘;’   str[24] = ‘3’   str[25] = ‘;’   str[26] = ‘4’   str[27] = ‘;’   str[28] = ‘5’   str[29] = ‘\n’   str[30] = ‘\0’

    la lunghezza di str escludendo il carattere \0 è 30 (da str[0] a str[29] per cui line = strtok (line + len + 1, "\n") equivale a line = strtok (line + 31, "\n") ; il primo parametro (line+31) risulta str[31] che a me risulta non determinabile poichè oltre la fine della stringa, giusto ? 

    Line + len +1 = punta sempre al carattere successivo al delimitatore, che nel caso dell'ultimo token, non si conosce perchè la stringa è termina prima.

    E' giusto cio' che dico ?

  • Re: Dubbio su strtok

    Premetto che non so come sia effettivamente strutturata la funzione strtok(), ma ipotizzo che un'implementazione del genere possa aggirare il “problema” a cui fai riferimento:

    #include <stdio.h>
    
    char* my_strtok(char *str, const char delimiter)
    {
        static char *current;
        char *token = NULL;
        if(str)
        {
            current = str;
        }
        for(; *current; ++current)
        {
            if(*current == delimiter)
            {
                if(token)
                {
                    *current++ = '\0';
                    break;
                }
            }
            else if(!token)
            {
                token = current;
            }
        }
        return token;
    }
    
    int main()
    {
        char str[] = "..ab.c....def";
        for(char *p = NULL; p = my_strtok(p ? NULL : str, '.');  printf("%s\n", p));
        return 0;
    }


    Ovviamente è probabile che la funzione originale sfrutti un approccio diverso per evitare di andare a leggere zone di memoria non allocate, il mio è solo un esempio.

  • Re: Dubbio su strtok

    26/06/2023 - zio_mangrovia ha scritto:


    26/06/2023 - Weierstrass ha scritto:


     A str[30] c'è obbligatoriamente uno zero, altrimenti la tua stringa letterale sarebbe senza terminatore.

    Giusto, ho fatto male i conti ma non credo sposti il concetto:

    str[0] = ‘a’   str[1] = ‘;’   str[2] = ‘b’   str[3] = ‘;’   str[4] = ‘c’   str[5] = ‘;’   str[6] = ‘d’   str[7] = ‘;’   str[8] = ‘e’   str[9] = ‘\n’   str[10] = ‘f’   str[11] = ‘;’

    str[12] = ‘g’   str[13] = ‘;’   str[14] = ‘h'’   str[15] = ‘;’   str[16] = ‘i’   str[17] = ‘;’   str[18] = ‘j’   str[19] = ‘\n’   str[20] = ‘1’   str[21] = ‘;’   str[22] = ‘2’

    str[23] = ‘;’   str[24] = ‘3’   str[25] = ‘;’   str[26] = ‘4’   str[27] = ‘;’   str[28] = ‘5’   str[29] = ‘\n’   str[30] = ‘\0’

    la lunghezza di str escludendo il carattere \0 è 30 (da str[0] a str[29] per cui line = strtok (line + len + 1, "\n") equivale a line = strtok (line + 31, "\n") ; il primo parametro (line+31) risulta str[31] che a me risulta non determinabile poichè oltre la fine della stringa, giusto ? 

    Line + len +1 = punta sempre al carattere successivo al delimitatore, che nel caso dell'ultimo token, non si conosce perchè la stringa è termina prima.

    E' giusto cio' che dico ?

    Ma non ce l'hai il debugger? Quand'è che len diventa 30 che la strtok ci piazza degli zeri in mezzo?

  • Re: Dubbio su strtok

    27/06/2023 - Weierstrass ha scritto:


    Ma non ce l'hai il debugger? Quand'è che len diventa 30 che la strtok ci piazza degli zeri in mezzo?

    Hai ragione la strtok altera la stringa originale sostituendo il delimitatore con il carattere di fine stringa ma secondo me non sposta di una virgola il problema perchè se prendiamo in esame solo l'ultimo token e la lunghezza dello stesso + 1 andiamo oltre la fine della stringa.

    supposto di essere in questa condizione dove è stata chiamata + volte la strtok 

    str[] = "a;b;c;d;e\0f;g;h;i;j\01;2;3;4;5\0";

    la stringa in verde è lunga 9

    quindi il puntatore è fatto avanzare di 10 e si sposterebbe nella posizione contrassegnata dal colore rosa:

    str[] = "a;b;c;d;e\0f;g;h;i;j\01;2;3;4;5\0 ";

    Ovviamente queste deduzioni sono state dedotte e verificate con GDB

    line = strtok (line + len + 1, "\n")

    ovviamente non voglio risolvere il problema con la strtok per forza ma mi ero impuntato di comprendere questo codice aldilà che fosse scorretto, non puoi voltare pagina se prima non hai chiaro quello che è stato fatto prima.

    Grazie

  • Re: Dubbio su strtok

    @zio_mangrovia dubito che la strtok() vada a leggere zone di memoria non allocate. Non so se hai letto il mio precedente post, ma comunque nella funzione my_strtok() ho implementato uno dei vari modi in cui è possibile aggirare il “problema” a cui ti stai riferendo.

  • Re: Dubbio su strtok

    27/06/2023 - Nippolo ha scritto:


    @zio_mangrovia dubito che la strtok() vada a leggere zone di memoria non allocate. Non so se hai letto il mio precedente post, ma comunque nella funzione my_strtok() ho implementato uno dei vari modi in cui è possibile aggirare il “problema” a cui ti stai riferendo.

    volevo essere confortato dal fatto che effettivamente quello a cui mi sto riferendo è un problema, che la mia analisi è corretta indipendentemtne dalla soluzione.

    Grazie per l'escamotage

  • Re: Dubbio su strtok

    Lo spazio in rosa che indichi ha uno zero esattamente come detto all'inizio. Ci sono due zeri dopo il 5 alla fine di tutto!

    Forse è meglio se riprendi in mano la teoria.

    Oppure segui il consiglio di nippolo e fai tutto a manazza

  • Re: Dubbio su strtok

    Ho riletto meglio la discussione e confermo  che per la stringa riportata non c'è alcun problema di accesso a zone di memoria non allocate, infatti, riprendendo il codice iniziale di @zio_mangrovia

    #include <string.h>
    #include <stdio.h>
    
    int main()
    {
        char str[] = "a;b;c;d;e\nf;g;h;i;j\n1;2;3;4;5\n";
        char *line;
        char *token;
        char buf[256];
    
        printf("strlen(str) = %d\n", strlen(str));
    
        for(line = strtok(str, "\n"); line != NULL; line = strtok(line + strlen(line) + 1, "\n"))
        {
            strncpy(buf, line, sizeof(buf));
            printf("\nLine: %s\n", buf);
            for(token = strtok(buf, ";"); token != NULL; token = strtok(token + strlen(token) + 1, ";"))
            {
                printf("\tToken: %s\n", token);
            }
            printf("\nPROSSIMO ACCESSO str[%d]\n", line + strlen(line) + 1 - str);
        }
        return 0;
    }

    si ottiene il seguente output:

    strlen(str) = 30
    
    Line: a;b;c;d;e
            Token: a
            Token: b
            Token: c
            Token: d
            Token: e
    
    PROSSIMO ACCESSO str[10]
    
    Line: f;g;h;i;j
            Token: f
            Token: g
            Token: h
            Token: i
            Token: j
    
    PROSSIMO ACCESSO str[20]
    
    Line: 1;2;3;4;5
            Token: 1
            Token: 2
            Token: 3
            Token: 4
            Token: 5
    
    PROSSIMO ACCESSO str[30]


    Ma se invece modifichiamo str rimuovendo il newline finale, allora effettivamente il programma va oltre la fine dell'array:

    strlen(str) = 29
    
    Line: a;b;c;d;e
            Token: a
            Token: b
            Token: c
            Token: d
            Token: e
    
    PROSSIMO ACCESSO str[10]
    
    Line: f;g;h;i;j
            Token: f
            Token: g
            Token: h
            Token: i
            Token: j
    
    PROSSIMO ACCESSO str[20]
    
    Line: 1;2;3;4;5
            Token: 1
            Token: 2
            Token: 3
            Token: 4
            Token: 5
    
    PROSSIMO ACCESSO str[30]
    

    Il codice postato da @Weierstrass giustamente fa a meno della strncpy() e nel for interno utilizza la strtok() in modo “canonico”, ma nel caso di stringa str troncata del newline finale mi sembra presenti lo stesso problema.

  • Re: Dubbio su strtok

    28/06/2023 - Nippolo ha scritto:


    Il codice postato da @Weierstrass giustamente fa a meno della strncpy() e nel for interno utilizza la strtok() in modo “canonico”, ma nel caso di stringa str troncata del newline finale mi sembra presenti lo stesso problema.

    Perfetto e grazie.

    Il tuo codice mi ha aiutato a capire finalmente.

  • Re: Dubbio su strtok

    27/06/2023 - Weierstrass ha scritto:


    Lo spazio in rosa che indichi ha uno zero esattamente come detto all'inizio. Ci sono due zeri dopo il 5 alla fine di tutto!

    Accipicchia ! Bravissimo! Ero caduto nell'unico ' \0'…. il debugger mi ha tratto in inganno perche di zeri ne vedeno tantissimi a fine stringa per cui non ho notato i 2 consecutivi: uno sostituito dalla strtok e l'altro invece già presente per marcare la fine stringa.

    Non c'e' miglior cieco di chi non vuole vedere… mi ero impuntato.

    Grazie di nuovo e soprattutto per la pazienza.

  • Re: Dubbio su strtok

    Comunque, volendo utilizzare un algoritmo simile a quello che hai postato, un modo per evitare di andare oltre la fine dell'array potrebbe essere il seguente:

    #include <stdio.h>
    #include <string.h>
    
    int main ()
    {
        char str[] = "a;b;c;d;e\nf;g;h;i;j\n1;2;3;4;5";
        unsigned int len = strlen(str);
        unsigned int n;
    
        for(char *line = strtok(str, "\n"); line; line = strtok(line + n, "\n"))
        {
            n = strlen(line) + (line + strlen(line) != str + len);
            printf("\nLine: %s\n", line);
            for(char *token = strtok(line, ";"); token; token = strtok(NULL, ";"))
            {
                printf("\tToken: %s\n", token);
            }
        }
        return 0;
    }
Devi accedere o registrarti per scrivere nel forum
12 risposte