| 381 | const shardHashes: Array<number> = [] |
| 382 | |
| 383 | function getIndexForInput<A extends PrimaryKey.PrimaryKey>( |
| 384 | self: HashRing<A>, |
| 385 | hash: number, |
| 386 | exclude?: ReadonlySet<string> | undefined |
| 387 | ): readonly [index: number, distance: number] { |
| 388 | const ring = self.ring |
| 389 | const len = ring.length |
| 390 | |
| 391 | let mid: number |
| 392 | let lo = 0 |
| 393 | let hi = len - 1 |
| 394 | |
| 395 | while (lo <= hi) { |
| 396 | mid = ((lo + hi) / 2) >>> 0 |
| 397 | if (ring[mid][0] >= hash) { |
| 398 | hi = mid - 1 |
| 399 | } else { |
| 400 | lo = mid + 1 |
| 401 | } |
| 402 | } |
| 403 | const a = lo === len ? lo - 1 : lo |
| 404 | const distA = Math.abs(ring[a][0] - hash) |
| 405 | if (exclude === undefined) { |
| 406 | const b = lo - 1 |
| 407 | if (b < 0) { |
| 408 | return [a, distA] |
| 409 | } |
| 410 | const distB = Math.abs(ring[b][0] - hash) |
| 411 | return distA <= distB ? [a, distA] : [b, distB] |
| 412 | } else if (!exclude.has(ring[a][1])) { |
| 413 | return [a, distA] |
| 414 | } |
| 415 | const range = Math.max(lo, len - lo) |
| 416 | for (let i = 1; i < range; i++) { |
| 417 | let index = lo - i |
| 418 | if (index >= 0 && index < len && !exclude.has(ring[index][1])) { |
| 419 | return [index, Math.abs(ring[index][0] - hash)] |
| 420 | } |
| 421 | index = lo + i |
| 422 | if (index >= 0 && index < len && !exclude.has(ring[index][1])) { |
| 423 | return [index, Math.abs(ring[index][0] - hash)] |
| 424 | } |
| 425 | } |
| 426 | return [a, distA] |
| 427 | } |