dict.c 35 KB

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