10

I'm having a strange issues with an array inside a struct. I will copy you the example code, so that you can understand:

  Foo[] public foos;

  struct Foo {
    uint fooX;
    uint[] fooArray;
  }

  function insertionSort(uint[] a)internal {
   for (uint i = 1;i < a.length;i++){
    uint temp = a[i];
    uint j;
    for (j = i -1; j >= 0 && temp < a[j]; j--)
      a[j+1] = a[j];
    a[j + 1] = temp;
   }
  }

  function doesntWork(uint num,uint _id){
    Foo f = foos[_id];
    f.fooArray[f.fooArray.length++] = nun;
    instertionSort(f.fooArray);
  }

  function work1(uit _id){
    Foo f = foos[_id];
    instertionSort(f.fooArray);
  }

  function work2(uint price,uint pair_id){
    Foo p = pairs[pair_id];
    p.boPrices[p.boPrices.length++] = price;
  }

Whenever I am trying to call the insertionSort function on an array, it doesn't work # method 1.

The same function works, when I don't modify the array before hand (as shown in example 2,3).

As my goal is to keep my array sorted after every new value is added it's a problem.

I think it has to do something with the storage of my arrays. But I am having trouble grasping those concept of Data location, and how to fix it.

Does a workaround exist there?

Edit: also does the same with this quickstort

Improve this question
1
  • If you are interested in keeping an array sorted, it's better to use a structure like PriorityQueue rather that sort array on every update.
    – Jakub Wojciechowski
    Jul 11, 2017 at 17:03

1 Answer 1

Reset to default
9

The Working Solution

contract InsertionSort {

    struct Record {
        uint recId;
        uint[] data;
    }

    mapping(uint => Record) records;

    function insertionSortMemory(uint[5] a) internal {
      for (uint i = 0; i < a.length; i++) {
        uint j = i;
        while (j > 0 && a[j] < a[j-1]) {
          uint temp = a[j];
          a[j] = a[j-1];
          a[j-1] = temp;
          j--;
        }
      }
    }

    function testInsertionSort() public constant returns (uint[5]) {
      uint[5] memory data;
      data[0] = 1235;
      data[1] = 1234;
      data[2] = 1233;
      data[3] = 1232;
      data[4] = 1231;
      insertionSortMemory(data);
      return data;
    }

    function insertionSort(uint[] a, uint length) internal returns (uint[]) {
      for (uint i = 0; i < length; i++) {
        uint j = i;
        while (j > 0 && a[j] < a[j-1]) {
          uint temp = a[j];
          a[j] = a[j-1];
          a[j-1] = temp;
          j--;
        }
      }
      return a;
    }

    function addRecordWithoutInsertionSort(uint _recId, uint _num) public {
        Record record = records[_recId];
        record.recId = _recId;
        record.data.length++;
        record.data[record.data.length-1] = _num;
    }

    function addRecordWithInsertionSort(uint _recId, uint _num) public {
        Record record = records[_recId];
        record.recId = _recId;
        record.data.length++;
        record.data[record.data.length-1] = _num;
        record.data = insertionSort(record.data, record.data.length);
    }



    function getRecord(uint _recId) public constant returns(uint, uint[]) {
        return (records[_recId].recId, records[_recId].data);
    }
}


The Test Results

Testing The Insertion Sort Algorithm

And the algorithm is working correctly.

> insertionSort.testInsertionSort()
[1231, 1232, 1233, 1234, 1235]

Testing The Rest Of The Code

Lets insert some records first, without calling the insertionSort() function :

> insertionSort.addRecordWithoutInsertionSort(123, 1233, eth.accounts[0], {
    from:web3.eth.accounts[0], 
    data: insertionSortCompiled.InsertionSort.code,
    gas: 1000000
});
> insertionSort.addRecordWithoutInsertionSort(123, 1235, eth.accounts[0], {
    from:web3.eth.accounts[0], 
    data: insertionSortCompiled.InsertionSort.code,
    gas: 1000000
});
> insertionSort.addRecordWithoutInsertionSort(123, 1231, eth.accounts[0], {
    from:web3.eth.accounts[0], 
    data: insertionSortCompiled.InsertionSort.code,
    gas: 1000000
});
> insertionSort.addRecordWithoutInsertionSort(123, 1232, eth.accounts[0], {
    from:web3.eth.accounts[0], 
    data: insertionSortCompiled.InsertionSort.code,
    gas: 1000000
});

Wait for transactions to be mined, and the records will be unsorted as we have not called the insertion sort yet

> insertionSort.getRecord(123);
[123, [1233, 1235, 1231, 1232]]

Insert one more record, with the addRecordWithInsertionSort() function calling the insertionSort() function:

> insertionSort.addRecordWithInsertionSort(123, 1234, eth.accounts[0], {
    from:web3.eth.accounts[0], 
    data: insertionSortCompiled.InsertionSort.code,
    gas: 2000000
});

Wait for this transaction to be mined, and the sort is working as expected!

> insertionSort.getRecord(123);
[123, [1231, 1232, 1233, 1234, 1235]]


And The Explanation

  • The Bad Array Jump Destination PC 00000651: JUMPI GAS: 1946706 COST: 10 ERROR: invalid jump destination (PUSH1) 2 was probably due to the algorithm being incorrect and addressing the wrong index in the array. I just looked up the insertion sort algorithm and rewrote the code based on the algorithm I found.

  • The main issue I had was that I originally had the insertionSort() function coded as follows:

    function insertionSort(uint[] a, uint length) internal {
  for (uint i = 0; i < length; i++) {
    uint j = i;
    while (j > 0 && a[j] < a[j-1]) {
      uint temp = a[j];
      a[j] = a[j-1];
      a[j-1] = temp;
      j--;
    }
  }
}

    And I called it from addRecordWithInsertionSort() as:

    function addRecordWithInsertionSort(uint _recId, uint _num) public {
    Record record = records[_recId];
    record.recId = _recId;
    record.data.length++;
    record.data[record.data.length-1] = _num;
    insertionSort(record.data, record.data.length);
}

    The data was not being sorted and this is most likely because the record.data variable was being passed to insertionSort() as a memory variable. The array was being sorted in the insertionSort() function, but the modified array was not being passed back to the calling function.

    According to Solidity - Frequently Asked Questions:

    There are defaults for the storage location depending on which type of variable it concerns:

    ...

     * function arguments are always in memory.

    I had to change the code such that the insertionSort() function returns the modified array.

    The new insertionSort() function is:

    function insertionSort(uint[] a, uint length) internal returns (uint[]) {
  for (uint i = 0; i < length; i++) {
    uint j = i;
    while (j > 0 && a[j] < a[j-1]) {
      uint temp = a[j];
      a[j] = a[j-1];
      a[j-1] = temp;
      j--;
    }
  }
  return a;
}

    And the code calling insertionSort() modified to update the data from the return value of the insertionSort() function, and the results are now correct:

    function addRecordWithInsertionSort(uint _recId, uint _num) public { 
  Record record = records[_recId];
  record.recId = _recId;
  record.data.length++;
  record.data[record.data.length-1] = _num;
  record.data = insertionSort(record.data, record.data.length);
}

  • And last, I used mapping instead of arrays so I don't have to keep track of array indices.


EDIT: Testing Out The Function Parameter With Storage

I got the above test code working by returning the sorted data as a function result and reassigning this data to the map.

The following code shows that you can also use the storage modifier with the parameter to the called function that will allow the function to sort the data passed to it with the changes persisted in the map data structure.

    function insertionSortStorage(uint[] storage a) internal {
      for (uint i = 0; i < a.length; i++) {
        uint j = i;
        while (j > 0 && a[j] < a[j-1]) {
          uint temp = a[j];
          a[j] = a[j-1];
          a[j-1] = temp;
          j--;
        }
      }
    }

    function addRecordWithInsertionSortStorage(uint _recId, uint _num) public {
        Record record = records[_recId];
        record.recId = _recId;
        record.data.length++;
        record.data[record.data.length-1] = _num;
        insertionSortStorage(record.data);
    }

With the test results showing a success:

insertionSort.addRecordWithoutInsertionSort(123, 1235, eth.accounts[0], {
  from:web3.eth.accounts[0], 
  data: insertionSortCompiled.InsertionSort.code,
  gas: 1000000
});
insertionSort.addRecordWithoutInsertionSort(123, 1231, eth.accounts[0], {
  from:web3.eth.accounts[0], 
  data: insertionSortCompiled.InsertionSort.code, 
  gas: 1000000
});
insertionSort.addRecordWithoutInsertionSort(123, 1232, eth.accounts[0], {
  from:web3.eth.accounts[0], 
  data: insertionSortCompiled.InsertionSort.code,
  gas: 1000000
});
> insertionSort.getRecord(123);
[123, [1235, 1231, 1232]]

insertionSort.addRecordWithInsertionSortStorage(123, 1220, eth.accounts[0], {
  from:web3.eth.accounts[0], 
  data: insertionSortCompiled.InsertionSort.code,
  gas: 2000000
});
> insertionSort.getRecord(123);
[123, [1220, 1231, 1232, 1235]]


Replicating ERROR: invalid jump destination (PUSH1) 2

I can replicate the invalid jump destination (PUSH1) 2 error by add the following function to the class:

function testInvalidJumpLocation() public constant returns (uint[5]) {
  uint[5] memory data;
  uint j = 1;
  j = j - 2;
  data[j] = 1235;
  return data;
}

And executing the function to get the following results:

insertionSort.testInvalidJumpLocation()
...
PC 00000304: JUMP GAS: 49978004 COST: 8 ERROR: invalid jump destination (PUSH1) 2
...
[0, 0, 0, 0, 0]

This error could have been caused by some other parts of your code, but an invalid array index definitely generates this message.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.