Mercurial > hg > nginx-quic
comparison src/core/ngx_radix_tree.c @ 4992:3be3de31d7dd
Geo: IPv6 support.
The "ranges" mode is still limited to IPv4 only.
author | Ruslan Ermilov <ru@nginx.com> |
---|---|
date | Tue, 25 Dec 2012 08:21:56 +0000 |
parents | 6b416e3bdd26 |
children |
comparison
equal
deleted
inserted
replaced
4991:a384c60d55f3 | 4992:3be3de31d7dd |
---|---|
261 | 261 |
262 return value; | 262 return value; |
263 } | 263 } |
264 | 264 |
265 | 265 |
266 #if (NGX_HAVE_INET6) | |
267 | |
268 ngx_int_t | |
269 ngx_radix128tree_insert(ngx_radix_tree_t *tree, u_char *key, u_char *mask, | |
270 uintptr_t value) | |
271 { | |
272 u_char bit; | |
273 ngx_uint_t i; | |
274 ngx_radix_node_t *node, *next; | |
275 | |
276 i = 0; | |
277 bit = 0x80; | |
278 | |
279 node = tree->root; | |
280 next = tree->root; | |
281 | |
282 while (bit & mask[i]) { | |
283 if (key[i] & bit) { | |
284 next = node->right; | |
285 | |
286 } else { | |
287 next = node->left; | |
288 } | |
289 | |
290 if (next == NULL) { | |
291 break; | |
292 } | |
293 | |
294 bit >>= 1; | |
295 node = next; | |
296 | |
297 if (bit == 0) { | |
298 if (++i == 16) { | |
299 break; | |
300 } | |
301 | |
302 bit = 0x80; | |
303 } | |
304 } | |
305 | |
306 if (next) { | |
307 if (node->value != NGX_RADIX_NO_VALUE) { | |
308 return NGX_BUSY; | |
309 } | |
310 | |
311 node->value = value; | |
312 return NGX_OK; | |
313 } | |
314 | |
315 while (bit & mask[i]) { | |
316 next = ngx_radix_alloc(tree); | |
317 if (next == NULL) { | |
318 return NGX_ERROR; | |
319 } | |
320 | |
321 next->right = NULL; | |
322 next->left = NULL; | |
323 next->parent = node; | |
324 next->value = NGX_RADIX_NO_VALUE; | |
325 | |
326 if (key[i] & bit) { | |
327 node->right = next; | |
328 | |
329 } else { | |
330 node->left = next; | |
331 } | |
332 | |
333 bit >>= 1; | |
334 node = next; | |
335 | |
336 if (bit == 0) { | |
337 if (++i == 16) { | |
338 break; | |
339 } | |
340 | |
341 bit = 0x80; | |
342 } | |
343 } | |
344 | |
345 node->value = value; | |
346 | |
347 return NGX_OK; | |
348 } | |
349 | |
350 | |
351 ngx_int_t | |
352 ngx_radix128tree_delete(ngx_radix_tree_t *tree, u_char *key, u_char *mask) | |
353 { | |
354 u_char bit; | |
355 ngx_uint_t i; | |
356 ngx_radix_node_t *node; | |
357 | |
358 i = 0; | |
359 bit = 0x80; | |
360 node = tree->root; | |
361 | |
362 while (node && (bit & mask[i])) { | |
363 if (key[i] & bit) { | |
364 node = node->right; | |
365 | |
366 } else { | |
367 node = node->left; | |
368 } | |
369 | |
370 bit >>= 1; | |
371 | |
372 if (bit == 0) { | |
373 if (++i == 16) { | |
374 break; | |
375 } | |
376 | |
377 bit = 0x80; | |
378 } | |
379 } | |
380 | |
381 if (node == NULL) { | |
382 return NGX_ERROR; | |
383 } | |
384 | |
385 if (node->right || node->left) { | |
386 if (node->value != NGX_RADIX_NO_VALUE) { | |
387 node->value = NGX_RADIX_NO_VALUE; | |
388 return NGX_OK; | |
389 } | |
390 | |
391 return NGX_ERROR; | |
392 } | |
393 | |
394 for ( ;; ) { | |
395 if (node->parent->right == node) { | |
396 node->parent->right = NULL; | |
397 | |
398 } else { | |
399 node->parent->left = NULL; | |
400 } | |
401 | |
402 node->right = tree->free; | |
403 tree->free = node; | |
404 | |
405 node = node->parent; | |
406 | |
407 if (node->right || node->left) { | |
408 break; | |
409 } | |
410 | |
411 if (node->value != NGX_RADIX_NO_VALUE) { | |
412 break; | |
413 } | |
414 | |
415 if (node->parent == NULL) { | |
416 break; | |
417 } | |
418 } | |
419 | |
420 return NGX_OK; | |
421 } | |
422 | |
423 | |
424 uintptr_t | |
425 ngx_radix128tree_find(ngx_radix_tree_t *tree, u_char *key) | |
426 { | |
427 u_char bit; | |
428 uintptr_t value; | |
429 ngx_uint_t i; | |
430 ngx_radix_node_t *node; | |
431 | |
432 i = 0; | |
433 bit = 0x80; | |
434 value = NGX_RADIX_NO_VALUE; | |
435 node = tree->root; | |
436 | |
437 while (node) { | |
438 if (node->value != NGX_RADIX_NO_VALUE) { | |
439 value = node->value; | |
440 } | |
441 | |
442 if (key[i] & bit) { | |
443 node = node->right; | |
444 | |
445 } else { | |
446 node = node->left; | |
447 } | |
448 | |
449 bit >>= 1; | |
450 | |
451 if (bit == 0) { | |
452 i++; | |
453 bit = 0x80; | |
454 } | |
455 } | |
456 | |
457 return value; | |
458 } | |
459 | |
460 #endif | |
461 | |
462 | |
266 static ngx_radix_node_t * | 463 static ngx_radix_node_t * |
267 ngx_radix_alloc(ngx_radix_tree_t *tree) | 464 ngx_radix_alloc(ngx_radix_tree_t *tree) |
268 { | 465 { |
269 ngx_radix_node_t *p; | 466 ngx_radix_node_t *p; |
270 | 467 |