在项目里面有一个需求，将屏幕通过水平线分割为一个个Channel，并通过Allocator基于某一个已分配的段进行新段分配，而为了提升自己的代码设计能力和拓展性的要求，我将这个功能做成了一个Allocator功能库。
项目中只需要对线性空间进行分配，因此实现时只考虑了线性可分配区域。
首先我将每个Channel称为AllocatableRegion（以下简称Region），每个 Region都知晓其邻近Region，并拥有一个RegionId,而每一段已分配的空间被称为AllocatedSpace。每个Region都拥有一个TryOcuppy函数，参数为数轴上一段距离而返回null或者AllocatedSpace。用户只通过管理所有Region的Allocator申请空间。而申请空间时的策略通过在创建Allocator时传入一个AllocateStrategy数组指定（TODO：更改为Hub形式，但是需要考虑性能问题）。
Allocator功能库包含以下类：
- Sequence：仅代表数轴上某起始点到终点的一段距离。
- AllocatedSpace：代表某Region上已分配的一段空间。
- AllocatableRegion：代表某一个可分配区域，相邻Region通过链表指针相连。
- RegionFactory：Region生成的工厂方法。
- Allocator：用户直接操作的分配器对象。
- AllocateTask：在Allocator工具库内部使用的上下文类。
- AllocateStrategyPayload：在AllocateStrategy中使用的上下文类，成员包含AllocateTask。
- AllocateStrategyBook：AllocateStrategy数组和策略执行类。
- AllocateStrategy：分配策略。
Sequence类
sequence类表明数轴上某一段线段，同时包含比较函数和冲突检测函数。
class Sequence {
from: number;
to: number;
constructor(from: number = 0, to: number = 0) {
this.from = from;
this.to = to;
}
compare(seq: Sequence) {
return this.conflict(seq) ? 0 : this.to <= seq.from ? -1 : 1;
}
conflict(seq: Sequence) {
return !(
this.from != seq.from &&
(this.from >= seq.to || this.to <= seq.from)
);
}
}
使用：
let firstSeg = new Sequence(0,100); let conflictSeg = new Sequence(50,200); let thirdSeg = new Sequence(200,300); console.log(firstSeg.conflict(conflictSeg))//true console.log(firstSeg.conflict(thirdSeg ))//false
AllocatableRegion类
AllocatableRegion类是整个Allocator工具库的核心数据存储类，其中包含该区域所有已分配块的链表。
class AllocatableRegion<T> {
id: number = 0;
allocatedSpaceNum: number = 0;
next: AllocatableRegion<T> | null = null;
previous: AllocatableRegion<T> | null = null;
allocator: Allocator<T>;
head: AllocatedSpace<T> | null = null;
tail: AllocatedSpace<T> | null = null;
constructor(
allocator: Allocator<T>,
addEntityToRegion: (entity: T) => void
) {
this.allocator = allocator;
this.addEntityToRegion = addEntityToRegion;
}
addEntityToRegion: (entity: T) => void;
tryOccupy(req: AllocateTask<T>): AllocatedSpace<T> | null {
if (!this.head) {
this.head = new AllocatedSpace(req.seq, req.entity, this);
this.tail = this.head;
this.allocatedSpaceNum++;
this.addEntityToRegion(req.entity);
return this.head;
}
let space = null;
let node: AllocatedSpace<T> | null = this.head;
let res = 0;
while (node) {
//
res = node.seq.compare(req.seq);
if (res == 0) return null;
// req -- node
let cmp;
if (res > 0) {
if (node.previous) {
cmp = node.previous.seq.compare(req.seq);
if (cmp < 0) {
space = new AllocatedSpace(req.seq, req.entity, this);
space.next = node;
space.previous = node.previous;
node.previous.next = space;
node.previous = space;
this.allocatedSpaceNum++;
this.addEntityToRegion(req.entity);
return space;
} else if (cmp == 0) {
return null;
}
node = node.next;
continue;
} else {
space = new AllocatedSpace(req.seq, req.entity, this);
node.previous = space;
space.next = node;
this.head = space;
this.allocatedSpaceNum++;
this.addEntityToRegion(req.entity);
return space;
}
}
// node -- req
else {
if (node.next) {
cmp = node.next.seq.compare(req.seq);
if (cmp > 0) {
space = new AllocatedSpace(req.seq, req.entity, this);
space.previous = node;
space.next = node.next;
node.next.previous = space;
node.next = space;
this.allocatedSpaceNum++;
this.addEntityToRegion(req.entity);
return space;
} else if (cmp == 0) {
return null;
}
node = node.next;
continue;
} else {
space = new AllocatedSpace(req.seq, req.entity, this);
node.next = space;
space.previous = node;
this.tail = space;
this.allocatedSpaceNum++;
this.addEntityToRegion(req.entity);
return space;
}
}
}
return null;
}
tryRelease(space: AllocatedSpace<T>): boolean {
if (space.previous) {
space.previous.next = space.next;
} else {
this.head = space.next;
}
if (space.next) {
space.next.previous = space.previous;
} else {
this.tail = space.previous;
}
return true;
}
}
export class RegionFactory<T> {
private creator: {
new (
allocator: Allocator<T>,
addEntityToChannel: (entity: T) => void
): AllocatableRegion<T>;
};
addTweakFunc: (entity: T) => void;
//@ts-ignore
allocator: Allocator<T>;
constructor(
Creator: {
new (
allocator: Allocator<T>,
addEntityToChannel: (entity: T) => void
): AllocatableRegion<T>;
},
addTweakFunc: (entity: T) => void
) {
this.creator = Creator;
this.addTweakFunc = addTweakFunc;
}
create(id: number, allocator?: Allocator<T>): AllocatableRegion<T>;
create(
id: number,
previous: AllocatableRegion<T> | null,
next: AllocatableRegion<T> | null,
allocator?: Allocator<T>
): AllocatableRegion<T>;
create(
id: number,
x?: AllocatableRegion<T> | Allocator<T> | null,
y?: AllocatableRegion<T> | null,
z?: Allocator<T>
): AllocatableRegion<T> {
let region;
switch (arguments.length) {
//@ts-ignore
case 4:
case 3:
x = x as AllocatableRegion<T>;
y = y as AllocatableRegion<T>;
region = new this.creator(z ?? this.allocator, this.addTweakFunc);
region.id = id;
if (x != null) x.next = x;
if (y != null) y.previous = region;
region.previous = x;
region.next = y;
return region;
case 1:
case 2:
default:
x = x as Allocator<T>;
region = new this.creator(x ?? this.allocator, this.addTweakFunc);
region.id = id;
return region;
}
}
}
核心方法为tryOccupy(req: AllocateTask<T>): AllocatedSpace<T> | null,调用该方法会尝试占据AllocateTask中标明的区域，成功则返回AllocatedSpace没有成功则返回null，该方法由Allocator调用。其中在占有区域成功时会调用一个用户回调函数addEntityToRegion，用户可在该函数中对传入的数据实体对象进行操作。
RegionFactory为Region的工厂方法，通过该类实例化新Region。
AllocatedSpace 类
AllocatedSpace类用于表明区域某一已分配段，会作为分配成功时的返回值。该类实现接口AllocateTask，是AllocatableRegion中已分类段链表的基本项。
class AllocateTask<T> {
allocator: Allocator<T>;
seq: Sequence;
type: number;
entity: T;
base?: AllocatedSpace<T>;
constructor(
entity: T,
seq: Sequence,
allocator: Allocator<T>,
type: number = 0,
base?: AllocatedSpace<T>
) {
this.entity = entity;
this.seq = seq;
this.allocator = allocator;
this.type = type;
this.base = base;
}
}
class AllocatedSpace<T> extends AllocateTask<T> {
seq: Sequence;
entity: T;
region: AllocatableRegion<T>;
reusable: boolean = false;
type: number;
allocator: Allocator<T>;
previous: AllocatedSpace<T> | null = null;
next: AllocatedSpace<T> | null = null;
constructor(seq: Sequence, entity: T, region: AllocatableRegion<T>) {
this.seq = seq;
this.entity = entity;
this.region = region;
this.allocator = this.region.allocator;
}
safeRemove() {
if (this.previous) {
this.previous.next = this.next;
} else {
this.region.head = this.next;
}
if (this.next) {
this.next.previous = this.previous;
} else {
this.region.tail = this.previous;
}
this.region.allocatedSpaceNum--;
}
}
AllocateStrategy类
分配策略AllocateStrategy类可以看成一个独立的系统，实例化Allocator时需要传入的为分配策略书AllocateStrategyBook，该类包含分配策略列表和执行函数，而AllocateStrategy需要用户传入judeFn和自定义data，每次执行策略时， AllocateStrategyBook会通过数据负载AllocateStrategyPayload类中result值进行判断下一个需要执行的策略（TODO：具名策略，{tryOcuppyBaseChannel:…},trySecondStrategy:{….}}这样也可以有代码提示），只有result为NaN时，才判断为分配成功。
class AllocateStrategy<T> {
data?: any;
judge: (pyload: AllocateStrategyPayload<T>) => AllocateStrategyPayload<T>;
constructor(
judgeFn: (pyload: AllocateStrategyPayload<T>) => AllocateStrategyPayload<T>,
data?: any
) {
this.judge = judgeFn;
this.data = data;
}
}
class AllocateStrategyBook<T> {
strategies: AllocateStrategy<T>[] = [];
execute(task: AllocateTask<T>): AllocateStrategyPayload<T> {
let payload = new AllocateStrategyPayload<T>(task);
let missionId = 0;
let missionLength = this.strategies.length;
while (missionLength > missionId) {
payload = this.strategies[payload.to()].judge(payload);
if (isNaN(payload.result) || payload.result < 0) {
return payload;
}
}
return payload;
}
}
class AllocateStrategyPayload<T> {
task: AllocateTask<T>;
result: number = 0;
private _to: number = 0;
next(id?: number) {
return (this._to = id ?? this._to + 1);
}
to() {
return this._to;
}
constructor(task: AllocateTask<T>) {
this.task = task;
this._to = task.type;
}
}
分配策略示例：
下面tryOccupyBaseChannel为尝试占有前一个AllocatedSpace相同Region的段，如果无法占有段则payload.next()执行下一条策略。
const tryOcuppyBaseChannel: PlotAllocateStrategy = {
judge: (payload) => {
let task = payload.task;
if (!task.base) {
if (!payload.task.allocator.regions.next) {
let res = task.allocator.regions.tryOccupy(task);
if (res) {
payload.task = res;
payload.result = NaN;
return payload;
}
}
payload.next();
return payload;
}
let res = task.base.region.tryOccupy(task);
if (!res) {
payload.next();
return payload;
}
payload.result = NaN;
payload.task = res;
return payload;
},
};
Allocator类
用户通过Allocator类操作分配区域。用户使用allocate方法申请分配空间。
export class Allocator<T> {
regions: AllocatableRegion<T>;
allocateStrategy: AllocateStrategyBook<T>;
regionFactory: RegionFactory<T>;
releaseStrategy: AllocateStrategyBook<T>;
constructor(
allocateStrategy: AllocateStrategyBook<T>,
releaseStrategy: AllocateStrategyBook<T>,
regionFactory: RegionFactory<T>
) {
this.allocateStrategy = allocateStrategy;
this.releaseStrategy = releaseStrategy;
this.regionFactory = regionFactory;
this.regions = this.regionFactory.create(0);
}
allocate(
from: number,
to: number,
entity: T,
base?: AllocatedSpace<T>,
type?:number
): AllocatedSpace<T> | null;
allocate(
task: AllocateTask<T> | number,
to: number,
entity: T,
base?: AllocatedSpace<T>,
type?:number
): AllocatedSpace<T> | null {
if (typeof task == 'number') {
task = new AllocateTask(entity, new Sequence(task, to), this, type, base);
}
let res = this.allocateStrategy.execute(task);
if (res.result < 0) {
return null;
}
return res.task as AllocatedSpace<T>;
}
release(space: AllocatedSpace<T>): boolean {
let res = this.releaseStrategy.execute(space);
return res.result >= 0;
}
}
整体架构
类图关系比较复杂，有空再画。
v1.0 wep 2022/01/13 文章基本内容