trie.hh (8951:4347de090956) | trie.hh (8952:6188362beee1) |
---|---|
1/* 2 * Copyright (c) 2012 Google 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; --- 134 unchanged lines hidden (view full) --- 143 { 144 // Just in case orig was 0. 145 const Key msb = ULL(1) << (MaxBits - 1); 146 return orig | (orig >> 1) | msb; 147 } 148 149 /** 150 * Method which looks up the Handle corresponding to a particular key. This | 1/* 2 * Copyright (c) 2012 Google 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; --- 134 unchanged lines hidden (view full) --- 143 { 144 // Just in case orig was 0. 145 const Key msb = ULL(1) << (MaxBits - 1); 146 return orig | (orig >> 1) | msb; 147 } 148 149 /** 150 * Method which looks up the Handle corresponding to a particular key. This |
151 * is useful if you want to delete the Node corresponding to a key since 152 * the "remove" function takes a Node as its argument. | 151 * is useful if you want to delete the Handle corresponding to a key since 152 * the "remove" function takes a Handle as its argument. |
153 * @param key The key to look up. | 153 * @param key The key to look up. |
154 * @return The first Node matching this key, or NULL if none was found. | 154 * @return The first Handle matching this key, or NULL if none was found. |
155 */ 156 Handle 157 lookupHandle(Key key) 158 { 159 Node *node = &head; 160 while (node) { 161 if (node->value) 162 return node; --- 10 unchanged lines hidden (view full) --- 173 } 174 175 public: 176 /** 177 * Method which inserts a key/value pair into the trie. 178 * @param key The key which can later be used to look up this value. 179 * @param width How many bits of the key (from msb) should be used. 180 * @param val A pointer to the value to store in the trie. | 155 */ 156 Handle 157 lookupHandle(Key key) 158 { 159 Node *node = &head; 160 while (node) { 161 if (node->value) 162 return node; --- 10 unchanged lines hidden (view full) --- 173 } 174 175 public: 176 /** 177 * Method which inserts a key/value pair into the trie. 178 * @param key The key which can later be used to look up this value. 179 * @param width How many bits of the key (from msb) should be used. 180 * @param val A pointer to the value to store in the trie. |
181 * @return A pointer to the Node which holds this value. | 181 * @return A Handle corresponding to this value. |
182 */ 183 Handle 184 insert(Key key, unsigned width, Value *val) 185 { 186 // Build a mask which masks off all the bits we don't care about. 187 Key new_mask = ~(Key)0; 188 if (width < MaxBits) 189 new_mask <<= (MaxBits - width); --- 79 unchanged lines hidden (view full) --- 269 if (node) 270 return node->value; 271 else 272 return NULL; 273 } 274 275 /** 276 * Method to delete a value from the trie. | 182 */ 183 Handle 184 insert(Key key, unsigned width, Value *val) 185 { 186 // Build a mask which masks off all the bits we don't care about. 187 Key new_mask = ~(Key)0; 188 if (width < MaxBits) 189 new_mask <<= (MaxBits - width); --- 79 unchanged lines hidden (view full) --- 269 if (node) 270 return node->value; 271 else 272 return NULL; 273 } 274 275 /** 276 * Method to delete a value from the trie. |
277 * @param node A pointer to the Node to remove. | 277 * @param node A Handle to remove. |
278 * @return The Value pointer from the removed entry. 279 */ 280 Value * 281 remove(Handle handle) 282 { 283 Node *node = handle; 284 Value *val = node->value; 285 if (node->kids[1]) { --- 73 unchanged lines hidden --- | 278 * @return The Value pointer from the removed entry. 279 */ 280 Value * 281 remove(Handle handle) 282 { 283 Node *node = handle; 284 Value *val = node->value; 285 if (node->kids[1]) { --- 73 unchanged lines hidden --- |