هل Qsort خيط آمن؟

Question

لدي بعض الرمز القديم الذي يستخدم qsort لفرز MFC CArray من الهياكل ولكن أرى تحطم عرضي ذلك مايو يكون لأسفل إلى مؤشرات الترابط متعددة qsort في نفس الوقت. الرمز الذي أستخدمه يبدو شيئا مثل هذا:

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();

أنا على وشك إعادة تكوين هذا الرمز الرهيب للاستخدام std::sort بدلا من ذلك، لكن تساءلت عما إذا كان ما سبق غير آمن بالفعل؟

تعديل: Sorter::DoSort هو في الواقع وظيفة ثابتة ولكنها لا تستخدم أي متغيرات ثابت نفسها.

Edit2: تم تغيير وظيفة SortProc لتتناسب مع الرمز الحقيقي.

Answer 1

مشكلتك لا تملك بالضرورة أي شيء للقيام به مع صفحات السلامة.

تأخذ وظيفة رد الاتصال الفرز في مؤشرات لكل عنصر، وليس العنصر نفسه. منذ أن أنت فرز Foo* ما تريد فعلا القيام به هو الوصول إلى المعلمات Foo**, ، مثله:

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

لا يعيد SortProc الخاص بك النتائج الصحيحة، وهذا يحتمل أن يؤدي إلى تلف الذاكرة بشيء يفترض أن البيانات هي، حسنا، مرتبة بعد القيام به فرزها. يمكنك حتى أن تقود Qsort في الفساد حيث تحاول الفرز، ولكن هذا بالطبع يختلف عن طريق التنفيذ.

يجب أن تعود وظيفة المقارنة ل Qsort سالبة إذا كان الكائن الأول أقل من الثانية، الصفر إذا كانوا متساوين، وإيجاد خلاف ذلك. يعود الرمز الحالي الخاص بك فقط 0 أو 1، والعودة 1 عندما يجب أن تعود سلبي.

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 ++ حقا بإجراء أي ضمانات حول سلامة الخيط. حول أكثر ما تستطيع أن تقول هو أن عداء متعددين أو كاتب واحد إلى بنية بيانات سيكون على ما يرام. أي مزيج من القراء والكتاب، وتحتاج إلى تسلسل الوصول بطريقة أو بأخرى.

Answer 4

منذ أن تم وضع علامة على سؤالك مع MFC علامة "افترض"، يجب عليك تحديد مكتبة تشغيل متعددة الخيوط في إعدادات المشروع.

Answer 5

الآن، رمزك آمن للخيط، ولكن عديمة الفائدة، حيث تستخدم طريقة Dosort فقط المتغيرات المحلية، ولا تعيد أي شيء. إذا كانت البيانات التي تقوم بها الفرز هي عضو في فارز، فليس من الآمن استدعاء الوظيفة من مؤشرات ترابط متعددة. في جيرينال، اقرأ reentrancy., ، قد يمنحك هذا فكرة عما تحتاجه للبحث عنه.

Answer 6

ما الذي يجعله مؤمنا، ما إذا كان كائنك آمن، على سبيل المثال لجعل QSort Thread-Safe، يجب عليك التأكد من أن أي شيء يكتب أو يقرأ إليه أو للكائن وإلى كائن آمن مؤشر ترابط.

Answer 7

يسرد صفحة Pthreads Man الوظائف القياسية غير المطلوبة لتكون آمنة للخيط. Qsort ليس من بينها، لذلك يجب أن يكون آمنا للخيط في بوسيكس.

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

لا يمكنني العثور على القائمة المكافئة لنظام التشغيل Windows، لذلك، لذلك ليس هذا بالفعل إجابة على سؤالك. سأكون مفاجأة بعض الشيء إذا كان مختلفا.

كن يدرك ما يعنيه "آمنة الخيط" في هذا السياق. هذا يعني أنه يمكنك استدعاء نفس الوظيفة بشكل متزامن على صفائف مختلفة - لا يعني أن الوصول المتزامن إلى نفس البيانات عبر QSort آمنة (ليس).

Answer 8

ككلمة تحذير، قد تجد std::sort ليس بسرعة qsort. وبعد إذا وجدت أن المحاولة std::stable_sort.

كتبت ذات مرة ضاغط BWT استنادا إلى التعليمات البرمجية مارك نيلسون في الدكتور دوبس وعندما قمت بتشغيلها إلى فصول وجدت sort كان أبطأ كثيرا. stable_sort إصلاح مشاكل السرعة.