5

In my application players can create and join games. I store every game in a mapping(uint => Game), and send out a GameCreated event whenever a game is created. My issue is efficiently getting a list of open (not yet joined) games on the client side.

I could iterate through all Game objects and filter out those that have been joined, but this is not scalable. At first I thought that listening for GameCreated events would help, but I'd still have to filter out using GameJoined events, since I don't think I can modify logs that have been logged already. This has the same scalability issue. I could mitigate it by only getting logs from the past week or whatever, but I don't really like this option.

I considered making a dynamically sized array where each item is the game id of an open game, but in order to update this list I'd need to be able to delete entries when a game was joined, which would require storing the index in each Game object. But then when an entry was deleted, all those other game objects would need to be updated with the new index and it's just a mess.

Ideally this application will get a lot of traffic some day, so I kind of need an efficient solution. Is there something obvious I'm missing here? Are there any better workarounds you've come across? I wish I could iterate through a mapping with only the currently open games, but I don't think that's possible.

0

How many Games are you expecting to have?

Solidity can return an entire array at once, so you could keep every Game in an array, return it all with one call, then use client-side filtering. You might try mocking up a function that returns, say, 10,000 games and seeing if plain old JS .filter() will handle it fast enough. (Although I don't know how fast the node will be able to return the whole list.)

But let's say that doesn't work. My next suggestion would be a linked list. It's not native to Solidity, and you might have to write a library for it for ease of use, but you'd be able to add and delete in constant time. I'm not sure how much more (or less?) expensive it would be in gas, but I suspect it wouldn't be that much more expensive.

  • Don't arrays in solidity have to be a fixed length? – Mike Shultz Jul 15 '17 at 18:19
  • Since I'd have to access elements in the linked list sequentially I don't think it really offers an improvement over updating an array of game ids. – Warkgnall Jul 15 '17 at 20:58
  • @Mike: Arrays can be variable length, but currently a contract cannot call a function that returns a variable-width array. This is slated to change in metropolis. – Matthew Schmidt Jul 16 '17 at 16:01
  • Unfortunately, Solidity can only return an array of structs internally. To get all the games from a Solidity function I think I'd have to convert every Game into an array of values and return an array of arrays, which sounds very expensive. – Warkgnall Jul 21 '17 at 21:30
  • @Warkgnall it's only expensive gas wise if it's an on-chain call. If it's a constant function then you can do .call() for free, which is what it sounds like you want to do anyway. – flygoing Jan 29 '18 at 20:10
0

You need to use doubly linked list like this:

struct GameListItem {
  uint prev;
  uint next;
}

mapping (uint => GameListItem) public openGamesList;
uint public firstOpenGame;

function addOpenGame (uint gameID) internal {
    require (gameID != 0, "Game ID is NULL");
    GameListItem storage item = openGamesList [gameID];
    require (item.next == 0, "Game is already in the list");

    if (firstOpenGame == 0) {
        item.next = gameID;
        item.prev = gameID;
        firstOpenGame = gameID;
    } else {
        GameListItem storage first = openGamesList [firstOpenGame];
        uint lastID = first.prev;
        GameListItem storage last = openGamesList [lastID];

        item.next = firstOpenGame;
        item.prev = lastID;
        first.prev = gameID;
        last.next = gameID;
    }
}

function removeOpenGame (uint gameID) internal {
    require (gameID != 0, "Game ID is NULL");
    GameListItem storage item = openGamesList [gameID];
    uint nextID = item.next;
    require (nextID != 0, "Game is not in the list");

    uint prevID = item.prev;
    if (nextID == gameID)
        firstOpenGame = 0;
    else {
        GameListItem storage next = openGamesList [nextID];
        GameListItem storage prev = openGamesList [prevID];

        next.prev = prevID;
        prev.next = nextID;

        if (firstOpenGame == gameID) firstOpenGame = nextID;
    }

    item.next = 0;
    item.prev = 0;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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