(defpackage :cuckoo
  (:export :make-cuckoo-hash
           :cuckoo-insert
           :cuckoo-delete
           :cuckoo-lookup)
  (:use :cl))

(in-package :cuckoo)

(defparameter *word-size* 32)
(defparameter *initial-table-size* 16)

(defun universal-hash-fn (a table-size)
  (assert (< a (ash 1 (1- *word-size*))))
  (let ((odd-a (1+ (* a 2)))
        (size-log-2 (truncate (log table-size 2))))
    (lambda (x)
      (ash (mod (* odd-a x) (ash 1 *word-size*))
           (- (- *word-size* size-log-2))))))

(defun make-hash-fn (table-size)
  (flet ((rand-hash ()
           (universal-hash-fn (random (ash 1 (1- *word-size*)))
                              table-size)))
    (let ((a (rand-hash))
          (b (rand-hash))
          (c (rand-hash)))
      (lambda (x)
        (logxor (funcall a x)
                (funcall b x)
                (funcall c x))))))

(defstruct cuckoo-hash
  (fn-a (make-hash-fn *initial-table-size*))
  (fn-b (make-hash-fn *initial-table-size*))
  (table-a (make-array *initial-table-size*
                       :adjustable t
                       :initial-element nil))
  (table-b (make-array *initial-table-size*
                       :adjustable t
                       :initial-element nil)))

(defun cuckoo-lookup (h k)
  (let ((a (funcall (cuckoo-hash-fn-a h) k))
        (b (funcall (cuckoo-hash-fn-b h) k)))
    (or (let ((a-val (aref (cuckoo-hash-table-a h) a)))
          (and a-val (= a-val k)))
        (let ((b-val (aref (cuckoo-hash-table-b h) b)))
          (and b-val (= b-val k))))))

(defmacro swap (a b)
  (let ((tmp (gensym)))
    `(let ((,tmp ,a))
       (setf ,a ,b)
       (setf ,b ,tmp))))

(defparameter *max-loop* 20)

(defun cuckoo-insert (h k)
  (unless (cuckoo-lookup h k)
    (loop repeat *max-loop*
       do (progn
            (let ((f-a (funcall (cuckoo-hash-fn-a h) k)))
              (swap k (aref (cuckoo-hash-table-a h) f-a)))
            (unless k
              (return-from cuckoo-insert))
            (let ((f-b (funcall (cuckoo-hash-fn-b h) k)))
              (swap k (aref (cuckoo-hash-table-b h) f-b)))
            (unless k
              (return-from cuckoo-insert))))
    (rehash h)
    (cuckoo-insert h k)))

(defun delete-with-fn (h k hash-fn-a hash-fn-b)
  (let* ((a (funcall hash-fn-a k))
         (b (funcall hash-fn-b k))
         (a-val (aref (cuckoo-hash-table-a h) a))
         (b-val (aref (cuckoo-hash-table-b h) b)))
    (when (and a-val (= a-val k))
      (setf (aref (cuckoo-hash-table-a h) a) nil))
    (when (and b-val (= b-val k))
      (setf (aref (cuckoo-hash-table-b h) b) nil))))

(defun cuckoo-delete (h k)
  (delete-with-fn h k (cuckoo-hash-fn-a h) (cuckoo-hash-fn-b h)))

(defun rehash (h)
  (let ((new-size (* 2 (array-dimension (cuckoo-hash-table-a h) 0)))
        (old-fn-a (cuckoo-hash-fn-a h))
        (old-fn-b (cuckoo-hash-fn-b h)))
    (setf (cuckoo-hash-fn-a h) (make-hash-fn new-size))
    (setf (cuckoo-hash-fn-b h) (make-hash-fn new-size))
    (adjust-array (cuckoo-hash-table-a h) new-size
                  :initial-element nil)
    (adjust-array (cuckoo-hash-table-b h) new-size
                  :initial-element nil)
    (loop for i from 0 below new-size
       do (let ((elem-a (aref (cuckoo-hash-table-a h) i))
                (elem-b (aref (cuckoo-hash-table-b h) i)))
            (when elem-a
              (delete-with-fn h elem-a old-fn-a old-fn-b)
              (cuckoo-insert h elem-a))
            (when elem-b
              (delete-with-fn h elem-b old-fn-a old-fn-b)
              (cuckoo-insert h elem-b))))))

(defun test (n)
  (let ((h (make-cuckoo-hash))
        (keys (loop for i from 1 to n collect (random 10000))))
    (dolist (k keys)
      (cuckoo-insert h k))
    (dolist (k keys)
      (unless (cuckoo-lookup h k)
        (format t "key ~a not in table!~%" k)))
    h))