How to access dynamic list from web3?

Question

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.

Answer 1

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.

Answer 2

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