git.ozlabs.org Git - ccan/blob - ccan/btree/btree.c

   1 /*
   2  * Copyright (C) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a copy
   5  * of this software and associated documentation files (the "Software"), to deal
   6  * in the Software without restriction, including without limitation the rights
   7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  * copies of the Software, and to permit persons to whom the Software is
   9  * furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20  * THE SOFTWARE.
  21  */
  22
  23 #include "btree.h"
  24
  25 #include <assert.h>
  26 #include <stdlib.h>
  27 #include <stdio.h>
  28
  29 #define MAX (BTREE_ITEM_MAX)
  30 #define MIN (BTREE_ITEM_MAX >> 1)
  31
  32 static struct btree_node *node_alloc(int internal);
  33 static void node_delete(struct btree_node *node, struct btree *btree);
  34
  35 static void branch_begin(btree_iterator iter);
  36 static void branch_end(btree_iterator iter);
  37 static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr);
  38
  39 /*
  40  * If iter->node has parent, returns 1 and ascends the iterator such that
  41  * iter->node->branch[iter->k] will be what iter->node was.
  42  *
  43  * If iter->node does not have a parent (is a root), returns 0 and leaves the
  44  * iterator untouched.
  45  */
  46 #define ascend(iter) ((iter)->node->parent \
  47         ? (iter)->k = (iter)->node->k, (iter)->node = (iter)->node->parent, 1 \
  48         : 0)
  49
  50 static void node_insert(const void *x, struct btree_node *xr,
  51                                 struct btree_node *p, unsigned int k);
  52 static void node_split(const void **x, struct btree_node **xr,
  53                                 struct btree_node *p, unsigned int k);
  54
  55 static void node_remove_leaf_item(struct btree_node *node, unsigned int k);
  56 void node_restore(struct btree_node *node, unsigned int k);
  57
  58 static int node_walk_backward(const struct btree_node *node,
  59                                 btree_action_t action, void *ctx);
  60 static int node_walk_forward(const struct btree_node *node,
  61                                 btree_action_t action, void *ctx);
  62
  63
  64 /************************* Public functions *************************/
  65
  66 struct btree *btree_new(btree_search_t search)
  67 {
  68         struct btree *btree = calloc(1, sizeof(struct btree));
  69         struct btree_node *node = node_alloc(0);
  70                 node->parent = NULL;
  71                 node->count = 0;
  72                 node->depth = 0;
  73         btree->root = node;
  74         btree->search = search;
  75         btree->multi = false;
  76         return btree;
  77 }
  78
  79 void btree_delete(struct btree *btree)
  80 {
  81         node_delete(btree->root, btree);
  82         free(btree);
  83 }
  84
  85 bool btree_insert(struct btree *btree, const void *item)
  86 {
  87         btree_iterator iter;
  88
  89         if (btree_find_last(btree, item, iter) && !btree->multi)
  90                 return false;
  91
  92         btree_insert_at(iter, item);
  93         return true;
  94 }
  95
  96 bool btree_remove(struct btree *btree, const void *key)
  97 {
  98         btree_iterator iter;
  99         bool success = false;
 100         bool multi = btree->multi;
 101
 102         do {
 103                 if (btree_find_first(btree, key, iter)) {
 104                         btree_remove_at(iter);
 105                         success = true;
 106                 }
 107         } while (multi);
 108
 109         return success;
 110 }
 111
 112 void *btree_lookup(struct btree *btree, const void *key)
 113 {
 114         btree_iterator iter;
 115
 116         if (btree_find_first(btree, key, iter))
 117                 return iter->item;
 118
 119         return NULL;
 120 }
 121
 122 int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr)
 123 {
 124         struct btree_node *node;
 125
 126         iter->btree = (struct btree *)btree;
 127         begin_end_lr(iter, btree->root, lr);
 128
 129         /* Set iter->item if any items exist. */
 130         node = iter->node;
 131         if (node->count) {
 132                 iter->item = (void*)node->item[iter->k - lr];
 133                 return 1;
 134         }
 135
 136         return 0;
 137 }
 138
 139 int btree_deref(btree_iterator iter)
 140 {
 141         if (iter->k >= iter->node->count) {
 142                 struct btree_iterator_s tmp = *iter;
 143                 do {
 144                         if (!ascend(iter)) {
 145                                 *iter = tmp;
 146                                 return 0;
 147                         }
 148                 } while (iter->k >= iter->node->count);
 149         }
 150
 151         iter->item = (void*)iter->node->item[iter->k];
 152         return 1;
 153 }
 154
 155 int btree_prev(btree_iterator iter)
 156 {
 157         if (iter->node->depth) {
 158                 branch_end(iter);
 159         } else if (iter->k == 0) {
 160                 struct btree_iterator_s tmp = *iter;
 161                 do {
 162                         if (!ascend(iter)) {
 163                                 *iter = tmp;
 164                                 return 0;
 165                         }
 166                 } while (iter->k == 0);
 167         }
 168
 169         iter->item = (void*)iter->node->item[--iter->k];
 170         return 1;
 171 }
 172
 173 int btree_next(btree_iterator iter)
 174 {
 175         int ret = btree_deref(iter);
 176         if (ret) {
 177                 iter->k++;
 178                 if (iter->node->depth)
 179                         branch_begin(iter);
 180         }
 181         return ret;
 182 }
 183
 184 int btree_find_lr(const struct btree *btree, const void *key,
 185                                 btree_iterator iter, int lr)
 186 {
 187         struct btree_node *node = btree->root;
 188         unsigned int k;
 189         unsigned int depth;
 190         int found = 0;
 191
 192         iter->btree = (struct btree *)btree;
 193         iter->item = NULL;
 194
 195         depth = node->depth;
 196         for (;;) {
 197                 int f = 0;
 198                 k = btree->search(key, node->item, node->count, lr, &f);
 199
 200                 if (f) {
 201                         iter->item = (void*)node->item[k - lr];
 202                         found = 1;
 203                 }
 204                 if (!depth--)
 205                         break;
 206
 207                 node = node->branch[k];
 208         }
 209
 210         iter->node = node;
 211         iter->k = k;
 212
 213         return found;
 214 }
 215
 216 int btree_walk_backward(const struct btree *btree,
 217                                 btree_action_t action, void *ctx)
 218 {
 219         return node_walk_backward(btree->root, action, ctx);
 220 }
 221
 222 int btree_walk_forward(const struct btree *btree,
 223                                 btree_action_t action, void *ctx)
 224 {
 225         return node_walk_forward(btree->root, action, ctx);
 226 }
 227
 228 void btree_insert_at(btree_iterator iter, const void *item)
 229 {
 230         const void *x = item;
 231         struct btree_node *xr = NULL;
 232         struct btree_node *p;
 233         struct btree *btree = iter->btree;
 234
 235         /* btree_insert_at always sets iter->item to item. */
 236         iter->item = (void*)item;
 237
 238         /*
 239          * If node is not a leaf, fall to the end of the left branch of item[k]
 240          * so that it will be a leaf. This does not modify the iterator's logical
 241          * position.
 242          */
 243         if (iter->node->depth)
 244                 branch_end(iter);
 245
 246         /*
 247          * First try inserting item into this node.
 248          * If it's too big, split it, and repeat by
 249          * trying to insert the median and right subtree into parent.
 250          */
 251         if (iter->node->count < MAX) {
 252                 node_insert(x, xr, iter->node, iter->k);
 253                 goto finished;
 254         } else {
 255                 for (;;) {
 256                         node_split(&x, &xr, iter->node, iter->k);
 257
 258                         if (!ascend(iter))
 259                                 break;
 260
 261                         if (iter->node->count < MAX) {
 262                                 node_insert(x, xr, iter->node, iter->k);
 263                                 goto finished;
 264                         }
 265                 }
 266
 267                 /*
 268                  * If splitting came all the way up to the root, create a new root whose
 269                  * left branch is the current root, median is x, and right branch is the
 270                  * half split off from the root.
 271                  */
 272                 assert(iter->node == btree->root);
 273                 p = node_alloc(1);
 274                 p->parent = NULL;
 275                 p->count = 1;
 276                 p->depth = btree->root->depth + 1;
 277                 p->item[0] = x;
 278                 p->branch[0] = btree->root;
 279                         btree->root->parent = p;
 280                         btree->root->k = 0;
 281                 p->branch[1] = xr;
 282                         xr->parent = p;
 283                         xr->k = 1;
 284                 btree->root = p;
 285         }
 286
 287 finished:
 288         btree->count++;
 289         iter->node = NULL;
 290 }
 291
 292 int btree_remove_at(btree_iterator iter)
 293 {
 294         struct btree *btree = iter->btree;
 295         struct btree_node *root;
 296
 297         if (!btree_deref(iter))
 298                 return 0;
 299
 300         if (!iter->node->depth) {
 301                 node_remove_leaf_item(iter->node, iter->k);
 302                 if (iter->node->count >= MIN || !iter->node->parent)
 303                         goto finished;
 304         } else {
 305                 /*
 306                  * We can't remove an item from an internal node, so we'll replace it
 307                  * with its successor (which will always be in a leaf), then remove
 308                  * the original copy of the successor.
 309                  */
 310
 311                 /* Save pointer to condemned item. */
 312                 const void **x = &iter->node->item[iter->k];
 313
 314                 /* Descend to successor. */
 315                 iter->k++;
 316                 branch_begin(iter);
 317
 318                 /* Replace condemned item with successor. */
 319                 *x = iter->node->item[0];
 320
 321                 /* Remove successor. */
 322                 node_remove_leaf_item(iter->node, 0);
 323         }
 324
 325         /*
 326          * Restore nodes that fall under their minimum count.  This may
 327          * propagate all the way up to the root.
 328          */
 329         for (;;) {
 330                 if (iter->node->count >= MIN)
 331                         goto finished;
 332                 if (!ascend(iter))
 333                         break;
 334                 node_restore(iter->node, iter->k);
 335         }
 336
 337         /*
 338          * If combining came all the way up to the root, and it has no more
 339          * dividers, delete it and make its only branch the root.
 340          */
 341         root = iter->node;
 342         assert(root == btree->root);
 343         assert(root->depth > 0);
 344         if (root->count == 0) {
 345                 btree->root = root->branch[0];
 346                 btree->root->parent = NULL;
 347                 free(root);
 348         }
 349
 350 finished:
 351         btree->count--;
 352         iter->node = NULL;
 353         return 1;
 354 }
 355
 356 /*
 357  * ascends iterator a until it matches iterator b's depth.
 358  *
 359  * Returns -1 if they end up on the same k (meaning a < b).
 360  * Returns 0 otherwise.
 361  */
 362 static int elevate(btree_iterator a, btree_iterator b)
 363 {
 364         while (a->node->depth < b->node->depth)
 365                 ascend(a);
 366
 367         if (a->k == b->k)
 368                 return -1;
 369         return 0;
 370 }
 371
 372 int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b)
 373 {
 374         btree_iterator a = {*iter_a}, b = {*iter_b};
 375         int ad, bd;
 376
 377         ad = btree_deref(a);
 378         bd = btree_deref(b);
 379
 380         /* Check cases where one or both iterators are at the end. */
 381         if (!ad)
 382                 return bd ? 1 : 0;
 383         if (!bd)
 384                 return ad ? -1 : 0;
 385
 386         /* Bring iterators to the same depth. */
 387         if (a->node->depth < b->node->depth) {
 388                 if (elevate(a, b))
 389                         return -1;
 390         } else if (a->node->depth > b->node->depth) {
 391                 if (elevate(b, a))
 392                         return 1;
 393         }
 394
 395         /* Bring iterators to the same node. */
 396         while (a->node != b->node) {
 397                 ascend(a);
 398                 ascend(b);
 399         }
 400
 401         /* Now we can compare by k directly. */
 402         if (a->k < b->k)
 403                 return -1;
 404         if (a->k > b->k)
 405                 return 1;
 406
 407         return 0;
 408 }
 409
 410 /********************* Built-in ordering functions *******************/
 411
 412 btree_search_implement
 413 (
 414         btree_strcmp,
 415         char*,
 416         int c = strcmp(a, b),
 417         c == 0,
 418         c < 0
 419 )
 420
 421
 422 /************************* Private functions *************************/
 423
 424 static struct btree_node *node_alloc(int internal)
 425 {
 426         struct btree_node *node;
 427         size_t isize = internal
 428                 ? sizeof(struct btree_node*) * (BTREE_ITEM_MAX+1)
 429                 : 0;
 430         node = malloc(sizeof(struct btree_node) + isize);
 431         return node;
 432 }
 433
 434 static void node_delete(struct btree_node *node, struct btree *btree)
 435 {
 436         unsigned int i, count = node->count;
 437
 438         if (!node->depth) {
 439                 if (btree->destroy) {
 440                         for (i=0; i<count; i++)
 441                                 btree->destroy((void*)node->item[i], btree->destroy_ctx);
 442                 }
 443         } else {
 444                 for (i=0; i<count; i++) {
 445                         node_delete(node->branch[i], btree);
 446                         if (btree->destroy)
 447                                 btree->destroy((void*)node->item[i], btree->destroy_ctx);
 448                 }
 449                 node_delete(node->branch[count], btree);
 450         }
 451
 452         free(node);
 453 }
 454
 455 /* Set iter to beginning of branch pointed to by iter. */
 456 static void branch_begin(btree_iterator iter)
 457 {
 458         struct btree_node *node = iter->node->branch[iter->k];
 459         unsigned int depth = node->depth;
 460         while (depth--)
 461                 node = node->branch[0];
 462         iter->node = node;
 463         iter->k = 0;
 464 }
 465
 466 /* Set iter to end of branch pointed to by iter. */
 467 static void branch_end(btree_iterator iter)
 468 {
 469         struct btree_node *node = iter->node->branch[iter->k];
 470         unsigned int depth = node->depth;
 471         while (depth--)
 472                 node = node->branch[node->count];
 473         iter->node = node;
 474         iter->k = node->count;
 475 }
 476
 477 /* Traverse to the beginning or end of node, depending on lr. */
 478 static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr)
 479 {
 480         iter->node = node;
 481         iter->k = lr ? node->count : 0;
 482         if (node->depth)
 483                 (lr ? branch_end : branch_begin)(iter);
 484 }
 485
 486 /*
 487  * Inserts item x and right branch xr into node p at position k.
 488  *
 489  * Assumes p exists and has enough room.
 490  * Ignores xr if p is a leaf.
 491  */
 492 static void node_insert(const void *x, struct btree_node *xr,
 493                                 struct btree_node *p, unsigned int k)
 494 {
 495         unsigned int i;
 496
 497         for (i = p->count; i-- > k;)
 498                 p->item[i+1] = p->item[i];
 499         p->item[k] = x;
 500
 501         if (p->depth) {
 502                 k++;
 503                 for (i = p->count+1; i-- > k;) {
 504                         p->branch[i+1] = p->branch[i];
 505                         p->branch[i+1]->k = i+1;
 506                 }
 507                 p->branch[k] = xr;
 508                 xr->parent = p;
 509                 xr->k = k;
 510         }
 511
 512         p->count++;
 513 }
 514
 515 /*
 516  * Inserts item *x and subtree *xr into node p at position k, splitting it into
 517  * nodes p and *xr with median item *x.
 518  *
 519  * Assumes p->count == MAX.
 520  * Ignores original *xr if p is a leaf, but always sets it.
 521  */
 522 static void node_split(const void **x, struct btree_node **xr,
 523                                 struct btree_node *p, unsigned int k)
 524 {
 525         unsigned int i, split;
 526         struct btree_node *l = p, *r;
 527
 528         /*
 529          * If k <= MIN, item will be inserted into left subtree, so give l
 530          * fewer items initially.
 531          * Otherwise, item will be inserted into right subtree, so give r
 532          * fewer items initially.
 533          */
 534         if (k <= MIN)
 535                 split = MIN;
 536         else
 537                 split = MIN + 1;
 538
 539         /*
 540          * If l->depth is 0, allocate a leaf node.
 541          * Otherwise, allocate an internal node.
 542          */
 543         r = node_alloc(l->depth);
 544
 545         /* l and r will be siblings, so they will have the same parent and depth. */
 546         r->parent = l->parent;
 547         r->depth = l->depth;
 548
 549         /*
 550          * Initialize items/branches of right side.
 551          * Do not initialize r's leftmost branch yet because we don't know
 552          * whether it will be l's current rightmost branch or if *xr will
 553          * take its place.
 554          */
 555         for (i = split; i < MAX; i++)
 556                 r->item[i-split] = l->item[i];
 557         if (r->depth) {
 558                 for (i = split+1; i <= MAX; i++) {
 559                         r->branch[i-split] = l->branch[i];
 560                         r->branch[i-split]->parent = r;
 561                         r->branch[i-split]->k = i-split;
 562                 }
 563         }
 564
 565         /* Update counts. */
 566         l->count = split;
 567         r->count = MAX - split;
 568
 569         /*
 570          * The nodes are now split, but the key isn't inserted yet.
 571          *
 572          * Insert key into left or right half,
 573          * depending on which side it fell on.
 574          */
 575         if (k <= MIN)
 576                 node_insert(*x, *xr, l, k);
 577         else
 578                 node_insert(*x, *xr, r, k - split);
 579
 580         /*
 581          * Give l's rightmost branch to r because l's rightmost item
 582          * is going up to become the median.
 583          */
 584         if (r->depth) {
 585                 r->branch[0] = l->branch[l->count];
 586                 r->branch[0]->parent = r;
 587                 r->branch[0]->k = 0;
 588         }
 589
 590         /*
 591          * Take up l's rightmost item to make it the median.
 592          * That item's right branch is now r.
 593          */
 594         *x = l->item[--l->count];
 595         *xr = r;
 596 }
 597
 598 /*
 599  * Removes item k from node p, shifting successor items back and
 600  * decrementing the count.
 601  *
 602  * Assumes node p has the item k and is a leaf.
 603  */
 604 static void node_remove_leaf_item(struct btree_node *node, unsigned int k)
 605 {
 606         unsigned int i;
 607         for (i = k+1; i < node->count; i++)
 608                 node->item[i-1] = node->item[i];
 609         node->count--;
 610 }
 611
 612 static void move_left(struct btree_node *node, unsigned int k);
 613 static void move_right(struct btree_node *node, unsigned int k);
 614 static void combine(struct btree_node *node, unsigned int k);
 615
 616 /*
 617  * Fixes node->branch[k]'s problem of having one less than MIN items.
 618  * May or may not cause node to fall below MIN items, depending on whether
 619  * two branches are combined or not.
 620  */
 621 void node_restore(struct btree_node *node, unsigned int k)
 622 {
 623         if (k == 0) {
 624                 if (node->branch[1]->count > MIN)
 625                         move_left(node, 0);
 626                 else
 627                         combine(node, 0);
 628         } else if (k == node->count) {
 629                 if (node->branch[k-1]->count > MIN)
 630                         move_right(node, k-1);
 631                 else
 632                         combine(node, k-1);
 633         } else if (node->branch[k-1]->count > MIN) {
 634                 move_right(node, k-1);
 635         } else if (node->branch[k+1]->count > MIN) {
 636                 move_left(node, k);
 637         } else {
 638                 combine(node, k-1);
 639         }
 640 }
 641
 642 static void move_left(struct btree_node *node, unsigned int k)
 643 {
 644         struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
 645         unsigned int i;
 646
 647         l->item[l->count] = node->item[k];
 648         node->item[k] = r->item[0];
 649         for (i = 1; i < r->count; i++)
 650                 r->item[i-1] = r->item[i];
 651
 652         if (r->depth) {
 653                 mv = r->branch[0];
 654                 l->branch[l->count+1] = mv;
 655                 mv->parent = l;
 656                 mv->k = l->count+1;
 657
 658                 for (i = 1; i <= r->count; i++) {
 659                         r->branch[i-1] = r->branch[i];
 660                         r->branch[i-1]->k = i-1;
 661                 }
 662         }
 663
 664         l->count++;
 665         r->count--;
 666 }
 667
 668 static void move_right(struct btree_node *node, unsigned int k)
 669 {
 670         struct btree_node *l = node->branch[k], *r = node->branch[k+1];
 671         unsigned int i;
 672
 673         for (i = r->count; i--;)
 674                 r->item[i+1] = r->item[i];
 675         r->item[0] = node->item[k];
 676         node->item[k] = l->item[l->count-1];
 677
 678         if (r->depth) {
 679                 for (i = r->count+1; i--;) {
 680                         r->branch[i+1] = r->branch[i];
 681                         r->branch[i+1]->k = i+1;
 682                 }
 683                 r->branch[0] = l->branch[l->count];
 684                 r->branch[0]->parent = r;
 685                 r->branch[0]->k = 0;
 686         }
 687
 688         l->count--;
 689         r->count++;
 690 }
 691
 692 /* Combine node->branch[k] and node->branch[k+1]. */
 693 static void combine(struct btree_node *node, unsigned int k)
 694 {
 695         struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
 696         const void **o = &l->item[l->count];
 697         unsigned int i;
 698
 699         //append node->item[k] followed by right node's items to left node
 700         *o++ = node->item[k];
 701         for (i=0; i<r->count; i++)
 702                 *o++ = r->item[i];
 703
 704         //if applicable, append right node's branches to left node
 705         if (r->depth) {
 706                 for (i=0; i<=r->count; i++) {
 707                         mv = r->branch[i];
 708                         l->branch[l->count + i + 1] = mv;
 709                         mv->parent = l;
 710                         mv->k = l->count + i + 1;
 711                 }
 712         }
 713
 714         //remove k and its right branch from parent node
 715         for (i = k+1; i < node->count; i++) {
 716                 node->item[i-1] = node->item[i];
 717                 node->branch[i] = node->branch[i+1];
 718                 node->branch[i]->k = i;
 719         }
 720
 721         //don't forget to update the left and parent node's counts and to free the right node
 722         l->count += r->count + 1;
 723         node->count--;
 724         free(r);
 725 }
 726
 727 static int node_walk_backward(const struct btree_node *node,
 728                                 btree_action_t action, void *ctx)
 729 {
 730         unsigned int i, count = node->count;
 731
 732         if (!node->depth) {
 733                 for (i=count; i--;)
 734                         if (!action((void*)node->item[i], ctx))
 735                                 return 0;
 736         } else {
 737                 if (!node_walk_backward(node->branch[count], action, ctx))
 738                         return 0;
 739                 for (i=count; i--;) {
 740                         if (!action((void*)node->item[i], ctx))
 741                                 return 0;
 742                         if (!node_walk_backward(node->branch[i], action, ctx))
 743                                 return 0;
 744                 }
 745         }
 746
 747         return 1;
 748 }
 749
 750 static int node_walk_forward(const struct btree_node *node,
 751                                 btree_action_t action, void *ctx)
 752 {
 753         unsigned int i, count = node->count;
 754
 755         if (!node->depth) {
 756                 for (i=0; i<count; i++)
 757                         if (!action((void*)node->item[i], ctx))
 758                                 return 0;
 759         } else {
 760                 for (i=0; i<count; i++) {
 761                         if (!node_walk_forward(node->branch[i], action, ctx))
 762                                 return 0;
 763                         if (!action((void*)node->item[i], ctx))
 764                                 return 0;
 765                 }
 766                 if (!node_walk_forward(node->branch[count], action, ctx))
 767                         return 0;
 768         }
 769
 770         return 1;
 771 }