Advertisement
Guest User

Untitled

a guest
Jul 21st, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.79 KB | None | 0 0
  1. // Gibt das kleinste j zurück, so dass element <= j und k_level[j]=1
  2. // Hierbei beachten, dass j zwar Bitweise adressiert wird, die Level-Arrays allerdings ganze 64-Bit-Blöcke besitzen. Somit ist z.B: root_top[5] nicht das 6.
  3. // Bit sondern, der 6. 64-Bit-Block. Die Methode gibt aber die Bit-Position zurück!
  4. #[inline]
  5. fn locate_top_level(&mut self, bit: Int, level: u8) -> Option<Int> {
  6. let index = bit as usize/64;
  7. let in_index = bit%64;
  8. // Da der Index von links nach rechts gezählt wird, aber 2^i mit i=index von rechts nach Links gilt, muss 64-in_index gerechnet werden.
  9. // Diese Bit_Maske dient dem Nullen der Zahlen hinter in_index
  10. let bit_mask: u64 = (1 << (64-in_index))-1; // genau falschherum
  11. // Siehe Paper, irgendwo muss noch Fill Zeros implementiert werden
  12.  
  13. if level != 0 {
  14. for i in index..self.root_top_sub.len() {
  15. if self.root_top_sub[i] != 0 {
  16. let nulls = self.root_top_sub[i].leading_zeros();
  17. return Some(i as i32*64 + nulls as i32);
  18. }
  19. }
  20. return None;
  21. }
  22.  
  23. let nulls = (self.root_top[index] & bit_mask).leading_zeros();
  24.  
  25. // Leading Zeros von root_top[index] bestimmen und mit in_index vergleichen. Die erste führende 1 muss rechts von in_index liegen oder an Position in_index.
  26. if nulls != 64 {
  27. return Some(index as i32 *64+val as i32);
  28. }
  29.  
  30. // Wenn Leading Zeros=64, dann locate_top_level(element,level+1)
  31. let new_index = self.locate_top_level(index as i32 ,level+1);
  32.  
  33. new_index
  34. .map(|x| self.root_top[x as usize].leading_zeros())
  35. .filter(|x| x != 64)
  36. .map(|x| x as i32*64 + val as i32)
  37. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement