动态储存管理小教程2012-1-9?其实这个不是真正正统的教程（甚至可以认为是不务正业），因为我使用的语言是JAS
动态储存管理小教程
2012-1-9?
其实这个不是真正正统的教程（甚至可以认为是不务正业），因为我使用的语言是JASS语言 即魔兽争霸3地图编辑器的脚本语言。（好吧 我知道石头你又该嘲笑我了。确实 整这么长时间我一张成型的图也没拿出来。。。。但是，你不能否认我的技术！！
）
但是其中算法和思想。其实和操作系统中储存管理是没啥区别的。在家各种冷，没事码码字活动活动僵硬的手指。正好也尝试以浅显易懂的方式写一下自己小小的研究成果。
JASS这个语言是很简陋的(PASCAL风格)。他本身的数组全都固定是8192长度的。这样利用率非常的低。所以我就想做一套动态分配的数组。可以自定义数组长度提高利用率。所以我这个系统应运而生。
原理概要
jass中提供的数组都是8192长度。如此的规整因此我们可以把他看成一条内存。以下称作内存数组
实际上动态数组就是一个内存分配与回收的过程。就好比切一块长条的吐司面包。把最初是一块整的面包，逐渐切成根据具体需要的小块。而不是一口吞下。因此一个动态数组就是一个内存块。如何申请动态数组就是如何切面包的问题。（下文会交替使用内存块和面包块大家知道指的是一个东西就行）
首先。我要管理这个面包，我必须要了解他。这里我要给每块内存块记录一些信息。这样我才能更好的分配他们给大家吃。
控制信息如下。
? ??struct block
? ? {? ?int state;//1 :内存块状态----1=占用、 0=空闲??
? ?? ???int initaddr;//2:内存块头地址 也就是这块空间在内存数组中的起始索引
? ?? ???int size;//3:内存块大小
? ?? ???int prev;//4:前相邻内存块索引(前指针)
? ?? ???int next;//5:后相邻内存块索引(后指针)
? ? }
这里面我是用C语言的struct表示。在jass中其实就是以5个连续整数为整体放到数组中的，这个数组姑且叫做目录表。其实就是一个清单，纪录目前都有哪些面包块，都是多大。是分配给烧饼了还是分配给山炮了。或者是还没有分配。
然后这些控制信息节点在目录表中组成了一个双向链表。即知道自己的邻居在哪。能够方便的找到相邻的内存块。
1、申请
发面包了！首先我要从一大整块面包切一刀（这一大整块面包是目录表初始生成的一个节点）。然后把切出来的一块同时记录各种信息放到目录表里。然后分配给用户一个id 就像这样 integer a=allocArray(INT,200)?
这样a就是一个200大小的整型数组了。这个a其实就是对应的内存块的控制信息节点的序号或者说索引。（因为我一个节点是包含5个数据的因此实际的索引是id*5再加上目录表初始位置）。这样就能通过目录表中的内存块信息。存取这段（数组）内存了。
存取就象这样 LoadInt(id,index);SaveInt(id,index,value)
2、回收
由于来面包party人比较多。你吃了面包，一定要自己再烤一块放到面包盘里供其他食用。否则后来到的人岂不是要饿死了。
做面包虽然复杂但对于咱们的内存块就简单多了。直接把内存块状态从占用改为空闲不就行了么！
真的这么简单？
确实是这么简单，但同时带来很大的问题。随着吃面包的人越来越多。原来那一整块面包被切的越来越碎。这样一来，后面如果来了饭量大的。每块面包都不够他吃但我们的规则又是只能拿一块。那么这个倒霉蛋是不是要注定饿死了。因此，当一个人吃完了之后又烤好新的放回去的时候。他要看下左右有没有别人新烤好放回去的面包，如果有，那他就应该回炉合并这两块或者三块面包组成一个更大块的面包。这样前面的杯具就不会发生了。这样就是释放做的最大的工作，合并相邻的空闲内存块。这里我的系统使用了一个策略即向右合并。即总是把左边的内存块合并到又边去，同时删掉左边的节点。如ABC三块A和C是空闲块。B是即将释放的。这是后会把A删掉各种信息合并到B里。变成B'C然后删掉B'把B'再合并到C里。
这样的好处是什么呢？因为我切面包总是从左开始切，那么那块面包剩余的部分（一般是较大的部分）总是在右边。这样的策略，总是能优先把内存释放到最大的那部分里。
不得不提的是，使用数组结构储存的另一大有点。上面所说的最大部分的面包在物理上总是存在数组的最左边的。而搜索可用内存块时又是从左边搜索。这样一来，分配总是从那块大的分配，而释放又总是释放到那块大的里面。这样就大大提高了内存的吞吐率，减少了内存碎片的产生。
3、存取
这个系统的重点就在于上述的分配与回首。当然存取也不得不提。
我这个系统内存理论上是没有长度限制的。我把多个数组拼成一个线性地址空间了。只需索引对8191取模即可 当然还需要分支语句使用这几个数组
具体看实际代码吧
4、相关技术
? ? 下面我讲一下目录表表本身的存储机制
? ? 其实我是把他们存到一个特殊的栈里的。这种栈只能在栈顶添加节点。但是允许在任意位置删除节点。
? ? 原理是，栈顶指针指的是逻辑上的栈顶并不代表是物理上的顶端。举例如下【sp:stack pointer 栈顶指针】
? ???0? ?1??2??3? ?4? ?5??6? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?0??1? ?2? ?3? ?4??5? ?6??7? ?8
? ? [1][2][3][4][0][0][0]??此时sp=4 如果删除第2个元素则变成 [1][(4)][3][4][0][0][0][0][0]?
? ?? ?? ?? ?? ?? ? I? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???I
? ? 这时sp=1即指向刚刚被删除的那个元素。但是刚才那个元素要储存上个栈顶的位置。用来指导sp的移动。
? ? 也即是说这种情况下，如果新数据到来，会存到第2个元素这里。同时sp为指向第2元素所指导的位置。即索引4.
? ? 以此类推。
? ? 当然需要说明的是。我的元素不止一个字段。必须有字段来表示这个位置是否是空的。
? ? 不然无法判断该位置是所存的4是业务数据还是栈顶指导数据。因此使用了块大小那个字段。
? ? 如果扫描节点时遇到一个节点的块大小是-1，则此节点是被删掉的节点，即【SP位移指导节点】(好吧自己胡乱起的名字)。
? ? 注：如果在需要位移指导时没有发现【SP位移指导节点】（其实就是初始的情况 如图1sp指的那个位置是个空节点没有指导信息）
? ? 。那么此时sp=sp+1。和普通栈一样。
这种算法的好处就是利用本身的字段空间储存一些信息。而不用进行栈顶元素以为补空。但是对于单元素节点的表不适合此方法。
5、struct vector 与类型检查
我的代码中并未提供struct解决方案（这里是想在jass语言里实现struct封装）
但是我基于这个系统可以提供一个思路。
如struct
{
??int a;
??int b;
??real c;
unit u
}
则可以这样?
integer a=allocArray(INT,2)//假设此时a=3
real b=allocArray(REAL,1)//b=11
unit u=allocArray(UNIT,1)//u=321
然后将a、b、u这3个数封装为一个数。即3210011003做为这个struct的id
然后使用这个id存取对用类型数据时再对这个数解析取出符合该类型的数就行了。
为什么要同时说下类型检查呢 因为思路和这个是一样
我的动态数组分配的id号本身是无法表示类型的如果你申请了个整型的数组id用来存取unit的起步乱套了。
因此同理 我把类型代号封装到这个id里 存取时先检查类型。
当然这些所谓的类型检查是运行期检查而已 ，很没有意义。
也正如struct的意义在于一个新的语言支持（像vj）一样。
这些东西，如果我做一个新语言，实现也就显得有那么些价值了。编译器类型检查也比这方便效率多了。
globals?
????//内存地址空间?
????integer?array?IntArray1?
????integer?array?IntArray2?
????real?array?RealArray1?
????real?array?RealArray2?
????string?array?StrArray1?
????string?array?StrArray2?
????unit?array?UnitArray1?
????unit?array?UnitArray2?
????integer?array?ContentTable//目录表?记录着系统中内存块的信息。?
????//每块内存信息作为一个节点链式储存在这个数组中?
?????integer?CTRLINFO_LEN=5//内存块控制字段的长度?具体含义上面已经有解释了?
????integer??MAXTYPE=4//这个是支持的类型的最大数目。系统会根据这个为每个类型划分目录表的存储区间?
????//目前只是用了几个常用类型如下?如果需要添加则增加MAXTYPE的值并添入类型代号即可?注意类型代号必须是依次的。?
????//例如我想加一个新类型timer?则定义integer?TIMER=4?
????integer?INT=0//代表整形?
????integer?REAL=1?
????integer?STRING=2?
????integer?UNIT=3?
????integer?test=1?
endglobals?
function?initArray?takes?nothing?returns?nothing?
//初始化内存块。也就是分配第一个内存块。?
????local?integer?atype=0?
????local?integer?initaddr?
????loop?
????????exitwhen?atype>=MAXTYPE?
????????set?initaddr=atype*R2I(8000/MAXTYPE)+atype?
????????set?ContentTable[initaddr]=1?
????????set?ContentTable[initaddr+2]=0?
????????set?ContentTable[initaddr+3]=16000?//寻址两个数组长度?
????????set?ContentTable[initaddr+4]=-1?
????????set?ContentTable[initaddr+5]=-1?
????????set?atype=atype+1?
????endloop?
endfunctionfunction?dump?takes?string?str?returns?nothing?
????call?DisplayTextToPlayer(GetLocalPlayer(),0,0,str)?
endfunction?
function?searchBlock?takes?integer?asklen,integer?initaddr?returns?integer?
????//寻找第一个满足分配要求的内存块?大多数情况总会是第一块最大的。（因为他就在位置0）?
????local?integer?n=0?
????????loop?
????????????exitwhen?ContentTable[initaddr+n*CTRLINFO_LEN+3]==0?
????????????//因为不存在内存块大小为0的内存块（被删除的块大小为-1）因此遇到这个情况说明搜索到目录表物理末端了?
????????????if(ContentTable[initaddr+n*CTRLINFO_LEN+1]==0?and?ContentTable[initaddr+n*CTRLINFO_LEN+3]>=asklen)?then?
????????????????return?n?
????????????endif?
????????????set?n=n+1?
????????endloop?
????????return?-1?
endfunction?
function?setPrevBlock?takes?integer?initaddr,integer?id,integer?previd?returns?nothing?
????//设置内存块id的前接内存块为previd?
????set?ContentTable[initaddr+id*CTRLINFO_LEN+4]=previd?
endfunction?
function?getPrevBlock?takes?integer?initaddr,integer?id?returns?integer?
????//获取内存块id的前内存接块?
????return?ContentTable[initaddr+id*CTRLINFO_LEN+4]?
endfunction?
function?setNextBlock?takes?integer?initaddr,integer?id,integer?nextid?returns?nothing?
????//设置?内存块id的后接内存块为nextid?
????set?ContentTable[initaddr+id*CTRLINFO_LEN+5]=nextid?
endfunction?
function?getNextBlock?takes?integer?initaddr,integer?id?returns?integer?
????//获取内存块id的后接内存块?
????return?ContentTable[initaddr+id*CTRLINFO_LEN+5]?
endfunction?
function?removeBlock?takes?integer?id,integer?atype?returns?nothing?
????//删除一个已经合并到其他空闲块的内存块。?
????local?integer?initaddr=atype*R2I(8000/MAXTYPE)+atype?
????local?integer?previd?
????local?integer?nextid?
????if(id==0)?then?
???????????call?dump("严重警告?第0块被删除了")//因为第0块其实是最右边的那块?因此不可能被删除?
??????
????endif?
?????if(ContentTable[initaddr+id*CTRLINFO_LEN+3]==0)?then?
????????call?BJDebugMsg("无法删除一个不存在的节点")?
????????return?
????else?
????????set?ContentTable[initaddr+id*CTRLINFO_LEN+1]=ContentTable[initaddr]?
????????set?ContentTable[initaddr+id*CTRLINFO_LEN+3]=-1//块大小变成-1?表示此节点变成sp位移指导节点?
????????set?ContentTable[initaddr]=id?
????????//以下是标准的双向链表删除节点操作?学过数据结构的都应该清楚?
????????//就是把前节点的后指针指向该节点的后节点?
????????//把后节点的前指针指向该节点的前节点?
????????set?previd=getPrevBlock(initaddr,id)?
????????set?nextid=getNextBlock(initaddr,id)?
????????if(previd>=0)?then?
????????????call?setNextBlock(initaddr,previd,nextid)?
????????endif?
????????if(nextid>=0)?then?
????????????call?setPrevBlock(initaddr,nextid,previd)?
????????endif?
?????endif?
endfunction?
?function?allocArray?takes?integer?len,integer?atype?returns?integer?
????local?integer?initaddr=atype*R2I(8000/MAXTYPE)+atype?
????local?integer?nid=-1?
????local?integer?bid=searchBlock(len,initaddr)//找到待切的蛋糕?
????if(bid==-1)?then?
????????call?MemDefrag(atype)??
????????//内存不足?
????????call?dump("内存不足！")?
????else?
????????set?nid=ContentTable[initaddr]?
????????if(nid>8000/MAXTYPE/5)?then?
????????????call?dump("内存块数量溢出!")?
????????????return?-1?
????????endif?
????????if(ContentTable[initaddr+nid*CTRLINFO_LEN+1]==0)?then//处理无sp指导信息时的sp步进位移?
????????????set?ContentTable[initaddr]=ContentTable[initaddr]+1?
????????else?
????????????set?ContentTable[initaddr]=ContentTable[initaddr+nid*CTRLINFO_LEN+1]//否则sp位移到指导信息所标识位置?
????????endif?
????????set?ContentTable[initaddr+nid*CTRLINFO_LEN+1]=1?
????????set?ContentTable[initaddr+nid*CTRLINFO_LEN+2]=ContentTable[initaddr+bid*CTRLINFO_LEN+2]?
????????set?ContentTable[initaddr+nid*CTRLINFO_LEN+3]=len?
????????set?ContentTable[initaddr+nid*CTRLINFO_LEN+4]=ContentTable[initaddr+bid*CTRLINFO_LEN+4]?
????????if(ContentTable[initaddr+bid*CTRLINFO_LEN+4]!=-1)?then?
????????????set?ContentTable[initaddr+ContentTable[initaddr+bid*CTRLINFO_LEN+4]*CTRLINFO_LEN+5]=nid?
????????endif?
????????set?ContentTable[initaddr+nid*CTRLINFO_LEN+5]=bid?
????????//set?test=test+1?
????????if(ContentTable[initaddr+bid*CTRLINFO_LEN+3]-len==0)?then//如果正好分配完?老内存块删掉?
????????????????call?removeBlock(bid,atype)?
????????else?
????????????set?ContentTable[initaddr+bid*CTRLINFO_LEN+2]=ContentTable[initaddr+bid*CTRLINFO_LEN+2]+len?
????????????set?ContentTable[initaddr+bid*CTRLINFO_LEN+3]=ContentTable[initaddr+bid*CTRLINFO_LEN+3]-len?
????????????set?ContentTable[initaddr+bid*CTRLINFO_LEN+4]=nid???????
????????endif?
????endif?
????return?nid?
endfunction?
function?destroyArray?takes?integer?id,integer?atype?returns?nothing?
????local?integer?initaddr=atype*R2I(8000/MAXTYPE)+atype?
????local?integer?flag=4?
????local?integer?nid?
????set?ContentTable[initaddr+id*CTRLINFO_LEN+1]=0?
????set?nid=ContentTable[initaddr+id*CTRLINFO_LEN+4]?//合并前接空闲块?
?????if(nid>=0?and?ContentTable[initaddr+nid*CTRLINFO_LEN+1]==0)?then?
????????set?ContentTable[initaddr+id*CTRLINFO_LEN+2]=ContentTable[initaddr+nid*CTRLINFO_LEN+2]?
????????set?ContentTable[initaddr+id*CTRLINFO_LEN+3]=ContentTable[initaddr+id*CTRLINFO_LEN+3]+ContentTable[initaddr+nid*CTRLINFO_LEN+3]?
????????set?ContentTable[initaddr+id*CTRLINFO_LEN+4]=ContentTable[initaddr+nid*CTRLINFO_LEN+4]?
????????call?removeBlock(nid,atype)?
????endif?
????set?nid=ContentTable[initaddr+id*CTRLINFO_LEN+5]//合并后接空闲快?
????if(nid>=0?and?ContentTable[initaddr+nid*CTRLINFO_LEN+1]==0)?then?
?????????set?ContentTable[initaddr+nid*CTRLINFO_LEN+2]=ContentTable[initaddr+id*CTRLINFO_LEN+2]?
?????????set?ContentTable[initaddr+nid*CTRLINFO_LEN+3]=ContentTable[initaddr+nid*CTRLINFO_LEN+3]+ContentTable[initaddr+id*CTRLINFO_LEN+3]?
?????????set?ContentTable[initaddr+nid*CTRLINFO_LEN+4]=ContentTable[initaddr+id*CTRLINFO_LEN+4]?
????????call?removeBlock(id,atype)?
????endif?
endfunction?
function?CountRealIndex?takes?integer?atype,integer?id,integer?index?returns?integer?
//计算真实的索引?
????local?integer?initaddr=atype*R2I(8000/MAXTYPE)+atype?
????local?integer?loc=ContentTable[initaddr+id*CTRLINFO_LEN+2]+index?
????if(index>=ContentTable[initaddr+id*CTRLINFO_LEN+3]?or?ContentTable[initaddr+id*CTRLINFO_LEN+1]==0)?then?
????????call?dump("非法的索引："+I2S(index))?
????endif?
????return?loc?
endfunction?
function?LDI?takes?integer?id,integer?index?returns?integer?//loadinteger?
????local?integer?loc=CountRealIndex(INT,id,index)?
???if(loc>=8100)?then?
????????return?IntArray2[loc-8100]?
????else?
????????return?IntArray1[loc]?
????endif?
endfunction?
function?SVI?takes?integer?id,integer?index,integer?val?returns?nothing?//saveinteger?
????local?integer?loc=CountRealIndex(INT,id,index)?
???if(loc>=8100)?then?
???????set?IntArray2[loc-8100]=val?
????else?
???????set?IntArray1[loc]=val?
????endif?
endfunction?
）