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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
// 블록을 주소 순서로 늘어놓는다: 시작 주소, 크기, 쓰는 중인가first = コンソール.行読み().空白除去().分ける(" ");heap = first[0].数に();q = first[1].数に();start = [0];size = [heap];used = [偽];// 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1find(addr){ 繰り返す (i = 0; i < start.個数; i++) { もし (start[i] == addr) { もし (used[i]) { 返す i; } 返す -1; } } 返す -1;}// 주소가 가장 낮은, 충분히 큰 빈 블록firstFit(need){ 繰り返す (i = 0; i < start.個数; i++) { もし (!used[i] && size[i] >= need) { 返す i; } } 返す -1;}// 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다split(i, need){ start.挿入(i + 1, start[i] + need); size.挿入(i + 1, size[i] - need); used.挿入(i + 1, 偽); size[i] = need;}take(i, need){ もし (size[i] > need) { split(i, need); } used[i] = 真;}removeAt(i){ start.位置で取り除く(i); size.位置で取り除く(i); used.位置で取り除く(i);}// 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다mergeNext(i){ もし (i + 1 < start.個数 && !used[i + 1]) { size[i] = size[i] + size[i + 1]; removeAt(i + 1); }}release(i){ used[i] = 偽; mergeNext(i); もし (i > 0 && !used[i - 1]) { mergeNext(i - 1); }}// 8의 배수로 올림round8(n){ 返す 数学.商(n + 7, 8) * 8;}繰り返す (t = 0; t < q; t++){ p = コンソール.行読み().空白除去().分ける(" "); もし (p[0] == "malloc") { need = round8(p[1].数に()); i = firstFit(need); もし (i < 0) { コンソール.書く("null"); } でなければ { take(i, need); コンソール.書く(start[i]); } } でなければ もし (p[0] == "free") { i = find(p[1].数に()); もし (i < 0) { コンソール.書く("error"); } でなければ { release(i); コンソール.書く("ok"); } } でなければ { i = find(p[1].数に()); need = round8(p[2].数に()); もし (i < 0) { コンソール.書く("error"); } でなければ もし (need <= size[i]) { // 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 もし (need < size[i]) { split(i, need); mergeNext(i + 1); } コンソール.書く(start[i]); } でなければ もし (i + 1 < start.個数 && !used[i + 1] && size[i] + size[i + 1] >= need) { // 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 rest = size[i] + size[i + 1] - need; size[i] = need; もし (rest > 0) { start[i + 1] = start[i] + need; size[i + 1] = rest; } でなければ { removeAt(i + 1); } コンソール.書く(start[i]); } でなければ { // 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 j = firstFit(need); もし (j < 0) { コンソール.書く("null"); // 옛 블록은 그대로 남는다 } でなければ { old = start[i]; take(j, need); コンソール.書く(start[j]); release(find(old)); // take가 자리를 밀었을 수 있으니 다시 찾는다 } } }}busy = 0;holes = 0;largest = 0;繰り返す (i = 0; i < start.個数; i++){ もし (used[i]) { busy = busy + 1; } でなければ { holes = holes + 1; もし (size[i] > largest) { largest = size[i]; } }}コンソール.書く("" + busy + " " + holes + " " + largest);