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

ConsistentHash::__construct() A
last analyzed 2025-08-12 19:58 UTC

↳ Parent: ConsistentHash

Complexity

Conditions	2
Paths	2

Size

Total Lines	9
Code Lines	4

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	5
CRAP Score	2

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	2
eloc	4
c	1
b	0
f	0
nc	2
nop	2
dl	0
loc	9
rs	10
ccs	5
cts	5
cp	1
crap	2

<?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\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 round;

use const SORT_REGULAR;

/**
 * A simple consistent hashing implementation with pluggable hash algorithms.
 */
class ConsistentHash
{
    /**
     * The hash algorithm, encapsulated in a HasherInterface implementation.
     */
    private HasherInterface $hasher;

    /**
     * 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;

    /**
     * The number of positions to hash each target to.
     */
    private int $replicas = 64;

    /** @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 null|HasherInterface $hasher
     * @param null|int             $replicas Amount of positions to hash each target to.
     */
    public function __construct(null|HasherInterface $hasher = null, null|int $replicas = null)
    {
        $this->hasher = $hasher ?? new Crc32Hasher();

        if ($replicas === null) {
            return;
        }

        $this->replicas = $replicas;
    }

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

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

        // Hash the target into multiple positions.
        $partitionCount = round($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->positionToTargetSorted = false;
        ++$this->targetCount;
    }

    /**
     * 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): 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 (\count($targets) === 0) {
            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.
     *
     * @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  = [];

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

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

ericsizemore / consistent-hash

ConsistentHash::__construct() A last analyzed 2025-08-12 19:58 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

ConsistentHash::__construct() A
last analyzed 2025-08-12 19:58 UTC