Iterating links/edges

To obtain an iterator for the graph links or edges, users need to invoke the Links or Edges methods. Let's take a look at how the Links method is implemented:

func (s *InMemoryGraph) Links(fromID, toID uuid.UUID, retrievedBefore time.Time) (graph.LinkIterator, error) {
    from, to := fromID.String(), toID.String()

    s.mu.RLock()
    var list []*graph.Link
    for linkID, link := range s.links {
        if id := linkID.String(); id >= from && id < to && link.RetrievedAt.Before(retrievedBefore) {
            list = append(list, link)
        }
    }
    s.mu.RUnlock()

    return &linkIterator{s: s, links: list}, nil
}

In the preceding implementation, we obtain a read lock and then proceed to iterate all the links in the graph, searching for the ones that belong to the [fromID, toID) partition range and whose RetrievedAt value is less than the specified retrievedBefore value. Any links that satisfy this predicate are appended to the list variable.

To figure out whether a link ID belongs to the specified partition range, we convert it into a string and then rely on string comparisons to verify that it is either equal to fromID or falls between the two ends of the partition range. Obviously, performing string conversions and comparisons is not as efficient as directly comparing the underlying byte representation of the UUID values. However, since this particular implementation is meant to be used just for debugging purposes, we can focus on keeping the code simple rather than worrying about its performance.

Once we have finished iterating all the links, we create a new linkIterator instance and return it to the user. Now, let's examine how the iterator is implemented, starting with its type definition:

type linkIterator struct {
    s *InMemoryGraph

    links    []*graph.Link
    curIndex int
}

As you can see, the iterator stores a pointer to the in-memory graph, a list of Link models to iterate, and an index for keeping track of the iterator's offset within the list.

The implementation of the iterator's Next method is quite trivial:

func (i *edgeIterator) Next() bool {
    if i.curIndex >= len(i.links) {
        return false
    }
    i.curIndex++
    return true
}

Unless we have already reached the end of the list of links, we advance curIndex and return true to indicate that more data is available for retrieval via a call to the Link method, whose implementation is listed as follows:

func (i *linkIterator) Link() *graph.Link {
    i.s.mu.RLock()
    link := new(graph.Link)
    *link = *i.links[i.curIndex-1]
    i.s.mu.RUnlock()
    return link
}

Keep in mind that the Link model instances associated with this iterator are maintained by the in-memory graph and may potentially be shared with other iterator instances. As a result, while one go-routine may consuming links from the iterator, another go-routine may be modifying their contents. To avoid data races, whenever the user invokes the iterator's Link method, we obtain a read lock on the link graph. While holding the lock, we can safely fetch the next link and make a copy, which is then returned to the caller.

Finally, let's take a look at the implementation of the Edges method. The logic is quite similar to Links, but with a minor difference in the way we populate the list of edges that belong to the requested partition:

func (s *InMemoryGraph) Edges(fromID, toID uuid.UUID, updatedBefore time.Time) (graph.EdgeIterator, error) {
    from, to := fromID.String(), toID.String()
    s.mu.RLock()
    var list []*graph.Edge
    for linkID := range s.links {
        if id := linkID.String(); id < from || id >= to {
            continue
        }
        for _, edgeID := range s.linkEdgeMap[linkID] {
            if edge := s.edges[edgeID]; edge.UpdatedAt.Before(updatedBefore) {
                list = append(list, edge)
            }
        }
    }
    s.mu.RUnlock()
    return &edgeIterator{s: s, edges: list}, nil
}

As we mentioned in the Partitioning links and edges for processing the graph in parallel section, each edge belongs to the same partition as the link it originates from. Therefore, in the preceding implementation, we begin by iterating the set of links in the graph and skip the ones that do not belong to the partition we need. Once we have located a link belonging to the requested partition range, we iterate the list of edges that originate from it (via the linkEdgeMap field) and append any edges that satisfy the updated-before-X predicate to the list variable.

The content of the list variable is then used to create a new edgeIterator instance, which is then returned to the caller. The edgeIterator is implemented in more or less the same way as the linkIterator, so we will attempt to save some space by not including its full implementation here. You can easily look it up by visiting this book's GitHub repository.