[發明專利]針對查找樹的緩存著色內存分配方法和裝置

在審

• 申請號: 201610805579.8
• 申請日: 2016-09-06
• 公開（公告）號: CN107797941A
• 公開（公告）日: 2018-03-13
• 發明（設計）人: 賀鵬;楊馥榕;謝高崗
• 申請（專利權）人: 華為技術有限公司;中國科學院計算技術研究所
• 主分類號: G06F12/0871
• 分類號: G06F12/0871
• 代理公司: 北京同立鈞成知識產權代理有限公司11205
• 代理人: 宋揚,劉芳

1.一種針對查找樹的緩存著色內存分配方法，其特征在于，包括：

構造第一查找樹；

確定所述第一查找樹具有N層結點，所述N為大于或等于1的整數；

獲取所述N層結點中每層中具有的結點的個數；

根據所述N層結點中每層中具有的結點的個數，從內存的著色顏色中為所述每層結點分配對應的顏色；所述N層結點分配對應的顏色的種類數之和為內存的著色顏色的種類數之和；各層結點所分配的對應的顏色各不相同；

根據所述每層結點對應的顏色和所述顏色對應的內存，生成緩存著色后的第二查找樹。

2.根據權利要求1所述的方法，其特征在于，每層結點分配的對應的顏色的種類數為至少一種，其中，所述至少一種顏色在所述內存的著色顏色中是連續的。

3.根據權利要求1或2所述的方法，其特征在于，相鄰各層分配的對應的顏色在所述內存的著色顏色中是連續的。

4.根據權利要求1或2所述的方法，其特征在于，所述根據所述N層結點中每層中具有的結點的個數，從內存的著色顏色中為所述每層結點分配對應的顏色，包括：

獲取所述N層結點中的結點的個數之和為X；

根據第k層結點中的結點的個數為X_k，確定為第k層結點分配的顏色的種類數為Y_k，所述Y_k＝(X_k/X)×Y，其中，所述Y為內存的著色顏色的種類數之和；所述k為大于等于1且小于等于所述N的整數；

從所述內存的著色顏色中獲取連續的Y_k種顏色為所述第k層結點分配的對應的顏色。

5.根據權利要求3所述的方法，其特征在于，所述根據所述N層結點中每層中具有的結點的個數，從內存的著色顏色中為所述每層結點分配對應的顏色，包括：

獲取所述N層結點中的結點的個數之和為X；

根據第k層結點中的結點的個數為X_k，確定為第k層結點分配的顏色的種類數為Y_k，所述Y_k＝(X_k/X)×Y，其中，所述Y為內存的著色顏色的種類數之和；所述k為大于等于1且小于等于所述N的整數；

從所述內存的著色顏色中獲取連續的Y_k種顏色為所述第k層結點分配的對應的顏色。

6.根據權利要求1或2或5所述的方法，其特征在于，所述N層中的第k層結點中每個結點對應的在所述內存中的物理地址為A_k；

其中，當k等于1時，

當k不等于1時，

i_j為第j層結點分配的對應的顏色的種類數，H為操作系統頁大小。

7.根據權利要求3所述的方法，其特征在于，所述N層中的第k層結點中每個結點對應的在所述內存中的物理地址為Ak；

其中，當k等于1時，

當k不等于1時，

i_j為第j層結點分配的對應的顏色的種類數，H為操作系統頁大小。

8.根據權利要求4所述的方法，其特征在于，所述第k層結點中每個結點對應的在所述內存中的物理地址為A_k；

其中，當k等于1時，

當k不等于1時，

i_j為第j層結點分配的對應的顏色的種類數，H為操作系統頁大小。