Changeset 208db5a in mainline for uspace/lib/c/generic/adt/odict.c


Ignore:
Timestamp:
2018-10-31T11:05:32Z (5 years ago)
Author:
Jiri Svoboda <jiri@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
c70e841
Parents:
beb83c1
git-author:
Jiri Svoboda <jiri@…> (2018-10-31 06:04:28)
git-committer:
Jiri Svoboda <jiri@…> (2018-10-31 11:05:32)
Message:

Make ordered dictionary available in kernel, too.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/c/generic/adt/odict.c

    • Property mode changed from 100644 to 120000
    rbeb83c1 r208db5a  
    1 /*
    2  * Copyright (c) 2016 Jiri Svoboda
    3  * All rights reserved.
    4  *
    5  * Redistribution and use in source and binary forms, with or without
    6  * modification, are permitted provided that the following conditions
    7  * are met:
    8  *
    9  * - Redistributions of source code must retain the above copyright
    10  *   notice, this list of conditions and the following disclaimer.
    11  * - Redistributions in binary form must reproduce the above copyright
    12  *   notice, this list of conditions and the following disclaimer in the
    13  *   documentation and/or other materials provided with the distribution.
    14  * - The name of the author may not be used to endorse or promote products
    15  *   derived from this software without specific prior written permission.
    16  *
    17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
    18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
    19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
    20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
    21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
    22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
    26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    27  */
    28 
    29 /** @addtogroup libc
    30  * @{
    31  */
    32 
    33 /** @file Ordered dictionary.
    34  *
    35  * Implementation based on red-black trees.
    36  * Note that non-data ('leaf') nodes are implemented as NULLs, not
    37  * as actual nodes.
    38  */
    39 
    40 #include <adt/list.h>
    41 #include <adt/odict.h>
    42 #include <assert.h>
    43 #include <errno.h>
    44 #include <stdbool.h>
    45 #include <stdio.h>
    46 #include <stdlib.h>
    47 
    48 static void odict_pgu(odlink_t *, odlink_t **, odict_child_sel_t *,
    49     odlink_t **, odict_child_sel_t *, odlink_t **);
    50 
    51 static void odict_rotate_left(odlink_t *);
    52 static void odict_rotate_right(odlink_t *);
    53 static void odict_swap_node(odlink_t *, odlink_t *);
    54 static void odict_replace_subtree(odlink_t *, odlink_t *);
    55 static void odict_unlink(odlink_t *);
    56 static void odict_link_child_a(odlink_t *, odlink_t *);
    57 static void odict_link_child_b(odlink_t *, odlink_t *);
    58 static void odict_sibling(odlink_t *, odlink_t *, odict_child_sel_t *,
    59     odlink_t **);
    60 static odlink_t *odict_search_start_node(odict_t *, void *, odlink_t *);
    61 
    62 /** Print subtree.
    63  *
    64  * Print subtree rooted at @a cur
    65  *
    66  * @param cur Root of tree to print
    67  */
    68 static void odict_print_tree(odlink_t *cur)
    69 {
    70         if (cur == NULL) {
    71                 printf("0");
    72                 return;
    73         }
    74 
    75         printf("[%p/%c", cur, cur->color == odc_red ? 'r' : 'b');
    76         if (cur->a != NULL || cur->b != NULL) {
    77                 putchar(' ');
    78                 odict_print_tree(cur->a);
    79                 putchar(',');
    80                 odict_print_tree(cur->b);
    81         }
    82         putchar(']');
    83 }
    84 
    85 /** Validate ordered dictionary subtree.
    86  *
    87  * Verify that red-black tree properties are satisfied.
    88  *
    89  * @param cur Root of tree to verify
    90  * @param rbd Place to store black depth of the subtree
    91  *
    92  * @return EOK on success, EINVAL on failure
    93  */
    94 static errno_t odict_validate_tree(odlink_t *cur, int *rbd)
    95 {
    96         errno_t rc;
    97         int bd_a, bd_b;
    98         int cur_d;
    99 
    100         if (cur->up == NULL) {
    101                 /* Verify root pointer */
    102                 if (cur->odict->root != cur) {
    103                         printf("cur->up == NULL and yet cur != root\n");
    104                         return EINVAL;
    105                 }
    106 
    107                 /* Verify root color */
    108                 if (cur->color != odc_black) {
    109                         printf("Root is not black\n");
    110                         return EINVAL;
    111                 }
    112         }
    113 
    114         if (cur->a != NULL) {
    115                 /* Verify symmetry of a - up links */
    116                 if (cur->a->up != cur) {
    117                         printf("cur->a->up != cur\n");
    118                         return EINVAL;
    119                 }
    120 
    121                 /* Verify that if a node is red, its left child is red */
    122                 if (cur->a->color == odc_red && cur->color == odc_red) {
    123                         printf("cur->a is red, cur is red\n");
    124                         return EINVAL;
    125                 }
    126 
    127                 /* Recurse to left child */
    128                 rc = odict_validate_tree(cur->a, &bd_a);
    129                 if (rc != EOK)
    130                         return rc;
    131         } else {
    132                 bd_a = -1;
    133         }
    134 
    135         if (cur->b != NULL) {
    136                 /* Verify symmetry of b - up links */
    137                 if (cur->b->up != cur) {
    138                         printf("cur->b->up != cur\n");
    139                         return EINVAL;
    140                 }
    141 
    142                 /* Verify that if a node is red, its right child is red */
    143                 if (cur->b->color == odc_red && cur->color == odc_red) {
    144                         printf("cur->b is red, cur is red\n");
    145                         return EINVAL;
    146                 }
    147 
    148                 /* Recurse to right child */
    149                 rc = odict_validate_tree(cur->b, &bd_b);
    150                 if (rc != EOK)
    151                         return rc;
    152         } else {
    153                 bd_b = -1;
    154         }
    155 
    156         /* Verify that black depths of both children are equal */
    157         if (bd_a >= 0 && bd_b >= 0) {
    158                 if (bd_a != bd_b) {
    159                         printf("Black depth %d != %d\n", bd_a, bd_b);
    160                         return EINVAL;
    161                 }
    162         }
    163 
    164         cur_d = cur->color == odc_black ? 1 : 0;
    165         if (bd_a >= 0)
    166                 *rbd = bd_a + cur_d;
    167         else if (bd_b >= 0)
    168                 *rbd = bd_b + cur_d;
    169         else
    170                 *rbd = cur_d;
    171 
    172         return EOK;
    173 }
    174 
    175 /** Validate ordered dictionary properties.
    176  *
    177  * @param odict Ordered dictionary
    178  */
    179 errno_t odict_validate(odict_t *odict)
    180 {
    181         int bd;
    182         errno_t rc;
    183 
    184         if (odict->root == NULL)
    185                 return EOK;
    186 
    187         rc = odict_validate_tree(odict->root, &bd);
    188         if (rc != EOK)
    189                 odict_print_tree(odict->root);
    190 
    191         return rc;
    192 }
    193 
    194 /** Initialize ordered dictionary.
    195  *
    196  * @param odict Ordered dictionary
    197  * @param getkey Funcition to get key
    198  * @param cmp Function to compare entries
    199  */
    200 void odict_initialize(odict_t *odict, odgetkey_t getkey, odcmp_t cmp)
    201 {
    202         odict->root = NULL;
    203         list_initialize(&odict->entries);
    204         odict->getkey = getkey;
    205         odict->cmp = cmp;
    206 }
    207 
    208 /** Initialize ordered dictionary link.
    209  *
    210  * @param odlink Ordered dictionary link
    211  */
    212 void odlink_initialize(odlink_t *odlink)
    213 {
    214         odlink->odict = NULL;
    215         odlink->up = NULL;
    216         odlink->a = NULL;
    217         odlink->b = NULL;
    218         link_initialize(&odlink->lentries);
    219 }
    220 
    221 /** Insert entry in ordered dictionary.
    222  *
    223  * Insert entry in ordered dictionary, placing it after other entries
    224  * with the same key.
    225  *
    226  * @param odlink New entry
    227  * @param odict Ordered dictionary
    228  * @param hint An entry that might be near the new entry or @c NULL
    229  */
    230 void odict_insert(odlink_t *odlink, odict_t *odict, odlink_t *hint)
    231 {
    232         int d;
    233         odlink_t *cur;
    234         odlink_t *p;
    235         odlink_t *g;
    236         odlink_t *u;
    237         odict_child_sel_t pcs, gcs;
    238 
    239         assert(!odlink_used(odlink));
    240 
    241         if (odict->root == NULL) {
    242                 /* odlink is the root node */
    243                 odict->root = odlink;
    244                 odlink->odict = odict;
    245                 odlink->color = odc_black;
    246                 list_append(&odlink->lentries, &odict->entries);
    247                 return;
    248         }
    249 
    250         cur = odict_search_start_node(odict, odict->getkey(odlink), hint);
    251         while (true) {
    252                 d = odict->cmp(odict->getkey(odlink), odict->getkey(cur));
    253                 if (d < 0) {
    254                         if (cur->a == NULL) {
    255                                 odict_link_child_a(odlink, cur);
    256                                 break;
    257                         }
    258                         cur = cur->a;
    259                 } else {
    260                         if (cur->b == NULL) {
    261                                 odict_link_child_b(odlink, cur);
    262                                 break;
    263                         }
    264                         cur = cur->b;
    265                 }
    266         }
    267 
    268         odlink->color = odc_red;
    269 
    270         while (true) {
    271                 /* Fix up odlink and its parent potentially being red */
    272                 if (odlink->up == NULL) {
    273                         odlink->color = odc_black;
    274                         break;
    275                 }
    276 
    277                 if (odlink->up->color == odc_black)
    278                         break;
    279 
    280                 /* Get parent, grandparent, uncle */
    281                 odict_pgu(odlink, &p, &pcs, &g, &gcs, &u);
    282 
    283                 if (g == NULL) {
    284                         p->color = odc_black;
    285                         break;
    286                 }
    287 
    288                 if (p->color == odc_red && u != NULL && u->color == odc_red) {
    289                         /* Parent and uncle are both red */
    290                         p->color = odc_black;
    291                         u->color = odc_black;
    292                         g->color = odc_red;
    293                         odlink = g;
    294                         continue;
    295                 }
    296 
    297                 /* Parent is red but uncle is black, odlink-P-G is trans */
    298                 if (pcs != gcs) {
    299                         if (gcs == odcs_a) {
    300                                 /* odlink is right child of P */
    301                                 /* P is left child of G */
    302                                 odict_rotate_left(p);
    303                         } else {
    304                                 /* odlink is left child of P */
    305                                 /* P is right child of G */
    306                                 odict_rotate_right(p);
    307                         }
    308 
    309                         odlink = p;
    310                         odict_pgu(odlink, &p, &pcs, &g, &gcs, &u);
    311                 }
    312 
    313                 /* odlink-P-G is now cis */
    314                 assert(pcs == gcs);
    315                 if (pcs == odcs_a) {
    316                         /* odlink is left child of P */
    317                         /* P is left child of G */
    318                         odict_rotate_right(g);
    319                 } else {
    320                         /* odlink is right child of P */
    321                         /* P is right child of G */
    322                         odict_rotate_left(g);
    323                 }
    324 
    325                 p->color = odc_black;
    326                 g->color = odc_red;
    327                 break;
    328         }
    329 }
    330 
    331 /** Remove entry from ordered dictionary.
    332  *
    333  * @param odlink Ordered dictionary link
    334  */
    335 void odict_remove(odlink_t *odlink)
    336 {
    337         odlink_t *n;
    338         odlink_t *c;
    339         odlink_t *p;
    340         odlink_t *s;
    341         odlink_t *sc, *st;
    342         odict_child_sel_t pcs;
    343 
    344         if (odlink->a != NULL && odlink->b != NULL) {
    345                 n = odict_next(odlink, odlink->odict);
    346                 assert(n != NULL);
    347 
    348                 odict_swap_node(odlink, n);
    349         }
    350 
    351         /* odlink has at most one child */
    352         if (odlink->a != NULL) {
    353                 assert(odlink->b == NULL);
    354                 c = odlink->a;
    355         } else {
    356                 c = odlink->b;
    357         }
    358 
    359         if (odlink->color == odc_red) {
    360                 /* We can remove it harmlessly */
    361                 assert(c == NULL);
    362                 odict_unlink(odlink);
    363                 return;
    364         }
    365 
    366         /* odlink->color == odc_black */
    367         if (c != NULL && c->color == odc_red) {
    368                 /* Child is red: swap colors of S and C */
    369                 c->color = odc_black;
    370                 odict_replace_subtree(c, odlink);
    371                 odlink->up = odlink->a = odlink->b = NULL;
    372                 odlink->odict = NULL;
    373                 list_remove(&odlink->lentries);
    374                 return;
    375         }
    376 
    377         /* There cannot be one black child */
    378         assert(c == NULL);
    379 
    380         n = NULL;
    381         p = odlink->up;
    382         odict_unlink(odlink);
    383         /* We removed one black node, creating imbalance */
    384 again:
    385         /* Case 1: N is the new root */
    386         if (p == NULL)
    387                 return;
    388 
    389         odict_sibling(n, p, &pcs, &s);
    390 
    391         /* Paths through N have one less black node than paths through S */
    392 
    393         /* Case 2: S is red */
    394         if (s->color == odc_red) {
    395                 assert(p->color == odc_black);
    396                 p->color = odc_red;
    397                 s->color = odc_black;
    398                 if (n == p->a)
    399                         odict_rotate_left(p);
    400                 else
    401                         odict_rotate_right(p);
    402                 odict_sibling(n, p, &pcs, &s);
    403                 /* Now S is black */
    404                 assert(s->color == odc_black);
    405         }
    406 
    407         /* Case 3: P, S and S's children are black */
    408         if (p->color == odc_black &&
    409             s->color == odc_black &&
    410             (s->a == NULL || s->a->color == odc_black) &&
    411             (s->b == NULL || s->b->color == odc_black)) {
    412                 /*
    413                  * Changing S to red means all paths through S or N have one
    414                  * less black node than they should. So redo the same for P.
    415                  */
    416                 s->color = odc_red;
    417                 n = p;
    418                 p = n->up;
    419                 goto again;
    420         }
    421 
    422         /* Case 4: P is red, S and S's children are black */
    423         if (p->color == odc_red &&
    424             s->color == odc_black &&
    425             (s->a == NULL || s->a->color == odc_black) &&
    426             (s->b == NULL || s->b->color == odc_black)) {
    427                 /* Swap colors of S and P */
    428                 s->color = odc_red;
    429                 p->color = odc_black;
    430                 return;
    431         }
    432 
    433         /* N is the left child */
    434         if (pcs == odcs_a) {
    435                 st = s->a;
    436                 sc = s->b;
    437         } else {
    438                 st = s->b;
    439                 sc = s->a;
    440         }
    441 
    442         /* Case 5: S is black and S's trans child is red, S's cis child is black */
    443         if (s->color == odc_black &&
    444             (st != NULL && st->color == odc_red) &&
    445             (sc == NULL || sc->color == odc_black)) {
    446                 /* N is the left child */
    447                 if (pcs == odcs_a)
    448                         odict_rotate_right(s);
    449                 else
    450                         odict_rotate_left(s);
    451                 s->color = odc_red;
    452                 s->up->color = odc_black;
    453                 /* Now N has a black sibling whose cis child is red */
    454                 odict_sibling(n, p, &pcs, &s);
    455                 /* N is the left child */
    456                 if (pcs == odcs_a) {
    457                         st = s->a;
    458                         sc = s->b;
    459                 } else {
    460                         st = s->b;
    461                         sc = s->a;
    462                 }
    463         }
    464 
    465         /* Case 6: S is black, S's cis child is red */
    466         assert(s->color == odc_black);
    467         assert(sc != NULL);
    468         assert(sc->color == odc_red);
    469 
    470         if (pcs == odcs_a)
    471                 odict_rotate_left(p);
    472         else
    473                 odict_rotate_right(p);
    474 
    475         s->color = p->color;
    476         p->color = odc_black;
    477         sc->color = odc_black;
    478 }
    479 
    480 /** Update dictionary after entry key has been changed.
    481  *
    482  * After the caller modifies the key of an entry, they need to call
    483  * this function so that the dictionary can update itself accordingly.
    484  *
    485  * @param odlink Ordered dictionary entry
    486  * @param odict Ordered dictionary
    487  */
    488 void odict_key_update(odlink_t *odlink, odict_t *odict)
    489 {
    490         odlink_t *n;
    491 
    492         n = odict_next(odlink, odict);
    493         odict_remove(odlink);
    494         odict_insert(odlink, odict, n);
    495 }
    496 
    497 /** Return true if entry is in a dictionary.
    498  *
    499  * @param odlink Ordered dictionary entry
    500  * @return @c true if entry is in a dictionary, @c false otherwise
    501  */
    502 bool odlink_used(odlink_t *odlink)
    503 {
    504         return odlink->odict != NULL;
    505 }
    506 
    507 /** Return true if ordered dictionary is empty.
    508  *
    509  * @param odict Ordered dictionary
    510  * @return @c true if @a odict is emptry, @c false otherwise
    511  */
    512 bool odict_empty(odict_t *odict)
    513 {
    514         return odict->root == NULL;
    515 }
    516 
    517 /** Return the number of entries in @a odict.
    518  *
    519  * @param odict Ordered dictionary
    520  */
    521 unsigned long odict_count(odict_t *odict)
    522 {
    523         unsigned long cnt;
    524         odlink_t *cur;
    525 
    526         cnt = 0;
    527         cur = odict_first(odict);
    528         while (cur != NULL) {
    529                 ++cnt;
    530                 cur = odict_next(cur, odict);
    531         }
    532 
    533         return cnt;
    534 }
    535 
    536 /** Return first entry in a list or @c NULL if list is empty.
    537  *
    538  * @param odict Ordered dictionary
    539  * @return First entry
    540  */
    541 odlink_t *odict_first(odict_t *odict)
    542 {
    543         link_t *link;
    544 
    545         link = list_first(&odict->entries);
    546         if (link == NULL)
    547                 return NULL;
    548 
    549         return list_get_instance(link, odlink_t, lentries);
    550 }
    551 
    552 /** Return last entry in a list or @c NULL if list is empty
    553  *
    554  * @param odict Ordered dictionary
    555  * @return Last entry
    556  */
    557 odlink_t *odict_last(odict_t *odict)
    558 {
    559         link_t *link;
    560 
    561         link = list_last(&odict->entries);
    562         if (link == NULL)
    563                 return NULL;
    564 
    565         return list_get_instance(link, odlink_t, lentries);
    566 }
    567 
    568 /** Return previous entry in list or @c NULL if @a link is the first one.
    569  *
    570  * @param odlink Entry
    571  * @param odict Ordered dictionary
    572  * @return Previous entry
    573  */
    574 odlink_t *odict_prev(odlink_t *odlink, odict_t *odict)
    575 {
    576         link_t *link;
    577 
    578         link = list_prev(&odlink->lentries, &odlink->odict->entries);
    579         if (link == NULL)
    580                 return NULL;
    581 
    582         return list_get_instance(link, odlink_t, lentries);
    583 }
    584 
    585 /** Return next entry in dictionary or @c NULL if @a odlink is the last one
    586  *
    587  * @param odlink Entry
    588  * @param odict Ordered dictionary
    589  * @return Next entry
    590  */
    591 odlink_t *odict_next(odlink_t *odlink, odict_t *odict)
    592 {
    593         link_t *link;
    594 
    595         link = list_next(&odlink->lentries, &odlink->odict->entries);
    596         if (link == NULL)
    597                 return NULL;
    598 
    599         return list_get_instance(link, odlink_t, lentries);
    600 }
    601 
    602 /** Find first entry whose key is equal to @a key/
    603  *
    604  * @param odict Ordered dictionary
    605  * @param key Key
    606  * @param hint Nearby entry
    607  * @return Pointer to entry on success, @c NULL on failure
    608  */
    609 odlink_t *odict_find_eq(odict_t *odict, void *key, odlink_t *hint)
    610 {
    611         odlink_t *geq;
    612 
    613         geq = odict_find_geq(odict, key, hint);
    614         if (geq == NULL)
    615                 return NULL;
    616 
    617         if (odict->cmp(odict->getkey(geq), key) == 0)
    618                 return geq;
    619         else
    620                 return NULL;
    621 }
    622 
    623 /** Find last entry whose key is equal to @a key/
    624  *
    625  * @param odict Ordered dictionary
    626  * @param key Key
    627  * @param hint Nearby entry
    628  * @return Pointer to entry on success, @c NULL on failure
    629  */
    630 odlink_t *odict_find_eq_last(odict_t *odict, void *key, odlink_t *hint)
    631 {
    632         odlink_t *leq;
    633 
    634         leq = odict_find_leq(odict, key, hint);
    635         if (leq == NULL)
    636                 return NULL;
    637 
    638         if (odict->cmp(odict->getkey(leq), key) == 0)
    639                 return leq;
    640         else
    641                 return NULL;
    642 }
    643 
    644 /** Find first entry whose key is greater than or equal to @a key
    645  *
    646  * @param odict Ordered dictionary
    647  * @param key Key
    648  * @param hint Nearby entry
    649  * @return Pointer to entry on success, @c NULL on failure
    650  */
    651 odlink_t *odict_find_geq(odict_t *odict, void *key, odlink_t *hint)
    652 {
    653         odlink_t *cur;
    654         odlink_t *next;
    655         int d;
    656 
    657         cur = odict_search_start_node(odict, key, hint);
    658         if (cur == NULL)
    659                 return NULL;
    660 
    661         while (true) {
    662                 d = odict->cmp(odict->getkey(cur), key);
    663                 if (d >= 0)
    664                         next = cur->a;
    665                 else
    666                         next = cur->b;
    667 
    668                 if (next == NULL)
    669                         break;
    670 
    671                 cur = next;
    672         }
    673 
    674         if (d >= 0) {
    675                 return cur;
    676         } else {
    677                 return odict_next(cur, odict);
    678         }
    679 }
    680 
    681 /** Find last entry whose key is greater than @a key.
    682  *
    683  * @param odict Ordered dictionary
    684  * @param key Key
    685  * @param hint Nearby entry
    686  * @return Pointer to entry on success, @c NULL on failure
    687  */
    688 odlink_t *odict_find_gt(odict_t *odict, void *key, odlink_t *hint)
    689 {
    690         odlink_t *leq;
    691 
    692         leq = odict_find_leq(odict, key, hint);
    693         if (leq != NULL)
    694                 return odict_next(leq, odict);
    695         else
    696                 return odict_first(odict);
    697 }
    698 
    699 /** Find last entry whose key is less than or equal to @a key
    700  *
    701  * @param odict Ordered dictionary
    702  * @param key Key
    703  * @param hint Nearby entry
    704  * @return Pointer to entry on success, @c NULL on failure
    705  */
    706 odlink_t *odict_find_leq(odict_t *odict, void *key, odlink_t *hint)
    707 {
    708         odlink_t *cur;
    709         odlink_t *next;
    710         int d;
    711 
    712         cur = odict_search_start_node(odict, key, hint);
    713         if (cur == NULL)
    714                 return NULL;
    715 
    716         while (true) {
    717                 d = odict->cmp(key, odict->getkey(cur));
    718                 if (d >= 0)
    719                         next = cur->b;
    720                 else
    721                         next = cur->a;
    722 
    723                 if (next == NULL)
    724                         break;
    725 
    726                 cur = next;
    727         }
    728 
    729         if (d >= 0) {
    730                 return cur;
    731         } else {
    732                 return odict_prev(cur, odict);
    733         }
    734 }
    735 
    736 /** Find last entry whose key is less than @a key.
    737  *
    738  * @param odict Ordered dictionary
    739  * @param key Key
    740  * @param hint Nearby entry
    741  * @return Pointer to entry on success, @c NULL on failure
    742  */
    743 odlink_t *odict_find_lt(odict_t *odict, void *key, odlink_t *hint)
    744 {
    745         odlink_t *geq;
    746 
    747         geq = odict_find_geq(odict, key, hint);
    748         if (geq != NULL)
    749                 return odict_prev(geq, odict);
    750         else
    751                 return odict_last(odict);
    752 }
    753 
    754 /** Return parent, grandparent and uncle.
    755  *
    756  * @param n Node
    757  * @param p Place to store pointer to parent of @a n
    758  * @param pcs Place to store position of @a n w.r.t. @a p
    759  * @param g Place to store pointer to grandparent of @a n
    760  * @param gcs Place to store position of @a p w.r.t. @a g
    761  * @param u Place to store pointer to uncle of @a n
    762  */
    763 static void odict_pgu(odlink_t *n, odlink_t **p, odict_child_sel_t *pcs,
    764     odlink_t **g, odict_child_sel_t *gcs, odlink_t **u)
    765 {
    766         *p = n->up;
    767 
    768         if (*p == NULL) {
    769                 /* No parent */
    770                 *g = NULL;
    771                 *u = NULL;
    772                 return;
    773         }
    774 
    775         if ((*p)->a == n) {
    776                 *pcs = odcs_a;
    777         } else {
    778                 assert((*p)->b == n);
    779                 *pcs = odcs_b;
    780         }
    781 
    782         *g = (*p)->up;
    783         if (*g == NULL) {
    784                 /* No grandparent */
    785                 *u = NULL;
    786                 return;
    787         }
    788 
    789         if ((*g)->a == *p) {
    790                 *gcs = odcs_a;
    791                 *u = (*g)->b;
    792         } else {
    793                 assert((*g)->b == *p);
    794                 *gcs = odcs_b;
    795                 *u = (*g)->a;
    796         }
    797 }
    798 
    799 /** Return sibling and parent w.r.t. parent.
    800  *
    801  * @param n Node
    802  * @param p Parent of @ an
    803  * @param pcs Place to store position of @a n w.r.t. @a p.
    804  * @param rs Place to strore pointer to sibling
    805  */
    806 static void odict_sibling(odlink_t *n, odlink_t *p, odict_child_sel_t *pcs,
    807     odlink_t **rs)
    808 {
    809         if (p->a == n) {
    810                 *pcs = odcs_a;
    811                 *rs = p->b;
    812         } else {
    813                 *pcs = odcs_b;
    814                 *rs = p->a;
    815         }
    816 }
    817 
    818 /** Ordered dictionary left rotation.
    819  *
    820  *    Q           P
    821  *  P   C   <- A    Q
    822  * A B             B C
    823  *
    824  */
    825 static void odict_rotate_left(odlink_t *p)
    826 {
    827         odlink_t *q;
    828 
    829         q = p->b;
    830         assert(q != NULL);
    831 
    832         /* Replace P with Q as the root of the subtree */
    833         odict_replace_subtree(q, p);
    834 
    835         /* Relink P under Q, B under P */
    836         p->up = q;
    837         p->b = q->a;
    838         if (p->b != NULL)
    839                 p->b->up = p;
    840         q->a = p;
    841 
    842         /* Fix odict root */
    843         if (p->odict->root == p)
    844                 p->odict->root = q;
    845 }
    846 
    847 /** Ordered dictionary right rotation.
    848  *
    849  *    Q           P
    850  *  P   C   -> A    Q
    851  * A B             B C
    852  *
    853  */
    854 static void odict_rotate_right(odlink_t *q)
    855 {
    856         odlink_t *p;
    857 
    858         p = q->a;
    859         assert(p != NULL);
    860 
    861         /* Replace Q with P as the root of the subtree */
    862         odict_replace_subtree(p, q);
    863 
    864         /* Relink Q under P, B under Q */
    865         q->up = p;
    866         q->a = p->b;
    867         if (q->a != NULL)
    868                 q->a->up = q;
    869         p->b = q;
    870 
    871         /* Fix odict root */
    872         if (q->odict->root == q)
    873                 q->odict->root = p;
    874 }
    875 
    876 /** Swap two nodes.
    877  *
    878  * Swap position of two nodes in the tree, keeping their identity.
    879  * This means we don't copy the contents, instead we shuffle around pointers
    880  * from and to the nodes.
    881  *
    882  * @param a First node
    883  * @param b Second node
    884  */
    885 static void odict_swap_node(odlink_t *a, odlink_t *b)
    886 {
    887         odlink_t *n;
    888         odict_color_t c;
    889 
    890         /* Backlink from A's parent */
    891         if (a->up != NULL && a->up != b) {
    892                 if (a->up->a == a) {
    893                         a->up->a = b;
    894                 } else {
    895                         assert(a->up->b == a);
    896                         a->up->b = b;
    897                 }
    898         }
    899 
    900         /* Backlink from A's left child */
    901         if (a->a != NULL && a->a != b)
    902                 a->a->up = b;
    903         /* Backling from A's right child */
    904         if (a->b != NULL && a->b != b)
    905                 a->b->up = b;
    906 
    907         /* Backlink from B's parent */
    908         if (b->up != NULL && b->up != a) {
    909                 if (b->up->a == b) {
    910                         b->up->a = a;
    911                 } else {
    912                         assert(b->up->b == b);
    913                         b->up->b = a;
    914                 }
    915         }
    916 
    917         /* Backlink from B's left child */
    918         if (b->a != NULL && b->a != a)
    919                 b->a->up = a;
    920         /* Backling from B's right child */
    921         if (b->b != NULL && b->b != a)
    922                 b->b->up = a;
    923 
    924         /*
    925          * Swap links going out of A and out of B
    926          */
    927         n = a->up;
    928         a->up = b->up;
    929         b->up = n;
    930 
    931         n = a->a;
    932         a->a = b->a;
    933         b->a = n;
    934 
    935         n = a->b;
    936         a->b = b->b;
    937         b->b = n;
    938 
    939         c = a->color;
    940         a->color = b->color;
    941         b->color = c;
    942 
    943         /* When A and B are adjacent, fix self-loops that might have arisen */
    944         if (a->up == a)
    945                 a->up = b;
    946         if (a->a == a)
    947                 a->a = b;
    948         if (a->b == a)
    949                 a->b = b;
    950         if (b->up == b)
    951                 b->up = a;
    952         if (b->a == b)
    953                 b->a = a;
    954         if (b->b == b)
    955                 b->b = a;
    956 
    957         /* Fix odict root */
    958         if (a == a->odict->root)
    959                 a->odict->root = b;
    960         else if (b == a->odict->root)
    961                 a->odict->root = a;
    962 }
    963 
    964 /** Replace subtree.
    965  *
    966  * Replace subtree @a old with another subtree @a n. This makes the parent
    967  * point to the new subtree root and the up pointer of @a n to point to
    968  * the parent.
    969  *
    970  * @param old Subtree to be replaced
    971  * @param n New subtree
    972  */
    973 static void odict_replace_subtree(odlink_t *n, odlink_t *old)
    974 {
    975         if (old->up != NULL) {
    976                 if (old->up->a == old) {
    977                         old->up->a = n;
    978                 } else {
    979                         assert(old->up->b == old);
    980                         old->up->b = n;
    981                 }
    982         } else {
    983                 assert(old->odict->root == old);
    984                 old->odict->root = n;
    985         }
    986 
    987         n->up = old->up;
    988 }
    989 
    990 /** Unlink node.
    991  *
    992  * @param n Ordered dictionary node
    993  */
    994 static void odict_unlink(odlink_t *n)
    995 {
    996         if (n->up != NULL) {
    997                 if (n->up->a == n) {
    998                         n->up->a = NULL;
    999                 } else {
    1000                         assert(n->up->b == n);
    1001                         n->up->b = NULL;
    1002                 }
    1003 
    1004                 n->up = NULL;
    1005         } else {
    1006                 assert(n->odict->root == n);
    1007                 n->odict->root = NULL;
    1008         }
    1009 
    1010         if (n->a != NULL) {
    1011                 n->a->up = NULL;
    1012                 n->a = NULL;
    1013         }
    1014 
    1015         if (n->b != NULL) {
    1016                 n->b->up = NULL;
    1017                 n->b = NULL;
    1018         }
    1019 
    1020         n->odict = NULL;
    1021         list_remove(&n->lentries);
    1022 }
    1023 
    1024 /** Link node as left child.
    1025  *
    1026  * Append new node @a n as left child of existing node @a old.
    1027  *
    1028  * @param n New node
    1029  * @param old Old node
    1030  */
    1031 static void odict_link_child_a(odlink_t *n, odlink_t *old)
    1032 {
    1033         old->a = n;
    1034         n->up = old;
    1035         n->odict = old->odict;
    1036         list_insert_before(&n->lentries, &old->lentries);
    1037 }
    1038 
    1039 /** Link node as right child.
    1040  *
    1041  * Append new node @a n as right child of existing node @a old.
    1042  *
    1043  * @param n New node
    1044  * @param old Old node
    1045  */
    1046 static void odict_link_child_b(odlink_t *n, odlink_t *old)
    1047 {
    1048         old->b = n;
    1049         n->up = old;
    1050         n->odict = old->odict;
    1051         list_insert_after(&n->lentries, &old->lentries);
    1052 }
    1053 
    1054 /** Get node where search should be started.
    1055  *
    1056  * @param odict Ordered dictionary
    1057  * @param key Key being searched for
    1058  * @param hint Node that might be near the search target or @c NULL
    1059  *
    1060  * @return Node from where search should be started
    1061  */
    1062 static odlink_t *odict_search_start_node(odict_t *odict, void *key,
    1063     odlink_t *hint)
    1064 {
    1065         odlink_t *a;
    1066         odlink_t *b;
    1067         odlink_t *cur;
    1068         int d, da, db;
    1069 
    1070         assert(hint == NULL || hint->odict == odict);
    1071 
    1072         /* If the key is greater than the maximum, start search in the maximum */
    1073         b = odict_last(odict);
    1074         if (b != NULL) {
    1075                 d = odict->cmp(odict->getkey(b), key);
    1076                 if (d < 0)
    1077                         return b;
    1078         }
    1079 
    1080         /* If the key is less tna the minimum, start search in the minimum */
    1081         a = odict_first(odict);
    1082         if (a != NULL) {
    1083                 d = odict->cmp(key, odict->getkey(a));
    1084                 if (d < 0)
    1085                         return a;
    1086         }
    1087 
    1088         /*
    1089          * Proposition: Let A, B be two BST nodes such that B is a descendant
    1090          * of A. Let N be a node such that either key(A) < key(N) < key(B)
    1091          * Then N is a descendant of A.
    1092          * Corollary: We can start searching for N from A, instead from
    1093          * the root.
    1094          *
    1095          * Proof: When walking the BST in order, visit_tree(A) does a
    1096          * visit_tree(A->a), visit(A), visit(A->b). If key(A) < key(B),
    1097          * we will first visit A, then while visiting all nodes with values
    1098          * between A and B we will not leave subtree A->b.
    1099          */
    1100 
    1101         /* If there is no hint, start search from the root */
    1102         if (hint == NULL)
    1103                 return odict->root;
    1104 
    1105         /*
    1106          * Start from hint and walk up to the root, keeping track of
    1107          * minimum and maximum. Once key is strictly between them,
    1108          * we can return the current node, which we've proven to be
    1109          * an ancestor of a potential node with the given key
    1110          */
    1111         a = b = cur = hint;
    1112         while (cur->up != NULL) {
    1113                 cur = cur->up;
    1114 
    1115                 d = odict->cmp(odict->getkey(cur), odict->getkey(a));
    1116                 if (d < 0)
    1117                         a = cur;
    1118 
    1119                 d = odict->cmp(odict->getkey(b), odict->getkey(cur));
    1120                 if (d < 0)
    1121                         b = cur;
    1122 
    1123                 da = odict->cmp(odict->getkey(a), key);
    1124                 db = odict->cmp(key, odict->getkey(b));
    1125                 if (da < 0 && db < 0) {
    1126                         /* Both a and b are descendants of cur */
    1127                         return cur;
    1128                 }
    1129         }
    1130 
    1131         return odict->root;
    1132 }
    1133 
    1134 /** @}
    1135  */
     1../../../../../kernel/generic/src/adt/odict.c
Note: See TracChangeset for help on using the changeset viewer.