Est-fil qsort sécurité?

Question

J'ai un vieux code qui utilise qsort pour trier un MFC CArray des structures, mais je vois le plantage occasionnel que peut être réduit à plusieurs threads appelant qsort en même temps. Le code que je utilise ressemble à quelque chose comme ceci:

struct Foo
{
  CString str;
  time_t t;

  Foo(LPCTSTR lpsz, time_t ti) : str(lpsz), t(ti)
  {
  }
};

class Sorter()
{
public:
    static void DoSort();
    static int __cdecl SortProc(const void* elem1, const void* elem2);
};

...

void Sorter::DoSort()
{
  CArray<Foo*, Foo*> data;
  for (int i = 0; i < 100; i++)
  {
    Foo* foo = new Foo("some string", 12345678);
    data.Add(foo);
  }

  qsort(data.GetData(), data.GetCount(), sizeof(Foo*), SortProc);
  ...
}

int __cdecl SortProc(const void* elem1, const void* elem2)
{
  Foo* foo1 = (Foo*)elem1;
  Foo* foo2 = (Foo*)elem2;
  // 0xC0000005: Access violation reading location blah here
  return (int)(foo1->t - foo2->t);
}

...

Sorter::DoSort();

Je suis sur le point de factoriser ce code horrible à utiliser au lieu std::sort mais me demandais si ce qui précède est en fait dangereux?

EDIT: Sorter::DoSort est en fait une fonction statique, mais utilise pas de variables statiques lui-même

.

EDIT2. La fonction SortProc a été modifiée pour correspondre au code réel

Answer 1

Votre problème ne doit pas nécessairement quelque chose à voir avec le fil saftey.

La fonction de rappel de tri prend en pointeurs pour chaque élément, et non l'élément lui-même. Puisque vous triez Foo* ce que vous voulez vraiment faire est d'accéder aux paramètres comme Foo**, comme ceci:

int __cdecl SortProc(const void* elem1, const void* elem2)
{
  Foo* foo1 = *(Foo**)elem1;
  Foo* foo2 = *(Foo**)elem2;
  if(foo1->t < foo2->t) return -1;
  else if (foo1->t > foo2->t) return 1;
  else return 0;
}

Answer 2

Votre SortProc ne retourne pas des résultats corrects, et cela conduit probablement à la corruption de la mémoire par quelque chose en supposant que les données sont, bien, triée après que vous obtenez fait les trier. Vous pourriez même dirigerai qsort dans la corruption comme il essaie de trier, mais bien sûr par la mise en œuvre varie.

La fonction de comparaison pour qsort doit retourner négatif si le premier objet est inférieure à la seconde, de zéro si elles sont égales et positives autrement. Votre code actuel ne retourne jamais 0 ou 1, et retourne 1 lorsque vous devez retournerez négatif.

int __cdecl Sorter::SortProc(const void* ap, const void* bp) {
  Foo const& a = *(Foo const*)ap;
  Foo const& b = *(Foo const*)bp;
  if (a.t == b.t) return 0;
  return (a.t < b.t) ? -1 : 1;
}

Answer 3

C ++ ne fait pas vraiment de garanties sur la sécurité de fil. A propos de la plupart, vous pouvez dire est que, soit plusieurs lecteurs ou un seul auteur à une structure de données seront OK. Toute combinaison de lecteurs et écrivains, et vous devez serialise l'accès en quelque sorte.

Answer 4

Depuis que vous avez taguée votre question avec tag MFC Je suppose que vous devez sélectionner la bibliothèque d'exécution multi-thread dans les paramètres du projet.

Answer 5

En ce moment, votre code est thread-safe, mais inutile, comme la méthode DoSort-utilise uniquement des variables locales, et ne retourne même pas quoi que ce soit. Si les données que vous triez est membre de trieuse, il n'est pas sûr d'appeler la fonction de plusieurs threads. En Gerenal, lire sur réentrée , cela peut vous donner une idée de ce que vous devez rechercher.

Answer 6

ce qui le rend thread-safe, à savoir si votre objet sont thread-safe, par exemple pour faire qsort thread-safe, vous devez vous assurer que tout ce qui écrire ou lire ou à partir et à l'objet sont thread-safe.

Answer 7

La page de manuel pthreads énumère les fonctions standard qui ne sont pas nécessaires pour être thread-safe. qsort ne figure pas parmi eux, il est donc nécessaire d'être thread-safe dans Posix .

http: //www.kernel .org / doc / man-pages / ligne / pages / man7 / pthreads.7.html

Je ne peux pas trouver la liste équivalente pour Windows, cependant, c'est donc pas vraiment une réponse à votre question. Je serais un peu surpris si c'était différent.

Sachez ce que « thread-safe » dans ce contexte, bien que. Cela signifie que vous pouvez appeler la même fonction simultanément sur différents tableaux - cela ne signifie pas que l'accès simultané aux mêmes données via qsort est sûr (il est)

.

Answer 8

En un mot d'avertissement, vous trouverez peut-être std::sort est pas aussi rapide que qsort. Si vous trouvez que std::stable_sort try.

J'ai écrit un compresseur BWT basé sur le code présenté mon Mark Nelson Dr Dobbs et quand je me suis retourné dans les classes, je trouve que sort régulière était beaucoup plus lent. stable_sort fixe les problèmes de vitesse.