Open-S2 / gis-tools / #6

Committed 23 Jan 2025 11:00PM UTC coverage: 92.693% (-0.3%) from 93.021%

Build # #6

Build Type

push

Committed by Mr Martian

Commit Message

gridCluster done; toTiles setup without tests; dataStores add has; fixed geometry 3dpoint to normalize from wm and s2 data

Run Details

120 of 399 new or added lines in 24 files covered. (30.08%)

26 existing lines in 9 files now uncovered.

59825 of 64541 relevant lines covered (92.69%)

95.07 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

90.53

/src/dataStore/file.ts

import { compareIDs } from '..';
import { externalSort } from './externalSort';
import { tmpdir } from 'os';
import { closeSync, fstatSync, openSync, readSync, unlinkSync, writeSync } from 'fs';

import type { S2CellId } from '..';
import type { Properties, Value, VectorKey } from '..';

/** Options to create a S2FileStore */
export interface FileOptions {
  /** If true, then the values are stored in the index section of the keys file */
  valuesAreIndex?: boolean;
  /** If true, then the data is already sorted and get calls can be immediately returned */
  isSorted?: boolean;
  /** The maximum heap size in bytes for each grouping of data. */
  maxHeap?: number;
  /** The number of threads to use for sorting */
  threadCount?: number;
  /** If desired, a temporary directory to use */
  tmpDir?: string;
}

/** An entry in a file */
export interface FileEntry<V> {
  key: S2CellId;
  value: V;
}

const KEY_LENGTH = 16;

/**
 * NOTE: The File KVStore is designed to be used in states:
 * - write-only. The initial state is write-only. Write all you need to before reading
 * - read-only. Once you have written everything, the first read will lock the file to be static
 * and read-only.
 */
export class S2FileStore<V = Properties | Value | VectorKey> {
  readonly fileName: string;
  #state: 'read' | 'write' = 'read';
  #size = 0;
  #sorted: boolean;
  #maxHeap?: number;
  #threadCount?: number;
  #tmpDir?: string;
  // options
  #indexIsValues = false;
  // write params
  #valueOffset = 0;
  // read write fd
  #keyFd: number = -1;
  #valueFd: number = -1;

  /**
   * Builds a new File based KV
   * @param fileName - the path + file name without the extension
   * @param options - the options of how the store should be created and used
   */
  constructor(fileName?: string, options?: FileOptions) {
    this.fileName = fileName ?? buildTmpFileName(options?.tmpDir);
    this.#sorted = options?.isSorted ?? false;
    this.#indexIsValues = options?.valuesAreIndex ?? false;
    this.#maxHeap = options?.maxHeap;
    this.#threadCount = options?.threadCount;
    this.#tmpDir = options?.tmpDir;
    if (!this.#sorted) this.#switchToWriteState();
    else {
      this.#keyFd = openSync(`${this.fileName}.sortedKeys`, 'r');
      if (!this.#indexIsValues) this.#valueFd = openSync(`${this.fileName}.values`, 'r');
    }
    // Update the size if the file already existed
    const stat = fstatSync(this.#keyFd);
    if (stat.size >= KEY_LENGTH) this.#size = stat.size / KEY_LENGTH;
  }

  /** @returns - the length of the store */
  get length(): number {
    return this.#size;
  }

  /**
   * Adds a value to be associated with a key
   * @param key - the uint64 id
   * @param value - the value to store
   */
  set(key: number | S2CellId, value: V): void {
    this.#switchToWriteState();
    // prepare value
    // @ts-expect-error - we know its an object
    if (typeof value === 'object' && 'cell' in value && typeof value.cell === 'bigint')
      value.cell = value.cell.toString();
    const valueBuf = Buffer.from(JSON.stringify(value));
    // write key offset as a uint64
    const buffer = Buffer.alloc(KEY_LENGTH);
    buffer.writeBigUInt64LE(BigInt(key), 0);
    // write value offset to point to the value position in the `${path}.values`
    if (this.#indexIsValues) {
      if (typeof value !== 'number' && typeof value !== 'bigint')
        throw new Error('value must be a number.');
      if (typeof value === 'number') {
        buffer.writeUInt32LE(value >>> 0, 8);
        buffer.writeUInt32LE(Math.floor(value / 0x100000000), 12);
      } else {
        buffer.writeBigInt64LE(value, 8);
      }
    } else {
      buffer.writeUInt32LE(this.#valueOffset, 8);
      buffer.writeUInt32LE(valueBuf.byteLength, 12);
    }
    writeSync(this.#keyFd, buffer);
    // write value and update value offset
    if (!this.#indexIsValues) writeSync(this.#valueFd, valueBuf);
    this.#valueOffset += valueBuf.byteLength;
    // update size
    this.#size++;
  }

  /**
   * Checks if the store contains a key
   * @param key - the key
   * @returns true if the store contains the key
   */
  async has(key: number | S2CellId): Promise<boolean> {
    key = BigInt(key);
    await this.#switchToReadState();
    if (this.#size === 0) return false;
    const lowerIndex = this.#lowerBound(key);
    if (lowerIndex >= this.#size) return false;
    const buffer = Buffer.alloc(KEY_LENGTH);
    readSync(this.#keyFd, buffer, 0, KEY_LENGTH, lowerIndex * KEY_LENGTH);
    return buffer.readBigUInt64LE(0) === key;
  }

  /**
   * Gets the value associated with a key
   * @param key - the key
   * @param max - the max number of values to return
   * @param bigint - set to true if the key is a bigint
   * @returns the value if the map contains values for the key
   */
  async get(key: number | S2CellId, max?: number, bigint = false): Promise<V[] | undefined> {
    key = BigInt(key);
    await this.#switchToReadState();
    if (this.#size === 0) return;
    let lowerIndex = this.#lowerBound(key);
    if (lowerIndex >= this.#size) return undefined;
    const res: V[] = [];
    const buffer = Buffer.alloc(KEY_LENGTH);
    while (true) {
      readSync(this.#keyFd, buffer, 0, KEY_LENGTH, lowerIndex * KEY_LENGTH);
      if (buffer.readBigUInt64LE(0) !== key) break;
      const valueOffset = buffer.readUInt32LE(8);
      const valueLength = buffer.readUInt32LE(12);
      if (this.#indexIsValues) {
        if (bigint) res.push((BigInt(valueOffset) + (BigInt(valueLength) << 32n)) as unknown as V);
        else res.push(((valueOffset >>> 0) + (valueLength >>> 0) * 0x100000000) as unknown as V);
      } else {
        const valueBuf = Buffer.alloc(valueLength);
        readSync(this.#valueFd, valueBuf, 0, valueLength, valueOffset);
        const json = JSON.parse(valueBuf.toString()) as V;
        // @ts-expect-error - we know its an object
        if (typeof json === 'object' && 'cell' in json) json.cell = BigInt(json.cell);
        res.push(json);
      }
      if (max !== undefined && res.length >= max) break;
      lowerIndex++;
      if (lowerIndex >= this.#size) break;
    }

    if (res.length === 0) return undefined;
    return res;
  }

  /** Sort the data if not sorted */
  async sort(): Promise<void> {
    await this.#switchToReadState();
  }

  /**
   * Iterates over all values in the store
   * @param bigint - set to true if the value is a bigint stored in the index
   * @yields an iterator
   */
  async *entries(bigint = false): AsyncIterableIterator<FileEntry<V>> {
    await this.#switchToReadState();
    for (let i = 0; i < this.#size; i++) {
      const buffer = Buffer.alloc(KEY_LENGTH);
      readSync(this.#keyFd, buffer, 0, KEY_LENGTH, i * KEY_LENGTH);
      const key = buffer.readBigUInt64LE(0);
      const valueOffset = buffer.readUInt32LE(8);
      const valueLength = buffer.readUInt32LE(12);
      if (this.#indexIsValues) {
        const value = bigint
          ? ((BigInt(valueOffset) + (BigInt(valueLength) << 32n)) as unknown as V)
          : ((valueOffset + valueLength * 0x100000000) as unknown as V);
        yield { key, value };
      } else {
        const valueBuf = Buffer.alloc(valueLength);
        readSync(this.#valueFd, valueBuf, 0, valueLength, valueOffset);
        const value = JSON.parse(valueBuf.toString()) as V;
        // @ts-expect-error - we know its an object
        if (typeof value === 'object' && 'cell' in value) value.cell = BigInt(value.cell);
        yield { key, value };
      }
    }
  }

  /**
   * Closes the store
   * @param cleanup - set to true if you want to remove the .keys and .values files upon closing
   */
  close(cleanup = false): void {
    if (this.#keyFd >= 0) {
      closeSync(this.#keyFd);
      this.#keyFd = -1;
    }
    if (!this.#indexIsValues && this.#valueFd >= 0) {
      closeSync(this.#valueFd);
      this.#valueFd = -1;
    }
    if (cleanup) {
      unlinkSync(`${this.fileName}.keys`);
      if (!this.#indexIsValues) unlinkSync(`${this.fileName}.values`);
      if (this.#sorted) unlinkSync(`${this.fileName}.sortedKeys`);
    }
  }

  /** Switches to write state if in read. */
  #switchToWriteState(): void {
    if (this.#state === 'write') return;
    this.#state = 'write';
    this.close();
    this.#keyFd = openSync(`${this.fileName}.keys`, 'a');
    if (!this.#indexIsValues) this.#valueFd = openSync(`${this.fileName}.values`, 'a');
  }

  /** Switches to read state if in write. Also sort the keys. */
  async #switchToReadState(): Promise<void> {
    if (this.#state === 'read') return;
    this.#state = 'read';
    this.close();
    if (this.#size === 0) return;
    await this.#sort();
    this.#keyFd = openSync(`${this.fileName}.sortedKeys`, 'r');
    if (!this.#indexIsValues) this.#valueFd = openSync(`${this.fileName}.values`, 'r');
  }

  /** Sort the data */
  async #sort(): Promise<void> {
    if (this.#sorted) return;
    await externalSort(
      [this.fileName],
      this.fileName,
      this.#maxHeap,
      this.#threadCount,
      this.#tmpDir,
    );
    this.#sorted = true;
  }

  /**
   * @param id - the id to search for
   * @returns the starting index from the lower bound of the id
   */
  #lowerBound(id: S2CellId): number {
    // lower bound search
    let lo: number = 0;
    let hi: number = this.#size;
    let mid: number;

    while (lo < hi) {
      mid = Math.floor(lo + (hi - lo) / 2);
      const loHi = this.#getKey(mid);
      if (compareIDs(loHi, id) === -1) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }

    return lo;
  }

  /**
   * @param index - the index to get the key from
   * @returns the key
   */
  #getKey(index: number): S2CellId {
    const buf = Buffer.alloc(8);
    readSync(this.#keyFd, buf, 0, 8, index * KEY_LENGTH);
    return buf.readBigUInt64LE(0);
  }
}

/**
 * @param tmpDir - the temporary directory to use if provided otherwise default os tmpdir
 * @returns - a temporary file name based on a random number.
 */
function buildTmpFileName(tmpDir?: string): string {
  const tmpd = tmpDir ?? tmpdir();
  const randomName = Math.random().toString(36).slice(2);
  return `${tmpd}/${randomName}`;
}

1	import { compareIDs } from '..';	128✔
2	import { externalSort } from './externalSort';	184✔
3	import { tmpdir } from 'os';	112✔
4	import { closeSync, fstatSync, openSync, readSync, unlinkSync, writeSync } from 'fs';	340✔
5
6	import type { S2CellId } from '..';
7	import type { Properties, Value, VectorKey } from '..';
8
9	/** Options to create a S2FileStore */
10	export interface FileOptions {
11	/** If true, then the values are stored in the index section of the keys file */
12	valuesAreIndex?: boolean;
13	/** If true, then the data is already sorted and get calls can be immediately returned */
14	isSorted?: boolean;
15	/** The maximum heap size in bytes for each grouping of data. */
16	maxHeap?: number;
17	/** The number of threads to use for sorting */
18	threadCount?: number;
19	/** If desired, a temporary directory to use */
20	tmpDir?: string;
21	}
22
23	/** An entry in a file */
24	export interface FileEntry<V> {
25	key: S2CellId;
26	value: V;
27	}
28
29	const KEY_LENGTH = 16;	86✔
30
31	/**
32	* NOTE: The File KVStore is designed to be used in states:
33	* - write-only. The initial state is write-only. Write all you need to before reading
34	* - read-only. Once you have written everything, the first read will lock the file to be static
35	* and read-only.
36	*/
37	export class S2FileStore<V = Properties \| Value \| VectorKey> {
38	readonly fileName: string;
39	#state: 'read' \| 'write' = 'read';
40	#size = 0;
41	#sorted: boolean;
42	#maxHeap?: number;
43	#threadCount?: number;
44	#tmpDir?: string;
45	// options
46	#indexIsValues = false;
47	// write params
48	#valueOffset = 0;
49	// read write fd
50	#keyFd: number = -1;
51	#valueFd: number = -1;	2✔
52
53	/**
54	* Builds a new File based KV
55	* @param fileName - the path + file name without the extension
56	* @param options - the options of how the store should be created and used
57	*/
58	constructor(fileName?: string, options?: FileOptions) {	110✔
59	this.fileName = fileName ?? buildTmpFileName(options?.tmpDir);	264✔
60	this.#sorted = options?.isSorted ?? false;	184✔
61	this.#indexIsValues = options?.valuesAreIndex ?? false;	236✔
62	this.#maxHeap = options?.maxHeap;	148✔
63	this.#threadCount = options?.threadCount;	180✔
64	this.#tmpDir = options?.tmpDir;	140✔
65	if (!this.#sorted) this.#switchToWriteState();	248✔
66	else {	8✔
67	this.#keyFd = openSync(`${this.fileName}.sortedKeys`, 'r');	260✔
68	if (!this.#indexIsValues) this.#valueFd = openSync(`${this.fileName}.values`, 'r');	398✔
69	}
70	// Update the size if the file already existed
71	const stat = fstatSync(this.#keyFd);	160✔
72	if (stat.size >= KEY_LENGTH) this.#size = stat.size / KEY_LENGTH;	312✔
73	}
74
75	/** @returns - the length of the store */
76	get length(): number {	32✔
77	return this.#size;	94✔
78	}
79
80	/**
81	* Adds a value to be associated with a key
82	* @param key - the uint64 id
83	* @param value - the value to store
84	*/
85	set(key: number \| S2CellId, value: V): void {	66✔
86	this.#switchToWriteState();	124✔
87	// prepare value
88	// @ts-expect-error - we know its an object
89	if (typeof value === 'object' && 'cell' in value && typeof value.cell === 'bigint')	348✔
90	value.cell = value.cell.toString();	160✔
91	const valueBuf = Buffer.from(JSON.stringify(value));	224✔
92	// write key offset as a uint64
93	const buffer = Buffer.alloc(KEY_LENGTH);	176✔
94	buffer.writeBigUInt64LE(BigInt(key), 0);	176✔
95	// write value offset to point to the value position in the `${path}.values`
96	if (this.#indexIsValues) {	118✔
97	if (typeof value !== 'number' && typeof value !== 'bigint')	260✔
98	throw new Error('value must be a number.');	116✔
99	if (typeof value === 'number') {	150✔
100	buffer.writeUInt32LE(value >>> 0, 8);	180✔
101	buffer.writeUInt32LE(Math.floor(value / 0x100000000), 12);	280✔
102	} else {	18✔
103	buffer.writeBigInt64LE(value, 8);	110✔
104	}
105	} else {	34✔
106	buffer.writeUInt32LE(this.#valueOffset, 8);	196✔
107	buffer.writeUInt32LE(valueBuf.byteLength, 12);	226✔
108	}
109	writeSync(this.#keyFd, buffer);	140✔
110	// write value and update value offset
111	if (!this.#indexIsValues) writeSync(this.#valueFd, valueBuf);	276✔
112	this.#valueOffset += valueBuf.byteLength;	180✔
113	// update size
UNCOV 114	this.#size++;	×
UNCOV 115	}	×
UNCOV 116		×
NEW 117	/**	×
NEW 118	* Checks if the store contains a key	×
NEW 119	* @param key - the key	×
NEW 120	* @returns true if the store contains the key	×
NEW 121	*/	×
NEW 122	async has(key: number \| S2CellId): Promise<boolean> {	×
NEW 123	key = BigInt(key);	×
NEW 124	await this.#switchToReadState();	×
NEW 125	if (this.#size === 0) return false;	×
NEW 126	const lowerIndex = this.#lowerBound(key);	×
NEW 127	if (lowerIndex >= this.#size) return false;	×
NEW 128	const buffer = Buffer.alloc(KEY_LENGTH);	×
NEW 129	readSync(this.#keyFd, buffer, 0, KEY_LENGTH, lowerIndex * KEY_LENGTH);	×
130	return buffer.readBigUInt64LE(0) === key;	110✔
131	}
132
133	/**
134	* Gets the value associated with a key
135	* @param key - the key
136	* @param max - the max number of values to return
137	* @param bigint - set to true if the key is a bigint
138	* @returns the value if the map contains values for the key
139	*/
140	async get(key: number \| S2CellId, max?: number, bigint = false): Promise<V[] \| undefined> {	122✔
141	key = BigInt(key);	88✔
142	await this.#switchToReadState();	144✔
143	if (this.#size === 0) return;	148✔
144	let lowerIndex = this.#lowerBound(key);	172✔
145	if (lowerIndex >= this.#size) return undefined;	168✔
146	const res: V[] = [];	76✔
147	const buffer = Buffer.alloc(KEY_LENGTH);	176✔
148	while (true) {	70✔
149	readSync(this.#keyFd, buffer, 0, KEY_LENGTH, lowerIndex * KEY_LENGTH);	304✔
150	if (buffer.readBigUInt64LE(0) !== key) break;	228✔
151	const valueOffset = buffer.readUInt32LE(8);	196✔
152	const valueLength = buffer.readUInt32LE(12);	200✔
153	if (this.#indexIsValues) {	122✔
154	if (bigint) res.push((BigInt(valueOffset) + (BigInt(valueLength) << 32n)) as unknown as V);	204✔
155	else res.push(((valueOffset >>> 0) + (valueLength >>> 0) * 0x100000000) as unknown as V);	160✔
156	} else {	34✔
157	const valueBuf = Buffer.alloc(valueLength);	204✔
158	readSync(this.#valueFd, valueBuf, 0, valueLength, valueOffset);	284✔
159	const json = JSON.parse(valueBuf.toString()) as V;	212✔
160	// @ts-expect-error - we know its an object
161	if (typeof json === 'object' && 'cell' in json) json.cell = BigInt(json.cell);	376✔
162	res.push(json);	118✔
163	}
164	if (max !== undefined && res.length >= max) break;	238✔
165	lowerIndex++;	76✔
166	if (lowerIndex >= this.#size) break;	204✔
167	}	6✔
168
169	if (res.length === 0) return undefined;	136✔
170	return res;	78✔
171	}
172
173	/** Sort the data if not sorted */
174	async sort(): Promise<void> {	28✔
175	await this.#switchToReadState();	172✔
176	}
177
178	/**
179	* Iterates over all values in the store
180	* @param bigint - set to true if the value is a bigint stored in the index
181	* @yields an iterator
182	*/
183	async *entries(bigint = false): AsyncIterableIterator<FileEntry<V>> {	88✔
184	await this.#switchToReadState();	144✔
185	for (let i = 0; i < this.#size; i++) {	162✔
186	const buffer = Buffer.alloc(KEY_LENGTH);	184✔
187	readSync(this.#keyFd, buffer, 0, KEY_LENGTH, i * KEY_LENGTH);	268✔
188	const key = buffer.readBigUInt64LE(0);	176✔
189	const valueOffset = buffer.readUInt32LE(8);	196✔
190	const valueLength = buffer.readUInt32LE(12);	200✔
191	if (this.#indexIsValues) {	126✔
192	const value = bigint	118✔
193	? ((BigInt(valueOffset) + (BigInt(valueLength) << 32n)) as unknown as V)	110✔
194	: ((valueOffset + valueLength * 0x100000000) as unknown as V);	158✔
195	yield { key, value };	136✔
196	} else {	34✔
197	const valueBuf = Buffer.alloc(valueLength);	204✔
198	readSync(this.#valueFd, valueBuf, 0, valueLength, valueOffset);	284✔
199	const value = JSON.parse(valueBuf.toString()) as V;	216✔
200	// @ts-expect-error - we know its an object
201	if (typeof value === 'object' && 'cell' in value) value.cell = BigInt(value.cell);	392✔
202	yield { key, value };	154✔
203	}
204	}	20✔
205	}
206
207	/**
208	* Closes the store
209	* @param cleanup - set to true if you want to remove the .keys and .values files upon closing
210	*/
211	close(cleanup = false): void {	90✔
212	if (this.#keyFd >= 0) {	106✔
213	closeSync(this.#keyFd);	116✔
214	this.#keyFd = -1;	104✔
215	}	6✔
216	if (!this.#indexIsValues && this.#valueFd >= 0) {	210✔
217	closeSync(this.#valueFd);	124✔
218	this.#valueFd = -1;	112✔
219	}	6✔
220	if (cleanup) {	70✔
221	unlinkSync(`${this.fileName}.keys`);	168✔
222	if (!this.#indexIsValues) unlinkSync(`${this.fileName}.values`);	304✔
223	if (this.#sorted) unlinkSync(`${this.fileName}.sortedKeys`);	300✔
224	}	18✔
225	}
226
227	/** Switches to write state if in read. */
228	#switchToWriteState(): void {	58✔
229	if (this.#state === 'write') return;	176✔
230	this.#state = 'write';	104✔
231	this.close();	68✔
232	this.#keyFd = openSync(`${this.fileName}.keys`, 'a');	228✔
233	if (!this.#indexIsValues) this.#valueFd = openSync(`${this.fileName}.values`, 'a');	386✔
234	}
235
236	/** Switches to read state if in write. Also sort the keys. */
237	async #switchToReadState(): Promise<void> {	54✔
238	if (this.#state === 'read') return;	172✔
239	this.#state = 'read';	100✔
240	this.close();	68✔
241	if (this.#size === 0) return;	148✔
242	await this.#sort();	92✔
243	this.#keyFd = openSync(`${this.fileName}.sortedKeys`, 'r');	252✔
244	if (!this.#indexIsValues) this.#valueFd = openSync(`${this.fileName}.values`, 'r');	388✔
245	}
246
247	/** Sort the data */
248	async #sort(): Promise<void> {	28✔
249	if (this.#sorted) return;	120✔
250	await externalSort(	88✔
251	[this.fileName],	68✔
252	this.fileName,	60✔
253	this.#maxHeap,	60✔
254	this.#threadCount,	76✔
255	this.#tmpDir,	48✔
256	);	12✔
257	this.#sorted = true;	110✔
258	}
259
260	/**
261	* @param id - the id to search for
262	* @returns the starting index from the lower bound of the id
263	*/
264	#lowerBound(id: S2CellId): number {	50✔
265	// lower bound search
266	let lo: number = 0;	60✔
267	let hi: number = this.#size;	96✔
268	let mid: number;	48✔
269
270	while (lo < hi) {	82✔
271	mid = Math.floor(lo + (hi - lo) / 2);	172✔
272	const loHi = this.#getKey(mid);	148✔
273	if (compareIDs(loHi, id) === -1) {	158✔
274	lo = mid + 1;	104✔
275	} else {	34✔
276	hi = mid;	106✔
277	}
278	}	6✔
279
280	return lo;	62✔
281	}
282
283	/**
284	* @param index - the index to get the key from
285	* @returns the key
286	*/
287	#getKey(index: number): S2CellId {	54✔
288	const buf = Buffer.alloc(8);	128✔
289	readSync(this.#keyFd, buf, 0, 8, index * KEY_LENGTH);	228✔
290	return buf.readBigUInt64LE(0);	140✔
291	}
292	}	4✔
293
294	/**
295	* @param tmpDir - the temporary directory to use if provided otherwise default os tmpdir
296	* @returns - a temporary file name based on a random number.
297	*/
298	function buildTmpFileName(tmpDir?: string): string {	92✔
299	const tmpd = tmpDir ?? tmpdir();	136✔
300	const randomName = Math.random().toString(36).slice(2);	228✔
301	return `${tmpd}/${randomName}`;	130✔
302	}

Open-S2 / gis-tools / #6

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous