[vivace-graph-devel] Rucksack Btree number-indexes on UUID integer-128 representations -- a sketch

[MON KEY]

Utilizing the idea sketched below could get us much of the way towards a
functional implementation of Rucksack's Btree number-indexes on UUIDs...

Following is a toy prototype which extends Unicly's UUID class
UNIQUE-UNIVERSAL-IDENTIFIER by subclassing UUID-INDEXABLE-V5 and
adding two new slots which "self host" bit-vector and integer-128s
representations. These are populated in an after method specialized on
the class UUID-INDEXABLE-V5.

e.g. with an index spec like:
 (btree :key< uuid-<
        :value= uuid-eql
        :value-type persistent-object)

(defclass uuid-indexable-v5 (unicly:unique-universal-identifier)
  ((bit-vector
    :reader bit-vector-of-uuid)
   (integer-128
    :reader integer-128-of-uuid)))

(defmethod initialize-instance :after ((obj uuid-indexable-v5)
                                       &key &allow-other-keys)
  (setf (slot-value obj 'bit-vector)
        (unicly:uuid-to-bit-vector obj))
  (setf (slot-value obj 'integer-128)
        (unicly::uuid-bit-vector-to-integer (slot-value obj 'bit-vector))))

(declaim (inline digested-v5-uuid-indexed))
(defun digested-v5-uuid-indexed (v5-digest-byte-array)
  (declare (type unicly::uuid-byte-array-20
                 unicly::v5-digest-byte-array)
           (inline unicly::%uuid_time-low-request
                   unicly::%uuid_time-mid-request
                   unicly::%uuid_time-high-and-version-request
                   unicly::%uuid_clock-seq-and-reserved-request
                   unicly::%uuid_node-request)
           (optimize (speed 3)))
  (the uuid-indexable-v5
    (make-instance 'uuid-indexable-v5
     :%uuid_time-low (unicly::%uuid_time-low-request v5-digest-byte-array)
     :%uuid_time-mid (unicly::%uuid_time-mid-request v5-digest-byte-array)
     :%uuid_time-high-and-version
(unicly::%uuid_time-high-and-version-request v5-digest-byte-array 5)
     :%uuid_clock-seq-and-reserved
(unicly::%uuid_clock-seq-and-reserved-request v5-digest-byte-array)
     :%uuid_clock-seq-low (the unicly::uuid-ub8
(unicly::%uuid_clock-seq-low-request v5-digest-byte-array))
     :%uuid_node (unicly::%uuid_node-request v5-digest-byte-array))))

(defun make-v5-uuid-indexed (namespace name)
  (declare (type string name)
           (type unicly:unique-universal-identifier namespace)
           (inline unicly::uuid-digest-uuid-instance
                   digested-v5-uuid-indexed)
           (optimize (speed 3)))
  (the (values uuid-indexable-v5 &optional)
    (digested-v5-uuid-indexed
     (the unicly::uuid-byte-array-20
       (unicly::uuid-digest-uuid-instance 5 namespace name)))))

(defparameter *tt--indexed*
  (make-v5-uuid-indexed unicly:*uuid-namespace-dns* "bubba"))
; => *TT--INDEXED*

(bit-vector-of-uuid *TT--INDEXED*)
;=> #*1110111010100001000100000101111000...

(integer-128-of-uuid *TT--INDEXED*)
;=> 317192554773903544674993329975922389959

(unicly:unique-universal-identifier-p *tt--indexed*)
;=> T

(unicly:uuid-princ-to-string *tt--indexed*)
;=> "eea1105e-3681-5117-99b6-7b2b5fe1f3c7"

(unicly::uuid-to-byte-array *tt--indexed*)
;=> #(238 161 16 94 54 129 81 23 153 182 123 43 95 225 243 199)

(unicly::uuid-from-bit-vector (bit-vector-of-uuid *tt--indexed*))
;=> eea1105e-3681-5117-99b6-7b2b5fe1f3c7

(describe *TT--INDEXED*)
; => eea1105e-3681-5117-99b6-7b2b5fe1f3c7
;   [standard-object]
;
; Slots with :INSTANCE allocation:
;   { ... %uuid_<FOO> slots elided ... }
;   BIT-VECTOR                   =
#*11101110101000010001000001011110001101101000000101010001000101111001..
;   INTEGER-128                  = 317192554773903544674993329975922389959