Est-ce une bonne et portable moyen de vérifier si 2 c-les chaînes de chevauchement dans la mémoire?

Question

Peut-être pas la manière la plus efficace, mais est-il correct et portable?

int are_overlapping(const char *a, const char *b) {
  return (a + strlen(a) == b + strlen(b));
}

Pour clarifier les choses: ce que je cherche est de chevauchement dans la mémoire, non pas dans le réel contenu. Par exemple:

const char a[] = "string";
const char b[] = "another string";
are_overlapping(a, b); // should return 0
are_overlapping(a, a + 3); // should return 1

Answer 1

Oui, votre code est correct. Si deux chaînes de fin à l'exemple de la place ils ont, par définition, se chevauchent - ils partager la même terminateur null. Soit les deux chaînes sont identiques, l'un est une sous-chaîne de l'autre.

Tout à propos de votre programme est parfaitement bien défini comportement, donc en supposant conforme aux normes des compilateurs, il doit être parfaitement portable.

Le tbi pertinent dans la norme est de 6.5.9 opérateurs d'Égalité (l'emphase est mienne):

Deux pointeurs de comparer l'égalité si et seulement si les deux sont des pointeurs nuls, tous les deux sont des pointeurs vers le même objet (y compris un pointeur vers un objet et un sous-objet à ses débuts) ou de la fonction, les deux sont des pointeurs vers un passé le dernier élément de la même matrice de l'objet, ou l'un est un pointeur vers un passé la fin d'un tableau d'objet, et l'autre est un pointeur sur le début d'un autre objet tableau qui arrive à suivre immédiatement le premier tableau de l'objet dans l'espace d'adressage.

Answer 2

La réflexion sur zdan, les commentaires de mon précédent post (qui sera probablement bientôt être supprimé), je suis arrivé à la conclusion que la vérification des points de terminaison est suffisant.

Si il y a un chevauchement, le terminateur null fera que les deux chaînes ne pas être distinctes. Regardons quelques possibilités.

Si vous commencez avec

a 0x10000000 "Hello" and somehow add
b 0x10000004 "World",

vous aurez un seul mot: HellWorld, depuis le W serait de remplacer le \0. Ils seraient au même point de terminaison.

Si vous écrivez à un même point de départ:

a 0x10000000 "Hello" and
b 0x10000000 "Jupiter"

Vous aurez le mot de Jupiter, et ont le même effet.

Est-il un cas où vous pouvez avoir le même effet et ne pas avoir de chevauchement? Genre de.

a = 0x1000000 "Four" and
b = 0x1000004 "".

Qui donnera un chevauchement.

Je ne peux pas penser à tout moment, vous aurez le chevauchement où vous n'aurez pas de correspondance des points de terminaison - en supposant que vous êtes en train de rédiger une valeur null chaînes dans la mémoire.

Donc, la réponse courte: Oui, votre chèque est bien suffisant.

Answer 3

Il n'est probablement pas pertinent à votre cas d'utilisation, comme votre question est précisément à propos de C-strings, mais le code ne fonctionnera pas dans le cas où les données ont intégré NUL octets dans les cordes.

char a[] = "abcd\0ABCD";
char *b = a + 5;

Autre que cela, votre solution est simple et correcte. Elle travaille depuis que vous êtes seulement en utilisant == pour le pointeur de la comparaison, et conformément à la norme (à partir de C11 6.5.9/6)

Deux pointeurs de comparer l'égalité si et seulement si les deux sont des pointeurs nuls, tous les deux sont des pointeurs vers le même objet (y compris un pointeur vers un objet et un sous-objet à ses débuts) ou de la fonction, les deux sont des pointeurs vers un passé le dernier élément de la même matrice de l'objet ou de l'un est un pointeur vers un passé la fin d'un tableau d'objet, et l'autre est un pointeur sur le début d'un autre objet tableau qui arrive à suivre immédiatement le premier tableau de l'objet dans l'espace d'adressage.

Toutefois, les opérateurs relationnels sont plus strictes (à partir de C11 6.5.8/5):

Lorsque deux pointeurs sont comparés, le résultat dépend de la position dans l'espace d'adressage des objets pointés. Si deux pointeurs de types d'objets pointent vers le même objet, ou à la fois un point après le dernier élément de la même matrice de l'objet, ils le comparent à l'égalité. Si les objets pointés sont membres de la même agrégat d'objets, des pointeurs de structure membres déclaré, plus tard, de comparer plus de pointeurs vers les membres déclaré plus tôt dans la structure, et des pointeurs vers des éléments d'un tableau avec les plus grandes indice des valeurs de comparer plus de pointeurs vers des éléments d'un même tableau avec le moindre indice des valeurs. Tous les pointeurs vers les membres de la même union de l'objet de comparer l'égalité. Si l'expression de P points à un élément d'un tableau d'objet et l'expression de Q points pour le dernier élément de la même matrice de l'objet, le pointeur expression Q+1 compare plus grand que P. Dans tous les autres cas, le comportement est indéfini.

La dernière phrase est la bosse.

Certains m'ont reproché le fait que votre code peut calculer la longueur du chevauchement de deux fois, et ont tenté de prendre d'autres précautions pour l'éviter. Cependant, l'efficacité de la réduction de calcul est contré avec un supplément de pointeur de la comparaison par itération, ou implique pas défini ou de mise en œuvre de comportement défini. En supposant que vous voulez un portable et la conformité de la solution, le gain moyen est susceptible de néant, et n'en vaut pas la peine.

Answer 4

Cette solution est toujours la même pour le pire des cas de la performance, mais il est optimisé pour la frappe -- vous n'avez pas à analyser les deux chaînes.

char * temp_a = a;
char * temp_b = b;

while (*temp_a != '\0') {

    if (temp_a++ == b) 
        return 1;

}

// check for b being an empty string
if (temp_a == b) return 1;

/* but if b was larger, we aren't done, so you have to try from b now */
while (*temp_b != '\0') {
    if (temp_b++ == a)
        return 1;
}

/* don't need the a==b check again here

return 0;

Apparemment, seul le pointeur de l'égalité (pas d'inégalité) est portable en C, donc les solutions suivantes ne sont pas portable -- tout ce qui est ci-dessous avant je le savais.

Votre solution est valable, mais pourquoi calculer strlen sur la deuxième chaîne? Vous savez le début et la fin d'une chaîne, vient de voir si l'autre est entre eux (inclus). vous permet d'économiser de passer à travers la deuxième chaîne -- O(M+N) à O(M)

char * lower_addr_string = a < b ? a : b
char * higher_addr_string = a > b ? a : b
length = strlen(lower_addr_string)
return higher_addr_string >= lower_addr_string && higher_addr_string <= lower_addr_string + length;

sinon, ne la chaîne d'analyse vous-même..

char * lower_addr_string = a < b ? a : b
char * higher_addr_string = a > b ? a : b
while(*lower_addr_string != '\0') {
    if (lower_addr_string == higher_addr_string)
        return 1;
    ++lower_addr_string;
}
/* check the last character */
if (lower_addr_string == higher_addr_string)
    return 1;
return 0;

Answer 5

Oui, votre enregistrement est correct, mais il n'est certainement pas le plus efficace (si par "efficacité" tu veux dire que le calcul de l'efficacité). L'évidence intuitive de l'inefficacité de la mise en œuvre est basée sur le fait que lorsque les chaînes en fait se chevauchent, l' strlen appels itérer sur leur partie commune à deux reprises.

Pour l'amour de la formelle de l'efficacité, on peut utiliser une approche légèrement différente

int are_overlapping(const char *a, const char *b) 
{
  if (a > b) /* or `(uintptr_t) a > (uintptr_t) b`, see note below! */
  {
    const char *t = a; 
    a = b; 
    b = t;
  }

  while (a != b && *a != '\0')
    ++a;

  return a == b;
}

Une remarque importante à propos de cette version est qu'elle effectue relationnel comparaison de deux pointeurs qui ne sont pas garantis pour pointer vers le même tableau, qui a officiellement conduit à un comportement indéfini. Il fonctionnera dans la pratique, sur un système de modèle de mémoire fixe, mais pourrait attirer les critiques de pédant code examinateur. Officiellement contourner ce problème, on pourrait convertir les pointeurs pour uintptr_t avant d'effectuer relationnelle des comparaisons. De cette façon, le comportement indéfini est converti à la mise en œuvre définies par le comportement avec une bonne sémantique pour nos fins, dans la plupart (si pas tous) des implémentations traditionnelles avec le plat de la mémoire de modèle.

Cette approche est libre à partir du "double comptage" problème: il analyse seulement le non-cumul partie de la chaîne qui se trouve "plus haut" dans la mémoire. Bien sûr, dans la pratique, les avantages de cette approche pourrait s'avérer être inexistante. Elle dépendra à la fois de la qualité de votre strlen de la mise en œuvre et l'une des propriétés de l'entrée effective.

Par exemple, dans cette situation

const char *str = "Very very very long string, say 64K characters long......";

are_overlapped(str, str + 1);

ma version de détecter le chevauchement beaucoup plus rapide que la vôtre. Ma version fera dans 1 itération du cycle, tandis que votre version passerons 2 * 64 K itérations (en supposant une implémentation naïve de l' strlen).

Si vous décidez de plonger dans le domaine de l'discutable pointeur de comparaison, l'idée ci-dessus peut également être réimplémentée comme

int are_overlapping(const char *a, const char *b) 
{
  if (a > b)
  {
    const char *t = a; 
    a = b; 
    b = t;
  }

  return b <= a + strlen(a);
}

Cette mise en œuvre ne permet pas de réaliser un supplément de pointeur de la comparaison de chaque itération. Le prix que nous payons pour cela, c'est qu'il a toujours itère jusqu'à la fin de l'une des chaînes au lieu de s'arrêter au début. Pourtant, il est encore plus efficace que votre mise en œuvre, étant donné qu'elle exige strlen qu'une seule fois.