• John Thacker's avatar
    wmem: Add a multimap · b5917d01
    John Thacker authored
    A number of protocols have IDs that can be reused that are used as
    lookup keys. In most cases the frame number should be used as well
    to differentiate repeat appearances of an ID. For response/request
    matching, it is frequently useful to find the most recent frame number
    (greatest value less than or equal to the current one) that contained
    an ID.
    We can achieve that by using a multimap that stores values with a given
    ID in a tree keyed with the frame number. This works better than using
    a map or a tree alone:
    1) A map isn't ordered, so doesn't allow for less than or equal comparison.
    2) Using a tree requires an ordering on all the ID components, and then
       having to test all the components other than the frame number separately
       for equality after retrieval.
    Currently the multimap does not support inserting items without specifying
    the tree key (and having the multimap generate a key), because the total
    capacity of trees (including deleted nodes) is not tracked. If other use