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 ---