Changeset a35b458 in mainline for kernel/generic/src/adt/btree.c


Ignore:
Timestamp:
2018-03-02T20:10:49Z (8 years ago)
Author:
Jiří Zárevúcky <zarevucky.jiri@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
f1380b7
Parents:
3061bc1
git-author:
Jiří Zárevúcky <zarevucky.jiri@…> (2018-02-28 17:38:31)
git-committer:
Jiří Zárevúcky <zarevucky.jiri@…> (2018-03-02 20:10:49)
Message:

style: Remove trailing whitespace on _all_ lines, including empty ones, for particular file types.

Command used: tools/srepl '\s\+$' '' -- *.c *.h *.py *.sh *.s *.S *.ag

Currently, whitespace on empty lines is very inconsistent.
There are two basic choices: Either remove the whitespace, or keep empty lines
indented to the level of surrounding code. The former is AFAICT more common,
and also much easier to do automatically.

Alternatively, we could write script for automatic indentation, and use that
instead. However, if such a script exists, it's possible to use the indented
style locally, by having the editor apply relevant conversions on load/save,
without affecting remote repository. IMO, it makes more sense to adopt
the simpler rule.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/src/adt/btree.c

    r3061bc1 ra35b458  
    8383{
    8484        unsigned int i;
    85        
     85
    8686        node->keys = 0;
    87        
     87
    8888        /* Clean also space for the extra key. */
    8989        for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
    … …  
    9292                node->subtree[i] = NULL;
    9393        }
    94        
     94
    9595        node->subtree[i] = NULL;
    9696        node->parent = NULL;
    97        
     97
    9898        link_initialize(&node->leaf_link);
    9999        link_initialize(&node->bfs_link);
    … …  
    122122{
    123123        size_t i;
    124        
     124
    125125        if (root->keys) {
    126126                for (i = 0; i < root->keys + 1; i++) {
    … …  
    129129                }
    130130        }
    131        
     131
    132132        slab_free(btree_node_cache, root);
    133133}
    … …  
    156156{
    157157        size_t i;
    158        
     158
    159159        for (i = 0; i < node->keys; i++) {
    160160                if (key < node->key[i]) {
    161161                        size_t j;
    162                        
     162
    163163                        for (j = node->keys; j > i; j--) {
    164164                                node->key[j] = node->key[j - 1];
    … …  
    166166                                node->subtree[j + 1] = node->subtree[j];
    167167                        }
    168                        
     168
    169169                        break;
    170170                }
    171171        }
    172        
     172
    173173        node->key[i] = key;
    174174        node->value[i] = value;
    … …  
    191191{
    192192        size_t i;
    193        
     193
    194194        for (i = 0; i < node->keys + 1; i++) {
    195195                if (subtree == node->subtree[i])
    196196                        return i - (int) (right != false);
    197197        }
    198        
     198
    199199        panic("Node %p does not contain subtree %p.", node, subtree);
    200200}
    … …  
    215215        size_t i;
    216216        size_t j;
    217        
     217
    218218        for (i = 0; i < node->keys; i++) {
    219219                if (key == node->key[i]) {
    … …  
    223223                                node->subtree[j - 1] = node->subtree[j];
    224224                        }
    225                        
     225
    226226                        node->subtree[j - 1] = node->subtree[j];
    227227                        node->keys--;
    228                        
     228
    229229                        return;
    230230                }
    231231        }
    232        
     232
    233233        panic("Node %p does not contain key %" PRIu64 ".", node, key);
    234234}
    … …  
    248248{
    249249        size_t i, j;
    250        
     250
    251251        for (i = 0; i < node->keys; i++) {
    252252                if (key == node->key[i]) {
    … …  
    256256                                node->subtree[j] = node->subtree[j + 1];
    257257                        }
    258                        
     258
    259259                        node->keys--;
    260260                        return;
    261261                }
    262262        }
    263        
     263
    264264        panic("Node %p does not contain key %" PRIu64 ".", node, key);
    265265}
    … …  
    280280{
    281281        size_t i;
    282        
     282
    283283        for (i = 0; i < node->keys; i++) {
    284284                if (key < node->key[i]) {
    285285                        size_t j;
    286                        
     286
    287287                        for (j = node->keys; j > i; j--) {
    288288                                node->key[j] = node->key[j - 1];
    … …  
    290290                                node->subtree[j + 1] = node->subtree[j];
    291291                        }
    292                        
     292
    293293                        node->subtree[j + 1] = node->subtree[j];
    294294                        break;
    295295                }
    296296        }
    297        
     297
    298298        node->key[i] = key;
    299299        node->value[i] = value;
    300300        node->subtree[i] = lsubtree;
    301        
     301
    302302        node->keys++;
    303303}
    … …  
    320320{
    321321        btree_key_t key = lnode->key[lnode->keys - 1];
    322        
     322
    323323        if (LEAF_NODE(lnode)) {
    324324                void *value = lnode->value[lnode->keys - 1];
    325                
     325
    326326                node_remove_key_and_rsubtree(lnode, key);
    327327                node_insert_key_and_lsubtree(rnode, key, value, NULL);
    … …  
    329329        } else {
    330330                btree_node_t *rsubtree = lnode->subtree[lnode->keys];
    331                
     331
    332332                node_remove_key_and_rsubtree(lnode, key);
    333333                node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
    334334                lnode->parent->key[idx] = key;
    335                
     335
    336336                /* Fix parent link of the reconnected right subtree. */
    337337                rsubtree->parent = rnode;
    … …  
    356356{
    357357        btree_key_t key = rnode->key[0];
    358        
     358
    359359        if (LEAF_NODE(rnode)) {
    360360                void *value = rnode->value[0];
    361                
     361
    362362                node_remove_key_and_lsubtree(rnode, key);
    363363                node_insert_key_and_rsubtree(lnode, key, value, NULL);
    … …  
    365365        } else {
    366366                btree_node_t *lsubtree = rnode->subtree[0];
    367                
     367
    368368                node_remove_key_and_lsubtree(rnode, key);
    369369                node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
    370370                rnode->parent->key[idx] = key;
    371                
     371
    372372                /* Fix parent link of the reconnected left subtree. */
    373373                lsubtree->parent = lnode;
    … …  
    395395        size_t idx;
    396396        btree_node_t *lnode;
    397        
     397
    398398        /*
    399399         * If this is root node, the rotation can not be done.
    … …  
    401401        if (ROOT_NODE(node))
    402402                return false;
    403        
     403
    404404        idx = find_key_by_subtree(node->parent, node, true);
    405405        if ((int) idx == -1) {
    … …  
    410410                return false;
    411411        }
    412        
     412
    413413        lnode = node->parent->subtree[idx];
    414414        if (lnode->keys < BTREE_MAX_KEYS) {
    … …  
    420420                return true;
    421421        }
    422        
     422
    423423        return false;
    424424}
    … …  
    444444        size_t idx;
    445445        btree_node_t *rnode;
    446        
     446
    447447        /*
    448448         * If this is root node, the rotation can not be done.
    … …  
    450450        if (ROOT_NODE(node))
    451451                return false;
    452        
     452
    453453        idx = find_key_by_subtree(node->parent, node, false);
    454454        if (idx == node->parent->keys) {
    … …  
    459459                return false;
    460460        }
    461        
     461
    462462        rnode = node->parent->subtree[idx + 1];
    463463        if (rnode->keys < BTREE_MAX_KEYS) {
    … …  
    469469                return true;
    470470        }
    471        
     471
    472472        return false;
    473473}
    … …  
    499499        size_t i;
    500500        size_t j;
    501        
     501
    502502        assert(median);
    503503        assert(node->keys == BTREE_MAX_KEYS);
    504        
     504
    505505        /*
    506506         * Use the extra space to store the extra node.
    507507         */
    508508        node_insert_key_and_rsubtree(node, key, value, rsubtree);
    509        
     509
    510510        /*
    511511         * Compute median of keys.
    512512         */
    513513        *median = MEDIAN_HIGH(node);
    514        
     514
    515515        /*
    516516         * Allocate and initialize new right sibling.
    … …  
    520520        rnode->parent = node->parent;
    521521        rnode->depth = node->depth;
    522        
     522
    523523        /*
    524524         * Copy big keys, values and subtree pointers to the new right sibling.
    … …  
    530530                rnode->value[j] = node->value[i];
    531531                rnode->subtree[j] = node->subtree[i];
    532                
     532
    533533                /*
    534534                 * Fix parent links in subtrees.
    … …  
    537537                        rnode->subtree[j]->parent = rnode;
    538538        }
    539        
     539
    540540        rnode->subtree[j] = node->subtree[i];
    541541        if (rnode->subtree[j])
    542542                rnode->subtree[j]->parent = rnode;
    543        
     543
    544544        rnode->keys = j;  /* Set number of keys of the new node. */
    545545        node->keys /= 2;  /* Shrink the old node. */
    546        
     546
    547547        return rnode;
    548548}
    … …  
    578578                btree_node_t *rnode;
    579579                btree_key_t median;
    580                
     580
    581581                /*
    582582                 * Node is full and both siblings (if both exist) are full too.
    … …  
    584584                 * bigger keys (i.e. the new node) into its parent.
    585585                 */
    586                
     586
    587587                rnode = node_split(node, key, value, rsubtree, &median);
    588                
     588
    589589                if (LEAF_NODE(node)) {
    590590                        list_insert_after(&rnode->leaf_link, &node->leaf_link);
    591591                }
    592                
     592
    593593                if (ROOT_NODE(node)) {
    594594                        /*
    … …  
    599599                        rnode->parent = t->root;
    600600                        node_initialize(t->root);
    601                        
     601
    602602                        /*
    603603                         * Left-hand side subtree will be the old root (i.e. node).
    … …  
    605605                         */
    606606                        t->root->subtree[0] = node;
    607                        
     607
    608608                        t->root->depth = node->depth + 1;
    609609                }
    … …  
    624624{
    625625        btree_node_t *lnode;
    626        
     626
    627627        assert(value);
    628        
     628
    629629        lnode = leaf_node;
    630630        if (!lnode) {
    … …  
    632632                        panic("B-tree %p already contains key %" PRIu64 ".", t, key);
    633633        }
    634        
     634
    635635        _btree_insert(t, key, value, NULL, lnode);
    636636}
    … …  
    648648        size_t idx;
    649649        btree_node_t *lnode;
    650        
     650
    651651        /*
    652652         * If this is root node, the rotation can not be done.
    … …  
    654654        if (ROOT_NODE(rnode))
    655655                return false;
    656        
     656
    657657        idx = find_key_by_subtree(rnode->parent, rnode, true);
    658658        if ((int) idx == -1) {
    … …  
    663663                return false;
    664664        }
    665        
     665
    666666        lnode = rnode->parent->subtree[idx];
    667667        if (lnode->keys > FILL_FACTOR) {
    … …  
    669669                return true;
    670670        }
    671        
     671
    672672        return false;
    673673}
    … …  
    685685        size_t idx;
    686686        btree_node_t *rnode;
    687        
     687
    688688        /*
    689689         * If this is root node, the rotation can not be done.
    … …  
    691691        if (ROOT_NODE(lnode))
    692692                return false;
    693        
     693
    694694        idx = find_key_by_subtree(lnode->parent, lnode, false);
    695695        if (idx == lnode->parent->keys) {
    … …  
    700700                return false;
    701701        }
    702        
     702
    703703        rnode = lnode->parent->subtree[idx + 1];
    704704        if (rnode->keys > FILL_FACTOR) {
    … …  
    706706                return true;
    707707        }
    708        
     708
    709709        return false;
    710710}
    … …  
    724724        btree_node_t *rnode;
    725725        size_t i;
    726        
     726
    727727        assert(!ROOT_NODE(node));
    728        
     728
    729729        idx = find_key_by_subtree(node->parent, node, false);
    730730        if (idx == node->parent->keys) {
    … …  
    737737        } else
    738738                rnode = node->parent->subtree[idx + 1];
    739        
     739
    740740        /* Index nodes need to insert parent node key in between left and right node. */
    741741        if (INDEX_NODE(node))
    742742                node->key[node->keys++] = node->parent->key[idx];
    743        
     743
    744744        /* Copy the key-value-subtree triplets from the right node. */
    745745        for (i = 0; i < rnode->keys; i++) {
    746746                node->key[node->keys + i] = rnode->key[i];
    747747                node->value[node->keys + i] = rnode->value[i];
    748                
     748
    749749                if (INDEX_NODE(node)) {
    750750                        node->subtree[node->keys + i] = rnode->subtree[i];
    … …  
    752752                }
    753753        }
    754        
     754
    755755        if (INDEX_NODE(node)) {
    756756                node->subtree[node->keys + i] = rnode->subtree[i];
    757757                rnode->subtree[i]->parent = node;
    758758        }
    759        
     759
    760760        node->keys += rnode->keys;
    761761        return rnode;
    … …  
    789789                        node_remove_key_and_rsubtree(node, key);
    790790                }
    791                
     791
    792792                return;
    793793        }
    794        
     794
    795795        if (node->keys <= FILL_FACTOR) {
    796796                /*
    … …  
    801801                        try_rotation_from_right(node);
    802802        }
    803        
     803
    804804        if (node->keys > FILL_FACTOR) {
    805805                size_t i;
    806                
     806
    807807                /*
    808808                 * The key can be immediately removed.
    … …  
    813813                 */
    814814                node_remove_key_and_rsubtree(node, key);
    815                
     815
    816816                for (i = 0; i < node->parent->keys; i++) {
    817817                        if (node->parent->key[i] == key)
    … …  
    822822                btree_node_t *rnode;
    823823                btree_node_t *parent;
    824                
     824
    825825                /*
    826826                 * The node is below the fill factor as well as its left and right sibling.
    … …  
    832832                node_remove_key_and_rsubtree(node, key);
    833833                rnode = node_combine(node);
    834                
     834
    835835                if (LEAF_NODE(rnode))
    836836                        list_remove(&rnode->leaf_link);
    837                
     837
    838838                idx = find_key_by_subtree(parent, rnode, true);
    839839                assert((int) idx != -1);
    … …  
    855855{
    856856        btree_node_t *lnode;
    857        
     857
    858858        lnode = leaf_node;
    859859        if (!lnode) {
    … …  
    861861                        panic("B-tree %p does not contain key %" PRIu64 ".", t, key);
    862862        }
    863        
     863
    864864        _btree_remove(t, key, lnode);
    865865}
    … …  
    877877{
    878878        btree_node_t *cur, *next;
    879        
     879
    880880        /*
    881881         * Iteratively descend to the leaf that can contain the searched key.
    … …  
    887887                 */
    888888                *leaf_node = cur;
    889                
     889
    890890                if (cur->keys == 0)
    891891                        return NULL;
    … …  
    901901                        void *val;
    902902                        size_t i;
    903                        
     903
    904904                        /*
    905905                         * Now if the key is smaller than cur->key[i]
    … …  
    911911                                        next = cur->subtree[i];
    912912                                        val = cur->value[i - 1];
    913                                        
     913
    914914                                        if (LEAF_NODE(cur))
    915915                                                return key == cur->key[i - 1] ? val : NULL;
    916                                        
     916
    917917                                        goto descend;
    918918                                }
    919919                        }
    920                        
     920
    921921                        /*
    922922                         * Last possibility is that the key is
    … …  
    925925                        next = cur->subtree[i];
    926926                        val = cur->value[i - 1];
    927                        
     927
    928928                        if (LEAF_NODE(cur))
    929929                                return key == cur->key[i - 1] ? val : NULL;
    … …  
    932932                ;
    933933        }
    934        
     934
    935935        /*
    936936         * The key was not found in the *leaf_node and
    … …  
    952952{
    953953        assert(LEAF_NODE(node));
    954        
     954
    955955        if (node->leaf_link.prev != &t->leaf_list.head)
    956956                return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link);
    … …  
    971971{
    972972        assert(LEAF_NODE(node));
    973        
     973
    974974        if (node->leaf_link.next != &t->leaf_list.head)
    975975                return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link);
    … …  
    988988        int depth = t->root->depth;
    989989        list_t list;
    990        
     990
    991991        printf("Printing B-tree:\n");
    992992        list_initialize(&list);
    993993        list_append(&t->root->bfs_link, &list);
    994        
     994
    995995        /*
    996996         * Use BFS search to print out the tree.
    … …  
    10001000                link_t *hlp;
    10011001                btree_node_t *node;
    1002                
     1002
    10031003                hlp = list_first(&list);
    10041004                assert(hlp != NULL);
    10051005                node = list_get_instance(hlp, btree_node_t, bfs_link);
    10061006                list_remove(hlp);
    1007                
     1007
    10081008                assert(node);
    1009                
     1009
    10101010                if (node->depth != depth) {
    10111011                        printf("\n");
    10121012                        depth = node->depth;
    10131013                }
    1014                
     1014
    10151015                printf("(");
    1016                
     1016
    10171017                for (i = 0; i < node->keys; i++) {
    10181018                        printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
    … …  
    10211021                        }
    10221022                }
    1023                
     1023
    10241024                if (node->depth && node->subtree[i])
    10251025                        list_append(&node->subtree[i]->bfs_link, &list);
    1026                
     1026
    10271027                printf(")");
    10281028        }
    1029        
     1029
    10301030        printf("\n");
    1031        
     1031
    10321032        printf("Printing list of leaves:\n");
    10331033        list_foreach(t->leaf_list, leaf_link, btree_node_t, node) {
    10341034                assert(node);
    1035                
     1035
    10361036                printf("(");
    1037                
     1037
    10381038                for (i = 0; i < node->keys; i++)
    10391039                        printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
    1040                
     1040
    10411041                printf(")");
    10421042        }
    1043        
     1043
    10441044        printf("\n");
    10451045}
Note: See TracChangeset for help on using the changeset viewer.