Subversion Repositories Code-Repo

Rev

Rev 93 | Blame | Compare with Previous | Last modification | View Log | RSS feed

> 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);