C Tokenizer - Comment ça marche?

Question

Comment cela fonctionne-t-il?

Je sais l'utiliser, vous passez:

• début: string (ex: "Article 1, point 2, point 3")
• delim: délimiteur (par exemple "")
• Tok: référence à une chaîne qui contiendra les
• nextpos jeton (facultatif): référence à une position dans la chaîne d'origine où le jeton suivant commence
• sdelim (en option): pointeur sur un caractère qui tiendra la départ délimiteur du toke n
• edelim (en option): pointeur sur un caractère qui tiendra délimiteur la fin du jeton

code:

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

int token(char* start, char* delim, char** tok, char** nextpos, char* sdelim, char* edelim) { 
    // Find beginning: 
    int len = 0; 
    char *scanner; 
    int dictionary[8]; 
    int ptr; 

    for(ptr = 0; ptr < 8; ptr++) { 
     dictionary[ptr] = 0; 
    } 

    for(; *delim; delim++) { 
     dictionary[*delim/32] |= 1 << *delim % 32; 
    } 

    if(sdelim) { 
     *sdelim = 0; 
    } 

    for(; *start; start++) { 
     if(!(dictionary[*start/32] & 1 << *start % 32)) { 
      break; 
     } 
     if(sdelim) { 
      *sdelim = *start; 
     } 
    } 

    if(*start == 0) { 
     if(nextpos != NULL) { 
      *nextpos = start; 
     } 
     *tok = NULL; 
     return 0; 
    } 

    for(scanner = start; *scanner; scanner++) { 
     if(dictionary[*scanner/32] & 1 << *scanner % 32) { 
      break; 
     } 
     len++; 
    } 

    if(edelim) { 
     *edelim = *scanner; 
    } 

    if(nextpos != NULL) { 
     *nextpos = scanner; 
    } 

    *tok = (char*)malloc(sizeof(char) * (len + 1)); 

    if(*tok == NULL) { 
     return 0; 
    } 

    memcpy(*tok, start, len); 
    *(*tok + len) = 0; 


    return len + 1; 
} 

Je reçois la plupart de l'exception:

dictionary[*delim/32] |= 1 << *delim % 32;

et

dictionary[*start/32] & 1 << *start % 32

Est-ce magique?

Answer 1

Ils stockent lequel les caractères sont produits en faisant une 8 x 32 = 256 table des bits stockés dans le dictionnaire.

dictionary[*delim/32] |= 1 << *delim % 32; 

définit le bit correspondant à * delim

dictionary[*start/32] & 1 << *start % 32 

vérifie le bit

Answer 2

Étant donné que chaque caractère du délimiteur est de 8 bits (sizeof(char) == 1 octet), il est limité à 256 valeurs possibles.

Le dictionnaire est divisé en 8 morceaux (int dictionary[8]), 32 possibilités par pièce (sizeof(int) est> = 4 octets) et 32 ​​* 8 = 256.

Ceci forme une matrice 256 de bits de valeurs. Il active ensuite le drapeau pour chaque caractère du délimiteur (dictionary[*delim/32] |= 1 << *delim % 32;). L'index du tableau est *delim/32, ou la valeur ASCII du caractère est divisée par 32. Puisque la valeur ASCII est comprise entre 0 et 255, cette division donne une valeur de 0 à 7 avec un reste. Le reste est le bit à activer, décidé par l'opération de module. Tout ce qui est fait est de marquer certains bits de la matrice de 256 bits comme vrai, si le caractère ASCII correspondant existe dans le délimiteur.

puis à déterminer si un caractère se trouve dans le délimiteur est simplement une recherche dans la matrice 256 de bit (dictionary[*start/32] & 1 << *start % 32)

Answer 3

OK, donc si nous envoyons dans la chaîne "," pour la delimiter alors dictionary[*delim/32] |= 1 << *delim % 32 sera dictionary[1] = 4096. L'expression dictionary[*start/32] & 1 << *start % 32 vérifie simplement s'il y a un caractère correspondant.

Ce qui m'intrigue est pourquoi ils n'utilisent pas la comparaison directe char.