Annotation of embedaddon/quagga/isisd/dict.c, revision 1.1
1.1 ! misho 1: /*
! 2: * Dictionary Abstract Data Type
! 3: * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
! 4: *
! 5: * Free Software License:
! 6: *
! 7: * All rights are reserved by the author, with the following exceptions:
! 8: * Permission is granted to freely reproduce and distribute this software,
! 9: * possibly in exchange for a fee, provided that this copyright notice appears
! 10: * intact. Permission is also granted to adapt this software to produce
! 11: * derivative works, as long as the modified versions carry this copyright
! 12: * notice and additional notices stating that the work has been modified.
! 13: * This source code may be translated into executable form and incorporated
! 14: * into proprietary software; there is no requirement for such software to
! 15: * contain a copyright notice related to this source.
! 16: */
! 17:
! 18: #include <stdlib.h>
! 19: #include <stddef.h>
! 20: #include "zebra.h"
! 21: #include "zassert.h"
! 22: #define DICT_IMPLEMENTATION
! 23: #include "dict.h"
! 24:
! 25: #ifdef KAZLIB_RCSID
! 26: static const char rcsid[] = "Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz";
! 27: #endif
! 28:
! 29: /*
! 30: * These macros provide short convenient names for structure members,
! 31: * which are embellished with dict_ prefixes so that they are
! 32: * properly confined to the documented namespace. It's legal for a
! 33: * program which uses dict to define, for instance, a macro called ``parent''.
! 34: * Such a macro would interfere with the dnode_t struct definition.
! 35: * In general, highly portable and reusable C modules which expose their
! 36: * structures need to confine structure member names to well-defined spaces.
! 37: * The resulting identifiers aren't necessarily convenient to use, nor
! 38: * readable, in the implementation, however!
! 39: */
! 40:
! 41: #define left dict_left
! 42: #define right dict_right
! 43: #define parent dict_parent
! 44: #define color dict_color
! 45: #define key dict_key
! 46: #define data dict_data
! 47:
! 48: #define nilnode dict_nilnode
! 49: #define nodecount dict_nodecount
! 50: #define maxcount dict_maxcount
! 51: #define compare dict_compare
! 52: #define allocnode dict_allocnode
! 53: #define freenode dict_freenode
! 54: #define context dict_context
! 55: #define dupes dict_dupes
! 56:
! 57: #define dictptr dict_dictptr
! 58:
! 59: #define dict_root(D) ((D)->nilnode.left)
! 60: #define dict_nil(D) (&(D)->nilnode)
! 61: #define DICT_DEPTH_MAX 64
! 62:
! 63: static dnode_t *dnode_alloc(void *context);
! 64: static void dnode_free(dnode_t *node, void *context);
! 65:
! 66: /*
! 67: * Perform a ``left rotation'' adjustment on the tree. The given node P and
! 68: * its right child C are rearranged so that the P instead becomes the left
! 69: * child of C. The left subtree of C is inherited as the new right subtree
! 70: * for P. The ordering of the keys within the tree is thus preserved.
! 71: */
! 72:
! 73: static void rotate_left(dnode_t *upper)
! 74: {
! 75: dnode_t *lower, *lowleft, *upparent;
! 76:
! 77: lower = upper->right;
! 78: upper->right = lowleft = lower->left;
! 79: lowleft->parent = upper;
! 80:
! 81: lower->parent = upparent = upper->parent;
! 82:
! 83: /* don't need to check for root node here because root->parent is
! 84: the sentinel nil node, and root->parent->left points back to root */
! 85:
! 86: if (upper == upparent->left) {
! 87: upparent->left = lower;
! 88: } else {
! 89: assert (upper == upparent->right);
! 90: upparent->right = lower;
! 91: }
! 92:
! 93: lower->left = upper;
! 94: upper->parent = lower;
! 95: }
! 96:
! 97: /*
! 98: * This operation is the ``mirror'' image of rotate_left. It is
! 99: * the same procedure, but with left and right interchanged.
! 100: */
! 101:
! 102: static void rotate_right(dnode_t *upper)
! 103: {
! 104: dnode_t *lower, *lowright, *upparent;
! 105:
! 106: lower = upper->left;
! 107: upper->left = lowright = lower->right;
! 108: lowright->parent = upper;
! 109:
! 110: lower->parent = upparent = upper->parent;
! 111:
! 112: if (upper == upparent->right) {
! 113: upparent->right = lower;
! 114: } else {
! 115: assert (upper == upparent->left);
! 116: upparent->left = lower;
! 117: }
! 118:
! 119: lower->right = upper;
! 120: upper->parent = lower;
! 121: }
! 122:
! 123: /*
! 124: * Do a postorder traversal of the tree rooted at the specified
! 125: * node and free everything under it. Used by dict_free().
! 126: */
! 127:
! 128: static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)
! 129: {
! 130: if (node == nil)
! 131: return;
! 132: free_nodes(dict, node->left, nil);
! 133: free_nodes(dict, node->right, nil);
! 134: dict->freenode(node, dict->context);
! 135: }
! 136:
! 137: /*
! 138: * This procedure performs a verification that the given subtree is a binary
! 139: * search tree. It performs an inorder traversal of the tree using the
! 140: * dict_next() successor function, verifying that the key of each node is
! 141: * strictly lower than that of its successor, if duplicates are not allowed,
! 142: * or lower or equal if duplicates are allowed. This function is used for
! 143: * debugging purposes.
! 144: */
! 145:
! 146: static int verify_bintree(dict_t *dict)
! 147: {
! 148: dnode_t *first, *next;
! 149:
! 150: first = dict_first(dict);
! 151:
! 152: if (dict->dupes) {
! 153: while (first && (next = dict_next(dict, first))) {
! 154: if (dict->compare(first->key, next->key) > 0)
! 155: return 0;
! 156: first = next;
! 157: }
! 158: } else {
! 159: while (first && (next = dict_next(dict, first))) {
! 160: if (dict->compare(first->key, next->key) >= 0)
! 161: return 0;
! 162: first = next;
! 163: }
! 164: }
! 165: return 1;
! 166: }
! 167:
! 168:
! 169: /*
! 170: * This function recursively verifies that the given binary subtree satisfies
! 171: * three of the red black properties. It checks that every red node has only
! 172: * black children. It makes sure that each node is either red or black. And it
! 173: * checks that every path has the same count of black nodes from root to leaf.
! 174: * It returns the blackheight of the given subtree; this allows blackheights to
! 175: * be computed recursively and compared for left and right siblings for
! 176: * mismatches. It does not check for every nil node being black, because there
! 177: * is only one sentinel nil node. The return value of this function is the
! 178: * black height of the subtree rooted at the node ``root'', or zero if the
! 179: * subtree is not red-black.
! 180: */
! 181:
! 182: static unsigned int verify_redblack(dnode_t *nil, dnode_t *root)
! 183: {
! 184: unsigned height_left, height_right;
! 185:
! 186: if (root != nil) {
! 187: height_left = verify_redblack(nil, root->left);
! 188: height_right = verify_redblack(nil, root->right);
! 189: if (height_left == 0 || height_right == 0)
! 190: return 0;
! 191: if (height_left != height_right)
! 192: return 0;
! 193: if (root->color == dnode_red) {
! 194: if (root->left->color != dnode_black)
! 195: return 0;
! 196: if (root->right->color != dnode_black)
! 197: return 0;
! 198: return height_left;
! 199: }
! 200: if (root->color != dnode_black)
! 201: return 0;
! 202: return height_left + 1;
! 203: }
! 204: return 1;
! 205: }
! 206:
! 207: /*
! 208: * Compute the actual count of nodes by traversing the tree and
! 209: * return it. This could be compared against the stored count to
! 210: * detect a mismatch.
! 211: */
! 212:
! 213: static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root)
! 214: {
! 215: if (root == nil)
! 216: return 0;
! 217: else
! 218: return 1 + verify_node_count(nil, root->left)
! 219: + verify_node_count(nil, root->right);
! 220: }
! 221:
! 222: /*
! 223: * Verify that the tree contains the given node. This is done by
! 224: * traversing all of the nodes and comparing their pointers to the
! 225: * given pointer. Returns 1 if the node is found, otherwise
! 226: * returns zero. It is intended for debugging purposes.
! 227: */
! 228:
! 229: static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node)
! 230: {
! 231: if (root != nil) {
! 232: return root == node
! 233: || verify_dict_has_node(nil, root->left, node)
! 234: || verify_dict_has_node(nil, root->right, node);
! 235: }
! 236: return 0;
! 237: }
! 238:
! 239:
! 240: /*
! 241: * Dynamically allocate and initialize a dictionary object.
! 242: */
! 243:
! 244: dict_t *dict_create(dictcount_t maxcount, dict_comp_t comp)
! 245: {
! 246: dict_t *new = malloc(sizeof *new);
! 247:
! 248: if (new) {
! 249: new->compare = comp;
! 250: new->allocnode = dnode_alloc;
! 251: new->freenode = dnode_free;
! 252: new->context = NULL;
! 253: new->nodecount = 0;
! 254: new->maxcount = maxcount;
! 255: new->nilnode.left = &new->nilnode;
! 256: new->nilnode.right = &new->nilnode;
! 257: new->nilnode.parent = &new->nilnode;
! 258: new->nilnode.color = dnode_black;
! 259: new->dupes = 0;
! 260: }
! 261: return new;
! 262: }
! 263:
! 264: /*
! 265: * Select a different set of node allocator routines.
! 266: */
! 267:
! 268: void dict_set_allocator(dict_t *dict, dnode_alloc_t al,
! 269: dnode_free_t fr, void *context)
! 270: {
! 271: assert (dict_count(dict) == 0);
! 272: assert ((al == NULL && fr == NULL) || (al != NULL && fr != NULL));
! 273:
! 274: dict->allocnode = al ? al : dnode_alloc;
! 275: dict->freenode = fr ? fr : dnode_free;
! 276: dict->context = context;
! 277: }
! 278:
! 279: /*
! 280: * Free a dynamically allocated dictionary object. Removing the nodes
! 281: * from the tree before deleting it is required.
! 282: */
! 283:
! 284: void dict_destroy(dict_t *dict)
! 285: {
! 286: assert (dict_isempty(dict));
! 287: free(dict);
! 288: }
! 289:
! 290: /*
! 291: * Free all the nodes in the dictionary by using the dictionary's
! 292: * installed free routine. The dictionary is emptied.
! 293: */
! 294:
! 295: void dict_free_nodes(dict_t *dict)
! 296: {
! 297: dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
! 298: free_nodes(dict, root, nil);
! 299: dict->nodecount = 0;
! 300: dict->nilnode.left = &dict->nilnode;
! 301: dict->nilnode.right = &dict->nilnode;
! 302: }
! 303:
! 304: /*
! 305: * Obsolescent function, equivalent to dict_free_nodes
! 306: */
! 307:
! 308: void dict_free(dict_t *dict)
! 309: {
! 310: #ifdef KAZLIB_OBSOLESCENT_DEBUG
! 311: assert ("call to obsolescent function dict_free()" && 0);
! 312: #endif
! 313: dict_free_nodes(dict);
! 314: }
! 315:
! 316: /*
! 317: * Initialize a user-supplied dictionary object.
! 318: */
! 319:
! 320: dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp)
! 321: {
! 322: dict->compare = comp;
! 323: dict->allocnode = dnode_alloc;
! 324: dict->freenode = dnode_free;
! 325: dict->context = NULL;
! 326: dict->nodecount = 0;
! 327: dict->maxcount = maxcount;
! 328: dict->nilnode.left = &dict->nilnode;
! 329: dict->nilnode.right = &dict->nilnode;
! 330: dict->nilnode.parent = &dict->nilnode;
! 331: dict->nilnode.color = dnode_black;
! 332: dict->dupes = 0;
! 333: return dict;
! 334: }
! 335:
! 336: /*
! 337: * Initialize a dictionary in the likeness of another dictionary
! 338: */
! 339:
! 340: void dict_init_like(dict_t *dict, const dict_t *template)
! 341: {
! 342: dict->compare = template->compare;
! 343: dict->allocnode = template->allocnode;
! 344: dict->freenode = template->freenode;
! 345: dict->context = template->context;
! 346: dict->nodecount = 0;
! 347: dict->maxcount = template->maxcount;
! 348: dict->nilnode.left = &dict->nilnode;
! 349: dict->nilnode.right = &dict->nilnode;
! 350: dict->nilnode.parent = &dict->nilnode;
! 351: dict->nilnode.color = dnode_black;
! 352: dict->dupes = template->dupes;
! 353:
! 354: assert (dict_similar(dict, template));
! 355: }
! 356:
! 357: /*
! 358: * Remove all nodes from the dictionary (without freeing them in any way).
! 359: */
! 360:
! 361: static void dict_clear(dict_t *dict)
! 362: {
! 363: dict->nodecount = 0;
! 364: dict->nilnode.left = &dict->nilnode;
! 365: dict->nilnode.right = &dict->nilnode;
! 366: dict->nilnode.parent = &dict->nilnode;
! 367: assert (dict->nilnode.color == dnode_black);
! 368: }
! 369:
! 370:
! 371: /*
! 372: * Verify the integrity of the dictionary structure. This is provided for
! 373: * debugging purposes, and should be placed in assert statements. Just because
! 374: * this function succeeds doesn't mean that the tree is not corrupt. Certain
! 375: * corruptions in the tree may simply cause undefined behavior.
! 376: */
! 377:
! 378: int dict_verify(dict_t *dict)
! 379: {
! 380: dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
! 381:
! 382: /* check that the sentinel node and root node are black */
! 383: if (root->color != dnode_black)
! 384: return 0;
! 385: if (nil->color != dnode_black)
! 386: return 0;
! 387: if (nil->right != nil)
! 388: return 0;
! 389: /* nil->left is the root node; check that its parent pointer is nil */
! 390: if (nil->left->parent != nil)
! 391: return 0;
! 392: /* perform a weak test that the tree is a binary search tree */
! 393: if (!verify_bintree(dict))
! 394: return 0;
! 395: /* verify that the tree is a red-black tree */
! 396: if (!verify_redblack(nil, root))
! 397: return 0;
! 398: if (verify_node_count(nil, root) != dict_count(dict))
! 399: return 0;
! 400: return 1;
! 401: }
! 402:
! 403: /*
! 404: * Determine whether two dictionaries are similar: have the same comparison and
! 405: * allocator functions, and same status as to whether duplicates are allowed.
! 406: */
! 407:
! 408: int dict_similar(const dict_t *left, const dict_t *right)
! 409: {
! 410: if (left->compare != right->compare)
! 411: return 0;
! 412:
! 413: if (left->allocnode != right->allocnode)
! 414: return 0;
! 415:
! 416: if (left->freenode != right->freenode)
! 417: return 0;
! 418:
! 419: if (left->context != right->context)
! 420: return 0;
! 421:
! 422: if (left->dupes != right->dupes)
! 423: return 0;
! 424:
! 425: return 1;
! 426: }
! 427:
! 428: /*
! 429: * Locate a node in the dictionary having the given key.
! 430: * If the node is not found, a null a pointer is returned (rather than
! 431: * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
! 432: * located node is returned.
! 433: */
! 434:
! 435: dnode_t *dict_lookup(dict_t *dict, const void *key)
! 436: {
! 437: dnode_t *root = dict_root(dict);
! 438: dnode_t *nil = dict_nil(dict);
! 439: dnode_t *saved;
! 440: int result;
! 441:
! 442: /* simple binary search adapted for trees that contain duplicate keys */
! 443:
! 444: while (root != nil) {
! 445: result = dict->compare(key, root->key);
! 446: if (result < 0)
! 447: root = root->left;
! 448: else if (result > 0)
! 449: root = root->right;
! 450: else {
! 451: if (!dict->dupes) { /* no duplicates, return match */
! 452: return root;
! 453: } else { /* could be dupes, find leftmost one */
! 454: do {
! 455: saved = root;
! 456: root = root->left;
! 457: while (root != nil && dict->compare(key, root->key))
! 458: root = root->right;
! 459: } while (root != nil);
! 460: return saved;
! 461: }
! 462: }
! 463: }
! 464:
! 465: return NULL;
! 466: }
! 467:
! 468: /*
! 469: * Look for the node corresponding to the lowest key that is equal to or
! 470: * greater than the given key. If there is no such node, return null.
! 471: */
! 472:
! 473: dnode_t *dict_lower_bound(dict_t *dict, const void *key)
! 474: {
! 475: dnode_t *root = dict_root(dict);
! 476: dnode_t *nil = dict_nil(dict);
! 477: dnode_t *tentative = 0;
! 478:
! 479: while (root != nil) {
! 480: int result = dict->compare(key, root->key);
! 481:
! 482: if (result > 0) {
! 483: root = root->right;
! 484: } else if (result < 0) {
! 485: tentative = root;
! 486: root = root->left;
! 487: } else {
! 488: if (!dict->dupes) {
! 489: return root;
! 490: } else {
! 491: tentative = root;
! 492: root = root->left;
! 493: }
! 494: }
! 495: }
! 496:
! 497: return tentative;
! 498: }
! 499:
! 500: /*
! 501: * Look for the node corresponding to the greatest key that is equal to or
! 502: * lower than the given key. If there is no such node, return null.
! 503: */
! 504:
! 505: dnode_t *dict_upper_bound(dict_t *dict, const void *key)
! 506: {
! 507: dnode_t *root = dict_root(dict);
! 508: dnode_t *nil = dict_nil(dict);
! 509: dnode_t *tentative = 0;
! 510:
! 511: while (root != nil) {
! 512: int result = dict->compare(key, root->key);
! 513:
! 514: if (result < 0) {
! 515: root = root->left;
! 516: } else if (result > 0) {
! 517: tentative = root;
! 518: root = root->right;
! 519: } else {
! 520: if (!dict->dupes) {
! 521: return root;
! 522: } else {
! 523: tentative = root;
! 524: root = root->right;
! 525: }
! 526: }
! 527: }
! 528:
! 529: return tentative;
! 530: }
! 531:
! 532: /*
! 533: * Insert a node into the dictionary. The node should have been
! 534: * initialized with a data field. All other fields are ignored.
! 535: * The behavior is undefined if the user attempts to insert into
! 536: * a dictionary that is already full (for which the dict_isfull()
! 537: * function returns true).
! 538: */
! 539:
! 540: void dict_insert(dict_t *dict, dnode_t *node, const void *key)
! 541: {
! 542: dnode_t *where = dict_root(dict), *nil = dict_nil(dict);
! 543: dnode_t *parent = nil, *uncle, *grandpa;
! 544: int result = -1;
! 545:
! 546: node->key = key;
! 547:
! 548: assert (!dict_isfull(dict));
! 549: assert (!dict_contains(dict, node));
! 550: assert (!dnode_is_in_a_dict(node));
! 551:
! 552: /* basic binary tree insert */
! 553:
! 554: while (where != nil) {
! 555: parent = where;
! 556: result = dict->compare(key, where->key);
! 557: /* trap attempts at duplicate key insertion unless it's explicitly allowed */
! 558: assert (dict->dupes || result != 0);
! 559: if (result < 0)
! 560: where = where->left;
! 561: else
! 562: where = where->right;
! 563: }
! 564:
! 565: assert (where == nil);
! 566:
! 567: if (result < 0)
! 568: parent->left = node;
! 569: else
! 570: parent->right = node;
! 571:
! 572: node->parent = parent;
! 573: node->left = nil;
! 574: node->right = nil;
! 575:
! 576: dict->nodecount++;
! 577:
! 578: /* red black adjustments */
! 579:
! 580: node->color = dnode_red;
! 581:
! 582: while (parent->color == dnode_red) {
! 583: grandpa = parent->parent;
! 584: if (parent == grandpa->left) {
! 585: uncle = grandpa->right;
! 586: if (uncle->color == dnode_red) { /* red parent, red uncle */
! 587: parent->color = dnode_black;
! 588: uncle->color = dnode_black;
! 589: grandpa->color = dnode_red;
! 590: node = grandpa;
! 591: parent = grandpa->parent;
! 592: } else { /* red parent, black uncle */
! 593: if (node == parent->right) {
! 594: rotate_left(parent);
! 595: parent = node;
! 596: assert (grandpa == parent->parent);
! 597: /* rotation between parent and child preserves grandpa */
! 598: }
! 599: parent->color = dnode_black;
! 600: grandpa->color = dnode_red;
! 601: rotate_right(grandpa);
! 602: break;
! 603: }
! 604: } else { /* symmetric cases: parent == parent->parent->right */
! 605: uncle = grandpa->left;
! 606: if (uncle->color == dnode_red) {
! 607: parent->color = dnode_black;
! 608: uncle->color = dnode_black;
! 609: grandpa->color = dnode_red;
! 610: node = grandpa;
! 611: parent = grandpa->parent;
! 612: } else {
! 613: if (node == parent->left) {
! 614: rotate_right(parent);
! 615: parent = node;
! 616: assert (grandpa == parent->parent);
! 617: }
! 618: parent->color = dnode_black;
! 619: grandpa->color = dnode_red;
! 620: rotate_left(grandpa);
! 621: break;
! 622: }
! 623: }
! 624: }
! 625:
! 626: dict_root(dict)->color = dnode_black;
! 627:
! 628: assert (dict_verify(dict));
! 629: }
! 630:
! 631: /*
! 632: * Delete the given node from the dictionary. If the given node does not belong
! 633: * to the given dictionary, undefined behavior results. A pointer to the
! 634: * deleted node is returned.
! 635: */
! 636:
! 637: dnode_t *dict_delete(dict_t *dict, dnode_t *delete)
! 638: {
! 639: dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;
! 640:
! 641: /* basic deletion */
! 642:
! 643: assert (!dict_isempty(dict));
! 644: assert (dict_contains(dict, delete));
! 645:
! 646: /*
! 647: * If the node being deleted has two children, then we replace it with its
! 648: * successor (i.e. the leftmost node in the right subtree.) By doing this,
! 649: * we avoid the traditional algorithm under which the successor's key and
! 650: * value *only* move to the deleted node and the successor is spliced out
! 651: * from the tree. We cannot use this approach because the user may hold
! 652: * pointers to the successor, or nodes may be inextricably tied to some
! 653: * other structures by way of embedding, etc. So we must splice out the
! 654: * node we are given, not some other node, and must not move contents from
! 655: * one node to another behind the user's back.
! 656: */
! 657:
! 658: if (delete->left != nil && delete->right != nil) {
! 659: dnode_t *next = dict_next(dict, delete);
! 660: dnode_t *nextparent = next->parent;
! 661: dnode_color_t nextcolor = next->color;
! 662:
! 663: assert (next != nil);
! 664: assert (next->parent != nil);
! 665: assert (next->left == nil);
! 666:
! 667: /*
! 668: * First, splice out the successor from the tree completely, by
! 669: * moving up its right child into its place.
! 670: */
! 671:
! 672: child = next->right;
! 673: child->parent = nextparent;
! 674:
! 675: if (nextparent->left == next) {
! 676: nextparent->left = child;
! 677: } else {
! 678: assert (nextparent->right == next);
! 679: nextparent->right = child;
! 680: }
! 681:
! 682: /*
! 683: * Now that the successor has been extricated from the tree, install it
! 684: * in place of the node that we want deleted.
! 685: */
! 686:
! 687: next->parent = delparent;
! 688: next->left = delete->left;
! 689: next->right = delete->right;
! 690: next->left->parent = next;
! 691: next->right->parent = next;
! 692: next->color = delete->color;
! 693: delete->color = nextcolor;
! 694:
! 695: if (delparent->left == delete) {
! 696: delparent->left = next;
! 697: } else {
! 698: assert (delparent->right == delete);
! 699: delparent->right = next;
! 700: }
! 701:
! 702: } else {
! 703: assert (delete != nil);
! 704: assert (delete->left == nil || delete->right == nil);
! 705:
! 706: child = (delete->left != nil) ? delete->left : delete->right;
! 707:
! 708: child->parent = delparent = delete->parent;
! 709:
! 710: if (delete == delparent->left) {
! 711: delparent->left = child;
! 712: } else {
! 713: assert (delete == delparent->right);
! 714: delparent->right = child;
! 715: }
! 716: }
! 717:
! 718: delete->parent = NULL;
! 719: delete->right = NULL;
! 720: delete->left = NULL;
! 721:
! 722: dict->nodecount--;
! 723:
! 724: assert (verify_bintree(dict));
! 725:
! 726: /* red-black adjustments */
! 727:
! 728: if (delete->color == dnode_black) {
! 729: dnode_t *parent, *sister;
! 730:
! 731: dict_root(dict)->color = dnode_red;
! 732:
! 733: while (child->color == dnode_black) {
! 734: parent = child->parent;
! 735: if (child == parent->left) {
! 736: sister = parent->right;
! 737: assert (sister != nil);
! 738: if (sister->color == dnode_red) {
! 739: sister->color = dnode_black;
! 740: parent->color = dnode_red;
! 741: rotate_left(parent);
! 742: sister = parent->right;
! 743: assert (sister != nil);
! 744: }
! 745: if (sister->left->color == dnode_black
! 746: && sister->right->color == dnode_black) {
! 747: sister->color = dnode_red;
! 748: child = parent;
! 749: } else {
! 750: if (sister->right->color == dnode_black) {
! 751: assert (sister->left->color == dnode_red);
! 752: sister->left->color = dnode_black;
! 753: sister->color = dnode_red;
! 754: rotate_right(sister);
! 755: sister = parent->right;
! 756: assert (sister != nil);
! 757: }
! 758: sister->color = parent->color;
! 759: sister->right->color = dnode_black;
! 760: parent->color = dnode_black;
! 761: rotate_left(parent);
! 762: break;
! 763: }
! 764: } else { /* symmetric case: child == child->parent->right */
! 765: assert (child == parent->right);
! 766: sister = parent->left;
! 767: assert (sister != nil);
! 768: if (sister->color == dnode_red) {
! 769: sister->color = dnode_black;
! 770: parent->color = dnode_red;
! 771: rotate_right(parent);
! 772: sister = parent->left;
! 773: assert (sister != nil);
! 774: }
! 775: if (sister->right->color == dnode_black
! 776: && sister->left->color == dnode_black) {
! 777: sister->color = dnode_red;
! 778: child = parent;
! 779: } else {
! 780: if (sister->left->color == dnode_black) {
! 781: assert (sister->right->color == dnode_red);
! 782: sister->right->color = dnode_black;
! 783: sister->color = dnode_red;
! 784: rotate_left(sister);
! 785: sister = parent->left;
! 786: assert (sister != nil);
! 787: }
! 788: sister->color = parent->color;
! 789: sister->left->color = dnode_black;
! 790: parent->color = dnode_black;
! 791: rotate_right(parent);
! 792: break;
! 793: }
! 794: }
! 795: }
! 796:
! 797: child->color = dnode_black;
! 798: dict_root(dict)->color = dnode_black;
! 799: }
! 800:
! 801: assert (dict_verify(dict));
! 802:
! 803: return delete;
! 804: }
! 805:
! 806: /*
! 807: * Allocate a node using the dictionary's allocator routine, give it
! 808: * the data item.
! 809: */
! 810:
! 811: int dict_alloc_insert(dict_t *dict, const void *key, void *data)
! 812: {
! 813: dnode_t *node = dict->allocnode(dict->context);
! 814:
! 815: if (node) {
! 816: dnode_init(node, data);
! 817: dict_insert(dict, node, key);
! 818: return 1;
! 819: }
! 820: return 0;
! 821: }
! 822:
! 823: void dict_delete_free(dict_t *dict, dnode_t *node)
! 824: {
! 825: dict_delete(dict, node);
! 826: dict->freenode(node, dict->context);
! 827: }
! 828:
! 829: /*
! 830: * Return the node with the lowest (leftmost) key. If the dictionary is empty
! 831: * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
! 832: */
! 833:
! 834: dnode_t *dict_first(dict_t *dict)
! 835: {
! 836: dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
! 837:
! 838: if (root != nil)
! 839: while ((left = root->left) != nil)
! 840: root = left;
! 841:
! 842: return (root == nil) ? NULL : root;
! 843: }
! 844:
! 845: /*
! 846: * Return the node with the highest (rightmost) key. If the dictionary is empty
! 847: * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
! 848: */
! 849:
! 850: dnode_t *dict_last(dict_t *dict)
! 851: {
! 852: dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;
! 853:
! 854: if (root != nil)
! 855: while ((right = root->right) != nil)
! 856: root = right;
! 857:
! 858: return (root == nil) ? NULL : root;
! 859: }
! 860:
! 861: /*
! 862: * Return the given node's successor node---the node which has the
! 863: * next key in the the left to right ordering. If the node has
! 864: * no successor, a null pointer is returned rather than a pointer to
! 865: * the nil node.
! 866: */
! 867:
! 868: dnode_t *dict_next(dict_t *dict, dnode_t *curr)
! 869: {
! 870: dnode_t *nil = dict_nil(dict), *parent, *left;
! 871:
! 872: if (curr->right != nil) {
! 873: curr = curr->right;
! 874: while ((left = curr->left) != nil)
! 875: curr = left;
! 876: return curr;
! 877: }
! 878:
! 879: parent = curr->parent;
! 880:
! 881: while (parent != nil && curr == parent->right) {
! 882: curr = parent;
! 883: parent = curr->parent;
! 884: }
! 885:
! 886: return (parent == nil) ? NULL : parent;
! 887: }
! 888:
! 889: /*
! 890: * Return the given node's predecessor, in the key order.
! 891: * The nil sentinel node is returned if there is no predecessor.
! 892: */
! 893:
! 894: dnode_t *dict_prev(dict_t *dict, dnode_t *curr)
! 895: {
! 896: dnode_t *nil = dict_nil(dict), *parent, *right;
! 897:
! 898: if (curr->left != nil) {
! 899: curr = curr->left;
! 900: while ((right = curr->right) != nil)
! 901: curr = right;
! 902: return curr;
! 903: }
! 904:
! 905: parent = curr->parent;
! 906:
! 907: while (parent != nil && curr == parent->left) {
! 908: curr = parent;
! 909: parent = curr->parent;
! 910: }
! 911:
! 912: return (parent == nil) ? NULL : parent;
! 913: }
! 914:
! 915: void dict_allow_dupes(dict_t *dict)
! 916: {
! 917: dict->dupes = 1;
! 918: }
! 919:
! 920: #undef dict_count
! 921: #undef dict_isempty
! 922: #undef dict_isfull
! 923: #undef dnode_get
! 924: #undef dnode_put
! 925: #undef dnode_getkey
! 926:
! 927: dictcount_t dict_count(dict_t *dict)
! 928: {
! 929: return dict->nodecount;
! 930: }
! 931:
! 932: int dict_isempty(dict_t *dict)
! 933: {
! 934: return dict->nodecount == 0;
! 935: }
! 936:
! 937: int dict_isfull(dict_t *dict)
! 938: {
! 939: return dict->nodecount == dict->maxcount;
! 940: }
! 941:
! 942: int dict_contains(dict_t *dict, dnode_t *node)
! 943: {
! 944: return verify_dict_has_node(dict_nil(dict), dict_root(dict), node);
! 945: }
! 946:
! 947: static dnode_t *dnode_alloc(void *context)
! 948: {
! 949: return malloc(sizeof *dnode_alloc(NULL));
! 950: }
! 951:
! 952: static void dnode_free(dnode_t *node, void *context)
! 953: {
! 954: free(node);
! 955: }
! 956:
! 957: dnode_t *dnode_create(void *data)
! 958: {
! 959: dnode_t *new = malloc(sizeof *new);
! 960: if (new) {
! 961: new->data = data;
! 962: new->parent = NULL;
! 963: new->left = NULL;
! 964: new->right = NULL;
! 965: }
! 966: return new;
! 967: }
! 968:
! 969: dnode_t *dnode_init(dnode_t *dnode, void *data)
! 970: {
! 971: dnode->data = data;
! 972: dnode->parent = NULL;
! 973: dnode->left = NULL;
! 974: dnode->right = NULL;
! 975: return dnode;
! 976: }
! 977:
! 978: void dnode_destroy(dnode_t *dnode)
! 979: {
! 980: assert (!dnode_is_in_a_dict(dnode));
! 981: free(dnode);
! 982: }
! 983:
! 984: void *dnode_get(dnode_t *dnode)
! 985: {
! 986: return dnode->data;
! 987: }
! 988:
! 989: const void *dnode_getkey(dnode_t *dnode)
! 990: {
! 991: return dnode->key;
! 992: }
! 993:
! 994: void dnode_put(dnode_t *dnode, void *data)
! 995: {
! 996: dnode->data = data;
! 997: }
! 998:
! 999: int dnode_is_in_a_dict(dnode_t *dnode)
! 1000: {
! 1001: return (dnode->parent && dnode->left && dnode->right);
! 1002: }
! 1003:
! 1004: void dict_process(dict_t *dict, void *context, dnode_process_t function)
! 1005: {
! 1006: dnode_t *node = dict_first(dict), *next;
! 1007:
! 1008: while (node != NULL) {
! 1009: /* check for callback function deleting */
! 1010: /* the next node from under us */
! 1011: assert (dict_contains(dict, node));
! 1012: next = dict_next(dict, node);
! 1013: function(dict, node, context);
! 1014: node = next;
! 1015: }
! 1016: }
! 1017:
! 1018: static void load_begin_internal(dict_load_t *load, dict_t *dict)
! 1019: {
! 1020: load->dictptr = dict;
! 1021: load->nilnode.left = &load->nilnode;
! 1022: load->nilnode.right = &load->nilnode;
! 1023: }
! 1024:
! 1025: void dict_load_begin(dict_load_t *load, dict_t *dict)
! 1026: {
! 1027: assert (dict_isempty(dict));
! 1028: load_begin_internal(load, dict);
! 1029: }
! 1030:
! 1031: void dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key)
! 1032: {
! 1033: dict_t *dict = load->dictptr;
! 1034: dnode_t *nil = &load->nilnode;
! 1035:
! 1036: assert (!dnode_is_in_a_dict(newnode));
! 1037: assert (dict->nodecount < dict->maxcount);
! 1038:
! 1039: #ifndef NDEBUG
! 1040: if (dict->nodecount > 0) {
! 1041: if (dict->dupes)
! 1042: assert (dict->compare(nil->left->key, key) <= 0);
! 1043: else
! 1044: assert (dict->compare(nil->left->key, key) < 0);
! 1045: }
! 1046: #endif
! 1047:
! 1048: newnode->key = key;
! 1049: nil->right->left = newnode;
! 1050: nil->right = newnode;
! 1051: newnode->left = nil;
! 1052: dict->nodecount++;
! 1053: }
! 1054:
! 1055: void dict_load_end(dict_load_t *load)
! 1056: {
! 1057: dict_t *dict = load->dictptr;
! 1058: dnode_t *tree[DICT_DEPTH_MAX] = { 0 };
! 1059: dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next;
! 1060: dnode_t *complete = 0;
! 1061: dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount;
! 1062: dictcount_t botrowcount;
! 1063: unsigned baselevel = 0, level = 0, i;
! 1064:
! 1065: assert (dnode_red == 0 && dnode_black == 1);
! 1066:
! 1067: while (fullcount >= nodecount && fullcount)
! 1068: fullcount >>= 1;
! 1069:
! 1070: botrowcount = nodecount - fullcount;
! 1071:
! 1072: for (curr = loadnil->left; curr != loadnil; curr = next) {
! 1073: next = curr->left;
! 1074:
! 1075: if (complete == NULL && botrowcount-- == 0) {
! 1076: assert (baselevel == 0);
! 1077: assert (level == 0);
! 1078: baselevel = level = 1;
! 1079: complete = tree[0];
! 1080:
! 1081: if (complete != 0) {
! 1082: tree[0] = 0;
! 1083: complete->right = dictnil;
! 1084: while (tree[level] != 0) {
! 1085: tree[level]->right = complete;
! 1086: complete->parent = tree[level];
! 1087: complete = tree[level];
! 1088: tree[level++] = 0;
! 1089: }
! 1090: }
! 1091: }
! 1092:
! 1093: if (complete == NULL) {
! 1094: curr->left = dictnil;
! 1095: curr->right = dictnil;
! 1096: curr->color = level % 2;
! 1097: complete = curr;
! 1098:
! 1099: assert (level == baselevel);
! 1100: while (tree[level] != 0) {
! 1101: tree[level]->right = complete;
! 1102: complete->parent = tree[level];
! 1103: complete = tree[level];
! 1104: tree[level++] = 0;
! 1105: }
! 1106: } else {
! 1107: curr->left = complete;
! 1108: curr->color = (level + 1) % 2;
! 1109: complete->parent = curr;
! 1110: tree[level] = curr;
! 1111: complete = 0;
! 1112: level = baselevel;
! 1113: }
! 1114: }
! 1115:
! 1116: if (complete == NULL)
! 1117: complete = dictnil;
! 1118:
! 1119: for (i = 0; i < DICT_DEPTH_MAX; i++) {
! 1120: if (tree[i] != 0) {
! 1121: tree[i]->right = complete;
! 1122: complete->parent = tree[i];
! 1123: complete = tree[i];
! 1124: }
! 1125: }
! 1126:
! 1127: dictnil->color = dnode_black;
! 1128: dictnil->right = dictnil;
! 1129: complete->parent = dictnil;
! 1130: complete->color = dnode_black;
! 1131: dict_root(dict) = complete;
! 1132:
! 1133: assert (dict_verify(dict));
! 1134: }
! 1135:
! 1136: void dict_merge(dict_t *dest, dict_t *source)
! 1137: {
! 1138: dict_load_t load;
! 1139: dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source);
! 1140:
! 1141: assert (dict_similar(dest, source));
! 1142:
! 1143: if (source == dest)
! 1144: return;
! 1145:
! 1146: dest->nodecount = 0;
! 1147: load_begin_internal(&load, dest);
! 1148:
! 1149: for (;;) {
! 1150: if (leftnode != NULL && rightnode != NULL) {
! 1151: if (dest->compare(leftnode->key, rightnode->key) < 0)
! 1152: goto copyleft;
! 1153: else
! 1154: goto copyright;
! 1155: } else if (leftnode != NULL) {
! 1156: goto copyleft;
! 1157: } else if (rightnode != NULL) {
! 1158: goto copyright;
! 1159: } else {
! 1160: assert (leftnode == NULL && rightnode == NULL);
! 1161: break;
! 1162: }
! 1163:
! 1164: copyleft:
! 1165: {
! 1166: dnode_t *next = dict_next(dest, leftnode);
! 1167: #ifndef NDEBUG
! 1168: leftnode->left = NULL; /* suppress assertion in dict_load_next */
! 1169: #endif
! 1170: dict_load_next(&load, leftnode, leftnode->key);
! 1171: leftnode = next;
! 1172: continue;
! 1173: }
! 1174:
! 1175: copyright:
! 1176: {
! 1177: dnode_t *next = dict_next(source, rightnode);
! 1178: #ifndef NDEBUG
! 1179: rightnode->left = NULL;
! 1180: #endif
! 1181: dict_load_next(&load, rightnode, rightnode->key);
! 1182: rightnode = next;
! 1183: continue;
! 1184: }
! 1185: }
! 1186:
! 1187: dict_clear(source);
! 1188: dict_load_end(&load);
! 1189: }
! 1190:
! 1191: #ifdef KAZLIB_TEST_MAIN
! 1192:
! 1193: #include <stdio.h>
! 1194: #include <string.h>
! 1195: #include <ctype.h>
! 1196: #include <stdarg.h>
! 1197:
! 1198: typedef char input_t[256];
! 1199:
! 1200: static int tokenize(char *string, ...)
! 1201: {
! 1202: char **tokptr;
! 1203: va_list arglist;
! 1204: int tokcount = 0;
! 1205:
! 1206: va_start(arglist, string);
! 1207: tokptr = va_arg(arglist, char **);
! 1208: while (tokptr) {
! 1209: while (*string && isspace((unsigned char) *string))
! 1210: string++;
! 1211: if (!*string)
! 1212: break;
! 1213: *tokptr = string;
! 1214: while (*string && !isspace((unsigned char) *string))
! 1215: string++;
! 1216: tokptr = va_arg(arglist, char **);
! 1217: tokcount++;
! 1218: if (!*string)
! 1219: break;
! 1220: *string++ = 0;
! 1221: }
! 1222: va_end(arglist);
! 1223:
! 1224: return tokcount;
! 1225: }
! 1226:
! 1227: static int comparef(const void *key1, const void *key2)
! 1228: {
! 1229: return strcmp(key1, key2);
! 1230: }
! 1231:
! 1232: static char *dupstring(char *str)
! 1233: {
! 1234: int sz = strlen(str) + 1;
! 1235: char *new = malloc(sz);
! 1236: if (new)
! 1237: memcpy(new, str, sz);
! 1238: return new;
! 1239: }
! 1240:
! 1241: static dnode_t *new_node(void *c)
! 1242: {
! 1243: static dnode_t few[5];
! 1244: static int count;
! 1245:
! 1246: if (count < 5)
! 1247: return few + count++;
! 1248:
! 1249: return NULL;
! 1250: }
! 1251:
! 1252: static void del_node(dnode_t *n, void *c)
! 1253: {
! 1254: }
! 1255:
! 1256: static int prompt = 0;
! 1257:
! 1258: static void construct(dict_t *d)
! 1259: {
! 1260: input_t in;
! 1261: int done = 0;
! 1262: dict_load_t dl;
! 1263: dnode_t *dn;
! 1264: char *tok1, *tok2, *val;
! 1265: const char *key;
! 1266: char *help =
! 1267: "p turn prompt on\n"
! 1268: "q finish construction\n"
! 1269: "a <key> <val> add new entry\n";
! 1270:
! 1271: if (!dict_isempty(d))
! 1272: puts("warning: dictionary not empty!");
! 1273:
! 1274: dict_load_begin(&dl, d);
! 1275:
! 1276: while (!done) {
! 1277: if (prompt)
! 1278: putchar('>');
! 1279: fflush(stdout);
! 1280:
! 1281: if (!fgets(in, sizeof(input_t), stdin))
! 1282: break;
! 1283:
! 1284: switch (in[0]) {
! 1285: case '?':
! 1286: puts(help);
! 1287: break;
! 1288: case 'p':
! 1289: prompt = 1;
! 1290: break;
! 1291: case 'q':
! 1292: done = 1;
! 1293: break;
! 1294: case 'a':
! 1295: if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
! 1296: puts("what?");
! 1297: break;
! 1298: }
! 1299: key = dupstring(tok1);
! 1300: val = dupstring(tok2);
! 1301: dn = dnode_create(val);
! 1302:
! 1303: if (!key || !val || !dn) {
! 1304: puts("out of memory");
! 1305: free((void *) key);
! 1306: free(val);
! 1307: if (dn)
! 1308: dnode_destroy(dn);
! 1309: }
! 1310:
! 1311: dict_load_next(&dl, dn, key);
! 1312: break;
! 1313: default:
! 1314: putchar('?');
! 1315: putchar('\n');
! 1316: break;
! 1317: }
! 1318: }
! 1319:
! 1320: dict_load_end(&dl);
! 1321: }
! 1322:
! 1323: int main(void)
! 1324: {
! 1325: input_t in;
! 1326: dict_t darray[10];
! 1327: dict_t *d = &darray[0];
! 1328: dnode_t *dn;
! 1329: int i;
! 1330: char *tok1, *tok2, *val;
! 1331: const char *key;
! 1332:
! 1333: char *help =
! 1334: "a <key> <val> add value to dictionary\n"
! 1335: "d <key> delete value from dictionary\n"
! 1336: "l <key> lookup value in dictionary\n"
! 1337: "( <key> lookup lower bound\n"
! 1338: ") <key> lookup upper bound\n"
! 1339: "# <num> switch to alternate dictionary (0-9)\n"
! 1340: "j <num> <num> merge two dictionaries\n"
! 1341: "f free the whole dictionary\n"
! 1342: "k allow duplicate keys\n"
! 1343: "c show number of entries\n"
! 1344: "t dump whole dictionary in sort order\n"
! 1345: "m make dictionary out of sorted items\n"
! 1346: "p turn prompt on\n"
! 1347: "s switch to non-functioning allocator\n"
! 1348: "q quit";
! 1349:
! 1350: for (i = 0; i < sizeof darray / sizeof *darray; i++)
! 1351: dict_init(&darray[i], DICTCOUNT_T_MAX, comparef);
! 1352:
! 1353: for (;;) {
! 1354: if (prompt)
! 1355: putchar('>');
! 1356: fflush(stdout);
! 1357:
! 1358: if (!fgets(in, sizeof(input_t), stdin))
! 1359: break;
! 1360:
! 1361: switch(in[0]) {
! 1362: case '?':
! 1363: puts(help);
! 1364: break;
! 1365: case 'a':
! 1366: if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
! 1367: puts("what?");
! 1368: break;
! 1369: }
! 1370: key = dupstring(tok1);
! 1371: val = dupstring(tok2);
! 1372:
! 1373: if (!key || !val) {
! 1374: puts("out of memory");
! 1375: free((void *) key);
! 1376: free(val);
! 1377: }
! 1378:
! 1379: if (!dict_alloc_insert(d, key, val)) {
! 1380: puts("dict_alloc_insert failed");
! 1381: free((void *) key);
! 1382: free(val);
! 1383: break;
! 1384: }
! 1385: break;
! 1386: case 'd':
! 1387: if (tokenize(in+1, &tok1, (char **) 0) != 1) {
! 1388: puts("what?");
! 1389: break;
! 1390: }
! 1391: dn = dict_lookup(d, tok1);
! 1392: if (!dn) {
! 1393: puts("dict_lookup failed");
! 1394: break;
! 1395: }
! 1396: val = dnode_get(dn);
! 1397: key = dnode_getkey(dn);
! 1398: dict_delete_free(d, dn);
! 1399:
! 1400: free(val);
! 1401: free((void *) key);
! 1402: break;
! 1403: case 'f':
! 1404: dict_free(d);
! 1405: break;
! 1406: case 'l':
! 1407: case '(':
! 1408: case ')':
! 1409: if (tokenize(in+1, &tok1, (char **) 0) != 1) {
! 1410: puts("what?");
! 1411: break;
! 1412: }
! 1413: dn = 0;
! 1414: switch (in[0]) {
! 1415: case 'l':
! 1416: dn = dict_lookup(d, tok1);
! 1417: break;
! 1418: case '(':
! 1419: dn = dict_lower_bound(d, tok1);
! 1420: break;
! 1421: case ')':
! 1422: dn = dict_upper_bound(d, tok1);
! 1423: break;
! 1424: }
! 1425: if (!dn) {
! 1426: puts("lookup failed");
! 1427: break;
! 1428: }
! 1429: val = dnode_get(dn);
! 1430: puts(val);
! 1431: break;
! 1432: case 'm':
! 1433: construct(d);
! 1434: break;
! 1435: case 'k':
! 1436: dict_allow_dupes(d);
! 1437: break;
! 1438: case 'c':
! 1439: printf("%lu\n", (unsigned long) dict_count(d));
! 1440: break;
! 1441: case 't':
! 1442: for (dn = dict_first(d); dn; dn = dict_next(d, dn)) {
! 1443: printf("%s\t%s\n", (char *) dnode_getkey(dn),
! 1444: (char *) dnode_get(dn));
! 1445: }
! 1446: break;
! 1447: case 'q':
! 1448: exit(0);
! 1449: break;
! 1450: case '\0':
! 1451: break;
! 1452: case 'p':
! 1453: prompt = 1;
! 1454: break;
! 1455: case 's':
! 1456: dict_set_allocator(d, new_node, del_node, NULL);
! 1457: break;
! 1458: case '#':
! 1459: if (tokenize(in+1, &tok1, (char **) 0) != 1) {
! 1460: puts("what?");
! 1461: break;
! 1462: } else {
! 1463: int dictnum = atoi(tok1);
! 1464: if (dictnum < 0 || dictnum > 9) {
! 1465: puts("invalid number");
! 1466: break;
! 1467: }
! 1468: d = &darray[dictnum];
! 1469: }
! 1470: break;
! 1471: case 'j':
! 1472: if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
! 1473: puts("what?");
! 1474: break;
! 1475: } else {
! 1476: int dict1 = atoi(tok1), dict2 = atoi(tok2);
! 1477: if (dict1 < 0 || dict1 > 9 || dict2 < 0 || dict2 > 9) {
! 1478: puts("invalid number");
! 1479: break;
! 1480: }
! 1481: dict_merge(&darray[dict1], &darray[dict2]);
! 1482: }
! 1483: break;
! 1484: default:
! 1485: putchar('?');
! 1486: putchar('\n');
! 1487: break;
! 1488: }
! 1489: }
! 1490:
! 1491: return 0;
! 1492: }
! 1493:
! 1494: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to dict.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / isisd