dict.c 34 KB

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