You imitate by hand what malloc, free and realloc do.
The heap is H bytes in a row with addresses 0 to H − 1, and at first the whole heap is one free block.
The first line has H and the number of commands q, and the next q lines have the commands, one per line.
In every command the requested size n is rounded up to a multiple of 8 before use (a multiple of 8 stays as it is).
A free block is a longest unbroken run of bytes that are not lent out. In other words, neighbouring free space is always merged into one block.
"malloc n" picks, among the free blocks at least as large as the rounded size, the one with the lowest address, lends the rounded size from the very front of that block, and prints its start address.
If there is no such free block, print "null" and change nothing.
"free a" takes the block back and prints "ok" if a is the start address of a block that is lent out now.
Otherwise (an address already taken back, an address in the middle of a block, an address never lent) print "error" and change nothing.
"realloc a n" prints "error" and changes nothing if a is not the start address of a block that is lent out now.
If the rounded size is at most the current size of the block, keep only that much of the front, take the rest at the back, and print a.
If it is larger, and a free block sits right behind the block and the two sizes added are at least the rounded size, grow the block backwards in place and print a.
If it cannot grow that way, leave the old block as it is and look for a new block in the same way as malloc.
If one is found, lend the new block, take the old block back, and print the new address; if none is found, print "null" and change nothing.
After all commands, print on the last line the number of lent blocks, the number of free blocks, and the size of the largest free block (0 if there is no free block), separated by single spaces.
Input
H is a multiple of 8, 8 ≤ H ≤ 1,000,000. 1 ≤ q ≤ 2,000. 1 ≤ n ≤ 1,000,000. 0 ≤ a ≤ 1,000,000
Output
One line per command (an address, null, ok, error), then a last line with the number of lent blocks, the number of free blocks, and the size of the largest free block
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
This problem imitates, with a list of blocks, what happens behind C's malloc, free and realloc. Keep the blocks (start address, size, in use or not) in address order and scan from the front. Splitting inserts into the middle of the list and merging removes from the middle: Python insert and del, JS/TS splice, Java add(i, x) and remove(i), C# Insert and RemoveAt, C++ vectorinsert and erase, Craykon Insert and RemoveAt. C shifts the back part of an array by hand, one slot at a time. In real C the program itself borrows and returns memory; in C++ new/delete or std::vector does it, and in Python, JS, TS, Java, C# and Craykon a garbage collector does it. So mistakes like this problem's error happen only in C, and in C++ when you write new/delete yourself. Real C does not report an error when you free twice or free an address in the middle of a block; what happens then is undefined. Also, address 0 in this problem is just the first byte of the heap, so it is not like real C's free(NULL), which does nothing. Trap one: round the size up to a multiple of 8, with (n + 7) / 8 * 8. Without rounding, the third malloc of the first example gets 26 instead of 32. Written as (n / 8 + 1) * 8, a size of 16 that is already a multiple of 8 becomes 24. In JS/TS / gives a fraction, so use Math.floor; Python uses // and Craykon Mathf.Quot. Trap two: a returned block merges not only with the free block behind it but also with the free block in front. In the second example the middle block is returned last, and the three must become one block of 48 bytes for malloc 41 to succeed. The back part left over by a shrinking realloc also merges with the free block behind it. Trap three: an address already taken back must not be taken back again (the second free 16 of the second example). Do not only check that a block starts at that address; check that it is in use. An address in the middle of a block is also an error (free 16 in the first example is in the middle, because the block at address 0 has grown). Trap four: realloc is not 'free, then malloc'. While the new place is searched, the old block is still in use. realloc 32 40 in the first example is null, although the 32 free bytes in front plus the 8 bytes of the old block make 40. A real realloc also returns the old block only after copying the contents to the new place. Trap five: when realloc fails, the old block stays. That is why p = realloc(p, n); in C loses the address of the old block on failure: p is overwritten with NULL. Receive the result in another variable, check it, then move it over. Trap six: when growing in place, the free block behind may fit exactly (realloc 0 30 in the first example: 16 + 16 = 32). The free block then disappears. Trap seven: the block chosen is the free block with the lowest address (first fit), not the one whose size fits most tightly (best fit).
Pythonmain.py · 97 lines
import sysdef main(): lines = sys.stdin.read().split("\n") heap, q = map(int, lines[0].split()) # 블록을 주소 순서로 늘어놓는다: 시작 주소, 크기, 쓰는 중인가 start, size, used = [0], [heap], [False] def find(addr): # 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 for i in range(len(start)): if start[i] == addr: return i if used[i] else -1 return -1 def first_fit(need): # 주소가 가장 낮은, 충분히 큰 빈 블록 for i in range(len(start)): if not used[i] and size[i] >= need: return i return -1 def take(i, need): # 빈 블록 i의 앞쪽 need 바이트를 빌려준다. 남는 뒤쪽은 빈 블록으로 쪼갠다 if size[i] > need: start.insert(i + 1, start[i] + need) size.insert(i + 1, size[i] - need) used.insert(i + 1, False) size[i] = need used[i] = True def merge_next(i): # 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 if i + 1 < len(start) and not used[i + 1]: size[i] += size[i + 1] del start[i + 1], size[i + 1], used[i + 1] def release(i): used[i] = False merge_next(i) if i > 0 and not used[i - 1]: merge_next(i - 1) out = [] for line in lines[1:1 + q]: p = line.split() if p[0] == "malloc": need = (int(p[1]) + 7) // 8 * 8 # 8의 배수로 올림 i = first_fit(need) if i < 0: out.append("null") else: take(i, need) out.append(str(start[i])) elif p[0] == "free": i = find(int(p[1])) if i < 0: out.append("error") else: release(i) out.append("ok") else: i = find(int(p[1])) need = (int(p[2]) + 7) // 8 * 8 if i < 0: out.append("error") elif need <= size[i]: # 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 if need < size[i]: start.insert(i + 1, start[i] + need) size.insert(i + 1, size[i] - need) used.insert(i + 1, False) size[i] = need merge_next(i + 1) out.append(str(start[i])) elif i + 1 < len(start) and not used[i + 1] and size[i] + size[i + 1] >= need: # 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 rest = size[i] + size[i + 1] - need size[i] = need if rest > 0: start[i + 1] = start[i] + need size[i + 1] = rest else: del start[i + 1], size[i + 1], used[i + 1] out.append(str(start[i])) else: j = first_fit(need) # 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 if j < 0: out.append("null") # 옛 블록은 그대로 남는다 else: old = start[i] take(j, need) out.append(str(start[j])) release(find(old)) # take가 자리를 밀었을 수 있으니 다시 찾는다 busy = sum(used) free_sizes = [size[i] for i in range(len(start)) if not used[i]] out.append(f"{busy} {len(free_sizes)} {max(free_sizes, default=0)}") print("\n".join(out))main()
JavaScriptmain.js · 110 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [heap, q] = lines[0].split(" ").map(Number);// 블록을 주소 순서로 늘어놓는다: 시작 주소, 크기, 쓰는 중인가const start = [0], size = [heap], used = [false];function find(addr) { // 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 for (let i = 0; i < start.length; i++) { if (start[i] === addr) return used[i] ? i : -1; } return -1;}function firstFit(need) { // 주소가 가장 낮은, 충분히 큰 빈 블록 for (let i = 0; i < start.length; i++) { if (!used[i] && size[i] >= need) return i; } return -1;}function split(i, need) { // 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다 start.splice(i + 1, 0, start[i] + need); size.splice(i + 1, 0, size[i] - need); used.splice(i + 1, 0, false); size[i] = need;}function take(i, need) { if (size[i] > need) split(i, need); used[i] = true;}function removeAt(i) { start.splice(i, 1); size.splice(i, 1); used.splice(i, 1);}function mergeNext(i) { // 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 if (i + 1 < start.length && !used[i + 1]) { size[i] += size[i + 1]; removeAt(i + 1); }}function release(i) { used[i] = false; mergeNext(i); if (i > 0 && !used[i - 1]) mergeNext(i - 1);}const round8 = (n) => Math.floor((n + 7) / 8) * 8; // 8의 배수로 올림const out = [];for (let t = 1; t <= q; t++) { const p = lines[t].trim().split(" "); if (p[0] === "malloc") { const need = round8(Number(p[1])); const i = firstFit(need); if (i < 0) { out.push("null"); } else { take(i, need); out.push(String(start[i])); } } else if (p[0] === "free") { const i = find(Number(p[1])); if (i < 0) { out.push("error"); } else { release(i); out.push("ok"); } } else { const i = find(Number(p[1])); const need = round8(Number(p[2])); if (i < 0) { out.push("error"); } else if (need <= size[i]) { // 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 if (need < size[i]) { split(i, need); mergeNext(i + 1); } out.push(String(start[i])); } else if (i + 1 < start.length && !used[i + 1] && size[i] + size[i + 1] >= need) { // 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 const rest = size[i] + size[i + 1] - need; size[i] = need; if (rest > 0) { start[i + 1] = start[i] + need; size[i + 1] = rest; } else { removeAt(i + 1); } out.push(String(start[i])); } else { const j = firstFit(need); // 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 if (j < 0) { out.push("null"); // 옛 블록은 그대로 남는다 } else { const old = start[i]; take(j, need); out.push(String(start[j])); release(find(old)); // take가 자리를 밀었을 수 있으니 다시 찾는다 } } }}let busy = 0, holes = 0, largest = 0;for (let i = 0; i < start.length; i++) { if (used[i]) busy++; else { holes++; if (size[i] > largest) largest = size[i]; }}out.push(busy + " " + holes + " " + largest);console.log(out.join("\n"));
TypeScriptmain.ts · 112 lines
import * as fs from "fs";const lines: string[] = fs.readFileSync(0, "utf8").split("\n");const [heap, q] = lines[0].split(" ").map(Number);// 블록을 주소 순서로 늘어놓는다: 시작 주소, 크기, 쓰는 중인가const start: number[] = [0], size: number[] = [heap], used: boolean[] = [false];function find(addr: number): number { // 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 for (let i = 0; i < start.length; i++) { if (start[i] === addr) return used[i] ? i : -1; } return -1;}function firstFit(need: number): number { // 주소가 가장 낮은, 충분히 큰 빈 블록 for (let i = 0; i < start.length; i++) { if (!used[i] && size[i] >= need) return i; } return -1;}function split(i: number, need: number): void { // 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다 start.splice(i + 1, 0, start[i] + need); size.splice(i + 1, 0, size[i] - need); used.splice(i + 1, 0, false); size[i] = need;}function take(i: number, need: number): void { if (size[i] > need) split(i, need); used[i] = true;}function removeAt(i: number): void { start.splice(i, 1); size.splice(i, 1); used.splice(i, 1);}function mergeNext(i: number): void { // 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 if (i + 1 < start.length && !used[i + 1]) { size[i] += size[i + 1]; removeAt(i + 1); }}function release(i: number): void { used[i] = false; mergeNext(i); if (i > 0 && !used[i - 1]) mergeNext(i - 1);}const round8 = (n: number): number => Math.floor((n + 7) / 8) * 8; // 8의 배수로 올림const out: string[] = [];for (let t = 1; t <= q; t++) { const p = lines[t].trim().split(" "); if (p[0] === "malloc") { const need = round8(Number(p[1])); const i = firstFit(need); if (i < 0) { out.push("null"); } else { take(i, need); out.push(String(start[i])); } } else if (p[0] === "free") { const i = find(Number(p[1])); if (i < 0) { out.push("error"); } else { release(i); out.push("ok"); } } else { const i = find(Number(p[1])); const need = round8(Number(p[2])); if (i < 0) { out.push("error"); } else if (need <= size[i]) { // 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 if (need < size[i]) { split(i, need); mergeNext(i + 1); } out.push(String(start[i])); } else if (i + 1 < start.length && !used[i + 1] && size[i] + size[i + 1] >= need) { // 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 const rest = size[i] + size[i + 1] - need; size[i] = need; if (rest > 0) { start[i + 1] = start[i] + need; size[i + 1] = rest; } else { removeAt(i + 1); } out.push(String(start[i])); } else { const j = firstFit(need); // 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 if (j < 0) { out.push("null"); // 옛 블록은 그대로 남는다 } else { const old = start[i]; take(j, need); out.push(String(start[j])); release(find(old)); // take가 자리를 밀었을 수 있으니 다시 찾는다 } } }}let busy = 0, holes = 0, largest = 0;for (let i = 0; i < start.length; i++) { if (used[i]) busy++; else { holes++; if (size[i] > largest) largest = size[i]; }}out.push(busy + " " + holes + " " + largest);console.log(out.join("\n"));
JavaMain.java · 128 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;public class Main { // 블록을 주소 순서로 늘어놓는다: {시작 주소, 크기, 쓰는 중이면 1} static ArrayList<int[]> blocks = new ArrayList<>(); static int find(int addr) { // 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 for (int i = 0; i < blocks.size(); i++) { if (blocks.get(i)[0] == addr) return blocks.get(i)[2] == 1 ? i : -1; } return -1; } static int firstFit(int need) { // 주소가 가장 낮은, 충분히 큰 빈 블록 for (int i = 0; i < blocks.size(); i++) { int[] b = blocks.get(i); if (b[2] == 0 && b[1] >= need) return i; } return -1; } static void split(int i, int need) { // 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다 int[] b = blocks.get(i); blocks.add(i + 1, new int[] {b[0] + need, b[1] - need, 0}); b[1] = need; } static void take(int i, int need) { if (blocks.get(i)[1] > need) split(i, need); blocks.get(i)[2] = 1; } static void mergeNext(int i) { // 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 if (i + 1 < blocks.size() && blocks.get(i + 1)[2] == 0) { blocks.get(i)[1] += blocks.get(i + 1)[1]; blocks.remove(i + 1); // int 자리 번호로 지운다 } } static void release(int i) { blocks.get(i)[2] = 0; mergeNext(i); if (i > 0 && blocks.get(i - 1)[2] == 0) mergeNext(i - 1); } static int round8(int n) { // 8의 배수로 올림 return (n + 7) / 8 * 8; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] first = br.readLine().trim().split(" "); int heap = Integer.parseInt(first[0]); int q = Integer.parseInt(first[1]); blocks.add(new int[] {0, heap, 0}); StringBuilder sb = new StringBuilder(); for (int t = 0; t < q; t++) { String[] p = br.readLine().trim().split(" "); if (p[0].equals("malloc")) { int need = round8(Integer.parseInt(p[1])); int i = firstFit(need); if (i < 0) { sb.append("null\n"); } else { take(i, need); sb.append(blocks.get(i)[0]).append('\n'); } } else if (p[0].equals("free")) { int i = find(Integer.parseInt(p[1])); if (i < 0) { sb.append("error\n"); } else { release(i); sb.append("ok\n"); } } else { int i = find(Integer.parseInt(p[1])); int need = round8(Integer.parseInt(p[2])); if (i < 0) { sb.append("error\n"); continue; } int[] b = blocks.get(i); if (need <= b[1]) { // 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 if (need < b[1]) { split(i, need); mergeNext(i + 1); } sb.append(b[0]).append('\n'); } else if (i + 1 < blocks.size() && blocks.get(i + 1)[2] == 0 && b[1] + blocks.get(i + 1)[1] >= need) { // 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 int[] next = blocks.get(i + 1); int rest = b[1] + next[1] - need; b[1] = need; if (rest > 0) { next[0] = b[0] + need; next[1] = rest; } else { blocks.remove(i + 1); } sb.append(b[0]).append('\n'); } else { int j = firstFit(need); // 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 if (j < 0) { sb.append("null\n"); // 옛 블록은 그대로 남는다 } else { take(j, need); sb.append(blocks.get(j)[0]).append('\n'); release(find(b[0])); // take가 자리를 밀었을 수 있으니 다시 찾는다 } } } } int busy = 0, holes = 0, largest = 0; for (int[] b : blocks) { if (b[2] == 1) busy++; else { holes++; largest = Math.max(largest, b[1]); } } sb.append(busy).append(' ').append(holes).append(' ').append(largest).append('\n'); System.out.print(sb); }}
C#Main.cs · 167 lines
using System;using System.Collections.Generic;using System.Text;class Block{ public int Start, Size; public bool Used;}class Program{ // 블록을 주소 순서로 늘어놓는다 static List<Block> blocks = new List<Block>(); static int Find(int addr) // 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 { for (int i = 0; i < blocks.Count; i++) { if (blocks[i].Start == addr) return blocks[i].Used ? i : -1; } return -1; } static int FirstFit(int need) // 주소가 가장 낮은, 충분히 큰 빈 블록 { for (int i = 0; i < blocks.Count; i++) { if (!blocks[i].Used && blocks[i].Size >= need) return i; } return -1; } static void Split(int i, int need) // 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다 { Block b = blocks[i]; blocks.Insert(i + 1, new Block { Start = b.Start + need, Size = b.Size - need, Used = false }); b.Size = need; } static void Take(int i, int need) { if (blocks[i].Size > need) Split(i, need); blocks[i].Used = true; } static void MergeNext(int i) // 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 { if (i + 1 < blocks.Count && !blocks[i + 1].Used) { blocks[i].Size += blocks[i + 1].Size; blocks.RemoveAt(i + 1); } } static void Release(int i) { blocks[i].Used = false; MergeNext(i); if (i > 0 && !blocks[i - 1].Used) MergeNext(i - 1); } static int Round8(int n) => (n + 7) / 8 * 8; // 8의 배수로 올림 static void Main() { string[] first = Console.ReadLine().Trim().Split(' '); int heap = int.Parse(first[0]); int q = int.Parse(first[1]); blocks.Add(new Block { Start = 0, Size = heap, Used = false }); var sb = new StringBuilder(); for (int t = 0; t < q; t++) { string[] p = Console.ReadLine().Trim().Split(' '); if (p[0] == "malloc") { int need = Round8(int.Parse(p[1])); int i = FirstFit(need); if (i < 0) { sb.Append("null\n"); } else { Take(i, need); sb.Append(blocks[i].Start).Append('\n'); } } else if (p[0] == "free") { int i = Find(int.Parse(p[1])); if (i < 0) { sb.Append("error\n"); } else { Release(i); sb.Append("ok\n"); } } else { int i = Find(int.Parse(p[1])); int need = Round8(int.Parse(p[2])); if (i < 0) { sb.Append("error\n"); continue; } Block b = blocks[i]; if (need <= b.Size) // 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 { if (need < b.Size) { Split(i, need); MergeNext(i + 1); } sb.Append(b.Start).Append('\n'); } else if (i + 1 < blocks.Count && !blocks[i + 1].Used && b.Size + blocks[i + 1].Size >= need) { // 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 Block next = blocks[i + 1]; int rest = b.Size + next.Size - need; b.Size = need; if (rest > 0) { next.Start = b.Start + need; next.Size = rest; } else { blocks.RemoveAt(i + 1); } sb.Append(b.Start).Append('\n'); } else { int j = FirstFit(need); // 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 if (j < 0) { sb.Append("null\n"); // 옛 블록은 그대로 남는다 } else { Take(j, need); sb.Append(blocks[j].Start).Append('\n'); Release(Find(b.Start)); // Take가 자리를 밀었을 수 있으니 다시 찾는다 } } } } int busy = 0, holes = 0, largest = 0; foreach (Block b in blocks) { if (b.Used) busy++; else { holes++; largest = Math.Max(largest, b.Size); } } sb.Append(busy).Append(' ').Append(holes).Append(' ').Append(largest).Append('\n'); Console.Write(sb); }}
C++main.cpp · 131 lines
#include <iostream>#include <string>#include <vector>using namespace std;struct Block { int start, size; bool used;};// 블록을 주소 순서로 늘어놓는다static vector<Block> blocks;static int findBlock(int addr) { // 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 for (int i = 0; i < (int)blocks.size(); i++) { if (blocks[i].start == addr) return blocks[i].used ? i : -1; } return -1;}static int firstFit(int need) { // 주소가 가장 낮은, 충분히 큰 빈 블록 for (int i = 0; i < (int)blocks.size(); i++) { if (!blocks[i].used && blocks[i].size >= need) return i; } return -1;}static void split(int i, int need) { // 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다 Block rest{blocks[i].start + need, blocks[i].size - need, false}; blocks[i].size = need; blocks.insert(blocks.begin() + i + 1, rest);}static void take(int i, int need) { if (blocks[i].size > need) split(i, need); blocks[i].used = true;}static void mergeNext(int i) { // 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 if (i + 1 < (int)blocks.size() && !blocks[i + 1].used) { blocks[i].size += blocks[i + 1].size; blocks.erase(blocks.begin() + i + 1); }}static void release(int i) { blocks[i].used = false; mergeNext(i); if (i > 0 && !blocks[i - 1].used) mergeNext(i - 1);}static int round8(int n) { return (n + 7) / 8 * 8; } // 8의 배수로 올림int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int heap, q; if (!(cin >> heap >> q)) return 0; blocks.push_back({0, heap, false}); for (int t = 0; t < q; t++) { string cmd; cin >> cmd; if (cmd == "malloc") { int n; cin >> n; int need = round8(n); int i = firstFit(need); if (i < 0) { cout << "null\n"; } else { take(i, need); cout << blocks[i].start << "\n"; } } else if (cmd == "free") { int a; cin >> a; int i = findBlock(a); if (i < 0) { cout << "error\n"; } else { release(i); cout << "ok\n"; } } else { int a, n; cin >> a >> n; int i = findBlock(a); int need = round8(n); if (i < 0) { cout << "error\n"; } else if (need <= blocks[i].size) { // 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 if (need < blocks[i].size) { split(i, need); mergeNext(i + 1); } cout << blocks[i].start << "\n"; } else if (i + 1 < (int)blocks.size() && !blocks[i + 1].used && blocks[i].size + blocks[i + 1].size >= need) { // 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 int rest = blocks[i].size + blocks[i + 1].size - need; blocks[i].size = need; if (rest > 0) { blocks[i + 1].start = blocks[i].start + need; blocks[i + 1].size = rest; } else { blocks.erase(blocks.begin() + i + 1); } cout << blocks[i].start << "\n"; } else { int j = firstFit(need); // 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 if (j < 0) { cout << "null\n"; // 옛 블록은 그대로 남는다 } else { int old = blocks[i].start; take(j, need); cout << blocks[j].start << "\n"; release(findBlock(old)); // take가 자리를 밀었을 수 있으니 다시 찾는다 } } } } int busy = 0, holes = 0, largest = 0; for (const Block& b : blocks) { if (b.used) busy++; else { holes++; if (b.size > largest) largest = b.size; } } cout << busy << " " << holes << " " << largest << "\n"; return 0;}
Cmain.c · 141 lines
#include <stdio.h>#include <string.h>#define MAXB 4096 /* 명령 하나가 블록을 많아야 1개 늘린다 *//* 블록을 주소 순서로 늘어놓는다: 시작 주소, 크기, 쓰는 중인가 */static int start[MAXB], size[MAXB], used[MAXB];static int count = 1;static int find(int addr) { /* 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 */ for (int i = 0; i < count; i++) { if (start[i] == addr) return used[i] ? i : -1; } return -1;}static int first_fit(int need) { /* 주소가 가장 낮은, 충분히 큰 빈 블록 */ for (int i = 0; i < count; i++) { if (!used[i] && size[i] >= need) return i; } return -1;}static void split(int i, int need) { /* 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다 */ for (int k = count; k > i + 1; k--) { start[k] = start[k - 1]; size[k] = size[k - 1]; used[k] = used[k - 1]; } count++; start[i + 1] = start[i] + need; size[i + 1] = size[i] - need; used[i + 1] = 0; size[i] = need;}static void take(int i, int need) { if (size[i] > need) split(i, need); used[i] = 1;}static void remove_at(int i) { for (int k = i; k + 1 < count; k++) { start[k] = start[k + 1]; size[k] = size[k + 1]; used[k] = used[k + 1]; } count--;}static void merge_next(int i) { /* 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 */ if (i + 1 < count && !used[i + 1]) { size[i] += size[i + 1]; remove_at(i + 1); }}static void release(int i) { used[i] = 0; merge_next(i); if (i > 0 && !used[i - 1]) merge_next(i - 1);}static int round8(int n) { return (n + 7) / 8 * 8; } /* 8의 배수로 올림 */int main(void) { int heap, q; if (scanf("%d %d", &heap, &q) != 2) return 0; start[0] = 0; size[0] = heap; used[0] = 0; for (int t = 0; t < q; t++) { char cmd[16]; int a, n; if (scanf("%15s", cmd) != 1) return 0; if (strcmp(cmd, "malloc") == 0) { if (scanf("%d", &n) != 1) return 0; int need = round8(n); int i = first_fit(need); if (i < 0) { printf("null\n"); } else { take(i, need); printf("%d\n", start[i]); } } else if (strcmp(cmd, "free") == 0) { if (scanf("%d", &a) != 1) return 0; int i = find(a); if (i < 0) { printf("error\n"); } else { release(i); printf("ok\n"); } } else { if (scanf("%d %d", &a, &n) != 2) return 0; int i = find(a); int need = round8(n); if (i < 0) { printf("error\n"); } else if (need <= size[i]) { /* 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 */ if (need < size[i]) { split(i, need); merge_next(i + 1); } printf("%d\n", start[i]); } else if (i + 1 < count && !used[i + 1] && size[i] + size[i + 1] >= need) { /* 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 */ int rest = size[i] + size[i + 1] - need; size[i] = need; if (rest > 0) { start[i + 1] = start[i] + need; size[i + 1] = rest; } else { remove_at(i + 1); } printf("%d\n", start[i]); } else { int j = first_fit(need); /* 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 */ if (j < 0) { printf("null\n"); /* 옛 블록은 그대로 남는다 */ } else { int old = start[i]; take(j, need); printf("%d\n", start[j]); release(find(old)); /* take가 자리를 밀었을 수 있으니 다시 찾는다 */ } } } } int busy = 0, holes = 0, largest = 0; for (int i = 0; i < count; i++) { if (used[i]) busy++; else { holes++; if (size[i] > largest) largest = size[i]; } } printf("%d %d %d\n", busy, holes, largest); return 0;}
Craykonmain.cray · 190 lines
// 블록을 주소 순서로 늘어놓는다: 시작 주소, 크기, 쓰는 중인가first = Console.ReadLine().Trim().Split(" ");heap = first[0].ToNumber();q = first[1].ToNumber();start = [0];size = [heap];used = [false];// 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1find(addr){ for (i = 0; i < start.Count; i++) { if (start[i] == addr) { if (used[i]) { return i; } return -1; } } return -1;}// 주소가 가장 낮은, 충분히 큰 빈 블록firstFit(need){ for (i = 0; i < start.Count; i++) { if (!used[i] && size[i] >= need) { return i; } } return -1;}// 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다split(i, need){ start.Insert(i + 1, start[i] + need); size.Insert(i + 1, size[i] - need); used.Insert(i + 1, false); size[i] = need;}take(i, need){ if (size[i] > need) { split(i, need); } used[i] = true;}removeAt(i){ start.RemoveAt(i); size.RemoveAt(i); used.RemoveAt(i);}// 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다mergeNext(i){ if (i + 1 < start.Count && !used[i + 1]) { size[i] = size[i] + size[i + 1]; removeAt(i + 1); }}release(i){ used[i] = false; mergeNext(i); if (i > 0 && !used[i - 1]) { mergeNext(i - 1); }}// 8의 배수로 올림round8(n){ return Mathf.Quot(n + 7, 8) * 8;}for (t = 0; t < q; t++){ p = Console.ReadLine().Trim().Split(" "); if (p[0] == "malloc") { need = round8(p[1].ToNumber()); i = firstFit(need); if (i < 0) { Console.WriteLine("null"); } else { take(i, need); Console.WriteLine(start[i]); } } else if (p[0] == "free") { i = find(p[1].ToNumber()); if (i < 0) { Console.WriteLine("error"); } else { release(i); Console.WriteLine("ok"); } } else { i = find(p[1].ToNumber()); need = round8(p[2].ToNumber()); if (i < 0) { Console.WriteLine("error"); } else if (need <= size[i]) { // 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 if (need < size[i]) { split(i, need); mergeNext(i + 1); } Console.WriteLine(start[i]); } else if (i + 1 < start.Count && !used[i + 1] && size[i] + size[i + 1] >= need) { // 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 rest = size[i] + size[i + 1] - need; size[i] = need; if (rest > 0) { start[i + 1] = start[i] + need; size[i + 1] = rest; } else { removeAt(i + 1); } Console.WriteLine(start[i]); } else { // 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 j = firstFit(need); if (j < 0) { Console.WriteLine("null"); // 옛 블록은 그대로 남는다 } else { old = start[i]; take(j, need); Console.WriteLine(start[j]); release(find(old)); // take가 자리를 밀었을 수 있으니 다시 찾는다 } } }}busy = 0;holes = 0;largest = 0;for (i = 0; i < start.Count; i++){ if (used[i]) { busy = busy + 1; } else { holes = holes + 1; if (size[i] > largest) { largest = size[i]; } }}Console.WriteLine("" + busy + " " + holes + " " + largest);