index_heap.c 1.2 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
  1. /*
  2. * File: dclxvi-20130329/index_heap.c
  3. * Author: Ruben Niederhagen, Peter Schwabe
  4. * Public Domain
  5. */
  6. #include <assert.h>
  7. #include "scalar.h"
  8. #include "index_heap.h"
  9. static void heap_push(unsigned long long *h, unsigned long long *hlen, unsigned long long elem, scalar_t *s)
  10. {
  11. /* Move up towards the root */
  12. /* XXX: Check size of hlen, whether cast to signed value is ok */
  13. signed long long pos = *hlen;
  14. signed long long ppos = (pos-1)/2;
  15. unsigned long long t;
  16. h[*hlen] = elem;
  17. while(pos > 0)
  18. {
  19. if(scalar_lt_vartime(s[h[ppos]], s[h[pos]]))
  20. {
  21. t = h[ppos];
  22. h[ppos] = h[pos];
  23. h[pos] = t;
  24. pos = ppos;
  25. ppos = (pos-1)/2;
  26. }
  27. else break;
  28. }
  29. (*hlen)++;
  30. }
  31. /* caller's responsibility to ensure hlen>=3 */
  32. void heap_init(unsigned long long *h, unsigned long long hlen, scalar_t *s)
  33. {
  34. assert(hlen>=5);
  35. assert(hlen&1);
  36. h[0] = 0;
  37. unsigned long long i=1;
  38. while(i<hlen)
  39. heap_push(h, &i, i, s);
  40. }
  41. /* Put the largest value in the heap in max1, the second largest in max2 */
  42. void heap_get2max(unsigned long long *h, unsigned long long *max1, unsigned long long *max2, scalar_t *s)
  43. {
  44. *max1 = h[0];
  45. *max2 = h[1];
  46. if(scalar_lt_vartime(s[h[1]],s[h[2]]))
  47. *max2 = h[2];
  48. }