Back to index

lightning-sunbird  0.9+nobinonly
PatriciaTree.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is Mozilla Communicator client code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Simon Fraser <sfraser@netscape.com>
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either of the GNU General Public License Version 2 or later (the "GPL"),
00027  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 
00040 #include <AEUtils.h>
00041 
00042 #include "PatriciaTree.h"
00043 
00044 
00045 /*----------------------------------------------------------------------------
00046        CPatriciaTree
00047        
00048 ----------------------------------------------------------------------------*/
00049 CPatriciaTree::CPatriciaTree(long keyBitsLen)
00050 :      mTree(nil)
00051 ,      mKeyBits(keyBitsLen)
00052 {
00053 
00054        mTree = PatriciaInitTree(mKeyBits);
00055        ThrowErrIfNil(mTree, paramErr);
00056 }
00057 
00058 /*----------------------------------------------------------------------------
00059        ~CPatriciaTree
00060        
00061 ----------------------------------------------------------------------------*/
00062 CPatriciaTree::~CPatriciaTree()
00063 {
00064        if (mTree)
00065        {
00066               PatriciaFreeTree(mTree, NodeFreeCallback, (void *)this);
00067        }
00068 }
00069 
00070 
00071 #pragma mark -
00072 
00073 /*----------------------------------------------------------------------------
00074        InsertNode
00075        
00076        Insert a node. Call the class's replace function by default.
00077        
00078        Returns true if replaced
00079 ----------------------------------------------------------------------------*/
00080 Boolean CPatriciaTree::InsertNode(TPatriciaKey key, CPatriciaNode* nodeData)
00081 {
00082        int    result = PatriciaInsert(mTree, NodeReplaceCallback, key, (void *)nodeData, (void *)this);
00083        return (result == 1);
00084 }
00085 
00086 /*----------------------------------------------------------------------------
00087        SeekNode
00088        
00089        Look for the node with the given key. Returns true if found
00090 ----------------------------------------------------------------------------*/
00091 Boolean CPatriciaTree::SeekNode(TPatriciaKey key, CPatriciaNode**outNodeData)
00092 {
00093        int    result = PatriciaSearch(mTree, key, (void **)outNodeData);
00094        return (result == 1);
00095 }
00096 
00097 /*----------------------------------------------------------------------------
00098        Traverse
00099        
00100        Traverse over every node in the tree. Returns true if traversed the entire
00101        tree without halting.
00102 ----------------------------------------------------------------------------*/
00103 Boolean CPatriciaTree::Traverse(NodeTraverseFunction traverseFcn, void *arg, void *refCon)
00104 {
00105        int    result = PatriciaTraverse(mTree, traverseFcn, arg, refCon);
00106        return (result == 0);
00107 }
00108 
00109 
00110 /*----------------------------------------------------------------------------
00111        GetNumNodes
00112        
00113        Get the number of entries in the tree
00114 ----------------------------------------------------------------------------*/
00115 long CPatriciaTree::GetNumNodes()
00116 {
00117        return (mTree) ? PatriciaGetNumNodes(mTree) : 0;
00118 }
00119 
00120 
00121 #pragma mark -
00122 
00123 /*----------------------------------------------------------------------------
00124        ReplaceNode
00125        
00126        Detault replace node implementation. Does nothing.
00127        
00128 ----------------------------------------------------------------------------*/
00129 int CPatriciaTree::ReplaceNode(CPatriciaNode**nodeDataPtr, TPatriciaKey key, CPatriciaNode *replaceData)
00130 {
00131        return 0;
00132 }
00133 
00134 /*----------------------------------------------------------------------------
00135        FreeNode
00136        
00137        Detault free node implementation. Does nothing.
00138        
00139 ----------------------------------------------------------------------------*/
00140 int CPatriciaTree::FreeNode(CPatriciaNode *nodeData, TPatriciaKey key)
00141 {
00142        return 0;
00143 }
00144 
00145 
00146 #pragma mark -
00147 
00148 /*----------------------------------------------------------------------------
00149        NodeReplaceCallback
00150        
00151        [static]
00152        
00153 ----------------------------------------------------------------------------*/
00154 int CPatriciaTree::NodeReplaceCallback(void**nodeDataPtr, unsigned char *key, void *replaceData, void *refCon)
00155 {
00156        CPatriciaTree*              theTree = reinterpret_cast<CPatriciaTree *>(refCon);
00157        Assert(theTree);
00158        return theTree->ReplaceNode((CPatriciaNode**)nodeDataPtr, key, static_cast<CPatriciaNode *>(replaceData));
00159 }
00160 
00161 /*----------------------------------------------------------------------------
00162        NodeTraverseCallback
00163        
00164        [static]
00165        
00166 ----------------------------------------------------------------------------*/
00167 int CPatriciaTree::NodeFreeCallback(void *nodeData, unsigned char *key, void *refCon)
00168 {
00169        CPatriciaTree*              theTree = reinterpret_cast<CPatriciaTree *>(refCon);
00170        Assert(theTree);
00171        return theTree->FreeNode(static_cast<CPatriciaNode *>(nodeData), key);
00172 }
00173