Overview

chain: مكتبة C لمصفوفات مرنة من أي نوع

تهدف هذه المكتبة لتوفير المصفوفات المرنة للمبرمج من دون فرض أنواع جديدة خاصة بالمصفوفات ومن دون التضحية بوسائل التعامل مع المصفوفات التي توفرها اللغة (الأقواس المربعة [] خصوصا).

يمكنك استخدام المصفوفات المرنة أينما تستخدم المصفوفات الأخرى.

مثال

    // compile with -std=c99
    #include <stdio.h>
    #include "chain.h"

    int main(){
        // An empty int array
        int *ia = chain_new(int);

        // Pushing 1 and 3, then inserting 2 in the middle
        chain_push(ia, 1);
        chain_push(ia, 3);
        chain_insert(ia, 1, 2);

        // printing `ia' here yeilds 1 2 3
        for (uint32_t i = 0; i < chain_len(ia); ++i) printf(" %d", ia[i]); puts("");

        // pushing in a full array; last argument is length, and parentheses are
        // required for macros 
        chain_push_all(ia, ((int[]){4, 5, 6, 7}), 4);

        // poping ia yeilds a 7 which gets printed
        printf("%d\n", chain_pop(ia));

        // any array allocated through chain must be freed using the fuction 
        chain_free(ia);

        return 0;
    }

ملاحظات:

  1. يمكنك تمرير ما طابت له نفسك من أنواع المتغيرات لـchain_new.
  2. جميع دوال الكتبة ليست دوالا بل قوالب (باستثناء chain_free). أنظر لقواعد استخدام القوالب.
  3. تتألف المكتبة من ملفين فقط: (chain.c وchain.h) ومن دون مستلزمات أخرى غير c99 والمكتبة القياسية.

دوال وقوالب المكتبة

أنظر في chain.h للتفاصيل.

قواعد الإستخدام قوالب المكتبة

فيما يلي قواعد عامة لاستخدام قوالب هذه المكتبة. لك أن تتفقد ملف التعريفات .h بنفيك وأن تحدد بنفسك ما لزم وما لا يلزم أن شئت أن تتجنب بعضها.

تنثق معظم القواعد التالية من حقيقة كونها قوالبا، ولهذا تجدها موافقة لقواعد قوالب السي العامة.

  1. تذكر أن ما تستخدمه قوالب وليست دوالا.
  2. لا تمرر القوالب كمدخلات للدوال، ولا تستخدمها في عبارات بشكل عام إلا إن تكون القوالب مصصمة لذلك.
  3. لا تمرر مدخلات ذات آثار جانبية لاحتمال تكرر ورود المدخل بالقالب.
  4. أحط المصفوفات من الجنس (type[]){ m, m, m} بأقواس إضافية.

كفاءة المكتبة

أكبر مؤثر على كفاءة المكتبة هو إضافة عنصر أول أو وسط المصفوفات، وهذا لنقل كل ما كل تلى العنصر المضاف إلى مواقع جديدة حفاظا غلى تسلسل العناصر.

يمكن أهمال أثر هذه الإضافات في المصفوفات الصغيرة، ولكنه يزداد ويتضخم مع ازدياد عدد العناصر.

فيما يلي نماذج لبعض الأنظمة، وسرعة تدهور كفاءة المكتبة. المحور الأفقي عدد العناصر في المصفوفة والرأسي الزمن المستغرق لإضافة عنصر واحد أول المصفوفة.

المنحنيين التاليين يبينان التدهور المصاحب لـchain_shove على نظامين مختلفين، وهو أسوء القوالب المضيفة لأنها تضيف العناصر الجديدة أول المصفوفة.

    intel/i7/M620@2.67GHz/4096KB

       0.0002 ++---------+----------+----------+---------+-----------+--------AA
              +"./data/chain_shove" +          +         +           +     AAAAA
              |                                                         A AAAAAA
              |                                                         AAAAAAAA
              |                                                       A AAAAAAAA
      0.00015 ++                                                  AAAAAAAAAAAAAA
              |                                                 AAAAAAAAAAAAAAAA
              |                                            A AAAAAAAAAAAAAAAAAAA
              |                                           AA AAAAAAAAAAAAAAAAAAA
       0.0001 ++                                      AAAAAAAAAAAAAAAAAAAAAAAAA+
              |                                A A AAAAAAAAAAAAAAAAAAAAAAAAA   |
              |                              A AAAAAAAAAAAAAAAAAAAAAAAA        |
              |                            AAAAAAAAAAAAAAAAAAAAAA              |
              |                    A  AAAAAAAAAAAAAAAAAAAA                     |
        5e-05 ++              A  A AAAAAAAAAAAAAAAAA                          ++
              |          AAAAAAAAAAAAAAAAAAAAA                                 |
              |    A AAAAAAAAAAAAAAAAAA                                        |
              |   AAAAAAAAAAAAAAA                                              |
              AAAAAAAAAAAA          +          +         +          +          +
            0 AAAAA------+----------+----------+---------+----------+---------++
              0        100k       200k       300k      400k       500k       600k



    ARM11/76/697.95MIS

      0.012 ++-----+-----+------+------+------+-----+------+------+-----+-----++
            +      +     +      +      +      +     +   "benchmark.dat" + A    +
            |                                                                 AA
       0.01 ++                                                           AAAAAAA
            |                                                       AAAAAAAAAAAA
            |                                                   AAAAAAAAAAAA   |
      0.008 ++                                              AAAAAAAAAAAA      ++
            |                                           AAAAAAAAAAAA     AAAAAAA
            |                                       AAAAAAAAAAAA    AAAAAAAAAAAA
      0.006 ++                                  AAAAAAAAAAA   AAAAAAAAAAAAAAAA++
            |                              AAAAAAAAAAAA AAAAAAAAAAAAAAA        |
            |                          AAAAAAAAAAAAAAAAAAAAAAAAAA              |
            |                     AAAAAAAAAAAAAAAAAAAAAAAAA                    |
      0.004 ++                AAAAAAAAAAAAAAAAAAAAAAA                         ++
            |             AAAAAAAAAAAAAAAAAAAAA                                |
            |          AAAAAAAAAAAAAAAAAA                                      |
      0.002 ++    AAAAAAAAAAAAAAAA                                            ++
            |    AAAAAAAAAAA                                                   |
            +  AAAAAAA   +      +      +      +     +      +      +     +      +
          0 AAAAA--+-----+------+------+------+-----+------+------+-----+-----++
             0    50k   100k   150k  200k   250k   300k  350k   400k  450k   500k

مقارنة بما سبق، كفائة القالب chain_push ثابتة نسبيا لعدم نقل العناصر القديمة من مكانها.

    intel/i7/M620@2.67GHz/4096KB

       0.0002 ++---------+----------+----------+---------+----------+---------++
              +"./data/chain_push"  +A         +         +          +          +
              |                                                                |
              |                                                                |
              |                                                                |
      0.00015 ++                                                              ++
              |                                                                |
              |                                                                |
              |                                                                |
       0.0001 ++                                                              ++
              |                                                                |
              |                                                                |
              |                                                                |
              |                                                                |
        5e-05 ++                                                              ++
              |                                                                |
              |                                                                |
              |                                                        A       |
              +A    A A  +        A A    A     +     A   +          A A  A A   +
            0 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
              0        100k       200k       300k      400k       500k       600k

ملكية فكرية

حقوق النشر © 2012 سليمان مصطفى

أنا صاحب هذه المكتبة قد رخصتك لنشرا المكتبة والتغيير فيها ضمن حدود بنود رخصة جنو أفرو العمومية GNU Affero General Public License المرفقة مع المكتبة (الإصدار الثالث) أو الإصدارات التالية منها إن شئت.

(( إتصل بي إن أردت رخصة غير هذه ))

راجع الرخصة نفسها للتفاصيل بنود الترخيص. راجع ملفات المكتبة أيضا.