Test your Ada skills with our puzzle

Produced by our software engineer Jack W for the Ada Europe 2019 event, below is a fiendishly tricky Ada code software puzzle.

/*Begin Puzzle*/

The following Ada code executes a procedure named insert_data with every integer value from 1 to 100. We expect insert_data to execute in approximately constant time, as it inserts elements of type t_packet into a Hashed_Set. Every element contains a different value, and we use CRC32 as part of the hash function.

with Ada.Unchecked_Conversion;
with GNAT.CRC32;
with Interfaces.C;
with Ada.Containers;
with Ada.Containers.Hashed_Sets;

package body puzzle is
  type t_color is (undefined, red, blue);
  type t_packet is record
    color : t_color := undefined;
    value : Natural := 0;
    text : String (1 .. 16);
  end record;

  function get_hash (packet : t_packet) return Ada.Containers.Hash_Type is
    use type Interfaces.C.size_t;
    subtype t_char_array is Interfaces.C.char_array (1 .. (t_packet'Size / 8));
    function to_char_array is new Ada.Unchecked_Conversion (t_packet, t_char_array);

    c : GNAT.CRC32.CRC32;
  begin
    GNAT.CRC32.Initialize (c);
    GNAT.CRC32.Update (c, Interfaces.C.To_Ada (to_char_array (packet)));
    return Ada.Containers.Hash_Type (GNAT.CRC32.Get_Value (c));
  end get_hash;
  package p_seen is new Ada.Containers.Hashed_Sets
    (Element_Type => t_packet, Hash => get_hash, Equivalent_Elements => "=");

  seen : p_seen.Set;

  procedure insert_data (value : Natural) is
    packet : t_packet;
  begin
    packet.value := value;
    packet.color := red;
    packet.text := " ada europe 2019";
    seen.Insert (packet);

    packet.value := value;
    packet.color := blue;
    packet.text := " rapita systems ";
    seen.Insert (packet);
  end insert_data;

  procedure run_test is
  begin
    seen.Reserve_Capacity (1000);
    for i in 1 .. 100 loop
      insert_data (i);
    end loop;
  end run_test;

end puzzle;

The problem...

However, when we measure the execution time of insert_data with RapiTime, we find each run takes longer than the last:

This behaviour is caused by a bug in the code.

Can you explain the bug, and suggest a simple fix?

For more puzzles, Ada and general software fun please subscribe to our newsletter.

If you would like to find out more about timing analysis for single or multicore embedded systems you can contact us.

Receive our blog by email