| 93 |
Kevin |
1 |
> Let's assume that this was called with a 10 slot array and a 175
|
|
|
2 |
> byte memory pool.
|
|
|
3 |
|
|
|
4 |
print
|
|
|
5 |
|
|
|
6 |
> Freelist: [0, 174] (175 bytes)
|
|
|
7 |
|
|
|
8 |
insert 0 4240 7345 Albany
|
|
|
9 |
|
|
|
10 |
> 15 bytes taken
|
|
|
11 |
> Freelist: [15, 174] (160 bytes)
|
|
|
12 |
|
|
|
13 |
insert 1 3455 13836 Albuquerque
|
|
|
14 |
|
|
|
15 |
> 20 bytes taken
|
|
|
16 |
> Freelist: [35, 174] (140 bytes)
|
|
|
17 |
|
|
|
18 |
insert 2 3511 10150 Amarillo
|
|
|
19 |
|
|
|
20 |
> 17 bytes taken
|
|
|
21 |
> Freelist: [52, 174] (123 bytes)
|
|
|
22 |
|
|
|
23 |
insert 3 6113 14954 Anchorage
|
|
|
24 |
|
|
|
25 |
> 18 bytes taken
|
|
|
26 |
> Freelist: [70, 174] (105 bytes)
|
|
|
27 |
|
|
|
28 |
insert 4 3345 8423 Atlanta
|
|
|
29 |
|
|
|
30 |
> 16 bytes taken
|
|
|
31 |
> Freelist: [86, 174] (89 bytes)
|
|
|
32 |
|
|
|
33 |
remove 4
|
|
|
34 |
|
|
|
35 |
> This frees up the 16 bytes at the end, which merges with the free block
|
|
|
36 |
> Freelist: [70, 174] (105 bytes)
|
|
|
37 |
|
|
|
38 |
> 0: (4240, 7345) Albany
|
|
|
39 |
> 1: (3455, 13836) Albuquerque
|
|
|
40 |
> 2: (3511, 10150) Amarillo
|
|
|
41 |
> 3: (6113, 14954) Anchorage
|
|
|
42 |
> 4: [no record]
|
|
|
43 |
> 5: [no record]
|
|
|
44 |
|
|
|
45 |
print 0
|
|
|
46 |
|
|
|
47 |
> 4240 7345 Albany
|
|
|
48 |
|
|
|
49 |
print 1
|
|
|
50 |
|
|
|
51 |
> 3455 13836 Albuquerque
|
|
|
52 |
|
|
|
53 |
print 2
|
|
|
54 |
|
|
|
55 |
> 3511 10150 Amarillo
|
|
|
56 |
|
|
|
57 |
print 3
|
|
|
58 |
|
|
|
59 |
> 6113 14954 Anchorage
|
|
|
60 |
|
|
|
61 |
print 4
|
|
|
62 |
|
|
|
63 |
> Slot 4 is empty
|
|
|
64 |
|
|
|
65 |
print 5
|
|
|
66 |
|
|
|
67 |
> Slot 5 is empty
|
|
|
68 |
|
|
|
69 |
insert 5 2515 5740 Asuncion_Paraguay
|
|
|
70 |
|
|
|
71 |
> 26 bytes taken
|
|
|
72 |
> Freelist: [96, 174] (79 bytes)
|
|
|
73 |
|
|
|
74 |
print 5
|
|
|
75 |
|
|
|
76 |
> 2515 5740 Asuncion_Paraguay
|
|
|
77 |
|
|
|
78 |
insert 6 4447 11750 Baker
|
|
|
79 |
|
|
|
80 |
> 14 bytes taken
|
|
|
81 |
> Freelist: [110, 174] (65 bytes)
|
|
|
82 |
|
|
|
83 |
insert 7 3918 7638 Baltimore
|
|
|
84 |
|
|
|
85 |
> 18 bytes taken
|
|
|
86 |
> Freelist: [128, 174] (47 bytes)
|
|
|
87 |
|
|
|
88 |
insert 7 3918 7638 Baltimore
|
|
|
89 |
|
|
|
90 |
> Since this is overwriting slot 7, the old message is deleted,
|
|
|
91 |
> freeing 18 bytes, which happen to be at the end and which merge with
|
|
|
92 |
> the existing free block.
|
|
|
93 |
> 18 bytes are then taken for the new message
|
|
|
94 |
> Freelist: [128, 174] (47 bytes)
|
|
|
95 |
|
|
|
96 |
insert 8 3955 11625 Beijing_China
|
|
|
97 |
|
|
|
98 |
> 22 bytes taken
|
|
|
99 |
> Freelist: [150, 174] (25 bytes)
|
|
|
100 |
|
|
|
101 |
insert 9 3330 8650 Birmingham
|
|
|
102 |
|
|
|
103 |
> 19 bytes taken
|
|
|
104 |
> Freelist: [169, 174] (6 bytes)
|
|
|
105 |
|
|
|
106 |
print
|
|
|
107 |
> [0] --> 0: (4240, 7345) Albany
|
|
|
108 |
> [15] --> 1: (3455, 13836) Albuquerque
|
|
|
109 |
> [35] --> 2: (3511, 10150) Amarillo
|
|
|
110 |
> [52] --> 3: (6113, 14954) Anchorage
|
|
|
111 |
> 4: [no record]
|
|
|
112 |
> [70] --> 5: (2515, 5740) Asuncion_Paraguay
|
|
|
113 |
> [96] --> 6: (4447, 11750) Baker
|
|
|
114 |
> [110] --> 7: (3918, 7638) Baltimore
|
|
|
115 |
> [128] --> 8: (3955, 11625) Beijing_China
|
|
|
116 |
> [150] --> 9: (3330, 8650) Birmingham
|
|
|
117 |
|
|
|
118 |
remove 9
|
|
|
119 |
|
|
|
120 |
> This frees 19 bytes, which merge with the free block at the end.
|
|
|
121 |
> Freelist: [150, 174] (25 bytes)
|
|
|
122 |
|
|
|
123 |
print 9
|
|
|
124 |
|
|
|
125 |
> Slot 9 is empty
|
|
|
126 |
|
|
|
127 |
insert 9 3355 1822 Cape_Town_South_Africa
|
|
|
128 |
|
|
|
129 |
> This requires 31 bytes, but there is not a block of this size
|
|
|
130 |
> available. Therefore, nothing is inserted (or otherwise changed)
|
|
|
131 |
> Freelist: [150, 174] (25 bytes)
|
|
|
132 |
|
|
|
133 |
print 9
|
|
|
134 |
|
|
|
135 |
> Slot 9 is empty
|
|
|
136 |
|
|
|
137 |
remove 3
|
|
|
138 |
|
|
|
139 |
> Free up 18 bytes
|
|
|
140 |
> Freelist: [52, 69] (18 bytes)
|
|
|
141 |
> [150, 174] (25 bytes)
|
|
|
142 |
|
|
|
143 |
remove 4
|
|
|
144 |
|
|
|
145 |
> Nothing happens since Slot 4 is empty
|
|
|
146 |
|
|
|
147 |
remove 6
|
|
|
148 |
|
|
|
149 |
> Free up 14 bytes starting at position 96
|
|
|
150 |
> Freelist: [52, 69] (18 bytes);
|
|
|
151 |
> [96, 109] (14 bytes);
|
|
|
152 |
> [150, 174] (25 bytes)
|
|
|
153 |
|
|
|
154 |
remove 7
|
|
|
155 |
|
|
|
156 |
> Free up 18 bytes starting at position 110. Since this is adjacent to
|
|
|
157 |
> an existing free block, they merge.
|
|
|
158 |
> Freelist: [52, 69] (18 bytes);
|
|
|
159 |
> [96, 127] (32 bytes);
|
|
|
160 |
> [150, 174] (25 bytes)
|
|
|
161 |
|
|
|
162 |
remove 7
|
|
|
163 |
|
|
|
164 |
> Since Slot 7 is empty, nothing happens.
|
|
|
165 |
> Freelist: [52, 69] (18 bytes);
|
|
|
166 |
> [96, 127] (32 bytes);
|
|
|
167 |
> [150, 174] (25 bytes)
|
|
|
168 |
|
|
|
169 |
remove 8
|
|
|
170 |
|
|
|
171 |
> Free 22 bytes starting at postion 128. Since there are free blocks
|
|
|
172 |
> to either side, all three merge together.
|
|
|
173 |
> Freelist: [52, 69] (18 bytes);
|
|
|
174 |
> [96, 174] (79 bytes);
|
|
|
175 |
|
|
|
176 |
insert 7 2308 8223 Havana_Cuba
|
|
|
177 |
|
|
|
178 |
> 20 bytes taken. The first free block is not big enough, so take from
|
|
|
179 |
> the second.
|
|
|
180 |
> Freelist: [52, 69] (18 bytes);
|
|
|
181 |
> [116, 174] (59 bytes);
|
|
|
182 |
|
|
|
183 |
insert 7 2946 10634 Chongqing_China
|
|
|
184 |
|
|
|
185 |
> First the 20 bytes from the message currently stored is freed, whose
|
|
|
186 |
> space merges with the block at the end of the list. Then 24 bytes
|
|
|
187 |
> are reserved from the second block, since the first is not big enough.
|
|
|
188 |
> Freelist: [52, 69] (18 bytes);
|
|
|
189 |
> [120, 174] (55 bytes);
|
|
|
190 |
|
|
|
191 |
insert 8 616 10648 Jakarta_Indonesia
|
|
|
192 |
|
|
|
193 |
> 26 bytes taken from the second block
|
|
|
194 |
> Freelist: [52, 69] (18 bytes);
|
|
|
195 |
> [146, 174] (29 bytes);
|
|
|
196 |
|
|
|
197 |
print
|
|
|
198 |
|
|
|
199 |
> Print out the current records in the array
|
|
|
200 |
> [0] --> 0: 4240 7345 Albany
|
|
|
201 |
> [15] --> 1: 3455 13836 Albuquerque
|
|
|
202 |
> [35] --> 2: 3511 10150 Amarillo
|
|
|
203 |
> 3: [no record]
|
|
|
204 |
> 4: [no record]
|
|
|
205 |
> [70] --> 5: (2515, 5740) Asuncion_Paraguay
|
|
|
206 |
> 6: [no record]
|
|
|
207 |
> [96] --> 7: 2946 10634 Chongqing_China
|
|
|
208 |
> [120] --> 8: 616 10648 Jakarta_Indonesia
|
|
|
209 |
> 9: [no record]
|
|
|
210 |
|
|
|
211 |
remove 8
|
|
|
212 |
|
|
|
213 |
> Free 26 bytes and merge with second block.
|
|
|
214 |
> Freelist: [52, 69] (18 bytes);
|
|
|
215 |
> [120, 174] (55 bytes);
|