intervalarray.h

mysee网络直播源代码Mysee Lite是Mysee独立研发的网络视频流媒体播放系统。在应有了P2P技术和一系列先进流媒体技术之后

/*
 *  Openmysee
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */
#pragma once

// 用于表示一个块的区间，start是起始块的ID，size是此区间的大小
// 是一个前闭后开的区间, [start, start+size)
// 实际使用中不会出现size=0的情况，因为只需要表示大小不为零的区间
class BlockInterval {
public:
	// 初始化start为非法值
	BlockInterval() : start(0xffffffff) {};
	BlockInterval(UINT s, UINT ss) : start(s), size(ss) {};

	static bool cmp_size(const BlockInterval& i1, const BlockInterval& i2) {
		return (i1.size < i2.size);
	};
	static bool cmp_start(const BlockInterval& i1, const BlockInterval& i2) {
		return (i1.start < i2.start);
	};
	bool operator == (const BlockInterval& a) const {
		return (start == a.start && size == a.size);
	};
	BlockInterval& operator=(const BlockInterval& another) {
		start = another.start;
		size = another.size;
        return *this;
    }
	// 两个区间的 & 操作，结果保存在result中
	static void and_op(const BlockInterval& i1, const BlockInterval& i2, BlockInterval& result) {
		result.start = max(i1.start, i2.start);	// &区间的start
		result.size = min(i1.start+i1.size, i2.start+i2.size); // &区间的end，临时使用result.size保存这个值
		if(result.size > result.start)	// 这两行把result.size当作&区间的end使用
			result.size = result.size-result.start;
		else
			result.size = 0;
	};

public:
	UINT	start;	// 起始位置
	UINT	size;	// 区间大小
};

class IntervalArray {
public:
	// 构造函数，指定初始化大小
	explicit IntervalArray() : m_array(NULL), m_totalsize(0), m_validsize(0) {
	};
	// 拷贝构造函数
	explicit IntervalArray(const IntervalArray& another) : m_array(NULL), m_totalsize(another.m_totalsize), m_validsize(another.m_validsize) {
		if(m_totalsize) {
			m_array = new BlockInterval[m_totalsize];
			memcpy(m_array, another.m_array, m_validsize*sizeof(BlockInterval));
		}
	};
	virtual ~IntervalArray(void) {
		m_totalsize = 0;
		m_validsize = 0;
		delete [] m_array;
		m_array = NULL;
	};

	bool operator == (const IntervalArray& a) const {
		if(m_validsize != a.m_validsize)
			return false;
		if(memcmp(m_array, a.m_array, sizeof(BlockInterval)*m_validsize) != 0)
			return false;
		return true;
	};
	IntervalArray& operator=(const IntervalArray& another) {
		m_totalsize = m_validsize = another.m_validsize;
		delete [] m_array;
		m_array = NULL;

		if(m_totalsize) {
			m_array = new BlockInterval[m_totalsize];
			memcpy(m_array, another.m_array, m_validsize*sizeof(BlockInterval));
		}
        return *this;
	}

	// 将another中的区间从m_array中删除
	void DeleteArray(const IntervalArray& another) {
		for(UINT16 i = 0; i < another.m_validsize; ++i) {
			DelInterval(another.m_array[i].start, another.m_array[i].size);
		}
	}

	// 对两个区间作&操作，结果保存在result
	// 这个方法效率比较低, 1. 有比遍历更好的比较办法，不必对所有的区间都作&操作
	// 2. 生成的区间列表直接就是有序无重叠的，使用AddInterval降低了效率
	void AndOperator(const IntervalArray& another, IntervalArray& result) const {
		BlockInterval temp;
		result.Clear();
		for(UINT16 i = 0; i < another.m_validsize; ++i) {
			for(UINT16 j = 0; j < m_validsize; ++j) {
				BlockInterval::and_op(m_array[j], another.m_array[i], temp);
				if(temp.size > 0)
					result.AddInterval(temp.start, temp.size);
			}
		}
	}

	// 添加一个区间，检查区间的合并
	void AddInterval(UINT start, UINT size) {
		if(start == UINT_MAX)
			return;
		assert(size != 0);
		if(size == 0)
			return;
		for(UINT16 i = 0; i < m_validsize; ++i) {
			if(m_array[i].start > start) {
				if(m_array[i].start > start+size) {
					// 在区间i之前添加一个新区间
					break;
				}
				else if(m_array[i].start+m_array[i].size >= start+size) {
					// 新的区间和区间i融合，形成新的独立区间，所以直接返回
					m_array[i].size += m_array[i].start-start;
					m_array[i].start = start;
					return;
				}
				else {
					// 新的区间覆盖了区间i，所以删除区间i，递归调用
					SafeDelete(i);
					AddInterval(start, size);
					return;
				}
			}
			else if(m_array[i].start+m_array[i].size >= start) {
				if(m_array[i].start+m_array[i].size >= start+size) {
					// 新的区间是区间i的子集，直接返回
					return;
				}
				if(i == m_validsize-1 || m_array[i+1].start > start+size) {
					// 新的区间和区间i融合，形成新的独立区间，所以直接返回
					m_array[i].size = start+size-m_array[i].start;
					return;
				}
				// 新的区间和区间i融合，并且形成的新区间连接了后面的区间，
				// 所以删除区间i，把形成的新区间当作要添加的区间，递归调用
				// TODO: 或许有更好的办法，但一时想不到
				size += start - m_array[i].start;
				start = m_array[i].start;

				SafeDelete(i);
				AddInterval(start, size);
				return;
			}
		}
		// 在区间数组的某个位置添加区间
		SafeInsert(i, start, size);
		return;
	};
	// 删除一个区间，检查多个区间的删除
	void DelInterval(UINT start, UINT size) {
		assert(size != 0);
		if(size == 0)
			return;
		for(UINT16 i = 0; i < m_validsize; ++i) {
			if(m_array[i].start > start) {
				if(m_array[i].start > start+size) {
					// 要删除的区间根本不存在
					return;
				}
				else if(m_array[i].start+m_array[i].size > start+size) {
					// 要删除的区间包含了区间i的前半部分，后半部分形成新的独立区间

					// 区间i的后半部分形成的区间
					m_array[i].size = (m_array[i].start+m_array[i].size) - (start+size);
					m_array[i].start = start+size;
					return;
				}
				else {
					// 要删除的区间覆盖了区间i，所以删除区间i，递归调用
					SafeDelete(i);
					DelInterval(start, size);
					return;
				}
			}
			else if(m_array[i].start+m_array[i].size > start) {
				// 区间i最多可能被分为两个区间，分别称之为前一部分和后一部分

				// 记录区间i的大小，因为它可能被改变，而后面可能要用到
				UINT oldSize = m_array[i].size;

				if(m_array[i].start != start) {
					// 前一部分非空，令区间i等于其前一部分
					m_array[i].size = start-m_array[i].start;
				}

				if(m_array[i].start+oldSize <= start+size) {
					// 后一部分为空
					if(m_array[i].start != start) {
						// 前一部分非空，递归
						DelInterval(start, size);
						return;
					}
					// 前一部分为空，则删除区间i
					SafeDelete(i);
					return;
				}
				// 后一部分非空
				if(m_array[i].start == start) {
					// 前一部分为空，令区间i等于其后一部分
					m_array[i].size -= start+size-m_array[i].start;
					m_array[i].start = start+size;
					return;
				}
				// 前后均非空，则在区间i之后插入一个新的区间
				SafeInsert(i+1, start+size, m_array[i].start+oldSize - (start+size));
				return;
			}
		}
	};

	// 查找一个block是否存在
	bool FindBlock(const UINT blockID) const {
		for(UINT16 i = 0; i < m_validsize; ++i) {
			if(m_array[i].start > blockID)
				return false;
			// 注意start+size不在区间之内
			else if(m_array[i].start+m_array[i].size > blockID)
				return true;
		}
		return false;
	};

	// 复制block区间的数组到传入的指针，传入需要的区间个数，返回实际复制的区间个数
	// 如果需要的个数小于总个数，则取其中最大的区间
	void CopyIntervalArray(BlockInterval* targetArray, UINT8& size) const {
		if(!targetArray || size == 0)
			return;
		if(size >= m_validsize) {
			// 因为size >= m_validsize，所以下面的转换不会丢失数据
			size = static_cast<UINT8>(m_validsize);
			memcpy(targetArray, m_array, size*sizeof(BlockInterval));
		}
		else {
			// 对m_array根据每个BlockInterval的size进行从小到大的排序，然后复制最大的size个到targetArray
			// 最后再根据每个BlockInterval的start进行从小到大的排序，恢复m_array和targetArray
			
			std::sort(m_array, m_array+m_validsize, BlockInterval::cmp_size);	// 按从大到小的顺序排序
			memcpy(targetArray, m_array, size*sizeof(BlockInterval));		// 复制最大的size个
			std::sort(m_array, m_array+m_validsize, BlockInterval::cmp_start);	// 恢复原来的顺序（按startBlockID从小到大排序）
			std::sort(targetArray, targetArray+size, BlockInterval::cmp_start);	// 使用正常的顺序（按startBlockID从小到大排序）
		}
	};

	// 清空列表
	void Clear() {
		m_validsize = 0;
	};

	// 是否为空
	bool IsEmpty() const {
		return (m_validsize == 0);
	}

	// 最大块的ID
	UINT GetMaxBlockID() const {
		if(m_validsize)
			return m_array[m_validsize-1].start+m_array[m_validsize-1].size;
		// 返回0表示没有任何块
		return 0;
	};
	// 最小块的ID
	UINT GetMinBlockID() const {
		if(m_validsize)
			return m_array[0].start;
		// 返回UINT_MAX表示没有任何块
		return UINT_MAX;
	}

	// 获取有效区间的个数
	UINT16 GetValidSize() const {
		return m_validsize;
	};

	// [blockID, blockID+len)中所有已经存在的块数
	UINT GetCountInInterval(const UINT blockID, const UINT len) const {
		UINT total = 0;

		BlockInterval result, in;
		in.start = blockID;
		in.size = min(len, UINT_MAX-blockID);

		for(UINT16 i = 0; i < m_validsize; ++i) {
			BlockInterval::and_op(m_array[i], in, result);
			total += result.size;
		}
		return total;
	};

	// 获取某个Block及其后的连续长度
	UINT GetContinousCount(const UINT blockID) const {
		for(UINT16 i = 0; i < m_validsize; ++i) {
			if(m_array[i].start > blockID)
				return 0;
			// 注意start+size不在区间之内
			else if(m_array[i].start+m_array[i].size > blockID) {
				return m_array[i].start+m_array[i].size-blockID;
			}
		}
		return 0;
	};

	// pop第一个区间
	void PopFront(BlockInterval& bi) {
		if(m_validsize) {
			bi = m_array[0];
			SafeDelete(0);
		}
		else
			memset(&bi, 0, sizeof(bi));
	}

	// 测试代码，打印出当前数组中的项
	void Print() const {
		printf("\nTOTAL: %d, VALID: %d.\n", m_totalsize, m_validsize);
		for(UINT16 i = 0; i < m_validsize; ++i) {
			printf("START: %d, END: %d, SIZE: %d.\n", m_array[i].start, m_array[i].start+m_array[i].size, m_array[i].size);
		}
	}

	// 检查区间列表是否有序且无重叠
	bool Verify() const {
		for(UINT16 i = 0; i < m_validsize; ++i) {
			if(m_array[i].size == 0)
				return false;
			if(UINT_MAX - m_array[i].start < m_array[i].size)
				return false;
			if(i == m_validsize-1)
				break;
			if(m_array[i].start + m_array[i].size >= m_array[i+1].start)
				return false;
		}
		return true;
	}

protected:
	// 在区间数组的某个位置添加区间，必须保证不破坏数组的有序性和无重叠性
	void SafeInsert(UINT16 i, UINT start, UINT size) {
		assert(m_validsize <= m_totalsize);
		assert(i <= m_validsize);
		assert(m_validsize <= 0xffff);

		// 不能再大了
		if(m_validsize == 0xffff)
			return;

		BlockInterval* temp = m_array;
		if(m_totalsize == m_validsize) {
			// 如果没有无效区间可以使用，那么需要增加数组大小
			// 分配一个空间更大的数组，并把区间i之前的数据复制过去
			m_array = new BlockInterval[m_validsize+1];
			memcpy(m_array, temp, i*sizeof(BlockInterval));
		}
		// 区间i及其之后的区间向数组尾部移动一格
		memcpy(m_array+i+1, temp+i, (m_validsize-i)*sizeof(BlockInterval));
		// 将区间i设置为新的区间
		m_array[i].start = start;
		m_array[i].size = size;

		// 此时m_totalsize和m_validsize尚未增加计数，所以可以用来判断是否增加过区间大小
		if(m_totalsize == m_validsize) {
			// 删除旧的数组，并增加数组大小的计数
			delete [] temp;
			++m_totalsize;
		}

		// 增加有效区间的计数
		++m_validsize;
		assert(m_validsize <= 0xffff);
	};

	// 删除一个区间，并把后面的区间向前移动，保证传入参数是有效的
	void SafeDelete(UINT16 i) {
		assert(i < m_validsize);
		::memmove(m_array+i, m_array+i+1, (m_validsize-i-1)*sizeof(BlockInterval));
		--m_validsize;
	}

private:
	// block区间的数组，保证无重叠和有序
	BlockInterval* m_array;
	// 数组的大小
	UINT16 m_totalsize;
	// 从数组头部开始有效区间的个数
	UINT16 m_validsize;
};