Posted to tcl by kbk at Wed Oct 16 20:01:22 GMT 2019view raw

  1. static inline unsigned char
  2. Patricia_bit(unsigned char* s, size_t l, int b)
  3. {
  4. if (b < 0 || b >= 8*l) {
  5. return 0;
  6. } else {
  7. int c = b>>3;
  8. int cb = b & 0x7;
  9. return !!(s[c] & (0x80 >> cb));
  10. }
  11. }
  12.  
  13.  
  14. int
  15. Patricia_search(const Patricia* tree, unsigned char* name)
  16. {
  17. int p = 0;
  18. size_t len = strlen(name);
  19. int x = tree[p].left;
  20. while (tree[p].bit < tree[x].bit) {
  21. p = x;
  22. x = (Patricia_bit(name, len, tree[x].bit)) ?
  23. tree[x].right : tree[x].left;
  24. }
  25. if (!strcmp(name, tree[x].key)) {
  26. return x;
  27. } else {
  28. return -1;
  29. }
  30. }