开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Internet/网络编程 > P2P编程 > 查看源码
IntervalArray.h
资源名称：p2p_vod.rar　[点击查看]
上传用户：liguizhu
上传日期：2015-11-01
资源大小：2422k
文件大小：12k
源码类别：

P2P编程

开发平台：

Visual C++

IntervalArray.h：源码内容
  1. /*
  2.  *  Openmysee
  3.  *
  4.  *  This program is free software; you can redistribute it and/or modify
  5.  *  it under the terms of the GNU General Public License as published by
  6.  *  the Free Software Foundation; either version 2 of the License, or
  7.  *  (at your option) any later version.
  8.  *
  9.  *  This program is distributed in the hope that it will be useful,
  10.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.  *  GNU General Public License for more details.
  13.  *
  14.  *  You should have received a copy of the GNU General Public License
  15.  *  along with this program; if not, write to the Free Software
  16.  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17.  *
  18.  */
  19. #pragma once
  21. // 用于表示一个块的区间，start是起始块的ID，size是此区间的大小
  22. // 是一个前闭后开的区间, [start, start+size)
  23. // 实际使用中不会出现size=0的情况，因为只需要表示大小不为零的区间
  24. class BlockInterval {
  25. public:
  26. // 初始化start为非法值
  27. BlockInterval() : start(0xffffffff) {};
  28. BlockInterval(UINT s, UINT ss) : start(s), size(ss) {};
  30. static bool cmp_size(const BlockInterval& i1, const BlockInterval& i2) {
  31. return (i1.size < i2.size);
  32. };
  33. static bool cmp_start(const BlockInterval& i1, const BlockInterval& i2) {
  34. return (i1.start < i2.start);
  35. };
  36. bool operator == (const BlockInterval& a) const {
  37. return (start == a.start && size == a.size);
  38. };
  39. BlockInterval& operator=(const BlockInterval& another) {
  40. start = another.start;
  41. size = another.size;
  42.         return *this;
  43.     }
  44. // 两个区间的 & 操作，结果保存在result中
  45. static void and_op(const BlockInterval& i1, const BlockInterval& i2, BlockInterval& result) {
  46. result.start = max(i1.start, i2.start); // &区间的start
  47. result.size = min(i1.start+i1.size, i2.start+i2.size); // &区间的end，临时使用result.size保存这个值
  48. if(result.size > result.start) // 这两行把result.size当作&区间的end使用
  49. result.size = result.size-result.start;
  50. else
  51. result.size = 0;
  52. };
  54. public:
  55. UINT start; // 起始位置
  56. UINT size; // 区间大小
  57. };
  59. class IntervalArray {
  60. public:
  61. // 构造函数，指定初始化大小
  62. explicit IntervalArray() : m_array(NULL), m_totalsize(0), m_validsize(0) {
  63. };
  64. // 拷贝构造函数
  65. explicit IntervalArray(const IntervalArray& another) : m_array(NULL), m_totalsize(another.m_totalsize), m_validsize(another.m_validsize) {
  66. if(m_totalsize) {
  67. m_array = new BlockInterval[m_totalsize];
  68. memcpy(m_array, another.m_array, m_validsize*sizeof(BlockInterval));
  69. }
  70. };
  71. virtual ~IntervalArray(void) {
  72. m_totalsize = 0;
  73. m_validsize = 0;
  74. delete [] m_array;
  75. m_array = NULL;
  76. };
  78. bool operator == (const IntervalArray& a) const {
  79. if(m_validsize != a.m_validsize)
  80. return false;
  81. if(memcmp(m_array, a.m_array, sizeof(BlockInterval)*m_validsize) != 0)
  82. return false;
  83. return true;
  84. };
  85. IntervalArray& operator=(const IntervalArray& another) {
  86. m_totalsize = m_validsize = another.m_validsize;
  87. delete [] m_array;
  88. m_array = NULL;
  90. if(m_totalsize) {
  91. m_array = new BlockInterval[m_totalsize];
  92. memcpy(m_array, another.m_array, m_validsize*sizeof(BlockInterval));
  93. }
  94.         return *this;
  95. }
  97. // 将another中的区间从m_array中删除
  98. void DeleteArray(const IntervalArray& another) {
  99. for(UINT16 i = 0; i < another.m_validsize; ++i) {
  100. DelInterval(another.m_array[i].start, another.m_array[i].size);
  101. }
  102. }
  104. // 对两个区间作&操作，结果保存在result
  105. // 这个方法效率比较低, 1. 有比遍历更好的比较办法，不必对所有的区间都作&操作
  106. // 2. 生成的区间列表直接就是有序无重叠的，使用AddInterval降低了效率
  107. void AndOperator(const IntervalArray& another, IntervalArray& result) const {
  108. BlockInterval temp;
  109. result.Clear();
  110. for(UINT16 i = 0; i < another.m_validsize; ++i) {
  111. for(UINT16 j = 0; j < m_validsize; ++j) {
  112. BlockInterval::and_op(m_array[j], another.m_array[i], temp);
  113. if(temp.size > 0)
  114. result.AddInterval(temp.start, temp.size);
  115. }
  116. }
  117. }
  119. // 添加一个区间，检查区间的合并
  120. void AddInterval(UINT start, UINT size) {
  121. if(start == UINT_MAX)
  122. return;
  123. assert(size != 0);
  124. if(size == 0)
  125. return;
  126. for(UINT16 i = 0; i < m_validsize; ++i) {
  127. if(m_array[i].start > start) {
  128. if(m_array[i].start > start+size) {
  129. // 在区间i之前添加一个新区间
  130. break;
  131. }
  132. else if(m_array[i].start+m_array[i].size >= start+size) {
  133. // 新的区间和区间i融合，形成新的独立区间，所以直接返回
  134. m_array[i].size += m_array[i].start-start;
  135. m_array[i].start = start;
  136. return;
  137. }
  138. else {
  139. // 新的区间覆盖了区间i，所以删除区间i，递归调用
  140. SafeDelete(i);
  141. AddInterval(start, size);
  142. return;
  143. }
  144. }
  145. else if(m_array[i].start+m_array[i].size >= start) {
  146. if(m_array[i].start+m_array[i].size >= start+size) {
  147. // 新的区间是区间i的子集，直接返回
  148. return;
  149. }
  150. if(i == m_validsize-1 || m_array[i+1].start > start+size) {
  151. // 新的区间和区间i融合，形成新的独立区间，所以直接返回
  152. m_array[i].size = start+size-m_array[i].start;
  153. return;
  154. }
  155. // 新的区间和区间i融合，并且形成的新区间连接了后面的区间，
  156. // 所以删除区间i，把形成的新区间当作要添加的区间，递归调用
  157. // TODO: 或许有更好的办法，但一时想不到
  158. size += start - m_array[i].start;
  159. start = m_array[i].start;
  161. SafeDelete(i);
  162. AddInterval(start, size);
  163. return;
  164. }
  165. }
  166. // 在区间数组的某个位置添加区间
  167. SafeInsert(i, start, size);
  168. return;
  169. };
  170. // 删除一个区间，检查多个区间的删除
  171. void DelInterval(UINT start, UINT size) {
  172. assert(size != 0);
  173. if(size == 0)
  174. return;
  175. for(UINT16 i = 0; i < m_validsize; ++i) {
  176. if(m_array[i].start > start) {
  177. if(m_array[i].start > start+size) {
  178. // 要删除的区间根本不存在
  179. return;
  180. }
  181. else if(m_array[i].start+m_array[i].size > start+size) {
  182. // 要删除的区间包含了区间i的前半部分，后半部分形成新的独立区间
  184. // 区间i的后半部分形成的区间
  185. m_array[i].size = (m_array[i].start+m_array[i].size) - (start+size);
  186. m_array[i].start = start+size;
  187. return;
  188. }
  189. else {
  190. // 要删除的区间覆盖了区间i，所以删除区间i，递归调用
  191. SafeDelete(i);
  192. DelInterval(start, size);
  193. return;
  194. }
  195. }
  196. else if(m_array[i].start+m_array[i].size > start) {
  197. // 区间i最多可能被分为两个区间，分别称之为前一部分和后一部分
  199. // 记录区间i的大小，因为它可能被改变，而后面可能要用到
  200. UINT oldSize = m_array[i].size;
  202. if(m_array[i].start != start) {
  203. // 前一部分非空，令区间i等于其前一部分
  204. m_array[i].size = start-m_array[i].start;
  205. }
  207. if(m_array[i].start+oldSize <= start+size) {
  208. // 后一部分为空
  209. if(m_array[i].start != start) {
  210. // 前一部分非空，递归
  211. DelInterval(start, size);
  212. return;
  213. }
  214. // 前一部分为空，则删除区间i
  215. SafeDelete(i);
  216. return;
  217. }
  218. // 后一部分非空
  219. if(m_array[i].start == start) {
  220. // 前一部分为空，令区间i等于其后一部分
  221. m_array[i].size -= start+size-m_array[i].start;
  222. m_array[i].start = start+size;
  223. return;
  224. }
  225. // 前后均非空，则在区间i之后插入一个新的区间
  226. SafeInsert(i+1, start+size, m_array[i].start+oldSize - (start+size));
  227. return;
  228. }
  229. }
  230. };
  232. // 查找一个block是否存在
  233. bool FindBlock(const UINT blockID) const {
  234. for(UINT16 i = 0; i < m_validsize; ++i) {
  235. if(m_array[i].start > blockID)
  236. return false;
  237. // 注意start+size不在区间之内
  238. else if(m_array[i].start+m_array[i].size > blockID)
  239. return true;
  240. }
  241. return false;
  242. };
  244. // 复制block区间的数组到传入的指针，传入需要的区间个数，返回实际复制的区间个数
  245. // 如果需要的个数小于总个数，则取其中最大的区间
  246. void CopyIntervalArray(BlockInterval* targetArray, UINT8& size) const {
  247. if(!targetArray || size == 0)
  248. return;
  249. if(size >= m_validsize) {
  250. // 因为size >= m_validsize，所以下面的转换不会丢失数据
  251. size = static_cast<UINT8>(m_validsize);
  252. memcpy(targetArray, m_array, size*sizeof(BlockInterval));
  253. }
  254. else {
  255. // 对m_array根据每个BlockInterval的size进行从小到大的排序，然后复制最大的size个到targetArray
  256. // 最后再根据每个BlockInterval的start进行从小到大的排序，恢复m_array和targetArray
  258. std::sort(m_array, m_array+m_validsize, BlockInterval::cmp_size); // 按从大到小的顺序排序
  259. memcpy(targetArray, m_array, size*sizeof(BlockInterval)); // 复制最大的size个
  260. std::sort(m_array, m_array+m_validsize, BlockInterval::cmp_start); // 恢复原来的顺序（按startBlockID从小到大排序）
  261. std::sort(targetArray, targetArray+size, BlockInterval::cmp_start); // 使用正常的顺序（按startBlockID从小到大排序）
  262. }
  263. };
  265. // 清空列表
  266. void Clear() {
  267. m_validsize = 0;
  268. };
  270. // 是否为空
  271. bool IsEmpty() const {
  272. return (m_validsize == 0);
  273. }
  275. // 最大块的ID
  276. UINT GetMaxBlockID() const {
  277. if(m_validsize)
  278. return m_array[m_validsize-1].start+m_array[m_validsize-1].size;
  279. // 返回0表示没有任何块
  280. return 0;
  281. };
  282. // 最小块的ID
  283. UINT GetMinBlockID() const {
  284. if(m_validsize)
  285. return m_array[0].start;
  286. // 返回UINT_MAX表示没有任何块
  287. return UINT_MAX;
  288. }
  290. // 获取有效区间的个数
  291. UINT16 GetValidSize() const {
  292. return m_validsize;
  293. };
  295. // [blockID, blockID+len)中所有已经存在的块数
  296. UINT GetCountInInterval(const UINT blockID, const UINT len) const {
  297. UINT total = 0;
  299. BlockInterval result, in;
  300. in.start = blockID;
  301. in.size = min(len, UINT_MAX-blockID);
  303. for(UINT16 i = 0; i < m_validsize; ++i) {
  304. BlockInterval::and_op(m_array[i], in, result);
  305. total += result.size;
  306. }
  307. return total;
  308. };
  310. // 获取某个Block及其后的连续长度
  311. UINT GetContinousCount(const UINT blockID) const {
  312. for(UINT16 i = 0; i < m_validsize; ++i) {
  313. if(m_array[i].start > blockID)
  314. return 0;
  315. // 注意start+size不在区间之内
  316. else if(m_array[i].start+m_array[i].size > blockID) {
  317. return m_array[i].start+m_array[i].size-blockID;
  318. }
  319. }
  320. return 0;
  321. };
  323. // pop第一个区间
  324. void PopFront(BlockInterval& bi) {
  325. if(m_validsize) {
  326. bi = m_array[0];
  327. SafeDelete(0);
  328. }
  329. else
  330. memset(&bi, 0, sizeof(bi));
  331. }
  333. // 测试代码，打印出当前数组中的项
  334. void Print() const {
  335. printf("nTOTAL: %d, VALID: %d.n", m_totalsize, m_validsize);
  336. for(UINT16 i = 0; i < m_validsize; ++i) {
  337. printf("START: %d, END: %d, SIZE: %d.n", m_array[i].start, m_array[i].start+m_array[i].size, m_array[i].size);
  338. }
  339. }
  341. // 检查区间列表是否有序且无重叠
  342. bool Verify() const {
  343. for(UINT16 i = 0; i < m_validsize; ++i) {
  344. if(m_array[i].size == 0)
  345. return false;
  346. if(UINT_MAX - m_array[i].start < m_array[i].size)
  347. return false;
  348. if(i == m_validsize-1)
  349. break;
  350. if(m_array[i].start + m_array[i].size >= m_array[i+1].start)
  351. return false;
  352. }
  353. return true;
  354. }
  356. protected:
  357. // 在区间数组的某个位置添加区间，必须保证不破坏数组的有序性和无重叠性
  358. void SafeInsert(UINT16 i, UINT start, UINT size) {
  359. assert(m_validsize <= m_totalsize);
  360. assert(i <= m_validsize);
  361. assert(m_validsize <= 0xffff);
  363. // 不能再大了
  364. if(m_validsize == 0xffff)
  365. return;
  367. BlockInterval* temp = m_array;
  368. if(m_totalsize == m_validsize) {
  369. // 如果没有无效区间可以使用，那么需要增加数组大小
  370. // 分配一个空间更大的数组，并把区间i之前的数据复制过去
  371. m_array = new BlockInterval[m_validsize+1];
  372. memcpy(m_array, temp, i*sizeof(BlockInterval));
  373. }
  374. // 区间i及其之后的区间向数组尾部移动一格
  375. memcpy(m_array+i+1, temp+i, (m_validsize-i)*sizeof(BlockInterval));
  376. // 将区间i设置为新的区间
  377. m_array[i].start = start;
  378. m_array[i].size = size;
  380. // 此时m_totalsize和m_validsize尚未增加计数，所以可以用来判断是否增加过区间大小
  381. if(m_totalsize == m_validsize) {
  382. // 删除旧的数组，并增加数组大小的计数
  383. delete [] temp;
  384. ++m_totalsize;
  385. }
  387. // 增加有效区间的计数
  388. ++m_validsize;
  389. assert(m_validsize <= 0xffff);
  390. };
  392. // 删除一个区间，并把后面的区间向前移动，保证传入参数是有效的
  393. void SafeDelete(UINT16 i) {
  394. assert(i < m_validsize);
  395. ::memmove(m_array+i, m_array+i+1, (m_validsize-i-1)*sizeof(BlockInterval));
  396. --m_validsize;
  397. }
  399. private:
  400. // block区间的数组，保证无重叠和有序
  401. BlockInterval* m_array;
  402. // 数组的大小
  403. UINT16 m_totalsize;
  404. // 从数组头部开始有效区间的个数
  405. UINT16 m_validsize;
  406. };