LabelSplicer.h 2.2 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
  1. /* vim: set expandtab ts=4 sw=4: */
  2. /*
  3. * You may redistribute this program and/or modify it under the terms of
  4. * the GNU General Public License as published by the Free Software Foundation,
  5. * either version 3 of the License, or (at your option) any later version.
  6. *
  7. * This program is distributed in the hope that it will be useful,
  8. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  9. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  10. * GNU General Public License for more details.
  11. *
  12. * You should have received a copy of the GNU General Public License
  13. * along with this program. If not, see <https://www.gnu.org/licenses/>.
  14. */
  15. #ifndef LabelSplicer_H
  16. #define LabelSplicer_H
  17. #include "util/Bits.h"
  18. #include <stdint.h>
  19. #include <stdbool.h>
  20. /**
  21. * Convert a full path (represention we can use) to a representaiton which a node
  22. * along that path can use.
  23. *
  24. * @param fullPath the full route to the destination
  25. * @param midPath a path to a node which falls somewhere within fullPath
  26. * @return a version of fullPath which is sutible for use by node at midPath
  27. */
  28. static inline uint64_t LabelSplicer_unsplice(uint64_t fullPath, uint64_t midPath)
  29. {
  30. return fullPath >> Bits_log2x64(midPath);
  31. }
  32. /**
  33. * Splice a label and a label fragment together.
  34. *
  35. */
  36. static inline uint64_t LabelSplicer_splice(uint64_t goHere, uint64_t viaHere)
  37. {
  38. uint64_t log2ViaHere = Bits_log2x64(viaHere);
  39. if (Bits_log2x64(goHere) + log2ViaHere > 59) {
  40. // Too big, can't splice.
  41. return UINT64_MAX;
  42. }
  43. return ((goHere ^ 1) << log2ViaHere) ^ viaHere;
  44. }
  45. /**
  46. * Determine if the route to one node passes through another node.
  47. * Given:
  48. * 1. alice->bob->charlie->fred->bob
  49. * 2. alice->bob
  50. * 1 routes through 2.
  51. *
  52. * @param destination the node to route to.
  53. * @param midPath the node which might be in the middle of the route.
  54. * @return true if midPath is in the middle of the route to destination.
  55. */
  56. static inline bool LabelSplicer_routesThrough(uint64_t destination, uint64_t midPath)
  57. {
  58. if (midPath > destination) {
  59. return false;
  60. } if (midPath < 2) {
  61. return true;
  62. }
  63. uint64_t mask = UINT64_MAX >> (64 - Bits_log2x64(midPath));
  64. return (destination & mask) == (midPath & mask);
  65. }
  66. #endif