| 0,0 → 1,215 |
|---|
| > Let's assume that this was called with a 10 slot array and a 175 |
| > byte memory pool. |
| |
| print |
| |
| > Freelist: [0, 174] (175 bytes) |
| |
| insert 0 4240 7345 Albany |
| |
| > 15 bytes taken |
| > Freelist: [15, 174] (160 bytes) |
| |
| insert 1 3455 13836 Albuquerque |
| |
| > 20 bytes taken |
| > Freelist: [35, 174] (140 bytes) |
| |
| insert 2 3511 10150 Amarillo |
| |
| > 17 bytes taken |
| > Freelist: [52, 174] (123 bytes) |
| |
| insert 3 6113 14954 Anchorage |
| |
| > 18 bytes taken |
| > Freelist: [70, 174] (105 bytes) |
| |
| insert 4 3345 8423 Atlanta |
| |
| > 16 bytes taken |
| > Freelist: [86, 174] (89 bytes) |
| |
| remove 4 |
| |
| > This frees up the 16 bytes at the end, which merges with the free block |
| > Freelist: [70, 174] (105 bytes) |
| |
| > 0: (4240, 7345) Albany |
| > 1: (3455, 13836) Albuquerque |
| > 2: (3511, 10150) Amarillo |
| > 3: (6113, 14954) Anchorage |
| > 4: [no record] |
| > 5: [no record] |
| |
| print 0 |
| |
| > 4240 7345 Albany |
| |
| print 1 |
| |
| > 3455 13836 Albuquerque |
| |
| print 2 |
| |
| > 3511 10150 Amarillo |
| |
| print 3 |
| |
| > 6113 14954 Anchorage |
| |
| print 4 |
| |
| > Slot 4 is empty |
| |
| print 5 |
| |
| > Slot 5 is empty |
| |
| insert 5 2515 5740 Asuncion_Paraguay |
| |
| > 26 bytes taken |
| > Freelist: [96, 174] (79 bytes) |
| |
| print 5 |
| |
| > 2515 5740 Asuncion_Paraguay |
| |
| insert 6 4447 11750 Baker |
| |
| > 14 bytes taken |
| > Freelist: [110, 174] (65 bytes) |
| |
| insert 7 3918 7638 Baltimore |
| |
| > 18 bytes taken |
| > Freelist: [128, 174] (47 bytes) |
| |
| insert 7 3918 7638 Baltimore |
| |
| > Since this is overwriting slot 7, the old message is deleted, |
| > freeing 18 bytes, which happen to be at the end and which merge with |
| > the existing free block. |
| > 18 bytes are then taken for the new message |
| > Freelist: [128, 174] (47 bytes) |
| |
| insert 8 3955 11625 Beijing_China |
| |
| > 22 bytes taken |
| > Freelist: [150, 174] (25 bytes) |
| |
| insert 9 3330 8650 Birmingham |
| |
| > 19 bytes taken |
| > Freelist: [169, 174] (6 bytes) |
| |
| print |
| > [0] --> 0: (4240, 7345) Albany |
| > [15] --> 1: (3455, 13836) Albuquerque |
| > [35] --> 2: (3511, 10150) Amarillo |
| > [52] --> 3: (6113, 14954) Anchorage |
| > 4: [no record] |
| > [70] --> 5: (2515, 5740) Asuncion_Paraguay |
| > [96] --> 6: (4447, 11750) Baker |
| > [110] --> 7: (3918, 7638) Baltimore |
| > [128] --> 8: (3955, 11625) Beijing_China |
| > [150] --> 9: (3330, 8650) Birmingham |
| |
| remove 9 |
| |
| > This frees 19 bytes, which merge with the free block at the end. |
| > Freelist: [150, 174] (25 bytes) |
| |
| print 9 |
| |
| > Slot 9 is empty |
| |
| insert 9 3355 1822 Cape_Town_South_Africa |
| |
| > This requires 31 bytes, but there is not a block of this size |
| > available. Therefore, nothing is inserted (or otherwise changed) |
| > Freelist: [150, 174] (25 bytes) |
| |
| print 9 |
| |
| > Slot 9 is empty |
| |
| remove 3 |
| |
| > Free up 18 bytes |
| > Freelist: [52, 69] (18 bytes) |
| > [150, 174] (25 bytes) |
| |
| remove 4 |
| |
| > Nothing happens since Slot 4 is empty |
| |
| remove 6 |
| |
| > Free up 14 bytes starting at position 96 |
| > Freelist: [52, 69] (18 bytes); |
| > [96, 109] (14 bytes); |
| > [150, 174] (25 bytes) |
| |
| remove 7 |
| |
| > Free up 18 bytes starting at position 110. Since this is adjacent to |
| > an existing free block, they merge. |
| > Freelist: [52, 69] (18 bytes); |
| > [96, 127] (32 bytes); |
| > [150, 174] (25 bytes) |
| |
| remove 7 |
| |
| > Since Slot 7 is empty, nothing happens. |
| > Freelist: [52, 69] (18 bytes); |
| > [96, 127] (32 bytes); |
| > [150, 174] (25 bytes) |
| |
| remove 8 |
| |
| > Free 22 bytes starting at postion 128. Since there are free blocks |
| > to either side, all three merge together. |
| > Freelist: [52, 69] (18 bytes); |
| > [96, 174] (79 bytes); |
| |
| insert 7 2308 8223 Havana_Cuba |
| |
| > 20 bytes taken. The first free block is not big enough, so take from |
| > the second. |
| > Freelist: [52, 69] (18 bytes); |
| > [116, 174] (59 bytes); |
| |
| insert 7 2946 10634 Chongqing_China |
| |
| > First the 20 bytes from the message currently stored is freed, whose |
| > space merges with the block at the end of the list. Then 24 bytes |
| > are reserved from the second block, since the first is not big enough. |
| > Freelist: [52, 69] (18 bytes); |
| > [120, 174] (55 bytes); |
| |
| insert 8 616 10648 Jakarta_Indonesia |
| |
| > 26 bytes taken from the second block |
| > Freelist: [52, 69] (18 bytes); |
| > [146, 174] (29 bytes); |
| |
| print |
| |
| > Print out the current records in the array |
| > [0] --> 0: 4240 7345 Albany |
| > [15] --> 1: 3455 13836 Albuquerque |
| > [35] --> 2: 3511 10150 Amarillo |
| > 3: [no record] |
| > 4: [no record] |
| > [70] --> 5: (2515, 5740) Asuncion_Paraguay |
| > 6: [no record] |
| > [96] --> 7: 2946 10634 Chongqing_China |
| > [120] --> 8: 616 10648 Jakarta_Indonesia |
| > 9: [no record] |
| |
| remove 8 |
| |
| > Free 26 bytes and merge with second block. |
| > Freelist: [52, 69] (18 bytes); |
| > [120, 174] (55 bytes); |