lib/ccmap.c
/* Count 'inc' for 'hash' is to be inserted into 'impl', but both candidate
 * buckets 'b1' and 'b2' are full.  This function attempts to rearrange buckets
 * within 'impl' to make room for 'hash'.
 *
 * Returns 'inc' if the new count for the 'hash' was inserted, otherwise
 * returns 0.
 *
 * The implementation is a general-purpose breadth-first search.  At first
 * glance, this is more complex than a random walk through 'impl' (suggested by
 * some references), but random walks have a tendency to loop back through a
 * single bucket.  We have to move nodes backward along the path that we find,
 * so that no node actually disappears from the hash table, which means a
 * random walk would have to be careful to deal with loops.  By contrast, a
 * successful breadth-first search always finds a *shortest* path through the
 * hash table, and a shortest path will never contain loops, so it avoids that
 * problem entirely.
 */


Returns 'inc' if the new count for the 'hash' was inserted, otherwise
returns 0.

The implementation is a general-purpose breadth-first search.  At first
glance, this is more complex than a random walk through 'impl' (suggested by
some references), but random walks have a tendency to loop back through a
single bucket.  We have to move nodes backward along the path that we find,
so that no node actually disappears from the hash table, which means a
random walk would have to be careful to deal with loops.  By contrast, a
successful breadth-first search always finds a *shortest* path through the
hash table, and a shortest path will never contain loops, so it avoids that
problem entirely.
Returns ' inc ' if the new count for the ' hash ' was inserted otherwise returns 0 . The implementation is a general - purpose breadth - first search . At first glance this is more complex than a random walk through ' impl ' ( suggested by some references ) but random walks have a tendency to loop back through a single bucket . We have to move nodes backward along the path that we find so that no node actually disappears from the hash table which means a random walk would have to be careful to deal with loops . By contrast a successful breadth - first search always finds a * shortest * path through the hash table and a shortest path will never contain loops so it avoids that problem entirely .
static uint32_t
ccmap_inc_bfs(struct ccmap_impl *impl, uint32_t hash,
              struct ccmap_bucket *b1, struct ccmap_bucket *b2, uint32_t inc)
{
    enum { MAX_DEPTH = 4 };
    struct ccmap_path {
        struct ccmap_bucket *start; 
        struct ccmap_bucket *end;   
        uint8_t slots[MAX_DEPTH];  
        int n;                     
    };
    enum { MAX_QUEUE = 500 };
    struct ccmap_path queue[MAX_QUEUE];
    int head = 0;
    int tail = 0;
    queue[head].start = b1;
    queue[head].end = b1;
    queue[head].n = 0;
    head++;
    if (b1 != b2) {
        queue[head].start = b2;
        queue[head].end = b2;
        queue[head].n = 0;
        head++;
    }
    while (tail < head) {
        const struct ccmap_path *path = &queue[tail++];
        struct ccmap_bucket *this = path->end;
        int i;
        for (i = 0; i < CCMAP_K; i++) {
            struct ccmap_bucket *next = other_bucket_protected(impl, this, i);
            int j;
            if (this == next) {
                continue;
            }
            j = ccmap_find_empty_slot_protected(next);
            if (j >= 0) {
                struct ccmap_bucket *buckets[MAX_DEPTH + 2];
                int slots[MAX_DEPTH + 2];
                int k;
                for (k = 0; k < path->n; k++) {
                    slots[k] = path->slots[k];
                }
                slots[path->n] = i;
                slots[path->n + 1] = j;
                buckets[0] = path->start;
                for (k = 0; k <= path->n; k++) {
                    buckets[k + 1] = other_bucket_protected(impl, buckets[k], slots[k]);
                }
                for (k = path->n + 1; k > 0; k--) {
                    uint64_t node = ccmap_node_get_protected
                        (&buckets[k - 1]->nodes[slots[k - 1]]);
                    ccmap_node_set_protected(&buckets[k]->nodes[slots[k]],
                                             node);
                }
                ccmap_set_bucket(buckets[0], slots[0], inc, hash);
                return inc;
            }
            if (path->n < MAX_DEPTH && head < MAX_QUEUE) {
                struct ccmap_path *new_path = &queue[head++];
                *new_path = *path;
                new_path->end = next;
                new_path->slots[new_path->n++] = i;
            }
        }
    }
    return 0;
}
static uint32_t ccmap_inc_bfs ( struct ccmap_impl * impl , uint32_t hash , struct ccmap_bucket * b1 , struct ccmap_bucket * b2 , uint32_t inc ) { enum { MAX_DEPTH = 4 } ; struct ccmap_path { struct ccmap_bucket * start ; struct ccmap_bucket * end ; uint8_t slots [ MAX_DEPTH ] ; int n ; } ; enum { MAX_QUEUE = 500 } ; struct ccmap_path queue [ MAX_QUEUE ] ; int head = 0 ; int tail = 0 ; queue [ head ] . start = b1 ; queue [ head ] . end = b1 ; queue [ head ] . n = 0 ; head ++ ; if ( b1 != b2 ) { queue [ head ] . start = b2 ; queue [ head ] . end = b2 ; queue [ head ] . n = 0 ; head ++ ; } while ( tail < head ) { const struct ccmap_path * path = & queue [ tail ++ ] ; struct ccmap_bucket * this = path -> end ; int i ; for ( i = 0 ; i < CCMAP_K ; i ++ ) { struct ccmap_bucket * next = other_bucket_protected ( impl , this , i ) ; int j ; if ( this == next ) { continue ; } j = ccmap_find_empty_slot_protected ( next ) ; if ( j >= 0 ) { struct ccmap_bucket * buckets [ MAX_DEPTH + 2 ] ; int slots [ MAX_DEPTH + 2 ] ; int k ; for ( k = 0 ; k < path -> n ; k ++ ) { slots [ k ] = path -> slots [ k ] ; } slots [ path -> n ] = i ; slots [ path -> n + 1 ] = j ; buckets [ 0 ] = path -> start ; for ( k = 0 ; k <= path -> n ; k ++ ) { buckets [ k + 1 ] = other_bucket_protected ( impl , buckets [ k ] , slots [ k ] ) ; } for ( k = path -> n + 1 ; k > 0 ; k -- ) { uint64_t node = ccmap_node_get_protected ( & buckets [ k - 1 ] -> nodes [ slots [ k - 1 ] ] ) ; ccmap_node_set_protected ( & buckets [ k ] -> nodes [ slots [ k ] ] , node ) ; } ccmap_set_bucket ( buckets [ 0 ] , slots [ 0 ] , inc , hash ) ; return inc ; } if ( path -> n < MAX_DEPTH && head < MAX_QUEUE ) { struct ccmap_path * new_path = & queue [ head ++ ] ; * new_path = * path ; new_path -> end = next ; new_path -> slots [ new_path -> n ++ ] = i ; } } } return 0 ; }
Count 'inc' for 'hash' is to be inserted into 'impl', but both candidate
 buckets 'b1' and 'b2' are full.
Count ' inc ' for ' hash ' is to be inserted into ' impl ' but both candidate buckets ' b1 ' and ' b2 ' are full .
/* A path from 'start' to 'end' via the 'n' steps in 'slots[]'.
     *
     * One can follow the path via:
     *
     *     struct ccmap_bucket *b;
     *     int i;
     *
     *     b = path->start;
     *     for (i = 0; i < path->n; i++) {
     *         b = other_bucket_protected(impl, b, path->slots[i]);
     *     }
     *     ovs_assert(b == path->end);
     */ /* First bucket along the path. */ /* Last bucket on the path. */ /* Slots used for each hop. */ /* Number of slots[]. */ /* We need to limit the amount of work we do trying to find a path.  It
     * might actually be impossible to rearrange the ccmap, and after some time
     * it is likely to be easier to rehash the entire ccmap.
     *
     * This value of MAX_QUEUE is an arbitrary limit suggested by one of the
     * references.  Empirically, it seems to work OK. */ /* Add 'b1' and 'b2' as starting points for the search. */ /* We've found a path along which we can rearrange the hash
                 * table:  Start at path->start, follow all the slots in
                 * path->slots[], then follow slot 'i', then the bucket you
                 * arrive at has slot 'j' empty. */ /* Figure out the full sequence of slots. */ /* Figure out the full sequence of buckets. */ /* Now the path is fully expressed.  One can start from
                 * buckets[0], go via slots[0] to buckets[1], via slots[1] to
                 * buckets[2], and so on.
                 *
                 * Move all the nodes across the path "backward".  After each
                 * step some node appears in two buckets.  Thus, every node is
                 * always visible to a concurrent search. */ /* Finally, insert the count. */