18951Sgblack@eecs.umich.edu/* 28951Sgblack@eecs.umich.edu * Copyright (c) 2012 Google 38951Sgblack@eecs.umich.edu * All rights reserved. 48951Sgblack@eecs.umich.edu * 58951Sgblack@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 68951Sgblack@eecs.umich.edu * modification, are permitted provided that the following conditions are 78951Sgblack@eecs.umich.edu * met: redistributions of source code must retain the above copyright 88951Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 98951Sgblack@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 108951Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 118951Sgblack@eecs.umich.edu * documentation and/or other materials provided with the distribution; 128951Sgblack@eecs.umich.edu * neither the name of the copyright holders nor the names of its 138951Sgblack@eecs.umich.edu * contributors may be used to endorse or promote products derived from 148951Sgblack@eecs.umich.edu * this software without specific prior written permission. 158951Sgblack@eecs.umich.edu * 168951Sgblack@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 178951Sgblack@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 188951Sgblack@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 198951Sgblack@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 208951Sgblack@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 218951Sgblack@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 228951Sgblack@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 238951Sgblack@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 248951Sgblack@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 258951Sgblack@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 268951Sgblack@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 278951Sgblack@eecs.umich.edu * 288951Sgblack@eecs.umich.edu * Authors: Gabe Black 298951Sgblack@eecs.umich.edu */ 308951Sgblack@eecs.umich.edu 318951Sgblack@eecs.umich.edu#ifndef __BASE_TRIE_HH__ 328951Sgblack@eecs.umich.edu#define __BASE_TRIE_HH__ 338951Sgblack@eecs.umich.edu 348959Sgblack@eecs.umich.edu#include <cassert> 3512335Sgabeblack@google.com#include <iostream> 368959Sgblack@eecs.umich.edu 378951Sgblack@eecs.umich.edu#include "base/cprintf.hh" 3812334Sgabeblack@google.com#include "base/logging.hh" 398951Sgblack@eecs.umich.edu#include "base/types.hh" 408951Sgblack@eecs.umich.edu 418951Sgblack@eecs.umich.edu// Key has to be an integral type. 428951Sgblack@eecs.umich.edutemplate <class Key, class Value> 438951Sgblack@eecs.umich.educlass Trie 448951Sgblack@eecs.umich.edu{ 458951Sgblack@eecs.umich.edu protected: 468951Sgblack@eecs.umich.edu struct Node 478951Sgblack@eecs.umich.edu { 488951Sgblack@eecs.umich.edu Key key; 498951Sgblack@eecs.umich.edu Key mask; 508951Sgblack@eecs.umich.edu 518951Sgblack@eecs.umich.edu bool 528951Sgblack@eecs.umich.edu matches(Key test) 538951Sgblack@eecs.umich.edu { 548951Sgblack@eecs.umich.edu return (test & mask) == key; 558951Sgblack@eecs.umich.edu } 568951Sgblack@eecs.umich.edu 578951Sgblack@eecs.umich.edu Value *value; 588951Sgblack@eecs.umich.edu 598951Sgblack@eecs.umich.edu Node *parent; 608951Sgblack@eecs.umich.edu Node *kids[2]; 618951Sgblack@eecs.umich.edu 628951Sgblack@eecs.umich.edu Node(Key _key, Key _mask, Value *_val) : 638951Sgblack@eecs.umich.edu key(_key & _mask), mask(_mask), value(_val), 648951Sgblack@eecs.umich.edu parent(NULL) 658951Sgblack@eecs.umich.edu { 668951Sgblack@eecs.umich.edu kids[0] = NULL; 678951Sgblack@eecs.umich.edu kids[1] = NULL; 688951Sgblack@eecs.umich.edu } 698951Sgblack@eecs.umich.edu 708951Sgblack@eecs.umich.edu void 718951Sgblack@eecs.umich.edu clear() 728951Sgblack@eecs.umich.edu { 738951Sgblack@eecs.umich.edu if (kids[1]) { 748951Sgblack@eecs.umich.edu kids[1]->clear(); 758951Sgblack@eecs.umich.edu delete kids[1]; 768951Sgblack@eecs.umich.edu kids[1] = NULL; 778951Sgblack@eecs.umich.edu } 788951Sgblack@eecs.umich.edu if (kids[0]) { 798951Sgblack@eecs.umich.edu kids[0]->clear(); 808951Sgblack@eecs.umich.edu delete kids[0]; 818951Sgblack@eecs.umich.edu kids[0] = NULL; 828951Sgblack@eecs.umich.edu } 838951Sgblack@eecs.umich.edu } 848951Sgblack@eecs.umich.edu 858951Sgblack@eecs.umich.edu void 8612335Sgabeblack@google.com dump(std::ostream &os, int level) 878951Sgblack@eecs.umich.edu { 888951Sgblack@eecs.umich.edu for (int i = 1; i < level; i++) { 8912335Sgabeblack@google.com ccprintf(os, "|"); 908951Sgblack@eecs.umich.edu } 918951Sgblack@eecs.umich.edu if (level == 0) 9212335Sgabeblack@google.com ccprintf(os, "Root "); 938951Sgblack@eecs.umich.edu else 9412335Sgabeblack@google.com ccprintf(os, "+ "); 9512335Sgabeblack@google.com ccprintf(os, "(%p, %p, %#X, %#X, %p)\n", 9612335Sgabeblack@google.com parent, this, key, mask, value); 978951Sgblack@eecs.umich.edu if (kids[0]) 9812335Sgabeblack@google.com kids[0]->dump(os, level + 1); 998951Sgblack@eecs.umich.edu if (kids[1]) 10012335Sgabeblack@google.com kids[1]->dump(os, level + 1); 1018951Sgblack@eecs.umich.edu } 1028951Sgblack@eecs.umich.edu }; 1038951Sgblack@eecs.umich.edu 1048951Sgblack@eecs.umich.edu protected: 1058951Sgblack@eecs.umich.edu Node head; 1068951Sgblack@eecs.umich.edu 1078951Sgblack@eecs.umich.edu public: 1088951Sgblack@eecs.umich.edu typedef Node *Handle; 1098951Sgblack@eecs.umich.edu 1108951Sgblack@eecs.umich.edu Trie() : head(0, 0, NULL) 1118951Sgblack@eecs.umich.edu {} 1128951Sgblack@eecs.umich.edu 1138951Sgblack@eecs.umich.edu static const unsigned MaxBits = sizeof(Key) * 8; 1148951Sgblack@eecs.umich.edu 1158951Sgblack@eecs.umich.edu private: 1168951Sgblack@eecs.umich.edu /** 1178951Sgblack@eecs.umich.edu * A utility method which checks whether the key being looked up lies 1188951Sgblack@eecs.umich.edu * beyond the Node being examined. If so, it returns true and advances the 1198951Sgblack@eecs.umich.edu * node being examined. 1208951Sgblack@eecs.umich.edu * @param parent The node we're currently "at", which can be updated. 1218951Sgblack@eecs.umich.edu * @param kid The node we may want to move to. 1228951Sgblack@eecs.umich.edu * @param key The key we're looking for. 1238951Sgblack@eecs.umich.edu * @param new_mask The mask to use when matching against the key. 1248951Sgblack@eecs.umich.edu * @return Whether the current Node was advanced. 1258951Sgblack@eecs.umich.edu */ 1268951Sgblack@eecs.umich.edu bool 1278951Sgblack@eecs.umich.edu goesAfter(Node **parent, Node *kid, Key key, Key new_mask) 1288951Sgblack@eecs.umich.edu { 1298951Sgblack@eecs.umich.edu if (kid && kid->matches(key) && (kid->mask & new_mask) == kid->mask) { 1308951Sgblack@eecs.umich.edu *parent = kid; 1318951Sgblack@eecs.umich.edu return true; 1328951Sgblack@eecs.umich.edu } else { 1338951Sgblack@eecs.umich.edu return false; 1348951Sgblack@eecs.umich.edu } 1358951Sgblack@eecs.umich.edu } 1368951Sgblack@eecs.umich.edu 1378951Sgblack@eecs.umich.edu /** 1388951Sgblack@eecs.umich.edu * A utility method which extends a mask value one more bit towards the 1398951Sgblack@eecs.umich.edu * lsb. This is almost just a signed right shift, except that the shifted 1408951Sgblack@eecs.umich.edu * in bits are technically undefined. This is also slightly complicated by 1418951Sgblack@eecs.umich.edu * the zero case. 1428951Sgblack@eecs.umich.edu * @param orig The original mask to extend. 1438951Sgblack@eecs.umich.edu * @return The extended mask. 1448951Sgblack@eecs.umich.edu */ 1458951Sgblack@eecs.umich.edu Key 1468951Sgblack@eecs.umich.edu extendMask(Key orig) 1478951Sgblack@eecs.umich.edu { 1488951Sgblack@eecs.umich.edu // Just in case orig was 0. 1498951Sgblack@eecs.umich.edu const Key msb = ULL(1) << (MaxBits - 1); 1508951Sgblack@eecs.umich.edu return orig | (orig >> 1) | msb; 1518951Sgblack@eecs.umich.edu } 1528951Sgblack@eecs.umich.edu 1538951Sgblack@eecs.umich.edu /** 1548951Sgblack@eecs.umich.edu * Method which looks up the Handle corresponding to a particular key. This 1558952Sgblack@eecs.umich.edu * is useful if you want to delete the Handle corresponding to a key since 1568952Sgblack@eecs.umich.edu * the "remove" function takes a Handle as its argument. 1578951Sgblack@eecs.umich.edu * @param key The key to look up. 1588952Sgblack@eecs.umich.edu * @return The first Handle matching this key, or NULL if none was found. 1598951Sgblack@eecs.umich.edu */ 1608951Sgblack@eecs.umich.edu Handle 1618951Sgblack@eecs.umich.edu lookupHandle(Key key) 1628951Sgblack@eecs.umich.edu { 1638951Sgblack@eecs.umich.edu Node *node = &head; 1648951Sgblack@eecs.umich.edu while (node) { 1658951Sgblack@eecs.umich.edu if (node->value) 1668951Sgblack@eecs.umich.edu return node; 1678951Sgblack@eecs.umich.edu 1688951Sgblack@eecs.umich.edu if (node->kids[0] && node->kids[0]->matches(key)) 1698951Sgblack@eecs.umich.edu node = node->kids[0]; 1708951Sgblack@eecs.umich.edu else if (node->kids[1] && node->kids[1]->matches(key)) 1718951Sgblack@eecs.umich.edu node = node->kids[1]; 1728951Sgblack@eecs.umich.edu else 1738951Sgblack@eecs.umich.edu node = NULL; 1748951Sgblack@eecs.umich.edu } 1758951Sgblack@eecs.umich.edu 1768951Sgblack@eecs.umich.edu return NULL; 1778951Sgblack@eecs.umich.edu } 1788951Sgblack@eecs.umich.edu 1798951Sgblack@eecs.umich.edu public: 1808951Sgblack@eecs.umich.edu /** 1818951Sgblack@eecs.umich.edu * Method which inserts a key/value pair into the trie. 1828951Sgblack@eecs.umich.edu * @param key The key which can later be used to look up this value. 1838951Sgblack@eecs.umich.edu * @param width How many bits of the key (from msb) should be used. 1848951Sgblack@eecs.umich.edu * @param val A pointer to the value to store in the trie. 1858952Sgblack@eecs.umich.edu * @return A Handle corresponding to this value. 1868951Sgblack@eecs.umich.edu */ 1878951Sgblack@eecs.umich.edu Handle 1888951Sgblack@eecs.umich.edu insert(Key key, unsigned width, Value *val) 1898951Sgblack@eecs.umich.edu { 19012332Sgabeblack@google.com // We use NULL value pointers to mark internal nodes of the trie, so 19112332Sgabeblack@google.com // we don't allow inserting them as real values. 19212332Sgabeblack@google.com assert(val); 19312332Sgabeblack@google.com 1948951Sgblack@eecs.umich.edu // Build a mask which masks off all the bits we don't care about. 1958951Sgblack@eecs.umich.edu Key new_mask = ~(Key)0; 1968951Sgblack@eecs.umich.edu if (width < MaxBits) 1978951Sgblack@eecs.umich.edu new_mask <<= (MaxBits - width); 1988951Sgblack@eecs.umich.edu // Use it to tidy up the key. 1998951Sgblack@eecs.umich.edu key &= new_mask; 2008951Sgblack@eecs.umich.edu 2018951Sgblack@eecs.umich.edu // Walk past all the nodes this new node will be inserted after. They 2028951Sgblack@eecs.umich.edu // can be ignored for the purposes of this function. 2038951Sgblack@eecs.umich.edu Node *node = &head; 2048951Sgblack@eecs.umich.edu while (goesAfter(&node, node->kids[0], key, new_mask) || 2058951Sgblack@eecs.umich.edu goesAfter(&node, node->kids[1], key, new_mask)) 2068951Sgblack@eecs.umich.edu {} 2078951Sgblack@eecs.umich.edu assert(node); 2088951Sgblack@eecs.umich.edu 2098951Sgblack@eecs.umich.edu Key cur_mask = node->mask; 2108951Sgblack@eecs.umich.edu // If we're already where the value needs to be... 2118951Sgblack@eecs.umich.edu if (cur_mask == new_mask) { 2128951Sgblack@eecs.umich.edu assert(!node->value); 2138951Sgblack@eecs.umich.edu node->value = val; 2148951Sgblack@eecs.umich.edu return node; 2158951Sgblack@eecs.umich.edu } 2168951Sgblack@eecs.umich.edu 2178951Sgblack@eecs.umich.edu for (unsigned int i = 0; i < 2; i++) { 2188951Sgblack@eecs.umich.edu Node *&kid = node->kids[i]; 2198951Sgblack@eecs.umich.edu Node *new_node; 2208951Sgblack@eecs.umich.edu if (!kid) { 2218951Sgblack@eecs.umich.edu // No kid. Add a new one. 2228951Sgblack@eecs.umich.edu new_node = new Node(key, new_mask, val); 2238951Sgblack@eecs.umich.edu new_node->parent = node; 2248951Sgblack@eecs.umich.edu kid = new_node; 2258951Sgblack@eecs.umich.edu return new_node; 2268951Sgblack@eecs.umich.edu } 2278951Sgblack@eecs.umich.edu 2288951Sgblack@eecs.umich.edu // Walk down the leg until something doesn't match or we run out 2298951Sgblack@eecs.umich.edu // of bits. 2308951Sgblack@eecs.umich.edu Key last_mask; 2318951Sgblack@eecs.umich.edu bool done; 2328951Sgblack@eecs.umich.edu do { 2338951Sgblack@eecs.umich.edu last_mask = cur_mask; 2348951Sgblack@eecs.umich.edu cur_mask = extendMask(cur_mask); 2358951Sgblack@eecs.umich.edu done = ((key & cur_mask) != (kid->key & cur_mask)) || 2368951Sgblack@eecs.umich.edu last_mask == new_mask; 2378951Sgblack@eecs.umich.edu } while (!done); 2388951Sgblack@eecs.umich.edu cur_mask = last_mask; 2398951Sgblack@eecs.umich.edu 2408951Sgblack@eecs.umich.edu // If this isn't the right leg to go down at all, skip it. 2418951Sgblack@eecs.umich.edu if (cur_mask == node->mask) 2428951Sgblack@eecs.umich.edu continue; 2438951Sgblack@eecs.umich.edu 2448951Sgblack@eecs.umich.edu // At the point we walked to above, add a new node. 2458951Sgblack@eecs.umich.edu new_node = new Node(key, cur_mask, NULL); 2468951Sgblack@eecs.umich.edu new_node->parent = node; 2478951Sgblack@eecs.umich.edu kid->parent = new_node; 2488951Sgblack@eecs.umich.edu new_node->kids[0] = kid; 2498951Sgblack@eecs.umich.edu kid = new_node; 2508951Sgblack@eecs.umich.edu 2518951Sgblack@eecs.umich.edu // If we ran out of bits, the value goes right here. 2528951Sgblack@eecs.umich.edu if (cur_mask == new_mask) { 2538951Sgblack@eecs.umich.edu new_node->value = val; 2548951Sgblack@eecs.umich.edu return new_node; 2558951Sgblack@eecs.umich.edu } 2568951Sgblack@eecs.umich.edu 2578951Sgblack@eecs.umich.edu // Still more bits to deal with, so add a new node for that path. 2588951Sgblack@eecs.umich.edu new_node = new Node(key, new_mask, val); 2598951Sgblack@eecs.umich.edu new_node->parent = kid; 2608951Sgblack@eecs.umich.edu kid->kids[1] = new_node; 2618951Sgblack@eecs.umich.edu return new_node; 2628951Sgblack@eecs.umich.edu } 2638951Sgblack@eecs.umich.edu 2648951Sgblack@eecs.umich.edu panic("Reached the end of the Trie insert function!\n"); 2658951Sgblack@eecs.umich.edu return NULL; 2668951Sgblack@eecs.umich.edu } 2678951Sgblack@eecs.umich.edu 2688951Sgblack@eecs.umich.edu /** 2698951Sgblack@eecs.umich.edu * Method which looks up the Value corresponding to a particular key. 2708951Sgblack@eecs.umich.edu * @param key The key to look up. 2718951Sgblack@eecs.umich.edu * @return The first Value matching this key, or NULL if none was found. 2728951Sgblack@eecs.umich.edu */ 2738951Sgblack@eecs.umich.edu Value * 2748951Sgblack@eecs.umich.edu lookup(Key key) 2758951Sgblack@eecs.umich.edu { 2768951Sgblack@eecs.umich.edu Node *node = lookupHandle(key); 2778951Sgblack@eecs.umich.edu if (node) 2788951Sgblack@eecs.umich.edu return node->value; 2798951Sgblack@eecs.umich.edu else 2808951Sgblack@eecs.umich.edu return NULL; 2818951Sgblack@eecs.umich.edu } 2828951Sgblack@eecs.umich.edu 2838951Sgblack@eecs.umich.edu /** 2848951Sgblack@eecs.umich.edu * Method to delete a value from the trie. 2858952Sgblack@eecs.umich.edu * @param node A Handle to remove. 2868951Sgblack@eecs.umich.edu * @return The Value pointer from the removed entry. 2878951Sgblack@eecs.umich.edu */ 2888951Sgblack@eecs.umich.edu Value * 2898951Sgblack@eecs.umich.edu remove(Handle handle) 2908951Sgblack@eecs.umich.edu { 2918951Sgblack@eecs.umich.edu Node *node = handle; 2928951Sgblack@eecs.umich.edu Value *val = node->value; 2938951Sgblack@eecs.umich.edu if (node->kids[1]) { 2948951Sgblack@eecs.umich.edu assert(node->value); 2958951Sgblack@eecs.umich.edu node->value = NULL; 2968951Sgblack@eecs.umich.edu return val; 2978951Sgblack@eecs.umich.edu } 2988951Sgblack@eecs.umich.edu if (!node->parent) 2998951Sgblack@eecs.umich.edu panic("Trie: Can't remove root node.\n"); 3008951Sgblack@eecs.umich.edu 3018951Sgblack@eecs.umich.edu Node *parent = node->parent; 3028951Sgblack@eecs.umich.edu 3038951Sgblack@eecs.umich.edu // If there's a kid, fix up it's parent pointer. 3048951Sgblack@eecs.umich.edu if (node->kids[0]) 3058951Sgblack@eecs.umich.edu node->kids[0]->parent = parent; 3068951Sgblack@eecs.umich.edu // Figure out which kid we are, and update our parent's pointers. 3078951Sgblack@eecs.umich.edu if (parent->kids[0] == node) 3088951Sgblack@eecs.umich.edu parent->kids[0] = node->kids[0]; 3098951Sgblack@eecs.umich.edu else if (parent->kids[1] == node) 3108951Sgblack@eecs.umich.edu parent->kids[1] = node->kids[0]; 3118951Sgblack@eecs.umich.edu else 3128951Sgblack@eecs.umich.edu panic("Trie: Inconsistent parent/kid relationship.\n"); 3138951Sgblack@eecs.umich.edu // Make sure if the parent only has one kid, it's kid[0]. 3148951Sgblack@eecs.umich.edu if (parent->kids[1] && !parent->kids[0]) { 3158951Sgblack@eecs.umich.edu parent->kids[0] = parent->kids[1]; 3168951Sgblack@eecs.umich.edu parent->kids[1] = NULL; 3178951Sgblack@eecs.umich.edu } 3188951Sgblack@eecs.umich.edu 3198951Sgblack@eecs.umich.edu // If the parent has less than two kids and no cargo and isn't the 3208951Sgblack@eecs.umich.edu // root, delete it too. 3218951Sgblack@eecs.umich.edu if (!parent->kids[1] && !parent->value && parent->parent) 3228951Sgblack@eecs.umich.edu remove(parent); 3238951Sgblack@eecs.umich.edu delete node; 3248951Sgblack@eecs.umich.edu return val; 3258951Sgblack@eecs.umich.edu } 3268951Sgblack@eecs.umich.edu 3278951Sgblack@eecs.umich.edu /** 3288951Sgblack@eecs.umich.edu * Method to lookup a value from the trie and then delete it. 3298951Sgblack@eecs.umich.edu * @param key The key to look up and then remove. 3308951Sgblack@eecs.umich.edu * @return The Value pointer from the removed entry, if any. 3318951Sgblack@eecs.umich.edu */ 3328951Sgblack@eecs.umich.edu Value * 3338951Sgblack@eecs.umich.edu remove(Key key) 3348951Sgblack@eecs.umich.edu { 3358951Sgblack@eecs.umich.edu Handle handle = lookupHandle(key); 3368951Sgblack@eecs.umich.edu if (!handle) 3378951Sgblack@eecs.umich.edu return NULL; 3388951Sgblack@eecs.umich.edu return remove(handle); 3398951Sgblack@eecs.umich.edu } 3408951Sgblack@eecs.umich.edu 3418951Sgblack@eecs.umich.edu /** 3428951Sgblack@eecs.umich.edu * A method which removes all key/value pairs from the trie. This is more 3438951Sgblack@eecs.umich.edu * efficient than trying to remove elements individually. 3448951Sgblack@eecs.umich.edu */ 3458951Sgblack@eecs.umich.edu void 3468951Sgblack@eecs.umich.edu clear() 3478951Sgblack@eecs.umich.edu { 3488951Sgblack@eecs.umich.edu head.clear(); 3498951Sgblack@eecs.umich.edu } 3508951Sgblack@eecs.umich.edu 3518951Sgblack@eecs.umich.edu /** 3528951Sgblack@eecs.umich.edu * A debugging method which prints the contents of this trie. 3538951Sgblack@eecs.umich.edu * @param title An identifying title to put in the dump header. 3548951Sgblack@eecs.umich.edu */ 3558951Sgblack@eecs.umich.edu void 35612335Sgabeblack@google.com dump(const char *title, std::ostream &os=std::cout) 3578951Sgblack@eecs.umich.edu { 35812335Sgabeblack@google.com ccprintf(os, "**************************************************\n"); 35912335Sgabeblack@google.com ccprintf(os, "*** Start of Trie: %s\n", title); 36012335Sgabeblack@google.com ccprintf(os, "*** (parent, me, key, mask, value pointer)\n"); 36112335Sgabeblack@google.com ccprintf(os, "**************************************************\n"); 36212335Sgabeblack@google.com head.dump(os, 0); 3638951Sgblack@eecs.umich.edu } 3648951Sgblack@eecs.umich.edu}; 3658951Sgblack@eecs.umich.edu 3668951Sgblack@eecs.umich.edu#endif 367