calloc ו-realloc ב-C: זיכרון מאופס והגדלת מערך

malloc עונה על שאלה אחת: תן לי כך וכך בתים. שתי חברות ב-<stdlib.h> עונות על השאלות שמגיעות אחר כך: תן לי כך וכך בתים, מנוקים (calloc), ואני צריך שהבלוק שכבר יש לי יהיה גדול יותר (realloc).

calloc: מספר, גודל ואפסים

void *calloc(size_t count, size_t size);

שני ארגומנטים במקום אחד, והתוצאה ממולאת בבתים של אפס.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    size_t n = 6;

    int *counts = calloc(n, sizeof *counts);
    if (counts == NULL) {
        fprintf(stderr, "out of memory\n");
        return 1;
    }

    /* already zero - no initialization loop needed */
    for (size_t i = 0; i < n; i++) {
        printf("%d ", counts[i]);
    }
    printf("\n");

    counts[2] += 1;
    counts[2] += 1;
    printf("counts[2] = %d\n", counts[2]);

    free(counts);
    return 0;
}

זה המקרה הקלאסי: היסטוגרמה או מערך ספירה שבו כל תא חייב להתחיל מאפס. עם malloc הייתם צריכים לולאה; calloc עושה את זה כחלק מההקצאה, הרבה פעמים בחינם, כי מערכת ההפעלה ממילא מחלקת דפים חדשים שכבר מאופסים.

טיעון הגלישה

הפיצול לשני ארגומנטים אינו קוסמטי. חשבו על מספר איברים שנקרא מקובץ:

size_t n = huge_value_from_input;

int *a = malloc(n * sizeof *a);     /* the product can wrap around */
int *b = calloc(n, sizeof *b);      /* required to detect the overflow */

אם n * sizeof *a חורג ממה ש-size_t יכול להכיל, הוא מתגלגל למספר קטן, malloc מצליחה עם בלוק זעיר, וכל כתיבה אחר כך רצה הרחק מעבר לסוף. לפי התקן, calloc חייבת להיכשל ולהחזיר NULL במקום זאת. כשגודל מגיע מחוץ לתוכנית שלכם, הבדיקה הזו שווה את זה.

מה "מאופס" אומר בפועל

calloc כותבת בתים של אפס. עבור מספרים שלמים ותווים זה הערך אפס, וזה מה שרוצים. עבור מצביעים וערכי נקודה צפה, כל הביטים אפס הם מצביע null ו-0.0 בכל פלטפורמה מרכזית, אבל תקן C לא מבטיח את זה. קוד שחייב להיות נייד לחלוטין משים את הערכים האלה במפורש.

calloc מול malloc ועוד memset

int *a = calloc(n, sizeof *a);

int *b = malloc(n * sizeof *b);
if (b != NULL) {
    memset(b, 0, n * sizeof *b);
}

הם מפיקים את אותה תוצאה. העדיפו את calloc: זו שורה אחת, היא מבצעת את בדיקת הגלישה, ובבלוקים גדולים היא יכולה להימנע מלגעת בזיכרון בכלל. העדיפו malloc רגילה כשאתם עומדים לדרוס כל בית בכל מקרה: לאפס מגה-בייט שתמלאו מיד הוא בזבוז טהור.

realloc: שינוי הגודל

void *realloc(void *p, size_t newsize);

realloc מחזירה בלוק של newsize בתים שהתוכן שלו תואם לבלוק הישן עד הקטן מבין שני הגדלים. היא עשויה להרחיב את הבלוק במקומו, או להקצות בלוק חדש, להעתיק ולשחרר את הישן. אי אפשר לדעת מה מהשניים, כך שהמצביע היחיד שמותר להשתמש בו אחר כך הוא זה שהיא החזירה.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    size_t n = 3;
    int *a = malloc(n * sizeof *a);
    if (a == NULL) {
        return 1;
    }
    for (size_t i = 0; i < n; i++) {
        a[i] = (int)i;
    }

    size_t bigger = 6;
    int *tmp = realloc(a, bigger * sizeof *a);
    if (tmp == NULL) {
        free(a);                 /* a is still valid - release it */
        fprintf(stderr, "grow failed\n");
        return 1;
    }
    a = tmp;

    /* the first 3 values survived; the new slots are uninitialized */
    for (size_t i = n; i < bigger; i++) {
        a[i] = (int)(i * 10);
    }

    for (size_t i = 0; i < bigger; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    free(a);
    return 0;
}

ניב המצביע tmp

שלוש השורות סביב tmp הן כל הסיבה שלפונקציה הזו יש מוניטין. הקיצור המפתה שבור:

/* BUG: leaks the original block when realloc fails */
p = realloc(p, newsize);
if (p == NULL) {
    return;
}

כש-realloc נכשלת היא מחזירה NULL ומשאירה את הבלוק המקורי מוקצה וללא שינוי. השמת התוצאה ישירות ל-p דורסת את המצביע היחיד לבלוק הזה, כך שלעולם אי אפשר יהיה לשחרר אותו: דליפה, וכזו שקורית בדיוק כשהזיכרון כבר נדיר. השימו ל-tmp, בדקו את tmp, ואז קבעו:

void *tmp = realloc(p, newsize);
if (tmp == NULL) {
    /* p is still valid; handle the failure however suits the caller */
    return 0;
}
p = tmp;

עוד שתי התנהגויות שכדאי להכיר: realloc(NULL, n) מתנהגת בדיוק כמו malloc(n), וזה מאפשר לפונקציית הגדלה לטפל בקריאה הראשונה שלה בלי מקרה מיוחד. והגדלה משאירה את הבתים החדשים לא מאותחלים: רק התוכן הישן נשמר.

הגדלת מערך: התבנית המקובלת

זו התבנית שכמעט כל מבנה נתונים ב-C משתמש בה: אורך, קיבולת, והכפלה כשהם נפגשים.

#include <stdio.h>
#include <stdlib.h>

struct IntVec {
    int   *data;
    size_t len;
    size_t cap;
};

/* returns 1 on success, 0 if the array could not grow */
int vec_push(struct IntVec *v, int value) {
    if (v->len == v->cap) {
        size_t newcap = (v->cap == 0) ? 4 : v->cap * 2;

        int *tmp = realloc(v->data, newcap * sizeof *v->data);
        if (tmp == NULL) {
            return 0;               /* v->data is untouched and still valid */
        }
        v->data = tmp;
        v->cap  = newcap;
    }

    v->data[v->len++] = value;
    return 1;
}

int main(void) {
    struct IntVec v = {NULL, 0, 0};

    for (int i = 1; i <= 10; i++) {
        if (!vec_push(&v, i * i)) {
            fprintf(stderr, "out of memory at %d\n", i);
            free(v.data);
            return 1;
        }
    }

    printf("len = %zu, cap = %zu\n", v.len, v.cap);
    for (size_t i = 0; i < v.len; i++) {
        printf("%d ", v.data[i]);
    }
    printf("\n");

    free(v.data);
    v.data = NULL;
    v.len = v.cap = 0;
    return 0;
}

שתי החלטות עיצוב נושאות כאן את המשקל.

הכפלה, לא הוספה של אחד. הגדלה בכמות קבועה גורמת לכל הוספה להעתיק את כל המערך, כך שמילוי n איברים עולה בערך n² העתקות. הכפלה הופכת את ההעתקות לנדירות מספיק כדי שכל הוספה תעלה זמן קבוע בממוצע. ההתחלה cap == 0 ? 4 : cap * 2 מטפלת בהוספה הראשונה בלי ענף נפרד, כי realloc(NULL, n) היא פשוט malloc.

ה-struct מחזיק הקצאה אחת. v.data משוחרר בדיוק פעם אחת, על ידי מי שמחזיק את ה-struct. לכתוב את כלל הבעלות הזה, בהערה או בזיווג של כל vec_init עם vec_free, זה מה שמונע ממבנה שגדל לדלוף כשהוא עובר בין פונקציות.

הקטנה

realloc עם גודל קטן יותר מקצצת בלוק, וזה שימושי אחרי שקראתם כמות לא ידועה של נתונים לחוצץ גדול מדי:

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    size_t cap = 1024;
    char *buf = malloc(cap);
    if (buf == NULL) {
        return 1;
    }

    const char *text = "only a few bytes";
    size_t used = 0;
    while (text[used] != '\0' && used < cap - 1) {
        buf[used] = text[used];
        used++;
    }
    buf[used] = '\0';

    char *tmp = realloc(buf, used + 1);
    if (tmp != NULL) {
        buf = tmp;               /* shrink succeeded */
    }
    /* if it failed, buf is still the larger block - perfectly usable */

    printf("[%s] now sized %zu\n", buf, used + 1);

    free(buf);
    return 0;
}

הקטנה שנכשלה אינה שגיאה שכדאי לעצור בגללה: הבלוק הישן והגדול יותר עדיין תקף ועדיין נכון. זה המקרה היחיד שבו התעלמות מהכישלון היא ההחלטה הנכונה, אבל שימו לב שעדיין עוברים דרך tmp, כי הכלל לא לדרוס את המצביע החי לא משתנה.

באיזו מהן להשתמש

את כל הארבע משחררים עם אותה free, בדיוק פעם אחת.

טעויות נפוצות

• p = realloc(p, n): דולף במקרה של כישלון. תמיד עברו דרך tmp.
• שמירת מצביע ישן לתוך הבלוק. אחרי realloc הנתונים אולי זזו, כך שכל מצביע פנימי שנשמר או כתובת שחושבה מאינדקס אינם עדכניים. אינדקסים שורדים מעבר; מצביעים לא.
• הנחה שהבתים החדשים הם אפס. רק calloc מאפסת. realloc משאירה את אזור ההגדלה לא מאותחל.
• calloc(n * size, 1): זה זורק את בדיקת הגלישה שבשבילה קיימת הצורה עם שני הארגומנטים.
• שחרור המצביע הישן אחרי realloc שהצליחה. realloc כבר שחררה אותו; free שנייה היא שחרור כפול.