Visual walkthrough — Dynamic memory — malloc, calloc, realloc, free

5.1.14 · D2 · Coding › C Programming › Dynamic memory — malloc, calloc, realloc, free

Yahan sab kuch yeh assume karta hai ki tumne sirf ek pointer (ek variable jo ek address hold karta hai) aur heap (memory ka ek bada pool jo tum runtime pe rent karte ho) dekha hai. Baaki hum build karte hain.

Step 1 — Heap bytes ki taraf pointer hota kya hai

KYA HAI. Hum heap se bytes ka ek slab rent karte hain aur uska starting address pointer v mein rakhte hain.

int *v = malloc(cap * sizeof(*v));

Aao har symbol ko theek wahan naam dein jahan woh appear hota hai:

$\underset{\text{kitne int slots}}{\underbrace{\text{cap}}}\times \underset{\text{EK int mein bytes}}{\underbrace{\text{sizeof(*v)}}}=\underset{\text{woh number jo malloc chahta hai}}{\underbrace{\text{total bytes to rent}}}$

• sizeof(*v) padha jaata hai "us cheez ki size jo v point karta hai" — ek int, typically $4$ bytes (dekho sizeof operator).
• cap (capacity) hai kitne int-sized boxes humne maange.

YEH FORM KYUN. malloc sirf bytes mein baat karta hai, lekin hum elements mein sochte hain. Multiplication dono languages ke beech translator hai.

PICTURE. v ek arrow hai. Yeh "array" ki taraf point nahi karta — yeh heap ke ek fenced-off strip ke pehle byte ki taraf point karta hai. Strip cap boxes wide hai.

Step 2 — Hume DO counters kyun chahiye, ek nahi

KYA HAI. Hum len (used) aur cap (rented) ko alag alag variables mein rakhte hain.

$\text{len}\le \text{cap}\text{hamesha sach, poore design ka invariant}$

• len $0$ se upar badhta hai jab hum values push karte hain.
• cap tabhi badalta hai jab hum re-rent karte hain.

KYUN. Agar hum sirf ek number track karte to hum "strip full hai" aur "strip half empty hai" mein fark nahi kar paate. Gap cap - len exactly remaining free room hai.

PICTURE. Ek hi strip ke neeche do rulers: len length ka solid amber bar (filled), cap ka cyan outline (rented). Bar ki tip aur fence ke beech ka white gap woh room hai jisme hum abhi bhi likh sakte hain.

Step 3 — "Kya main full hun?" test

KYA HAI. Har push se pehle hum ek condition check karte hain:

if (len == cap) { /* grow */ }

$\underset{\text{boxes used}}{\underbrace{\text{len}}}=\underset{\text{boxes rented}}{\underbrace{\text{cap}}}⟺\text{koi free room nahi bacha}$

== kyun aur >= nahi? Kyunki Step 2 ka hamara invariant guarantee karta hai ki len kabhi cap se aage nahi jump kar sakta — yeh ek step ek time badhta hai. To "full" hone ka ek hi tarika hai exact equality. (>= bhi kaam karta aur safer hota agar tum kabhi invariant tod do; == invariant ko document karta hai.)

PICTURE. Amber "used" bar itna badh gaya hai ki uski tip fence ko chhune lagi hai. Koi white gap nahi bacha. Woh touching moment trigger hai.

Step 4 — Capacity double kyun karein (derivation ka dil)

KYA HAI. Jab full ho, hum set karte hain:

cap *= 2;

${\text{cap}}_{\text{new}}=2\times {\text{cap}}_{\text{old}}$

Doubling kyun aur "add one" nahi? Yahi poori baat hai, to cost dekhte hain.

Har baar jab hum grow karte hain, realloc ko saare len existing integers kisi naye jagah copy karne pad sakte hain. k items copy karna k units of work leta hai.

• Grow-by-1 strategy: hum har push pe copy karte hain. $n$ items tak pahunchne ke liye total copies: $1+2+3+\cdots +n=\frac{n(n+1)}{2}\approx \frac{n^2}{2}⟹O(n^2)$ Har term hai "woh array jo hume us push pe copy karni padi." Kaam ka woh parabola brutal hai.

• Doubling strategy: hum sirf sizes $1,2,4,8,\dots$ pe copy karte hain. Total copies: $1+2+4+\cdots +n=2n-1⟹O(n)$ Ek geometric series jo do baar n se bhi kam mein sum ho jaati hai. Kaam ek flat line hai.

"Kabhi kabhi mehenga, zyaadatar sasta, average mein sasta" ke liye word hai per push amortized $O(1)$.

PICTURE. Ek hi axes pe do curves: grow-by-1 parabola tezi se upar chadh raha hai vs doubling line neeche reh rahi hai. Unke beech ka gap hi woh reason hai kyun hum double karte hain.

Step 5 — realloc physically kya karta hai

KYA HAI. Hum ek bade strip ki demand karte hain:

int *tmp = realloc(v, cap * sizeof(*v));

$\text{realloc}(\underset{\text{old start address}}{\underbrace{\text{v}}},\underset{\text{new size in bytes}}{\underbrace{\text{cap}\times \text{sizeof(*v)}}})\to \underset{\text{maybe-new address}}{\underbrace{\text{tmp}}}$

realloc ke paas do possible moves hain, aur woh tumhare liye choose karta hai:

1. In place extend — agar tumhare strip ke theek baad ke boxes free hote hain, toh woh sirf fence ko bahar ki taraf move kar deta hai. tmp == v (same address).
2. Relocate — agar neighbours occupied hain, toh woh kahin aur ek fresh, bada strip rent karta hai, tumhare len purane integers usme copy karta hai, purana strip free karta hai, aur naya address return karta hai. tmp != v.

tmp mein return kyun karein aur v mein nahi? Step 6 ka preview — kyunki move (2) fail ho sakta hai, aur agar humne v overwrite kar diya toh humhare paas abhi-bhi-valid purane strip ka address kho jaata. Dekho Memory Leaks and Valgrind.

PICTURE. Do panels side by side. Left: fence right slide karta hai, same address (cyan). Right: ek bilkul naya strip kahin aur appear hota hai, purane bytes ek amber copy-arrow ke zariye usme flow karte hain, aur purana strip grey ho jaata hai (freed).

Step 6 — Degenerate case: realloc FAIL ho jaata hai

KYA HAI. Heap exhaust ho sakta hai. Failure pe realloc NULL return karta hai aur purana block untouched aur valid rehta hai. Isliye safe pattern yeh hai:

int *tmp = realloc(v, cap * sizeof(*v));
if (!tmp) { free(v); return 1; }   // purana block abhi bhi hamaara → free karo, bail out
v = tmp;                           // success → naya address commit karo

$\text{tmp}=\{\begin{array}{ll}\text{new valid address}& \text{success}\\ \text{NULL}& \text{failure, aur }\text{v}\text{ abhi bhi valid}\end{array}$

Temporary optional kyun nahi hai. Broken version v = realloc(v, ...) trace karo:

• Failure pe realloc NULL return karta hai.
• Humne woh NULL v mein likh diya.
• Purana strip abhi bhi rented hai — lekin uska ek hi address gaya. Recover nahi ho sakta. Yeh hai ek memory leak.

PICTURE. Broken path: realloc NULL return karta hai, arrow v kuch nahi point karne ke liye bend ho jaata hai (NULL), aur purana amber strip untethered float kar jaata hai — leaked. Uske baaju mein, correct path v ko purane strip ki taraf aim kiye rakhta hai jab tak tmp proven good nahi ho jaata.

Step 7 — Write, aur zero-length edge case

KYA HAI. Room guaranteed hone ke baad, hum finally value store karte hain aur aage badhte hain:

v[len++] = x;

$\underset{\text{index len pe box}}{\underbrace{\text{v[len]}}}=x,\text{phir}\underset{\text{used count}}{\underbrace{\text{len}}}+=1$

len++ post-increment hai: purane len ko index ki tarah use karo, phir use bump karo. To hum pehle empty box mein likhte hain, phir use used mark karte hain.

Edge cases jinpe kabhi mat trip karo:

• realloc(v, 0) — zero bytes maangna. Standard allow karta hai ki yeh ya to free karke NULL return kare, ya ek tiny non-NULL "empty" block return kare. Kabhi rely mat karo kaun sa hoga — woh implementation-defined behaviour hai. $0$ tak mat bado.
• realloc(NULL, n) — agar pehla argument NULL hai, realloc exactly malloc(n) ki tarah behave karta hai. Isliye kuch code v = NULL se start karta hai aur pehle realloc ko pehla allocation karne deta hai.
• Pehla push jab cap $0$ se start ho — tab cap *= 2 $0$ hi rehta hai (do guna kuch nahi hota kuch nahi!). Isliye hum cap = 2 seed karte hain (ya special-case cap = cap ? cap*2 : 1). Ek pure "double" zero start ke khilaaf helpless hai.

PICTURE. Index len pe box amber ho jaata hai jab x usme girti hai; ek chota arrow dikhata hai len ek box right step karte hue baad mein. Inset: 0 * 2 = 0 trap amber mein crossed out.

Ek picture summary

Ek growable buffer ki poori zindagi: chhota rent karo → bhaaro → full detect karo → double karo aur (shayad) relocate karo → tmp ko v mein commit karo → bharte raho → ant mein free karo. Ek arrow, ek strip, powers of two pe doubling.

Active Recall