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