module Sumbur::NativeSumbur

Public Instance Methods

sumbur(p1, p2) click to toggle source
static VALUE
rb_sumbur(VALUE self, VALUE hashed_int, VALUE capacity)
{
    unsigned int h = NUM2UINT(hashed_int);
    unsigned int capa = NUM2UINT(capacity);
    unsigned int part, n, i, c;

    if (capa == 0) {
        rb_raise(rb_eArgError, "Sumbur is not applicable to empty cluster");
    }

    part = L / capa;

    if (L - h < part) return INT2FIX(0);

    n = 1;

    do {
        if (h >= L / 2) h -= L / 2;
        else {
            n = 2;
            if (L / 2 - h < part) return INT2FIX(1);
        }
        if (capa == 2) return INT2FIX(1);

#define curslice(i) (L / (i * (i - 1)))
#define unroll(i) \
        if (curslice(i) <= h) h -= curslice(i); \
        else {                                  \
            h += curslice(i) * (i - n - 1);     \
            n = i;                              \
            if (L / i - h < part) return INT2FIX(n-1);        \
        }                                       \
        if (capa == i) return INT2FIX(n-1)

        unroll(3); unroll(4); unroll(5);
        unroll(6); unroll(7); unroll(8);
        unroll(9); unroll(10); unroll(11);
        unroll(12); unroll(13); unroll(14);
        unroll(15); unroll(16); unroll(17);
        unroll(18); unroll(19); unroll(20);
        unroll(21); unroll(22); unroll(23);
        unroll(24); unroll(25); unroll(26);

        for (i = 27; i <= capa && i <= 62; i++) {
            c = LL27_38[i-27];
            if (c <= h) {
                h -= c;
            }
            else {
                h += c * (i - n - 1);
                n = i;
                if (L27_38[i-27] - h < part) return INT2FIX(n-1);
            }
        }

        for(i = 63; i <= capa; i++) {
            c = L / (i * (i - 1));
            if (c <= h) {
                h -= c;
            }
            else {
                h += c * (i - n - 1);
                n = i;
                if (L / i - h < part) return INT2FIX(n - 1);
            }
        }
    } while(0);
    return INT2FIX(n - 1);
}