ConsistentHash::addTarget() - Code Metrics - ericsizemore/consistent-hash - Measure and Improve Code Quality continuously with Scrutinizer

ConsistentHash::addTarget() A
last analyzed 2025-10-14 17:24 UTC

↳ Parent: ConsistentHash

Complexity

Conditions	4
Paths	4

Size

Total Lines	23
Code Lines	12

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	13
CRAP Score	4

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	4
eloc	12
c	1
b	0
f	0
nc	4
nop	2
dl	0
loc	23
ccs	13
cts	13
cp	1
crap	4
rs	9.8666

<?php

declare(strict_types=1);

/**
 * This file is part of Esi\ConsistentHash.
 *
 * (c) Eric Sizemore <[email protected]>
 * (c) Paul Annesley <[email protected]>
 *
 * This source file is subject to the MIT license. For the full copyright and
 * license information, please view the LICENSE file that was distributed with
 * this source code.
 */

namespace Esi\ConsistentHash;

use Esi\ConsistentHash\Exception\InvalidArgumentException;
use Esi\ConsistentHash\Exception\TargetException;
use Esi\ConsistentHash\Hasher\Crc32Hasher;
use Esi\ConsistentHash\Hasher\HasherInterface;

use function array_key_first;
use function array_keys;
use function array_unique;
use function array_values;
use function ksort;
use function min;
use function round;

use const SORT_REGULAR;

/**
 * A simple consistent hashing implementation with pluggable hash algorithms.
 */
final class ConsistentHash
{
    /**
     * Internal counter for current number of positions.
     */
    private int $positionCount = 0;

    /**
     * Internal map of positions (hash outputs) to targets.
     *
     * @var array<int, string>
     */
    private array $positionToTarget = [];

    /**
     * Whether the internal map of positions to targets is already sorted.
     */
    private bool $positionToTargetSorted = false;

    /** @var list<int> */
    private array $sortedPositions = [];

    /**
     * Internal counter for current number of targets.
     */
    private int $targetCount = 0;

    /**
     * Internal map of targets to lists of positions that target is hashed to.
     *
     * @var array<string, list<int>>
     */
    private array $targetToPositions = [];

    /**
     * @param HasherInterface $hasher   The hash algorithm, encapsulated in a HasherInterface implementation.
     * @param int             $replicas Amount of positions to hash each target to.
     *
     * @throws InvalidArgumentException If $replicas is not greater than 0.
     */
    public function __construct(
        private readonly HasherInterface $hasher = new Crc32Hasher(),
        private readonly int $replicas = 64
    ) {
        if ($replicas < 1) {
            throw InvalidArgumentException::invalidReplicaAmount($replicas);
        }
    }

    /**
     * @throws TargetException          if the $target already exists.
     * @throws InvalidArgumentException if the $weight is less than 0.0.
     */
    public function addTarget(string $target, float $weight = 1.0): void
    {
        if (\array_key_exists($target, $this->targetToPositions)) {
            throw TargetException::alreadyExists($target);
        }

        if ($weight <= 0.0) {
            throw InvalidArgumentException::invalidWeight($weight);
        }

        $this->targetToPositions[$target] = [];

        // Hash the target into multiple positions.
        $partitionCount = round((float) $this->replicas * $weight);

        for ($i = 0; $i < $partitionCount; ++$i) {
            $position                           = $this->hasher->hash($target . $i);
            $this->positionToTarget[$position]  = $target; // Lookup.
            $this->targetToPositions[$target][] = $position; // Target removal.
        }

        ++$this->targetCount;
        $this->positionToTargetSorted = false;
    }

    /**
     * Add a list of targets.
     *
     * @param array<string> $targets
     *
     * @throws TargetException if any of $targets already exists.
     */
    public function addTargets(array $targets, float $weight = 1.0): void
    {
        foreach ($targets as $target) {
            $this->addTarget($target, $weight);
        }
    }

    /**
     * A list of all potential targets.
     *
     * @return list<string>
     */
    public function getAllTargets(): array
    {
        return array_keys($this->targetToPositions);
    }

    /**
     * Looks up the target for the given resource.
     *
     * @throws TargetException when no targets are defined.
     */
    public function lookup(string $resource): string
    {
        $targets = $this->lookupList($resource, 1);

        if ($targets === []) {
            throw TargetException::noneExist();
        }

        return $targets[0];
    }

    /**
     * Get a list of targets for the resource, in order of precedence.
     * Up to $requestedCount targets are returned, less if there are fewer in total.
     *
     *  Example:
     *  ```
     *  $hash->addTargets(['server1', 'server2', 'server3']);
     *  $servers = $hash->lookupList('my-key', 2); // ['server2', 'server1']
     *  ```
     *
     * @param positive-int $requestedCount The length of the list to return
     *
     * @return list<string> List of targets
     */
    public function lookupList(string $resource, int $requestedCount): array
    {
        // handle no targets
        if ($this->positionToTarget === []) {
            return [];
        }

        // optimize single target
        if ($this->targetCount === 1) {
            return [$this->positionToTarget[array_key_first($this->positionToTarget)]];
        }

        $this->sortPositionTargets();
        $offset = self::bisectLeft(
            $this->sortedPositions,
            $this->hasher->hash($resource),
            $this->positionCount,
        );

        $resCount = 1;
        $results  = [];

        $maxIterations = min($requestedCount, $this->targetCount);

        while ($resCount++ <= $maxIterations) {
            $offset %= $this->positionCount;
            $results[] = $this->positionToTarget[$this->sortedPositions[$offset]];
            ++$offset;
        }

        return array_values(array_unique($results));
    }

    /**
     * @throws TargetException when target does not exist.
     */
    public function removeTarget(string $target): void
    {
        if (!isset($this->targetToPositions[$target])) {
            throw TargetException::doesNotExist($target);
        }

        foreach ($this->targetToPositions[$target] as $position) {
            unset($this->positionToTarget[$position]);
        }

        unset($this->targetToPositions[$target]);

        $this->positionToTargetSorted = false;
        --$this->targetCount;
    }

    /**
     * Locate the insertion point for $value in $sortedArray to maintain sorted order.
     *
     * @param list<int> $sortedArray
     */
    public static function bisectLeft(array $sortedArray, int $value, int $arraySize): int
    {
        $low  = 0;
        $high = $arraySize - 1;

        if ($value < $sortedArray[$low]) {
            return 0;
        }

        if ($value >= $sortedArray[$high]) {
            return $arraySize; // Out of bounds.
        }

        while ($low < $high) {
            $middle = (int) (($low + $high) / 2);

            if ($sortedArray[$middle] < $value) {
                $low = $middle + 1;
            } else {
                $high = $middle;
            }
        }

        return $high;
    }

    /**
     * Sorts the internal mapping (positions to targets) by position.
     */
    private function sortPositionTargets(): void
    {
        // Sort by key (position), if not already.
        if ($this->positionToTargetSorted) {
            return;
        }

        ksort($this->positionToTarget, SORT_REGULAR);

        $this->positionToTargetSorted = true;
        $this->sortedPositions        = array_keys($this->positionToTarget);
        $this->positionCount          = \count($this->sortedPositions);
    }
}


1		<?php
2
3		declare(strict_types=1);
4
5		/**
6		* This file is part of Esi\ConsistentHash.
7		*
8		* (c) Eric Sizemore <[email protected]>
9		* (c) Paul Annesley <[email protected]>
10		*
11		* This source file is subject to the MIT license. For the full copyright and
12		* license information, please view the LICENSE file that was distributed with
13		* this source code.
14		*/
15
16		namespace Esi\ConsistentHash;
17
18		use Esi\ConsistentHash\Exception\InvalidArgumentException;
19		use Esi\ConsistentHash\Exception\TargetException;
20		use Esi\ConsistentHash\Hasher\Crc32Hasher;
21		use Esi\ConsistentHash\Hasher\HasherInterface;
22
23		use function array_key_first;
24		use function array_keys;
25		use function array_unique;
26		use function array_values;
27		use function ksort;
28		use function min;
29		use function round;
30
31		use const SORT_REGULAR;
32
33		/**
34		* A simple consistent hashing implementation with pluggable hash algorithms.
35		*/
36		final class ConsistentHash
37		{
38		/**
39		* Internal counter for current number of positions.
40		*/
41		private int $positionCount = 0;
42
43		/**
44		* Internal map of positions (hash outputs) to targets.
45		*
46		* @var array<int, string>
47		*/
48		private array $positionToTarget = [];
49
50		/**
51		* Whether the internal map of positions to targets is already sorted.
52		*/
53		private bool $positionToTargetSorted = false;
54
55		/** @var list<int> */
56		private array $sortedPositions = [];
57
58		/**
59		* Internal counter for current number of targets.
60		*/
61		private int $targetCount = 0;
62
63		/**
64		* Internal map of targets to lists of positions that target is hashed to.
65		*
66		* @var array<string, list<int>>
67		*/
68		private array $targetToPositions = [];
69
70		/**
71		* @param HasherInterface $hasher The hash algorithm, encapsulated in a HasherInterface implementation.
72		* @param int $replicas Amount of positions to hash each target to.
73		*
74		* @throws InvalidArgumentException If $replicas is not greater than 0.
75		*/
76	22	public function __construct(
77		private readonly HasherInterface $hasher = new Crc32Hasher(),
78		private readonly int $replicas = 64
79		) {
80	22	if ($replicas < 1) {
81	1	throw InvalidArgumentException::invalidReplicaAmount($replicas);
82		}
83		}
84
85		/**
86		* @throws TargetException if the $target already exists.
87		* @throws InvalidArgumentException if the $weight is less than 0.0.
88		*/
89	17	public function addTarget(string $target, float $weight = 1.0): void
90		{
91	17	if (\array_key_exists($target, $this->targetToPositions)) {
92	1	throw TargetException::alreadyExists($target);
93		}
94
95	17	if ($weight <= 0.0) {
96	1	throw InvalidArgumentException::invalidWeight($weight);
97		}
98
99	17	$this->targetToPositions[$target] = [];
100
101		// Hash the target into multiple positions.
102	17	$partitionCount = round((float) $this->replicas * $weight);
103
104	17	for ($i = 0; $i < $partitionCount; ++$i) {
105	17	$position = $this->hasher->hash($target . $i);
106	17	$this->positionToTarget[$position] = $target; // Lookup.
107	17	$this->targetToPositions[$target][] = $position; // Target removal.
108		}
109
110	17	++$this->targetCount;
111	17	$this->positionToTargetSorted = false;
112		}
113
114		/**
115		* Add a list of targets.
116		*
117		* @param array<string> $targets
118		*
119		* @throws TargetException if any of $targets already exists.
120		*/
121	2	public function addTargets(array $targets, float $weight = 1.0): void
122		{
123	2	foreach ($targets as $target) {
124	2	$this->addTarget($target, $weight);
125		}
126		}
127
128		/**
129		* A list of all potential targets.
130		*
131		* @return list<string>
132		*/
133	4	public function getAllTargets(): array
134		{
135	4	return array_keys($this->targetToPositions);
136		}
137
138		/**
139		* Looks up the target for the given resource.
140		*
141		* @throws TargetException when no targets are defined.
142		*/
143	7	public function lookup(string $resource): string
144		{
145	7	$targets = $this->lookupList($resource, 1);
146
147	7	if ($targets === []) {
148	1	throw TargetException::noneExist();
149		}
150
151	6	return $targets[0];
152		}
153
154		/**
155		* Get a list of targets for the resource, in order of precedence.
156		* Up to $requestedCount targets are returned, less if there are fewer in total.
157		*
158		* Example:
159		* ```
160		* $hash->addTargets(['server1', 'server2', 'server3']);
161		* $servers = $hash->lookupList('my-key', 2); // ['server2', 'server1']
162		* ```
163		*
164		* @param positive-int $requestedCount The length of the list to return
165		*
166		* @return list<string> List of targets
167		*/
168	14	public function lookupList(string $resource, int $requestedCount): array
169		{
170		// handle no targets
171	14	if ($this->positionToTarget === []) {
172	2	return [];
173		}
174
175		// optimize single target
176	12	if ($this->targetCount === 1) {
177	2	return [$this->positionToTarget[array_key_first($this->positionToTarget)]];
178		}
179
180	11	$this->sortPositionTargets();
181	11	$offset = self::bisectLeft(
182	11	$this->sortedPositions,
183	11	$this->hasher->hash($resource),
184	11	$this->positionCount,
185	11	);
186
187	11	$resCount = 1;
188	11	$results = [];
189
190	11	$maxIterations = min($requestedCount, $this->targetCount);
191
192	11	while ($resCount++ <= $maxIterations) {
193	11	$offset %= $this->positionCount;
194	11	$results[] = $this->positionToTarget[$this->sortedPositions[$offset]];
195	11	++$offset;
196		}
197
198	11	return array_values(array_unique($results));
199		}
200
201		/**
202		* @throws TargetException when target does not exist.
203		*/
204	4	public function removeTarget(string $target): void
205		{
206	4	if (!isset($this->targetToPositions[$target])) {
207	1	throw TargetException::doesNotExist($target);
208		}
209
210	3	foreach ($this->targetToPositions[$target] as $position) {
211	3	unset($this->positionToTarget[$position]);
212		}
213
214	3	unset($this->targetToPositions[$target]);
215
216	3	$this->positionToTargetSorted = false;
217	3	--$this->targetCount;
218		}
219
220		/**
221		* Locate the insertion point for $value in $sortedArray to maintain sorted order.
222		*
223		* @param list<int> $sortedArray
224		*/
225	11	public static function bisectLeft(array $sortedArray, int $value, int $arraySize): int
226		{
227	11	$low = 0;
228	11	$high = $arraySize - 1;
229
230	11	if ($value < $sortedArray[$low]) {
231	1	return 0;
232		}
233
234	10	if ($value >= $sortedArray[$high]) {
235	1	return $arraySize; // Out of bounds.
236		}
237
238	9	while ($low < $high) {
239	9	$middle = (int) (($low + $high) / 2);
240
241	9	if ($sortedArray[$middle] < $value) {
242	9	$low = $middle + 1;
243		} else {
244	9	$high = $middle;
245		}
246		}
247
248	9	return $high;
249		}
250
251		/**
252		* Sorts the internal mapping (positions to targets) by position.
253		*/
254	11	private function sortPositionTargets(): void
255		{
256		// Sort by key (position), if not already.
257	11	if ($this->positionToTargetSorted) {
258	5	return;
259		}
260
261	11	ksort($this->positionToTarget, SORT_REGULAR);
262
263	11	$this->positionToTargetSorted = true;
264	11	$this->sortedPositions = array_keys($this->positionToTarget);
265	11	$this->positionCount = \count($this->sortedPositions);
266		}
267		}
268

ericsizemore / consistent-hash

ConsistentHash::addTarget() A last analyzed 2025-10-14 17:24 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

ConsistentHash::addTarget() A
last analyzed 2025-10-14 17:24 UTC