1
0

bintree_findprevious.c 2.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
  1. /*********************** -*- Mode: C -*- ***********************
  2. * File : bintree_findprevious.c
  3. *---------------------------------------------------------------
  4. * Description
  5. * ===========
  6. * This operation searches the specified "tree" for a "clientnode" which is
  7. * the one which logically preceeds the specified "key"
  8. *
  9. * A "clientnode" with the specified "key" doesn't need to be in the tree.
  10. *
  11. * tree - the "tree" instance to invoke this operation upon
  12. * key - the "key" to search with
  13. *
  14. * RETURNS
  15. * "clientnode" instance or NULL if no node is found.
  16. *---------------------------------------------------------------
  17. * Author : Graeme McKerrell
  18. * Created On : Wed Jan 28 10:33:12 2004
  19. * Status : TESTED
  20. *---------------------------------------------------------------
  21. * HISTORY
  22. * 7-Dec-2004 Graeme McKerrell
  23. * Renamed to the "lub_" namespace
  24. * 5-May-2004 Graeme McKerrell
  25. * updates following review
  26. * 27-Feb-2004 Graeme McKerrell
  27. * Fixed to account for empty tree
  28. * 9-Feb-2004 Graeme McKerrell
  29. * updated to use new node,key comparison ordering
  30. * 28-Jan-2004 Graeme McKerrell
  31. * Initial verison
  32. *---------------------------------------------------------------
  33. * Copyright (C) 2004 3Com Corporation. All Rights Reserved.
  34. **************************************************************** */
  35. #include "private.h"
  36. /*--------------------------------------------------------- */
  37. void *
  38. lub_bintree_findprevious(lub_bintree_t *this,
  39. const void *clientkey)
  40. {
  41. lub_bintree_node_t *t = this->root;
  42. int comp;
  43. /*
  44. * have a look for a direct match
  45. */
  46. t = this->root = lub_bintree_splay(this,t,clientkey);
  47. if(NULL != t)
  48. {
  49. /* now look at what we have got */
  50. comp = lub_bintree_compare(this,t,clientkey);
  51. if(comp >= 0)
  52. {
  53. /*
  54. * time to fiddle with the left hand side of the tree
  55. * we need the closest node from the left hand side
  56. */
  57. t = t->left = lub_bintree_splay(this,t->left,clientkey);
  58. }
  59. }
  60. if(NULL == t)
  61. {
  62. return NULL;
  63. }
  64. else
  65. {
  66. return lub_bintree_getclientnode(this,t);
  67. }
  68. }
  69. /*--------------------------------------------------------- */