Skip to content

Instantly share code, notes, and snippets.

@ibsusu

ibsusu/buffer-backed-objects_with_sorting.js

Created August 2, 2021 21:07
Show Gist options
  • Save ibsusu/cc95a8f7aed4a1d58b54c1db256bcb79 to your computer and use it in GitHub Desktop.
Save ibsusu/cc95a8f7aed4a1d58b54c1db256bcb79 to your computer and use it in GitHub Desktop.
Download ZIP
Sorting works with buffer backed objects. This is probably not the fastest or most complete implementation.
Raw
buffer-backed-objects_with_sorting.js
/**
* Copyright 2020 Google Inc. All Rights Reserved.
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
* http://www.apache.org/licenses/LICENSE-2.0
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
// modified by ibsusu, all rights belong to whomever wants to use it, including removing this line.
// `globalThis` polyfill
(function () {
if (typeof globalThis === "object") return;
Object.prototype.__defineGetter__("__magic__", function () {
return this;
});
__magic__.globalThis = __magic__; // lolwat
delete Object.prototype.__magic__;
})();
// Like `isNaN` but returns `true` for symbols.
function betterIsNaN(s) {
if (typeof s === "symbol") {
return true;
}
return isNaN(s);
}
export function structSize(descriptors) {
let stride = 0;
for (const { size } of Object.values(descriptors)) {
stride += size;
}
return stride;
}
export function ArrayOfBufferBackedObjects(
buffer,
descriptors,
{ byteOffset = 0, length = 0 } = {}
) {
const dataView = new DataView(buffer, byteOffset);
// Accumulate the size of one struct
let stride = 0;
// Copy
descriptors = Object.assign({}, descriptors);
for (const [name, descriptor] of Object.entries(descriptors)) {
// Copy second layer and add offset property
descriptors[name] = Object.assign({}, descriptor, { offset: stride });
stride += descriptor.size;
}
if (!length) {
length = Math.floor((buffer.byteLength - byteOffset) / stride);
}
return new Proxy(new Array(length), {
has(target, propName) {
// The underlying array is hole-y, but we want to pretend that it is not.
// So we need to return `true` for all indices so that `map` et al. work
// as expected.
if (!betterIsNaN(propName)) {
return propName < length;
}
if (propName === "buffer") {
return true;
}
if (propName === "sort"){
return true;
}
return propName in target;
},
get(target, propName, proxy) {
if (propName === "buffer") {
return buffer;
}
if(propName === "size"){
function sizer(keyName){
return descriptors[keyName].size;
}
return sizer;
}
if(propName === 'descriptors'){
let descs = {};
for(let key in descriptors){
descs[key] = descriptors[key].size;
}
return descs;
}
if(propName === 'sort'){
function sorter(compareFunction){
// this doesn't work
// TimSort.sort(proxy, compareFunction);
quickSort(proxy, compareFunction);
}
return sorter;
}
if (betterIsNaN(propName)) {
let prop = target[propName];
if (typeof prop === "function") {
prop = prop.bind(proxy);
}
return prop;
}
// getting an array index for normal indexing
const idx = parseInt(propName);
const itemOffset = idx * stride;
// Just like real arrays, we return `undefined`
// outside the boundaries.
if (idx >= target.length) {
return undefined;
}
if(!target[idx]){
target[idx] = new Proxy(new Uint8Array(dataView.buffer, itemOffset+byteOffset, stride), {
has(target, propName){
return propName in target || propName in descriptors;
},
get(target, propName, proxy){
// if it's a property native to Uint8Array return it
if (target[propName]){
return target[propName];
}
// without this we just get a json stringified Uint8Array.
if(propName === 'toJSON'){
return () => {
const abstractObject = {};
for(const name in descriptors){
const descriptor = descriptors[name];
// skipping reserved
if(!descriptor.get){continue;}
abstractObject[name] = descriptor.get(target.subarray(descriptor.offset, descriptor.offset+descriptor.size));
}
return abstractObject;
};
}
// check for the descriptor now
let descriptor = descriptors[propName];
if(!descriptor){
return undefined;
}
// return descriptor.get(new DataView(target.buffer, itemOffset, stride), descriptor.offset);
return descriptor.get(target.subarray(descriptor.offset, descriptor.offset+descriptor.size));
},
set(target, propName, value, receiver){
if(propName === "underlyingArray"){
target.set(value);
return true;
}
let descriptor = descriptors[propName];
if(!descriptor){
return false;
}
descriptor.set(target.subarray(descriptor.offset, descriptor.offset+descriptor.size), value);
return true;
}
});
}
return target[idx];
},
set(target, propName, value, receiver){
const idx = parseInt(propName);
const itemOffset = idx * stride;
if(!target[idx]){
target[idx] = new Proxy(new Uint8Array(dataView.buffer, itemOffset+byteOffset, stride), {
has(target, propName){
return propName in target || propName in descriptors;
},
get(target, propName, proxy){
// if it's a property native to Uint8Array return it
if (target[propName]){
return target[propName];
}
// without this we just get a json stringified Uint8Array.
if(propName === 'toJSON'){
return () => {
const abstractObject = {};
for(const name in descriptors){
const descriptor = descriptors[name];
// skipping reserved
if(!descriptor.get){continue;}
abstractObject[name] = descriptor.get(target.subarray(descriptor.offset, descriptor.offset+descriptor.size));
}
return abstractObject;
};
}
// check for the descriptor now
let descriptor = descriptors[propName];
if(!descriptor){
return undefined;
}
// return descriptor.get(new DataView(target.buffer, itemOffset, stride), descriptor.offset);
return descriptor.get(target.subarray(descriptor.offset, descriptor.offset+descriptor.size));
},
set(target, propName, value, receiver){
let descriptor = descriptors[propName];
if(!descriptor){
return false;
}
descriptor.set(target.subarray(descriptor.offset, descriptor.offset+descriptor.size), value);
return true;
}
});
}
target[idx].underlyingArray = value;
return true;
}
});
}
export function BufferBackedObject(
buffer,
descriptors,
{ byteOffset = 0 } = {}
) {
return ArrayOfBufferBackedObjects(buffer, descriptors, { byteOffset })[0];
}
[
"Uint16",
"Uint32",
"Int16",
"Int32",
"Float32",
"Float64",
"BigInt64",
"BigUint64",
].forEach((name) => {
BufferBackedObject[name] = ({ endianess: endianness = "big" } = {}) => {
if (endianness !== "big" && endianness !== "little") {
throw Error("Endianness needs to be either 'big' or 'little'");
}
const littleEndian = endianness === "little";
return {
size: globalThis[`${name}Array`].BYTES_PER_ELEMENT,
get: (u8Array) => {
return new DataView(
u8Array.buffer,
u8Array.byteOffset,
u8Array.byteLength
)[`get${name}`](0, littleEndian);
},
set: (u8Array, value) => {
new DataView(
u8Array.buffer,
u8Array.byteOffset,
u8Array.byteLength
)[`set${name}`](0, value, littleEndian);
},
};
};
});
BufferBackedObject.Uint8 = () => ({
size: 1,
get: (u8Array) => u8Array[0],
set: (u8Array, value) => u8Array[0] = value,
});
BufferBackedObject.Int8 = () => ({
size: 1,
get: (u8Array) => new DataView(u8Array.buffer, u8Array.byteOffset, 1).getInt8(),
set: (u8Array, value) => u8Array[0] = value,
});
BufferBackedObject.ArrayBuffer = (size) => ({
size,
get: (u8Array) => u8Array.subarray(0, size),
set: (u8Array, value) => u8Array.set(new Uint8Array(value)),
});
BufferBackedObject.NestedBufferBackedObject = (descriptors) => {
const size = structSize(descriptors);
return {
size,
get: (u8Array) =>
new ArrayOfBufferBackedObjects(u8Array.buffer, descriptors, {
byteOffset: u8Array.byteOffset,
length: 1,
})[0],
set: (u8Array, value) => {
throw Error("Can’t set an entire struct");
},
};
};
BufferBackedObject.NestedArrayOfBufferBackedObjects = (length, descriptors) => {
const size = structSize(descriptors) * length;
return {
size,
get: (u8Array) =>
new ArrayOfBufferBackedObjects(u8Array.buffer, descriptors, {
byteOffset: u8Array.byteOffset,
length,
}),
set: (u8Array, value) => {
throw Error("Can’t set an entire array");
},
};
};
BufferBackedObject.UTF8String = (maxBytes) => {
return {
size: maxBytes,
get: (u8Array) => {
return new TextDecoder()
.decode(u8Array)
.replace(/\u0000+$/, "");
},
set: (u8Array, value) => {
const encoding = new TextEncoder().encode(value);
u8Array.fill(0);
u8Array.set(encoding.subarray(0, maxBytes));
}
};
};
BufferBackedObject.reserved = (size) => ({ size });
// sorting function. timsort is better but more complicated. I just need this to work.
function quickSort(arr, compare, left = 0, right = arr.length - 1) {
let len = arr.length;
let index;
if(len > 1) {
index = partition(arr, compare, left, right);
if(left < index - 1) {
quickSort(arr, compare, left, index - 1);
}
if(index < right) {
quickSort(arr, compare, index, right);
}
}
return arr;
}
function partition(arr, compare, left, right) {
let middle = Math.floor((right + left) / 2);
let pivot = arr[middle];
let i = left;
let j = right;
while(i <= j) {
while(compare(arr[i], pivot) < 0) {
i++;
}
while(compare(arr[j], pivot) > 0) {
j--;
}
let buf = new ArrayBuffer(arr[0].length);
let swap = new Uint8Array(arr[0].length);
if(i <= j) {
swap.set(arr[i]);
arr[i] = arr[j];
arr[j] = swap;
i++;
j--;
}
}
return i;
}
export default BufferBackedObject;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment