Qu'advient-il de la mémoire après '\ 0' dans une chaîne C?

Question

Étonnamment simple/stupide/question de base, mais je n'ai aucune idée: Supposons que je veux retourner à l'utilisateur de ma fonction d'un C-string, dont la longueur je ne sais pas au début de la fonction. Je ne pouvez placer qu'une limite supérieure sur la longueur au début, et, selon le traitement, la taille peut se rétrécir.

La question est, est-il quelque chose de mal avec l'allocation de suffisamment d'espace de tas (limite supérieure) et puis la résiliation de la chaîne est bien en deçà de ce que lors de la transformation? c'est à dire Si je m'en tiens un '\0' dans le milieu de la mémoire allouée, n' (un.) free() fonctionnent encore correctement, et (b.) l'espace après le '\0' devenir sans conséquence? Une fois que '\0' est ajouté, la mémoire est juste se retourna, ou est-il assis là, monopolisant l'espace jusqu' free() est appelé? C'est généralement mauvais style de programmation pour quitter cette pendaison de l'espace, dans le but d'économiser de l'avance le temps de programmation le calcul de l'espace nécessaire avant d'appeler malloc?

Pour donner ce contexte, disons que je veux supprimer les doublons consécutifs, comme ceci:

l'entrée "Bonjour oOOOo !!" --> sortie "Helo oOo !"

... et un peu de code ci-dessous montre comment je suis pré-calcul de la taille résultant de mon opération, acquittent efficacement de traitement deux fois pour obtenir la taille de segment de droite.

char* RemoveChains(const char* str)
{
    if (str == NULL) {
        return NULL;
    }
    if (strlen(str) == 0) {
        char* outstr = (char*)malloc(1);
        *outstr = '\0';
        return outstr;
    }
    const char* original = str; // for reuse
    char prev = *str++;       // [prev][str][str+1]...
    unsigned int outlen = 1;  // first char auto-counted

    // Determine length necessary by mimicking processing
    while (*str) {
        if (*str != prev) { // new char encountered
            ++outlen;
            prev = *str; // restart chain
        }
        ++str; // step pointer along input
    }

    // Declare new string to be perfect size
    char* outstr = (char*)malloc(outlen + 1);
    outstr[outlen] = '\0';
    outstr[0] = original[0];
    outlen = 1;

    // Construct output
    prev = *original++;
    while (*original) {
        if (*original != prev) {
            outstr[outlen++] = *original;
            prev = *original;
        }
        ++original;
    }
    return outstr;
}

Answer 1

Si je m'en tiens un '\0' dans le milieu de la mémoire allouée, ne

(un.) free() fonctionnent encore correctement, et

Oui.

(b.) l'espace après le '\0' devenir sans conséquence? Une fois que '\0' est ajouté, la mémoire est juste se retourna, ou est-il assis là, monopolisant l'espace jusqu'à ce que free() est appelée?

Dépend. Souvent, lorsque vous affecter de grandes quantités de mémoire, le système alloue de l'espace d'adressage virtuel - comme vous l'écrivez à la quelques pages de mémoire physique réelle est attribué à l'arrière (et qui plus tard peut obtenir échangé sur le disque lors de votre système d'exploitation a de la mémoire virtuelle à l'appui). Célèbre, cette distinction entre le gaspillage de l'allocation de l'espace d'adressage virtuel et le réel physique/mémoire de swap permet de matrices creuses pour être raisonnablement efficace en terme de mémoire sur ces systèmes d'exploitation.

Maintenant, la granularité de ce virtuel d'adressage et de la pagination en mémoire les tailles de page - qui pourrait être 4k, 8k, 16k...? La plupart des OSs ont une fonction que vous pouvez appeler pour savoir la taille de la page. Donc, si vous faites beaucoup de petites allocations ensuite arrondi à l'tailles de page, c'est du gaspillage, et si vous disposez d'un espace d'adressage limité par rapport à la quantité de mémoire dont vous avez vraiment besoin d'utiliser ensuite en fonction virtuelle à aborder de la manière décrite ci-dessus ne sont pas à l'échelle (par exemple, 4 go de RAM avec l'adressage 32 bits). D'autre part, si vous avez une version 64 bits de processus en cours d'exécution à dire 32 go de RAM, et font relativement peu de ces allocations de chaîne, vous avez une énorme quantité d'espace d'adressage virtuel pour jouer avec et l'arrondi à la taille de la page ne sera pas d'une grande utilité.

Mais attention à la différence entre l'écriture à travers le tampon puis, mettant fin à un moment antérieur (dans ce cas, une fois écrit à la mémoire aura la sauvegarde de la mémoire et pourrait se retrouver dans la swap) au lieu d'avoir un gros tampon sur lesquelles vous ne jamais écrire le premier bit alors à l'arrêt (dans ce cas, la sauvegarde de la mémoire est allouée pour l'espace utilisé arrondi à la taille de la page).

Il est également intéressant de souligner que sur de nombreux systèmes d'exploitation de segment de mémoire ne peuvent pas être retournés pour le Système d'Exploitation jusqu'à la fin du processus: au lieu de cela, la fonction malloc/free bibliothèque informe le système d'exploitation lorsqu'il a besoin pour grandir le tas (par exemple à l'aide de sbrk() sur UNIX ou VirtualAlloc() sur Windows). En ce sens, free() de la mémoire est libre pour votre processus de ré-utiliser, mais pas pour d'autres processus à utiliser. Certains Systèmes d'Exploitation ne l'optimiser - par exemple, à l'aide d'un distincte et indépendante releasble région de mémoire pour les très grandes affectations.

C'est généralement mauvais style de programmation pour quitter cette pendaison de l'espace, dans le but d'économiser de l'avance le temps de programmation le calcul de l'espace nécessaire avant d'appeler malloc?

Encore une fois, cela dépend du nombre de ces allocations, vous avez affaire. Si il y a un grand nombre par rapport à votre espace d'adressage virtuel / RAM - vous voulez explicitement permettre la bibliothèque de la mémoire sais pas tout de l'origine de la demande de mémoire est nécessaire à l'aide de realloc(), ou vous pouvez même utiliser strdup() d'allouer un nouveau bloc plus étroitement basée sur les besoins réels (alors free() l'original) - en fonction de votre malloc/free bibliothèque de la mise en œuvre, qui pourrait travailler mieux ou pour le pire, mais très peu d'applications qui seraient fortement touchées par la différence.

Parfois, votre code peut être dans une bibliothèque, où vous ne pouvez pas deviner combien d'instances de chaîne à l'appel de l'application gestion - dans de tels cas, il est préférable de fournir plus lent comportement qui ne fait jamais trop de mal... donc pencher vers le rétrécissement des blocs de mémoire pour s'adapter à la chaîne de données (un certain nombre d'opérations supplémentaires afin de ne pas affecter le big-O de l'efficacité) plutôt que d'avoir une proportion inconnue de la chaîne d'origine tampon perdue (dans un cas pathologique - zéro ou un caractère utilisé après arbitrairement grandes affectations). Comme un rapport d'optimisation des performances, vous pourriez ne vous embêtez pas le retour de la mémoire si unusued espace est >= à l'espace utilisé dans l'accord sur le goût, ou faire de l'appelant-configurable.

- Vous faire un commentaire sur une autre réponse:

Il descend donc à même de juger si le realloc prendra plus de temps, ou le prétraitement détermination de la taille?

Si la performance est votre priorité, alors oui - vous voulez le profil. Si vous n'êtes pas dépendant du PROCESSEUR, alors que, en règle générale, prendre la "prétraitement" frapper et faire une bonne taille de l'allocation - il y a un peu moins de la fragmentation et le désordre. Lutte contre, si vous avez à écrire un prétraitement spécial mode pour certains fonction - c'est une "surface" et les erreurs de code à maintenir. (Ce compromis décision est souvent nécessaire lors de la mise en œuvre de votre propre asprintf() de snprintf(), mais au moins vous pouvez faire confiance snprintf() d'agir comme documenté et ne doivent pas personnellement à l'entretenir).

Answer 2

Une fois que '\0' est ajouté, la mémoire est juste se retourna, ou est-il assis là, monopolisant l'espace jusqu'à ce que free() est appelée?

Il n'y a rien de magique, \0. Vous appelez realloc si vous voulez "rétrécir" la mémoire allouée. Sinon, la mémoire va rester là jusqu'à ce que vous appelez free.

Si je m'en tiens un '\0' dans le milieu de la mémoire allouée, n' (un.) free() fonctionnent encore correctement

Tout ce que vous faites dans ce mémoire free fonctionnera correctement si vous passer exactement le même pointeur retourné par malloc. Bien sûr, si vous écrire en dehors de cela, tous les paris sont éteints.

Answer 3

\0 est juste un caractère de plus de malloc et free point de vue, ils ne se soucient pas ce que les données que vous mettez dans la mémoire. Donc, free continuera de fonctionner si vous ajoutez \0 dans le milieu ou ne pas ajouter \0 . L'espace alloué sera toujours là, il ne sera pas retourné à la procédure dès que vous ajoutez \0 à la mémoire. Personnellement, je préfère d'allouer seulement à la quantité de mémoire au lieu de les allouer à une certaine limite supérieure que ce sera juste gaspillage de la ressource.

Answer 4

Dès que vous obtenez de la mémoire de tas en appelant malloc (), la mémoire vous appartient. Insérer \ 0, c'est comme insérer n'importe quel autre caractère. Cette mémoire restera en votre possession jusqu'à ce que vous la libériez ou que OS le récupère.

Answer 5

Le \0 est une convention pure pour interpréter les tableaux de caractères comme des piqûres - il est indépendant de la gestion de la mémoire. En d'autres termes, si vous souhaitez récupérer votre argent, vous devez appeler realloc . La chaîne ne se soucie pas de la mémoire (source de nombreux problèmes de sécurité).