# Exercises for reading index and length arithmetic in C Fast reading of a line like your `memmove` comes from recognizing its parts, such as `S - c`, as familiar shapes instead of working out each operator. Sets A to C build the model, D to G apply it to `memmove` and real code, and H trains speed. Answers are at the end. ## The gap model Number the boundaries between elements, starting with 0 before the first element. A buffer of size $S$ has $S + 1$ gaps, numbered $0$ to $S$. Element $i$ sits between gap $i$ and gap $i + 1$. ``` gap 0 1 2 3 4 5 6 7 8 9 10 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ``` A text cursor, a pointer such as `&b[i]`, and the two ends of a range are all gaps. In `memmove(dest, src, n)`, the first two arguments are gaps and the third is a length. Four rules: 1. The range $[a, b)$ holds $b - a$ elements. 2. Gap + length = gap. Gap − gap = length. Length ± length = length. Gap + gap has no meaning, so it signals a bug. 3. A run of $n$ elements starting at gap $a$ ends at gap $a + n$. Its last element has index $a + n - 1$. 4. In gap terms, $-1$ belongs only where you need the index of a single element, such as the last one. Any other $\pm 1$ in a length needs a specific reason, such as a NUL terminator or an inclusive range. ## Idioms to recognize | Expression | Read as | |---|---| | `&b[i]`, `b + i` | gap $i$ | | `end - start` | length of $[\text{start}, \text{end})$ | | `start + len` | end gap of the run | | `start + len - 1` | index of the last element of the run | | `S - c` | length of the tail $[c, S)$ | | `S - c - n` | tail length minus $n$ (skipped, or pushed off the end) | | `c` used as a length | length of the head $[0, c)$ | | `i < n` | runs $n$ times from 0, `i` stays in $[0, n)$ | | `i <= n` | runs $n + 1$ times from 0, check it | | `i < n - 1` | stops one early so `a[i + 1]` is safe | | `i = n; i-- > 0` | counts $n - 1$ down to $0$, safe for unsigned `i` | | `sizeof arr / sizeof arr[0]` | element count, only for an array declared in scope | | `MAX(n, 0)` | $n$ if positive, else $0$ | ## A. Ranges and counts Use a buffer of size 10 unless stated. - **A1.** How many elements are in $[3, 7)$? Which indices? - **A2.** How many are in $[5, 5)$? - **A3.** A run starts at gap 2 and holds 5 elements. At which gap does it end? What is the index of its last element? - **A4.** Write "elements 4 through 9 inclusive" as a half-open range. How many elements? - **A5.** How many elements lie between gap 6 and the end? - **A6.** How many elements lie before gap 6? - **A7.** Split $[0, 10)$ at gap 4. Write both parts and their counts. - **A8.** A fence has 10 sections. How many posts? Which of posts and sections correspond to gaps and which to elements? - **A9.** How many elements are in the closed range $[a, b]$? Rewrite it as a half-open range. ## B. Loop bounds - **B1.** `for (i = 2; i < 8; i++)`: number of iterations, first `i`, last `i`. - **B2.** `for (i = 2; i <= 8; i++)`: same questions. - **B3.** `for (i = 0; i < n - 1; i++)` with $n = 10$: iterations, and the largest index reached by `a[i + 1]`. - **B4.** `for (i = n; i-- > 0; )` with $n = 5$: list the values of `i` inside the body. - **B5.** `for (p = buf + 3; p < buf + 8; p++)`: iterations, first and last index. - **B6.** Write a loop over the tail starting at gap `c` of a buffer of size `S`. How many iterations? - **B7.** Write a loop that visits indices 9 down to 4 inclusive. ## C. Pointers and sizeof Assume 64-bit pointers and 4-byte `int`. - **C1.** `char buf[10];` What is `sizeof buf`? - **C2.** `char *p = buf;` What is `sizeof p`? - **C3.** `void f(char text[10]) { ... sizeof text ... }` What is `sizeof text`? - **C4.** `int a[10];` What are `sizeof a` and `sizeof a / sizeof a[0]`? - **C5.** Are `&buf[4]` and `buf + 4` the same? Is `&buf[10]` allowed? - **C6.** `begin = buf + 2; end = buf + 9;` What is `end - begin`? - **C7.** `size_t pos = 4; size_t *cursor = &pos; char text[10];` What are `*cursor` and `&text[*cursor]`? Which compiles: `sizeof text - *cursor` or `sizeof text - cursor`? - **C8.** `int a[10];` Write a `memmove` that shifts elements $[3, 9)$ right by one. How many bytes is the count? ## D. Reading memmove Before each exercise, `char b[10]` holds `0123456789`. Each digit equals its index, so you can read positions directly off the result. Apply this template to every call `memmove(dest, src, n)`: 1. Convert `dest` and `src` to gap numbers. 2. Shift $= \text{dest} - \text{src}$. Positive moves right. 3. Source $[\text{src}, \text{src} + n)$, destination $[\text{dest}, \text{dest} + n)$. 4. Fits if $\max(\text{src}, \text{dest}) + n \le S$. 5. Destination cells get the old source contents. All other cells keep their values. For each call, give the shift, both ranges, whether it fits, and the contents after. - **D1.** `memmove(&b[3], &b[2], 7);` - **D2.** `memmove(&b[2], &b[3], 7);` - **D3.** `memmove(&b[5], &b[2], 5);` - **D4.** `memmove(&b[4], &b[2], 7);` - **D5.** `memmove(b, b + 1, sizeof b - 1);` - **D6.** `memmove(b + 1, b, sizeof b - 1);` - **D7.** `memmove(&b[0], &b[5], 5);` - **D8.** `memcpy(&b[1], &b[0], 9);` Why must this be `memmove`? ## E. Inserting and deleting at a cursor Buffer size $S$, cursor at gap $c$, amount $n \ge 0$ unless stated. Example of an insert of 2 at gap 4: ``` before | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ^ c = 4 after | 0 | 1 | 2 | 3 | _ | _ | 4 | 5 | 6 | 7 | 8 and 9 fall off the end ``` - **E1.** Insert: open a hole of $n$ at $c$. Write the `memmove`, then evaluate it with $S = 10$, $c = 4$, $n = 2$. - **E2.** Delete key: remove $n$ elements after the cursor. Write and evaluate. - **E3.** Backspace: remove $n$ elements before the cursor. Write and evaluate. Where does the cursor end up? - **E4.** Derive the count in E1 from rule 1. Hint: the destination must end at gap $S$. - **E5.** Let $n$ be signed: positive inserts, negative backspaces. Show that `memmove(&b[c + n], &b[c], S - c - MAX(n, 0));` performs E1 when $n > 0$ and E3 when $n < 0$. Evaluate with $c = 4$ for $n = 2$ and $n = -2$. - **E6.** The line you posted has one bug. Find it. - **E7.** What does the E5 call do when $n = 0$? - **E8.** Write the inequality on $n$ that keeps the E5 call in bounds. - **E9.** A string of `size` characters plus a NUL is grown, then a character is inserted: ```c row->chars = realloc(row->chars, row->size + 2); memmove(&row->chars[at + 1], &row->chars[at], row->size - at + 1); ``` Which range moves? Why does the count have $+1$ where E1 had $-n$? Does the destination fit? ## F. Bug hunt Each line is correct or has a fencepost error. Decide which, and fix the wrong ones. `a` has `n` elements, `b` has `S` bytes, and ranges are half-open unless stated. - **F1.** `for (i = 0; i <= n; i++) a[i] = 0;` - **F2.** `char s[5]; strcpy(s, "hello");` - **F3.** `last = start + len;` (want the index of the last element) - **F4.** `len = end - start;` - **F5.** `len = end - start + 1;` (end is the end gap) - **F6.** `memmove(&b[c + 1], &b[c], S - c);` (insert one character) - **F7.** `memmove(&b[c], &b[c + n], S - c);` (delete $n$ after the cursor) - **F8.** `if (pos + n > size) return -1;` (guard before writing $n$ bytes at `pos`) - **F9.** `if (pos + n >= size) return -1;` (same guard) - **F10.** `for (size_t i = n - 1; i >= 0; i--)` - **F11.** `lo = 0; hi = n; while (lo < hi) { mid = lo + (hi - lo) / 2; if (a[mid] < x) lo = mid + 1; else hi = mid; }` - **F12.** `char dst[16]; strncpy(dst, src, sizeof dst); dst[sizeof dst] = '\0';` - **F13.** `void f(int a[]) { size_t n = sizeof a / sizeof a[0]; ... }` - **F14.** `for (i = 1; i < n; i++) if (a[i - 1] > a[i]) ...` ## G. Rewriting dense lines - **G1.** Rewrite the corrected version of your line with named intermediates so the final `memmove` reads in one pass. - **G2.** `memcpy(out + off, in + start, end - start);` Name the parts. If `out` has `OS` bytes, what must hold? - **G3.** Which `memmove` is this loop equivalent to? `for (i = len; i-- > pos + 1; ) s[i] = s[i - 1];` - **G4.** `memmove(buf, buf + k, len - k); len -= k;` What does it do? - **G5.** `memmove(&a[j + 1], &a[j], (i - j) * sizeof a[0]);` Which elements move, and which element is overwritten? ## H. Speed drills **Flashcards.** Put each row of the idiom table on a card, in both directions (expression to meaning, meaning to expression). Use spaced repetition, on paper or in Anki. **Glance drill.** Cover a line, uncover it for 3 seconds, cover it again, and write down the dest gap, src gap, count, shift, and whether it fits. Then check with the template. Shorten the exposure to 2 seconds once you are accurate. Take lines from Sets D to G with new numbers. **Script drill.** Save as `drill.py` and run `python3 drill.py`. Stop with Ctrl-C. ```python import random import time S = 10 START = "0123456789" def after(dest, src, n): b = list(START) b[dest:dest + n] = START[src:src + n] return "".join(b) while True: src = random.randint(0, S - 1) dest = random.randint(0, S - 1) n = max(0, S - max(src, dest) + random.choice([0, 0, -1, -2, 1])) fits = max(src, dest) + n <= S print(f'\nb = "{START}"') print(f"memmove(&b[{dest}], &b[{src}], {n});") t0 = time.monotonic() if input("fits? (y/n) ").strip().lower() != ("y" if fits else "n"): over = max(src, dest) + n - S print("It fits." if fits else f"It overruns by {over}.") continue if fits: want = after(dest, src, n) got = input("b after: ").strip() print("Correct." if got == want else f"b after: {want}") else: print("Correct.") print(f"({time.monotonic() - t0:.1f} s)") ``` **Real code.** Run `grep -rn 'memmove\|memcpy' src/` on a C project you use, and apply the template to each hit. ## Reading aids - Use grid paper with one cell per element, and write gap numbers on the vertical lines. Mark the source range in one color and the destination in another. - Keep using the `0123456789` buffer. A wrong result shows exactly which cell went wrong. - Say the line aloud in gap terms. `&b[c + n]` is "gap c plus n", and `S - c - n` is "tail minus n". - Pick an editor font that clearly distinguishes 0/O and 1/l/I. Put spaces around binary operators: `sizeof text - *cursor - MAX(n, 0)` instead of `sizeof text-*cursor-MAX(n,0)`. - In your own code, name the parts as in G1. ## Practice schedule - **Week 1:** the gap model, the idiom table, and Sets A to C. 10 to 15 minutes a day. - **Week 2:** Sets D and E on grid paper. Redo them with $S = 12$, $c = 7$, $n = 3$ so you cannot rely on remembered answers. - **Week 3:** Sets F and G. Start the script drill. - **After that:** a few minutes of the script and glance drills each day, and the template on any index arithmetic you meet in real code. ## Answers ### A - **A1.** 4 elements: 3, 4, 5, 6. - **A2.** 0. - **A3.** Ends at gap 7. The last element is index 6. - **A4.** $[4, 10)$, 6 elements. - **A5.** $10 - 6 = 4$. - **A6.** 6. - **A7.** $[0, 4)$ with 4 and $[4, 10)$ with 6. Gap 4 is shared, but no element is counted twice. - **A8.** 11 posts. Posts are gaps, sections are elements. - **A9.** $b - a + 1$. It equals $[a, b + 1)$, because the last element $b$ has its right boundary at gap $b + 1$. ### B - **B1.** 6 iterations, first 2, last 7. - **B2.** 7 iterations, first 2, last 8. - **B3.** 9 iterations, `i` from 0 to 8. `a[i + 1]` reaches index 9, the last valid one. - **B4.** 4, 3, 2, 1, 0. The test reads the old value, then decrements, so the body sees one less. - **B5.** 5 iterations, first 3, last 7. - **B6.** `for (i = c; i < S; i++)`, with $S - c$ iterations. - **B7.** `for (i = 10; i-- > 4; )`, or with a signed `int`, `for (i = 9; i >= 4; i--)`. Both run $10 - 4 = 6$ times. ### C - **C1.** 10. - **C2.** 8. - **C3.** 8. An array parameter is a pointer. - **C4.** 40 and 10. - **C5.** Yes, they are the same. `&buf[10]` is the end gap: you may compute and compare it, but not dereference it. - **C6.** 7. - **C7.** `*cursor` is 4, and `&text[*cursor]` is `text + 4`. `sizeof text - *cursor` compiles and gives 6. `sizeof text - cursor` subtracts a pointer from an integer, which is a compile error. - **C8.** `memmove(&a[4], &a[3], 6 * sizeof a[0]);`, which is 24 bytes. ### D | # | Shift | Source | Destination | Fits | After | |---|---|---|---|---|---| | D1 | +1 | $[2, 9)$ | $[3, 10)$ | yes | `0122345678` | | D2 | −1 | $[3, 10)$ | $[2, 9)$ | yes | `0134567899` | | D3 | +3 | $[2, 7)$ | $[5, 10)$ | yes | `0123423456` | | D4 | +2 | $[2, 9)$ | $[4, 11)$ | no, 1 over | fix count to 6 | | D5 | −1 | $[1, 10)$ | $[0, 9)$ | yes | `1234567899` | | D6 | +1 | $[0, 9)$ | $[1, 10)$ | yes | `0012345678` | | D7 | −5 | $[5, 10)$ | $[0, 5)$ | yes | `5678956789` | | D8 | +1 | $[0, 9)$ | $[1, 10)$ | ranges overlap | undefined with `memcpy` | ### E - **E1.** `memmove(&b[c + n], &b[c], S - c - n);` evaluates to `memmove(&b[6], &b[4], 4)`, giving `0123454567`. Cells 4 and 5 hold stale values until the inserted text overwrites them. - **E2.** `memmove(&b[c], &b[c + n], S - c - n);` evaluates to `memmove(&b[4], &b[6], 4)`, giving `0123678989`. The last 2 cells are stale. - **E3.** `memmove(&b[c - n], &b[c], S - c);` evaluates to `memmove(&b[2], &b[4], 6)`, giving `0145678989`. The cursor moves to gap 2. - **E4.** The destination runs from gap $c + n$ to gap $S$, so its length is $S - (c + n) = S - c - n$. - **E5.** For $n > 0$, `MAX(n, 0)` is $n$, so the count is $S - c - n$, which is E1. For $n < 0$, write $n = -k$. The destination is gap $c - k$ and the count is $S - c$, which is E3. The counts differ because a right shift pushes $n$ bytes past the end, while a left shift keeps the whole tail inside the buffer. With $n = 2$ the result is `0123454567`. With $n = -2$ it is `0145678989`. - **E6.** `sizeof text - cursor` subtracts the pointer. It should be `*cursor`: ```c memmove(&text[*cursor + n], &text[*cursor], sizeof text - *cursor - MAX(n, 0)); ``` Also, `sizeof text` gives the buffer size only if `text` is an array declared in scope. See C3. - **E7.** Destination equals source, so nothing changes. - **E8.** $-c \le n \le S - c$. The lower bound keeps the destination at or after gap 0. The upper bound keeps the count non-negative. - **E9.** The string occupies $[0, \text{size} + 1)$, NUL included. The tail $[\text{at}, \text{size} + 1)$ has $\text{size} - \text{at} + 1$ bytes, and it moves to $[\text{at} + 1, \text{size} + 2)$. That fits the new allocation of $\text{size} + 2$. Nothing falls off because the buffer grew first. ### F - **F1.** Wrong: it writes `a[n]`. Use `i < n`. - **F2.** Wrong: it needs 6 bytes, including the NUL. Use `char s[6]`. - **F3.** Wrong: that is the end gap. Use `start + len - 1`. - **F4.** Correct. - **F5.** Wrong. Use `end - start`. - **F6.** Wrong: it overruns by 1. Use `S - c - 1`. - **F7.** Wrong: it reads $n$ bytes past the end. Use `S - c - n`. - **F8.** Correct. `pos + n == size` fills exactly to the end. - **F9.** Wrong: it rejects a write that ends exactly at the end gap. - **F10.** Wrong: unsigned `i >= 0` is always true. Use `for (size_t i = n; i-- > 0; )`. - **F11.** Correct. - **F12.** Wrong: it writes one past the end. Use `dst[sizeof dst - 1]`. - **F13.** Wrong: `a` is a pointer here. Pass the length as a separate parameter. - **F14.** Correct. ### G - **G1.** ```c size_t at = *cursor; size_t tail = sizeof text - at; /* bytes from cursor to end */ size_t lost = n > 0 ? n : 0; /* bytes an insert pushes off the end */ memmove(text + at + n, text + at, tail - lost); ``` - **G2.** `end - start` is the length of $[\text{start}, \text{end})$ in `in`. It is copied to $[\text{off}, \text{off} + \text{end} - \text{start})$ in `out`. Requires $\text{off} + (\text{end} - \text{start}) \le OS$. - **G3.** `i` runs from `len - 1` down to `pos + 1`, for $\text{len} - \text{pos} - 1$ iterations. It is equivalent to `memmove(&s[pos + 1], &s[pos], len - pos - 1);`. That opens a hole at `pos` and drops the last element. - **G4.** It deletes the first $k$ elements. Shift $-k$, source $[k, \text{len})$, destination $[0, \text{len} - k)$. - **G5.** Elements $[j, i)$ move right by one into $[j + 1, i + 1)$, so `a[i]` is overwritten. This is the shift step of insertion sort, which saves `a[i]` beforehand.