1838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 2838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Dictionary Abstract Data Type 3838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net> 4838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * 5838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Free Software License: 6838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * 7838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * All rights are reserved by the author, with the following exceptions: 8838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Permission is granted to freely reproduce and distribute this software, 9838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * possibly in exchange for a fee, provided that this copyright notice appears 10838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * intact. Permission is also granted to adapt this software to produce 11838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * derivative works, as long as the modified versions carry this copyright 12838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * notice and additional notices stating that the work has been modified. 13838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * This source code may be translated into executable form and incorporated 14838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * into proprietary software; there is no requirement for such software to 15838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * contain a copyright notice related to this source. 16838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * 17838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * $Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $ 18838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * $Name: kazlib_1_20 $ 19838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 20838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 21c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#define DICT_NODEBUG 22838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 23544349270e4c74a6feb971123884a8cf5052a7eeTheodore Ts'o#ifdef __GNUC__ 24544349270e4c74a6feb971123884a8cf5052a7eeTheodore Ts'o#define EXT2FS_ATTR(x) __attribute__(x) 25544349270e4c74a6feb971123884a8cf5052a7eeTheodore Ts'o#else 26544349270e4c74a6feb971123884a8cf5052a7eeTheodore Ts'o#define EXT2FS_ATTR(x) 27544349270e4c74a6feb971123884a8cf5052a7eeTheodore Ts'o#endif 28544349270e4c74a6feb971123884a8cf5052a7eeTheodore Ts'o 29d1154eb460efe588eaed3d439c1caaca149fa362Theodore Ts'o#include "config.h" 30838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#include <stdlib.h> 31838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#include <stddef.h> 32c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#ifdef DICT_NODEBUG 33c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#define dict_assert(x) 34c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#else 35838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#include <assert.h> 36c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#define dict_assert(x) assert(x) 37c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#endif 38838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define DICT_IMPLEMENTATION 39838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#include "dict.h" 40838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 41838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#ifdef KAZLIB_RCSID 42838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic const char rcsid[] = "$Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $"; 43838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#endif 44838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 45838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 46838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * These macros provide short convenient names for structure members, 47838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * which are embellished with dict_ prefixes so that they are 48efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o * properly confined to the documented namespace. It's legal for a 49838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * program which uses dict to define, for instance, a macro called ``parent''. 50838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Such a macro would interfere with the dnode_t struct definition. 51838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * In general, highly portable and reusable C modules which expose their 52838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * structures need to confine structure member names to well-defined spaces. 53838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * The resulting identifiers aren't necessarily convenient to use, nor 54838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * readable, in the implementation, however! 55838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 56838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 57838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define left dict_left 58838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define right dict_right 59838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define parent dict_parent 60838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define color dict_color 61838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define key dict_key 62838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define data dict_data 63838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 64838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define nilnode dict_nilnode 65838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define nodecount dict_nodecount 66838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define maxcount dict_maxcount 67838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define compare dict_compare 68838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define allocnode dict_allocnode 69838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define freenode dict_freenode 70838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define context dict_context 71838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define dupes dict_dupes 72838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 73838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define dictptr dict_dictptr 74838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 75838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define dict_root(D) ((D)->nilnode.left) 76838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define dict_nil(D) (&(D)->nilnode) 77838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#define DICT_DEPTH_MAX 64 78838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 79838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic dnode_t *dnode_alloc(void *context); 80838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic void dnode_free(dnode_t *node, void *context); 81838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 82838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 83838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Perform a ``left rotation'' adjustment on the tree. The given node P and 84838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * its right child C are rearranged so that the P instead becomes the left 85838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * child of C. The left subtree of C is inherited as the new right subtree 86838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * for P. The ordering of the keys within the tree is thus preserved. 87838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 88838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 89838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic void rotate_left(dnode_t *upper) 90838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 91838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *lower, *lowleft, *upparent; 92838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 93838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o lower = upper->right; 94838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o upper->right = lowleft = lower->left; 95838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o lowleft->parent = upper; 96838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 97838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o lower->parent = upparent = upper->parent; 98838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 99838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* don't need to check for root node here because root->parent is 100838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o the sentinel nil node, and root->parent->left points back to root */ 101838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 102838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (upper == upparent->left) { 103838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o upparent->left = lower; 104838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 105c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (upper == upparent->right); 106838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o upparent->right = lower; 107838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 108838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 109838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o lower->left = upper; 110838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o upper->parent = lower; 111838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 112838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 113838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 114838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * This operation is the ``mirror'' image of rotate_left. It is 115838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * the same procedure, but with left and right interchanged. 116838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 117838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 118838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic void rotate_right(dnode_t *upper) 119838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 120838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *lower, *lowright, *upparent; 121838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 122838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o lower = upper->left; 123838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o upper->left = lowright = lower->right; 124838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o lowright->parent = upper; 125838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 126838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o lower->parent = upparent = upper->parent; 127838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 128838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (upper == upparent->right) { 129838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o upparent->right = lower; 130838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 131c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (upper == upparent->left); 132838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o upparent->left = lower; 133838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 134838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 135838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o lower->right = upper; 136838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o upper->parent = lower; 137838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 138838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 139838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 140838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Do a postorder traversal of the tree rooted at the specified 141838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * node and free everything under it. Used by dict_free(). 142838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 143838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 144838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil) 145838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 146838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (node == nil) 147838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return; 148838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free_nodes(dict, node->left, nil); 149838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free_nodes(dict, node->right, nil); 150838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->freenode(node, dict->context); 151838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 152838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 153838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 154838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * This procedure performs a verification that the given subtree is a binary 155838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * search tree. It performs an inorder traversal of the tree using the 156838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * dict_next() successor function, verifying that the key of each node is 157838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * strictly lower than that of its successor, if duplicates are not allowed, 158838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * or lower or equal if duplicates are allowed. This function is used for 159efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o * debugging purposes. 160838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 161c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#ifndef DICT_NODEBUG 162838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic int verify_bintree(dict_t *dict) 163838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 164838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *first, *next; 165838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 166838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o first = dict_first(dict); 167838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 168838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (dict->dupes) { 169838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (first && (next = dict_next(dict, first))) { 170838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (dict->compare(first->key, next->key) > 0) 171838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 172838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o first = next; 173838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 174838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 175838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (first && (next = dict_next(dict, first))) { 176838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (dict->compare(first->key, next->key) >= 0) 177838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 178838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o first = next; 179838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 180838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 181838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 1; 182838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 183838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 184838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 185838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * This function recursively verifies that the given binary subtree satisfies 186838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * three of the red black properties. It checks that every red node has only 187838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * black children. It makes sure that each node is either red or black. And it 188838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * checks that every path has the same count of black nodes from root to leaf. 189838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * It returns the blackheight of the given subtree; this allows blackheights to 190838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * be computed recursively and compared for left and right siblings for 191838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * mismatches. It does not check for every nil node being black, because there 192838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * is only one sentinel nil node. The return value of this function is the 193838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * black height of the subtree rooted at the node ``root'', or zero if the 194838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * subtree is not red-black. 195838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 196838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 197838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic unsigned int verify_redblack(dnode_t *nil, dnode_t *root) 198838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 199838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o unsigned height_left, height_right; 200838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 201838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (root != nil) { 202838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o height_left = verify_redblack(nil, root->left); 203838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o height_right = verify_redblack(nil, root->right); 204838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (height_left == 0 || height_right == 0) 205838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 206838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (height_left != height_right) 207838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 208838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (root->color == dnode_red) { 209838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (root->left->color != dnode_black) 210838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 211838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (root->right->color != dnode_black) 212838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 213838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return height_left; 214838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 215838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (root->color != dnode_black) 216838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 217838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return height_left + 1; 218efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o } 219838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 1; 220838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 221838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 222838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 223838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Compute the actual count of nodes by traversing the tree and 224838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * return it. This could be compared against the stored count to 225838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * detect a mismatch. 226838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 227838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 228838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic dictcount_t verify_node_count(dnode_t *nil, dnode_t *root) 229838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 230838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (root == nil) 231838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 232838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o else 233838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 1 + verify_node_count(nil, root->left) 234838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o + verify_node_count(nil, root->right); 235838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 236838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#endif 237838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 238838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 239838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Verify that the tree contains the given node. This is done by 240838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * traversing all of the nodes and comparing their pointers to the 241838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * given pointer. Returns 1 if the node is found, otherwise 242838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * returns zero. It is intended for debugging purposes. 243838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 244838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 245838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node) 246838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 247838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (root != nil) { 248838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return root == node 249838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o || verify_dict_has_node(nil, root->left, node) 250838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o || verify_dict_has_node(nil, root->right, node); 251838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 252838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 253838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 254838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 255838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 256838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#ifdef E2FSCK_NOTUSED 257838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 258838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Dynamically allocate and initialize a dictionary object. 259838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 260838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 261838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'odict_t *dict_create(dictcount_t maxcount, dict_comp_t comp) 262838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 263838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_t *new = malloc(sizeof *new); 264838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 265838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (new) { 266838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->compare = comp; 267838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->allocnode = dnode_alloc; 268838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->freenode = dnode_free; 269838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->context = NULL; 270838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->nodecount = 0; 271838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->maxcount = maxcount; 272838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->nilnode.left = &new->nilnode; 273838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->nilnode.right = &new->nilnode; 274838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->nilnode.parent = &new->nilnode; 275838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->nilnode.color = dnode_black; 276838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->dupes = 0; 277838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 278838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return new; 279838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 280838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#endif /* E2FSCK_NOTUSED */ 281838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 282838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 283838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Select a different set of node allocator routines. 284838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 285838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 286838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dict_set_allocator(dict_t *dict, dnode_alloc_t al, 287838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_free_t fr, void *context) 288838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 289c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict_count(dict) == 0); 290c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert ((al == NULL && fr == NULL) || (al != NULL && fr != NULL)); 291838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 292838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->allocnode = al ? al : dnode_alloc; 293838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->freenode = fr ? fr : dnode_free; 294838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->context = context; 295838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 296838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 297838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#ifdef E2FSCK_NOTUSED 298838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 299838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Free a dynamically allocated dictionary object. Removing the nodes 300838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * from the tree before deleting it is required. 301838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 302838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 303838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dict_destroy(dict_t *dict) 304838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 305c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict_isempty(dict)); 306838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free(dict); 307838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 308838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#endif 309838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 310838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 311838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Free all the nodes in the dictionary by using the dictionary's 312838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * installed free routine. The dictionary is emptied. 313838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 314838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 315838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dict_free_nodes(dict_t *dict) 316838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 317838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *nil = dict_nil(dict), *root = dict_root(dict); 318838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free_nodes(dict, root, nil); 319838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nodecount = 0; 320838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nilnode.left = &dict->nilnode; 321838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nilnode.right = &dict->nilnode; 322838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 323838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 324838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#ifdef E2FSCK_NOTUSED 325838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 326838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Obsolescent function, equivalent to dict_free_nodes 327838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 328838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dict_free(dict_t *dict) 329838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 330838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#ifdef KAZLIB_OBSOLESCENT_DEBUG 331c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert ("call to obsolescent function dict_free()" && 0); 332838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#endif 333838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_free_nodes(dict); 334838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 335838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#endif 336838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 337838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 338838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Initialize a user-supplied dictionary object. 339838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 340838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 341838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'odict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp) 342838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 343838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->compare = comp; 344838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->allocnode = dnode_alloc; 345838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->freenode = dnode_free; 346838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->context = NULL; 347838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nodecount = 0; 348838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->maxcount = maxcount; 349838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nilnode.left = &dict->nilnode; 350838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nilnode.right = &dict->nilnode; 351838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nilnode.parent = &dict->nilnode; 352838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nilnode.color = dnode_black; 353838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->dupes = 0; 354838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return dict; 355838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 356838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 357838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#ifdef E2FSCK_NOTUSED 358efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o/* 359838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Initialize a dictionary in the likeness of another dictionary 360838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 361838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 362838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dict_init_like(dict_t *dict, const dict_t *template) 363838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 364838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->compare = template->compare; 365838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->allocnode = template->allocnode; 366838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->freenode = template->freenode; 367838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->context = template->context; 368838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nodecount = 0; 369838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->maxcount = template->maxcount; 370838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nilnode.left = &dict->nilnode; 371838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nilnode.right = &dict->nilnode; 372838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nilnode.parent = &dict->nilnode; 373838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nilnode.color = dnode_black; 374838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->dupes = template->dupes; 375838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 376c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict_similar(dict, template)); 377838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 378838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 379838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 380838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Remove all nodes from the dictionary (without freeing them in any way). 381838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 382838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 383838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic void dict_clear(dict_t *dict) 384838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 385838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nodecount = 0; 386838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nilnode.left = &dict->nilnode; 387838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nilnode.right = &dict->nilnode; 388838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nilnode.parent = &dict->nilnode; 389c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict->nilnode.color == dnode_black); 390838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 391c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#endif /* E2FSCK_NOTUSED */ 392838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 393838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 394838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 395838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Verify the integrity of the dictionary structure. This is provided for 396838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * debugging purposes, and should be placed in assert statements. Just because 397838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * this function succeeds doesn't mean that the tree is not corrupt. Certain 398838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * corruptions in the tree may simply cause undefined behavior. 399efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o */ 400c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#ifndef DICT_NODEBUG 401838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'oint dict_verify(dict_t *dict) 402838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 403838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *nil = dict_nil(dict), *root = dict_root(dict); 404838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 405838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* check that the sentinel node and root node are black */ 406838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (root->color != dnode_black) 407838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 408838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (nil->color != dnode_black) 409838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 410838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (nil->right != nil) 411838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 412838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* nil->left is the root node; check that its parent pointer is nil */ 413838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (nil->left->parent != nil) 414838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 415838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* perform a weak test that the tree is a binary search tree */ 416838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!verify_bintree(dict)) 417838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 418838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* verify that the tree is a red-black tree */ 419838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!verify_redblack(nil, root)) 420838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 421838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (verify_node_count(nil, root) != dict_count(dict)) 422838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 423838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 1; 424838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 425c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#endif /* DICT_NODEBUG */ 426838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 427c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#ifdef E2FSCK_NOTUSED 428838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 429838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Determine whether two dictionaries are similar: have the same comparison and 430838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * allocator functions, and same status as to whether duplicates are allowed. 431838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 432838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'oint dict_similar(const dict_t *left, const dict_t *right) 433838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 434838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (left->compare != right->compare) 435838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 436838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 437838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (left->allocnode != right->allocnode) 438838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 439838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 440838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (left->freenode != right->freenode) 441838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 442838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 443838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (left->context != right->context) 444838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 445838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 446838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (left->dupes != right->dupes) 447838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 448838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 449838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 1; 450838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 451838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#endif /* E2FSCK_NOTUSED */ 452838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 453838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 454838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Locate a node in the dictionary having the given key. 455efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o * If the node is not found, a null a pointer is returned (rather than 456838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * a pointer that dictionary's nil sentinel node), otherwise a pointer to the 457838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * located node is returned. 458838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 459838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 460838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'odnode_t *dict_lookup(dict_t *dict, const void *key) 461838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 462838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *root = dict_root(dict); 463838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *nil = dict_nil(dict); 464838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *saved; 465838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o int result; 466838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 467838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* simple binary search adapted for trees that contain duplicate keys */ 468838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 469838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (root != nil) { 470838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o result = dict->compare(key, root->key); 471838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (result < 0) 472838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o root = root->left; 473838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o else if (result > 0) 474838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o root = root->right; 475838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o else { 476838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!dict->dupes) { /* no duplicates, return match */ 477838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return root; 478838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { /* could be dupes, find leftmost one */ 479838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o do { 480838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o saved = root; 481838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o root = root->left; 482838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (root != nil && dict->compare(key, root->key)) 483838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o root = root->right; 484838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } while (root != nil); 485838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return saved; 486838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 487838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 488838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 489838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 490838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return NULL; 491838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 492838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 493838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#ifdef E2FSCK_NOTUSED 494838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 495838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Look for the node corresponding to the lowest key that is equal to or 496838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * greater than the given key. If there is no such node, return null. 497838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 498838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 499838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'odnode_t *dict_lower_bound(dict_t *dict, const void *key) 500838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 501838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *root = dict_root(dict); 502838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *nil = dict_nil(dict); 503838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *tentative = 0; 504838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 505838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (root != nil) { 506838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o int result = dict->compare(key, root->key); 507838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 508838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (result > 0) { 509838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o root = root->right; 510838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else if (result < 0) { 511838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tentative = root; 512838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o root = root->left; 513838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 514838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!dict->dupes) { 515838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return root; 516838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 517838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tentative = root; 518838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o root = root->left; 519838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 520efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o } 521838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 522efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 523838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return tentative; 524838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 525838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 526838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 527838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Look for the node corresponding to the greatest key that is equal to or 528838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * lower than the given key. If there is no such node, return null. 529838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 530838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 531838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'odnode_t *dict_upper_bound(dict_t *dict, const void *key) 532838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 533838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *root = dict_root(dict); 534838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *nil = dict_nil(dict); 535838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *tentative = 0; 536838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 537838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (root != nil) { 538838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o int result = dict->compare(key, root->key); 539838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 540838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (result < 0) { 541838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o root = root->left; 542838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else if (result > 0) { 543838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tentative = root; 544838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o root = root->right; 545838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 546838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!dict->dupes) { 547838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return root; 548838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 549838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tentative = root; 550838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o root = root->right; 551838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 552efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o } 553838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 554efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 555838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return tentative; 556838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 557838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#endif 558838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 559838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 560838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Insert a node into the dictionary. The node should have been 561838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * initialized with a data field. All other fields are ignored. 562838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * The behavior is undefined if the user attempts to insert into 563838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * a dictionary that is already full (for which the dict_isfull() 564838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * function returns true). 565838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 566838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 567838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dict_insert(dict_t *dict, dnode_t *node, const void *key) 568838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 569838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *where = dict_root(dict), *nil = dict_nil(dict); 570838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *parent = nil, *uncle, *grandpa; 571838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o int result = -1; 572838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 573838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o node->key = key; 574838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 575c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (!dict_isfull(dict)); 576c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (!dict_contains(dict, node)); 577c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (!dnode_is_in_a_dict(node)); 578838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 579838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* basic binary tree insert */ 580838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 581838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (where != nil) { 582838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent = where; 583838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o result = dict->compare(key, where->key); 584838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* trap attempts at duplicate key insertion unless it's explicitly allowed */ 585c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict->dupes || result != 0); 586838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (result < 0) 587838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o where = where->left; 588838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o else 589838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o where = where->right; 590838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 591838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 592c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (where == nil); 593838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 594838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (result < 0) 595838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent->left = node; 596838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o else 597838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent->right = node; 598838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 599838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o node->parent = parent; 600838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o node->left = nil; 601838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o node->right = nil; 602838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 603838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nodecount++; 604838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 605838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* red black adjustments */ 606838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 607838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o node->color = dnode_red; 608838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 609838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (parent->color == dnode_red) { 610838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o grandpa = parent->parent; 611838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (parent == grandpa->left) { 612838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o uncle = grandpa->right; 613838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (uncle->color == dnode_red) { /* red parent, red uncle */ 614838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent->color = dnode_black; 615838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o uncle->color = dnode_black; 616838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o grandpa->color = dnode_red; 617838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o node = grandpa; 618838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent = grandpa->parent; 619838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { /* red parent, black uncle */ 620838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (node == parent->right) { 621838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o rotate_left(parent); 622838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent = node; 623c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (grandpa == parent->parent); 624838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* rotation between parent and child preserves grandpa */ 625838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 626838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent->color = dnode_black; 627838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o grandpa->color = dnode_red; 628838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o rotate_right(grandpa); 629838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 630838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 631838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { /* symmetric cases: parent == parent->parent->right */ 632838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o uncle = grandpa->left; 633838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (uncle->color == dnode_red) { 634838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent->color = dnode_black; 635838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o uncle->color = dnode_black; 636838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o grandpa->color = dnode_red; 637838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o node = grandpa; 638838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent = grandpa->parent; 639838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 640838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (node == parent->left) { 641838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o rotate_right(parent); 642838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent = node; 643c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (grandpa == parent->parent); 644838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 645838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent->color = dnode_black; 646838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o grandpa->color = dnode_red; 647838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o rotate_left(grandpa); 648838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 649838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 650838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 651838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 652838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 653838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_root(dict)->color = dnode_black; 654838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 655c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict_verify(dict)); 656838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 657838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 658838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#ifdef E2FSCK_NOTUSED 659838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 660838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Delete the given node from the dictionary. If the given node does not belong 661838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * to the given dictionary, undefined behavior results. A pointer to the 662838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * deleted node is returned. 663838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 664838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 665838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'odnode_t *dict_delete(dict_t *dict, dnode_t *delete) 666838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 667838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent; 668838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 669838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* basic deletion */ 670838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 671c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (!dict_isempty(dict)); 672c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict_contains(dict, delete)); 673838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 674838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* 675838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * If the node being deleted has two children, then we replace it with its 676838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * successor (i.e. the leftmost node in the right subtree.) By doing this, 677838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * we avoid the traditional algorithm under which the successor's key and 678838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * value *only* move to the deleted node and the successor is spliced out 679838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * from the tree. We cannot use this approach because the user may hold 680838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * pointers to the successor, or nodes may be inextricably tied to some 681838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * other structures by way of embedding, etc. So we must splice out the 682838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * node we are given, not some other node, and must not move contents from 683838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * one node to another behind the user's back. 684838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 685838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 686838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (delete->left != nil && delete->right != nil) { 687838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *next = dict_next(dict, delete); 688838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *nextparent = next->parent; 689838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_color_t nextcolor = next->color; 690838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 691c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (next != nil); 692c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (next->parent != nil); 693c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (next->left == nil); 694838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 695838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* 696838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * First, splice out the successor from the tree completely, by 697838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * moving up its right child into its place. 698838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 699838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 700838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o child = next->right; 701838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o child->parent = nextparent; 702838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 703838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (nextparent->left == next) { 704838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o nextparent->left = child; 705838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 706c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (nextparent->right == next); 707838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o nextparent->right = child; 708838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 709838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 710838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* 711838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Now that the successor has been extricated from the tree, install it 712838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * in place of the node that we want deleted. 713838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 714838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 715838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o next->parent = delparent; 716838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o next->left = delete->left; 717838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o next->right = delete->right; 718838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o next->left->parent = next; 719838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o next->right->parent = next; 720838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o next->color = delete->color; 721838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o delete->color = nextcolor; 722838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 723838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (delparent->left == delete) { 724838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o delparent->left = next; 725838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 726c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (delparent->right == delete); 727838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o delparent->right = next; 728838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 729838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 730838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 731c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (delete != nil); 732c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (delete->left == nil || delete->right == nil); 733838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 734838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o child = (delete->left != nil) ? delete->left : delete->right; 735838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 736efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o child->parent = delparent = delete->parent; 737838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 738838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (delete == delparent->left) { 739efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o delparent->left = child; 740838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 741c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (delete == delparent->right); 742838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o delparent->right = child; 743838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 744838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 745838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 746838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o delete->parent = NULL; 747838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o delete->right = NULL; 748838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o delete->left = NULL; 749838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 750838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nodecount--; 751838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 752c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (verify_bintree(dict)); 753838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 754838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* red-black adjustments */ 755838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 756838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (delete->color == dnode_black) { 757838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *parent, *sister; 758838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 759838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_root(dict)->color = dnode_red; 760838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 761838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (child->color == dnode_black) { 762838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent = child->parent; 763838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (child == parent->left) { 764838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister = parent->right; 765c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (sister != nil); 766838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (sister->color == dnode_red) { 767838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister->color = dnode_black; 768838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent->color = dnode_red; 769838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o rotate_left(parent); 770838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister = parent->right; 771c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (sister != nil); 772838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 773838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (sister->left->color == dnode_black 774838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o && sister->right->color == dnode_black) { 775838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister->color = dnode_red; 776838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o child = parent; 777838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 778838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (sister->right->color == dnode_black) { 779c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (sister->left->color == dnode_red); 780838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister->left->color = dnode_black; 781838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister->color = dnode_red; 782838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o rotate_right(sister); 783838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister = parent->right; 784c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (sister != nil); 785838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 786838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister->color = parent->color; 787838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister->right->color = dnode_black; 788838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent->color = dnode_black; 789838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o rotate_left(parent); 790838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 791838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 792838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { /* symmetric case: child == child->parent->right */ 793c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (child == parent->right); 794838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister = parent->left; 795c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (sister != nil); 796838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (sister->color == dnode_red) { 797838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister->color = dnode_black; 798838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent->color = dnode_red; 799838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o rotate_right(parent); 800838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister = parent->left; 801c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (sister != nil); 802838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 803838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (sister->right->color == dnode_black 804838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o && sister->left->color == dnode_black) { 805838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister->color = dnode_red; 806838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o child = parent; 807838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 808838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (sister->left->color == dnode_black) { 809c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (sister->right->color == dnode_red); 810838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister->right->color = dnode_black; 811838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister->color = dnode_red; 812838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o rotate_left(sister); 813838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister = parent->left; 814c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (sister != nil); 815838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 816838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister->color = parent->color; 817838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o sister->left->color = dnode_black; 818838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent->color = dnode_black; 819838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o rotate_right(parent); 820838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 821838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 822838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 823838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 824838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 825838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o child->color = dnode_black; 826838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_root(dict)->color = dnode_black; 827838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 828838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 829c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict_verify(dict)); 830838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 831838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return delete; 832838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 833838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#endif /* E2FSCK_NOTUSED */ 834838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 835838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 836838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Allocate a node using the dictionary's allocator routine, give it 837838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * the data item. 838838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 839838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 840838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'oint dict_alloc_insert(dict_t *dict, const void *key, void *data) 841838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 842838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *node = dict->allocnode(dict->context); 843838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 844838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (node) { 845838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_init(node, data); 846838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_insert(dict, node, key); 847838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 1; 848838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 849838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 850838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 851838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 852838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#ifdef E2FSCK_NOTUSED 853838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dict_delete_free(dict_t *dict, dnode_t *node) 854838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 855838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_delete(dict, node); 856838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->freenode(node, dict->context); 857838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 858838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#endif 859838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 860838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 861838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Return the node with the lowest (leftmost) key. If the dictionary is empty 862838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * (that is, dict_isempty(dict) returns 1) a null pointer is returned. 863838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 864838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 865838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'odnode_t *dict_first(dict_t *dict) 866838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 867838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left; 868838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 869838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (root != nil) 870838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while ((left = root->left) != nil) 871838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o root = left; 872838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 873838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return (root == nil) ? NULL : root; 874838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 875838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 876838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 877838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Return the node with the highest (rightmost) key. If the dictionary is empty 878838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * (that is, dict_isempty(dict) returns 1) a null pointer is returned. 879838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 880838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 881838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'odnode_t *dict_last(dict_t *dict) 882838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 883838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right; 884838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 885838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (root != nil) 886838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while ((right = root->right) != nil) 887838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o root = right; 888838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 889838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return (root == nil) ? NULL : root; 890838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 891838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 892838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 893838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Return the given node's successor node---the node which has the 894838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * next key in the the left to right ordering. If the node has 895838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * no successor, a null pointer is returned rather than a pointer to 896838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * the nil node. 897838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 898838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 899838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'odnode_t *dict_next(dict_t *dict, dnode_t *curr) 900838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 901838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *nil = dict_nil(dict), *parent, *left; 902838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 903838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (curr->right != nil) { 904838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o curr = curr->right; 905838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while ((left = curr->left) != nil) 906838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o curr = left; 907838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return curr; 908838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 909838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 910838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent = curr->parent; 911838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 912838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (parent != nil && curr == parent->right) { 913838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o curr = parent; 914838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent = curr->parent; 915838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 916838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 917838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return (parent == nil) ? NULL : parent; 918838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 919838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 920838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o/* 921838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * Return the given node's predecessor, in the key order. 922838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o * The nil sentinel node is returned if there is no predecessor. 923838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o */ 924838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 925838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'odnode_t *dict_prev(dict_t *dict, dnode_t *curr) 926838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 927838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *nil = dict_nil(dict), *parent, *right; 928838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 929838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (curr->left != nil) { 930838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o curr = curr->left; 931838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while ((right = curr->right) != nil) 932838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o curr = right; 933838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return curr; 934838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 935838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 936838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent = curr->parent; 937838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 938838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (parent != nil && curr == parent->left) { 939838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o curr = parent; 940838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o parent = curr->parent; 941838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 942838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 943838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return (parent == nil) ? NULL : parent; 944838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 945838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 946838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dict_allow_dupes(dict_t *dict) 947838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 948838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->dupes = 1; 949838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 950838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 951838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#undef dict_count 952838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#undef dict_isempty 953838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#undef dict_isfull 954838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#undef dnode_get 955838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#undef dnode_put 956838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#undef dnode_getkey 957838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 958838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'odictcount_t dict_count(dict_t *dict) 959838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 960838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return dict->nodecount; 961838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 962838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 963838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'oint dict_isempty(dict_t *dict) 964838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 965838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return dict->nodecount == 0; 966838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 967838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 968838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'oint dict_isfull(dict_t *dict) 969838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 970838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return dict->nodecount == dict->maxcount; 971838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 972838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 973838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'oint dict_contains(dict_t *dict, dnode_t *node) 974838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 975838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return verify_dict_has_node(dict_nil(dict), dict_root(dict), node); 976838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 977838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 978544349270e4c74a6feb971123884a8cf5052a7eeTheodore Ts'ostatic dnode_t *dnode_alloc(void *context EXT2FS_ATTR((unused))) 979838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 980838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return malloc(sizeof *dnode_alloc(NULL)); 981838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 982838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 983544349270e4c74a6feb971123884a8cf5052a7eeTheodore Ts'ostatic void dnode_free(dnode_t *node, void *context EXT2FS_ATTR((unused))) 984838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 985838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free(node); 986838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 987838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 988838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'odnode_t *dnode_create(void *data) 989838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 990838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *new = malloc(sizeof *new); 991838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (new) { 992838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->data = data; 993838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->parent = NULL; 994838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->left = NULL; 995838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o new->right = NULL; 996838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 997838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return new; 998838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 999838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1000838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'odnode_t *dnode_init(dnode_t *dnode, void *data) 1001838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1002838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode->data = data; 1003838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode->parent = NULL; 1004838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode->left = NULL; 1005838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode->right = NULL; 1006838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return dnode; 1007838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1008838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1009838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dnode_destroy(dnode_t *dnode) 1010838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1011c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (!dnode_is_in_a_dict(dnode)); 1012838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free(dnode); 1013838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1014838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1015838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid *dnode_get(dnode_t *dnode) 1016838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1017838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return dnode->data; 1018838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1019838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1020838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'oconst void *dnode_getkey(dnode_t *dnode) 1021838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1022838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return dnode->key; 1023838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1024838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1025838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#ifdef E2FSCK_NOTUSED 1026838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dnode_put(dnode_t *dnode, void *data) 1027838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1028838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode->data = data; 1029838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1030c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#endif 1031838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1032c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#ifndef DICT_NODEBUG 1033838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'oint dnode_is_in_a_dict(dnode_t *dnode) 1034838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1035838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return (dnode->parent && dnode->left && dnode->right); 1036838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1037c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#endif 1038838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1039c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#ifdef E2FSCK_NOTUSED 1040838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dict_process(dict_t *dict, void *context, dnode_process_t function) 1041838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1042838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *node = dict_first(dict), *next; 1043838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1044838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (node != NULL) { 1045838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* check for callback function deleting */ 1046838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o /* the next node from under us */ 1047c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict_contains(dict, node)); 1048838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o next = dict_next(dict, node); 1049838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o function(dict, node, context); 1050838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o node = next; 1051838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1052838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1053838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1054838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic void load_begin_internal(dict_load_t *load, dict_t *dict) 1055838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1056838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o load->dictptr = dict; 1057838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o load->nilnode.left = &load->nilnode; 1058838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o load->nilnode.right = &load->nilnode; 1059838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1060838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1061838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dict_load_begin(dict_load_t *load, dict_t *dict) 1062838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1063c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict_isempty(dict)); 1064838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o load_begin_internal(load, dict); 1065838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1066838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1067838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key) 1068838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1069838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_t *dict = load->dictptr; 1070838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *nil = &load->nilnode; 1071efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 1072c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (!dnode_is_in_a_dict(newnode)); 1073c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict->nodecount < dict->maxcount); 1074838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1075c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#ifndef DICT_NODEBUG 1076838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (dict->nodecount > 0) { 1077838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (dict->dupes) 1078c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict->compare(nil->left->key, key) <= 0); 1079838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o else 1080c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict->compare(nil->left->key, key) < 0); 1081838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 108248e6e81362f264aee4f3945c14928efaf71a06c9Theodore Ts'o#endif 1083838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1084838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o newnode->key = key; 1085838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o nil->right->left = newnode; 1086838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o nil->right = newnode; 1087838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o newnode->left = nil; 1088838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict->nodecount++; 1089838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1090838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1091838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dict_load_end(dict_load_t *load) 1092838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1093838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_t *dict = load->dictptr; 1094838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *tree[DICT_DEPTH_MAX] = { 0 }; 1095838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next; 1096838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *complete = 0; 1097838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount; 1098838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dictcount_t botrowcount; 1099838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o unsigned baselevel = 0, level = 0, i; 1100838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1101c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dnode_red == 0 && dnode_black == 1); 1102838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1103838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (fullcount >= nodecount && fullcount) 1104838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o fullcount >>= 1; 1105838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1106838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o botrowcount = nodecount - fullcount; 1107838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1108838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o for (curr = loadnil->left; curr != loadnil; curr = next) { 1109838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o next = curr->left; 1110838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1111838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (complete == NULL && botrowcount-- == 0) { 1112c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (baselevel == 0); 1113c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (level == 0); 1114838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o baselevel = level = 1; 1115838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete = tree[0]; 1116838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1117838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (complete != 0) { 1118838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tree[0] = 0; 1119838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete->right = dictnil; 1120838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (tree[level] != 0) { 1121838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tree[level]->right = complete; 1122838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete->parent = tree[level]; 1123838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete = tree[level]; 1124838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tree[level++] = 0; 1125838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1126838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1127838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1128838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1129838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (complete == NULL) { 1130838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o curr->left = dictnil; 1131838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o curr->right = dictnil; 1132838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o curr->color = level % 2; 1133838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete = curr; 1134838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1135c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (level == baselevel); 1136838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (tree[level] != 0) { 1137838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tree[level]->right = complete; 1138838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete->parent = tree[level]; 1139838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete = tree[level]; 1140838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tree[level++] = 0; 1141838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1142838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 1143838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o curr->left = complete; 1144838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o curr->color = (level + 1) % 2; 1145838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete->parent = curr; 1146838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tree[level] = curr; 1147838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete = 0; 1148838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o level = baselevel; 1149838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1150838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1151838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1152838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (complete == NULL) 1153838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete = dictnil; 1154838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1155838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o for (i = 0; i < DICT_DEPTH_MAX; i++) { 1156838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (tree[i] != 0) { 1157838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tree[i]->right = complete; 1158838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete->parent = tree[i]; 1159838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete = tree[i]; 1160838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1161838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1162838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1163838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dictnil->color = dnode_black; 1164838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dictnil->right = dictnil; 1165838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete->parent = dictnil; 1166838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o complete->color = dnode_black; 1167838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_root(dict) = complete; 1168838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1169c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict_verify(dict)); 1170838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1171838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1172838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ovoid dict_merge(dict_t *dest, dict_t *source) 1173838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1174838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_load_t load; 1175838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source); 1176838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1177c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (dict_similar(dest, source)); 1178838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1179838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (source == dest) 1180838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return; 1181838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1182838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dest->nodecount = 0; 1183838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o load_begin_internal(&load, dest); 1184838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1185838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o for (;;) { 1186838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (leftnode != NULL && rightnode != NULL) { 1187838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (dest->compare(leftnode->key, rightnode->key) < 0) 1188838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o goto copyleft; 1189838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o else 1190838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o goto copyright; 1191838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else if (leftnode != NULL) { 1192838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o goto copyleft; 1193838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else if (rightnode != NULL) { 1194838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o goto copyright; 1195838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 1196c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o dict_assert (leftnode == NULL && rightnode == NULL); 1197838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1198838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1199838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1200838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o copyleft: 1201838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o { 1202838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *next = dict_next(dest, leftnode); 1203c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#ifndef DICT_NODEBUG 1204838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o leftnode->left = NULL; /* suppress assertion in dict_load_next */ 120548e6e81362f264aee4f3945c14928efaf71a06c9Theodore Ts'o#endif 1206838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_load_next(&load, leftnode, leftnode->key); 1207838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o leftnode = next; 1208838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o continue; 1209838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1210efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o 1211838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o copyright: 1212838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o { 1213838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *next = dict_next(source, rightnode); 1214c379cdc33425cabcce110ae63fbeb5ad9b6ce37fTheodore Ts'o#ifndef DICT_NODEBUG 1215838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o rightnode->left = NULL; 121648e6e81362f264aee4f3945c14928efaf71a06c9Theodore Ts'o#endif 1217838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_load_next(&load, rightnode, rightnode->key); 1218838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o rightnode = next; 1219838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o continue; 1220838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1221838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1222838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1223838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_clear(source); 1224838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_load_end(&load); 1225838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1226838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#endif /* E2FSCK_NOTUSED */ 1227838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1228838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#ifdef KAZLIB_TEST_MAIN 1229838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1230838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#include <stdio.h> 1231838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#include <string.h> 1232838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#include <ctype.h> 1233838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#include <stdarg.h> 1234838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1235838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'otypedef char input_t[256]; 1236838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1237838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic int tokenize(char *string, ...) 1238838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1239efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o char **tokptr; 1240838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o va_list arglist; 1241838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o int tokcount = 0; 1242838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1243838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o va_start(arglist, string); 1244838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tokptr = va_arg(arglist, char **); 1245838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (tokptr) { 1246838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (*string && isspace((unsigned char) *string)) 1247838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o string++; 1248838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!*string) 1249838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1250838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o *tokptr = string; 1251838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (*string && !isspace((unsigned char) *string)) 1252838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o string++; 1253838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tokptr = va_arg(arglist, char **); 1254838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o tokcount++; 1255838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!*string) 1256838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1257838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o *string++ = 0; 1258838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1259838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o va_end(arglist); 1260838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1261838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return tokcount; 1262838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1263838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1264838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic int comparef(const void *key1, const void *key2) 1265838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1266838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return strcmp(key1, key2); 1267838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1268838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1269838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic char *dupstring(char *str) 1270838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1271838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o int sz = strlen(str) + 1; 1272838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o char *new = malloc(sz); 1273838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (new) 1274838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o memcpy(new, str, sz); 1275838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return new; 1276838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1277838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1278838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic dnode_t *new_node(void *c) 1279838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1280838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o static dnode_t few[5]; 1281838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o static int count; 1282838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1283838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (count < 5) 1284838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return few + count++; 1285838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1286838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return NULL; 1287838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1288838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1289838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic void del_node(dnode_t *n, void *c) 1290838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1291838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1292838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1293838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic int prompt = 0; 1294838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1295838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'ostatic void construct(dict_t *d) 1296838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1297838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o input_t in; 1298838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o int done = 0; 1299838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_load_t dl; 1300838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *dn; 1301838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o char *tok1, *tok2, *val; 1302838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o const char *key; 1303efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o char *help = 1304838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "p turn prompt on\n" 1305838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "q finish construction\n" 1306838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "a <key> <val> add new entry\n"; 1307838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1308838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!dict_isempty(d)) 1309838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("warning: dictionary not empty!"); 1310838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1311838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_load_begin(&dl, d); 1312838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1313838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o while (!done) { 1314838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (prompt) 1315838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o putchar('>'); 1316838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o fflush(stdout); 1317838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1318838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!fgets(in, sizeof(input_t), stdin)) 1319838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1320838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1321838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o switch (in[0]) { 1322838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case '?': 1323838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts(help); 1324838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1325838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'p': 1326838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o prompt = 1; 1327838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1328838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'q': 1329838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o done = 1; 1330838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1331838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'a': 1332838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) { 1333838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("what?"); 1334838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1335838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1336838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o key = dupstring(tok1); 1337838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o val = dupstring(tok2); 1338838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dn = dnode_create(val); 1339838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1340838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!key || !val || !dn) { 1341838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("out of memory"); 1342838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free((void *) key); 1343838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free(val); 1344838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (dn) 1345838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_destroy(dn); 1346838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1347838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1348838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_load_next(&dl, dn, key); 1349838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1350838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o default: 1351838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o putchar('?'); 1352838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o putchar('\n'); 1353838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1354838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1355838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1356838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1357838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_load_end(&dl); 1358838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1359838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1360838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'oint main(void) 1361838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o{ 1362838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o input_t in; 1363838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_t darray[10]; 1364838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_t *d = &darray[0]; 1365838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dnode_t *dn; 1366838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o int i; 1367838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o char *tok1, *tok2, *val; 1368838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o const char *key; 1369838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1370838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o char *help = 1371838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "a <key> <val> add value to dictionary\n" 1372838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "d <key> delete value from dictionary\n" 1373838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "l <key> lookup value in dictionary\n" 1374838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "( <key> lookup lower bound\n" 1375838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o ") <key> lookup upper bound\n" 1376838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "# <num> switch to alternate dictionary (0-9)\n" 1377838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "j <num> <num> merge two dictionaries\n" 1378838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "f free the whole dictionary\n" 1379838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "k allow duplicate keys\n" 1380838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "c show number of entries\n" 1381838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "t dump whole dictionary in sort order\n" 1382838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "m make dictionary out of sorted items\n" 1383838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "p turn prompt on\n" 1384838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "s switch to non-functioning allocator\n" 1385838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o "q quit"; 1386838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1387838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o for (i = 0; i < sizeof darray / sizeof *darray; i++) 1388838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_init(&darray[i], DICTCOUNT_T_MAX, comparef); 1389838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1390838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o for (;;) { 1391838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (prompt) 1392838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o putchar('>'); 1393838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o fflush(stdout); 1394838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1395838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!fgets(in, sizeof(input_t), stdin)) 1396838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1397838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1398838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o switch(in[0]) { 1399838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case '?': 1400838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts(help); 1401838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1402838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'a': 1403838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) { 1404838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("what?"); 1405838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1406838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1407838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o key = dupstring(tok1); 1408838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o val = dupstring(tok2); 1409838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1410838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!key || !val) { 1411838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("out of memory"); 1412838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free((void *) key); 1413838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free(val); 1414838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1415838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1416838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!dict_alloc_insert(d, key, val)) { 1417838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("dict_alloc_insert failed"); 1418838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free((void *) key); 1419838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free(val); 1420838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1421838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1422838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1423838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'd': 1424838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (tokenize(in+1, &tok1, (char **) 0) != 1) { 1425838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("what?"); 1426838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1427838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1428838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dn = dict_lookup(d, tok1); 1429838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!dn) { 1430838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("dict_lookup failed"); 1431838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1432838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1433838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o val = dnode_get(dn); 1434838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o key = dnode_getkey(dn); 1435838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_delete_free(d, dn); 1436838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1437838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free(val); 1438838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o free((void *) key); 1439838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1440838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'f': 1441838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_free(d); 1442838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1443838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'l': 1444838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case '(': 1445838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case ')': 1446838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (tokenize(in+1, &tok1, (char **) 0) != 1) { 1447838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("what?"); 1448838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1449838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1450838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dn = 0; 1451838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o switch (in[0]) { 1452838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'l': 1453838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dn = dict_lookup(d, tok1); 1454838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1455838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case '(': 1456838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dn = dict_lower_bound(d, tok1); 1457838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1458838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case ')': 1459838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dn = dict_upper_bound(d, tok1); 1460838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1461838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1462838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (!dn) { 1463838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("lookup failed"); 1464838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1465838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1466838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o val = dnode_get(dn); 1467838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts(val); 1468838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1469838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'm': 1470838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o construct(d); 1471838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1472838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'k': 1473838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_allow_dupes(d); 1474838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1475838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'c': 1476838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o printf("%lu\n", (unsigned long) dict_count(d)); 1477838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1478838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 't': 1479838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o for (dn = dict_first(d); dn; dn = dict_next(d, dn)) { 1480838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o printf("%s\t%s\n", (char *) dnode_getkey(dn), 1481838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o (char *) dnode_get(dn)); 1482838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1483838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1484838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'q': 1485838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o exit(0); 1486838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1487838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case '\0': 1488838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1489838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'p': 1490838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o prompt = 1; 1491838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1492838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 's': 1493838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_set_allocator(d, new_node, del_node, NULL); 1494838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1495838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case '#': 1496838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (tokenize(in+1, &tok1, (char **) 0) != 1) { 1497838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("what?"); 1498838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1499838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 1500838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o int dictnum = atoi(tok1); 1501838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (dictnum < 0 || dictnum > 9) { 1502838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("invalid number"); 1503838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1504838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1505838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o d = &darray[dictnum]; 1506838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1507838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1508838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o case 'j': 1509838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) { 1510838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("what?"); 1511838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1512838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } else { 1513838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o int dict1 = atoi(tok1), dict2 = atoi(tok2); 1514838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o if (dict1 < 0 || dict1 > 9 || dict2 < 0 || dict2 > 9) { 1515838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o puts("invalid number"); 1516838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1517838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1518838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o dict_merge(&darray[dict1], &darray[dict2]); 1519838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1520838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1521838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o default: 1522838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o putchar('?'); 1523838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o putchar('\n'); 1524838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o break; 1525838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1526838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o } 1527838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1528838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o return 0; 1529838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o} 1530838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o 1531838e773e7a6899cec10884ad6c3fdcdaef72b82bTheodore Ts'o#endif 1532