C陷阱与缺陷之边界计算与不对称边界(下)

我们注意到前面代码段中出现了bufptr与&buffer[N]的比较,而buffer[N]这个元素是不存在的!数组buffer的元素下标从0到N-1,根本不可能是N。我们用这种写法:

代替了下面等效的写法:

原因在于我们要坚持遵循“不对称边界”的原则:我们要比较指针bufptr与缓冲区后第一个字符的地址,而&buffer[N]正这个地址。但是,引用一个并不存在元素又有什么意义呢?

幸运的是,我们并不需要引用这个元素,而只需要引用这个元素的地址,并且这个地址在我们遇到的所有C语言实现中又“千真万确”存在的。而且,ANSIC标准明确允许这种用法:数组中实际不存在的“溢界”元素的地址位于数组所占内存之后,这个地址可以用于进行赋值和比较。当然,如果要引用该元素,那就是非法的了。

照前面的写法,程序已经能够工作,但是我们还可以进一步优化,以提高程序的运行速度,尽管一般而论程序优化问题超过了本书所涉及的范围,但这个特定的例子中还是有值得我们考察其有关计数方面的特性。

这个程序绝大部分开销来自于每次迭代都要进行的两个检查:一个检查用于判断循环计数器是否到达终值;另一个检查用于判断缓冲区是否已满。这样做的结果就是一次只能转移一个字符到缓冲区。

假定我们有一种方法能够一次移动k个字符。大多数C语言实现(以及全部正确的ANSI C实现)都有一个库函数memcpy,可以做到这一点,而且这个函数通常是用汇编语言实现的以提高运行速度。即使你的C语言实现没有提供这个函数,自己写一个也很容易:

我们现在可以让函数bufwrite利用库函数memcpy来一次转移一批字符到缓冲区,而不是一次仅转移一个字符。循环中的每次迭代在必要时会刷新缓存,计算需要移动的字符数,移动这些字符数,最后恰当地更新计数器。如下所示:

很多编程在写出这样的程序时,总是感到有些犹豫不决,他们担心可能会写错。而有的程序似乎很有些“大无畏”精神,最后结果还是写错了。确实,像这样的代码技巧性很强,如果没有很好的理由,我们不应该尝试去做。但是如果是“师如有名”,那么理解这样的代码应该如何写就很重要了。只要我们记住前面的两个特例外推法和仔细计算边界,我们应该完全有信心做对。

在循环的入口处,n是需要转移到缓冲区的字符数。因此,只要n还大于0,也就是还有剩余字符没有被转移,循环就应该继续下去。每次进入循环体,我们将要转移的k个字符到缓冲区中,而不是像过去一样每次只转移一个字符。上面的代码中,最后四行语句管理着字符转移的过程,(1)从缓冲区中第一个未占用字符开始,复制k个字符到其中;(2)将指针bufptr指向的地址前移k个字符,使其仍然指向缓冲区中第1个未占用字符;(3)转入字符串的指针p前移k个字符;(4)将n(即待转移的字符数)减去k。我们很容易看到,这些语句正确地完成了各自任务。

在循环的一开始,仍然保留了原来版本中的第一个检查,如果缓冲区已满,则刷新之,并重置指针bufptr。这就保证了在检查之后,缓冲区还有空间。

惟一困难的部分就是k,即在保证缓冲区安全(不发生溢出)的情况下可以一次转移的最多字符数。k是下面两个数中较小的一个:输入数据中还剩余的待转移字符数(即n),以级缓冲区中未占用的字符数(即rem)。

计算rem的方法有两种。前面的例子显示了其中的一种:缓冲区中当前可用字符数(即rem),是缓冲区中总的字符数(N)减去已占用的字符数(即bufptrbuffer)的差,也就是N-(bufptr-buffer)。

另一种计算rem的方法是把缓冲区中的空余部分看成一个区间,直接计算这个区间的长度。指针bufptr指向这个区间的起点,而buffer+N(也就是&buffer[N])指向这个区间的终点(出界点)。并且它们满足“不对称边界”的条件,指针bufptr由于指向的是第1个未占用字符,因此是“入界点”;而&buffer[N]所代表的位置在数组buffer最后一个元素buffer[N-1]这后,因此是“出界点”。所以,根据我们的这一观点,缓冲区中的可用字符数(buffer+N)-bufptr。稍稍思考,我们就会发现

完全等价于

现看一个与计数有关的例子。这个例子中,我们需要编写一个程序,该程序按一定顺序生成一个整数,并将这些整数按列输出。把这个例子的要求说得更明确一点就是:程序的输出可能包括若干页的整数,每页包括NCOLS列,每列又包括NROW个元素,每个元素就是一个待输出的整数。还要注意,程序生成的整数是按列连续分布的,而不是按行分布的。

对这个例子,我们关注的重点应放在与计数有关的特性方面,因此不妨再做一些简化的假设。首先,我们假定这个程序是由两个函数print和flush来实现。而决定哪些数值应该打印,是其他程序的责任。每次当有新的数值生成时,这个另外的程序就会把数值作参数传递给print,要注意函数print仅当缓冲区已满时才打印,未满时将该数值存入缓冲区;而当最后一个数值生成出来之后,就会调用函数flush刷新,此时无论缓冲区是否已满,其中所有的数值都将被打印。其次,我们假定打印任务分别由三个函数完成:函数printnum在本页的当前位置打印一个数值;函数printnl则打印一个换行符,另起新的一行;函数printpage则打印一个分布符,另起新的一页。每一行都必须以换行符结束,即使是一页中的最后一行也必须以换行符结束后,然后再打印一个分布符。这些打印函数按照从左到右的顺序“填充”每个输出行,一行被打印后就不能被撤销或变更。

对于这个问题,我们需要意识到的第一点就是,如果要完成程序要求的任务,某种形式的缓冲区必不可少。我们必须在看到第1列所有元素之后,才可能知道第2列的第1个元素(也就是第1行的第2个元素)的内容。但是,我们又必须在打印完第1行之后,才有可能打印第1列的第2个元素(即第2行的第1个元素)。

这个缓冲区应该有多大呢?乍一看来,缓冲区似乎需要能够大到足一容纳一整页的数值;细细一想,并不需要这么大的空间:因为按照问题的定义,我们知道每页的列数与行数,那么对于最后一列中的每个元素,也就是相应行的最后一个元素,只要我们得到它的数值,就可以立即打印出来。因此,我们的缓冲区不必包括最后一列:

我们之所以声明buffer为静态数组,是为了预防它被程序的其他部分存取到。本书的4.3节详细讨论了static声明。

我们对函数print的编程策略大致如下:如果缓冲区未满,就所生成的数值放到缓冲区;而当缓冲区已清茶时,此时读入的数值就是一页中最后1列的某个元素,这时就打印出该元素所对应的行(按照上一段中所讲的,这个元素可以直接打印,不必放入缓冲区)。当一页中所有行都已经输出,我们就清空缓冲区。

需要注意,这些整数进入缓冲区的顺序与出缓冲区的顺序并不一致:我们是按列接受数值,却是按行打印数值。这就出现了一个问题在缓冲区中是同一行的元素相邻排列还是同一列的元素相邻排列?我们可以任意选择一种方式,这里假定是同一列的元素相邻排列。这咱选择使所有进入缓冲区非常地直截了当,径直连续排列下去就是了,但是出缓冲区的方式却相对复杂一些。要跟踪无素进入缓冲区时所处的位置,一个指针就足够了。我们可以初始化这指,使其指向缓冲区的第1个元素:

现在,我们对函数print的结构算是有了一点眉目。函数print接受一个整型参数,如果缓冲区还有空间,就将其置入缓冲区;否则,执行“某些暂时不能确定的操作”。让我们把目前为止对函数print的一些认识记录下来:

这里的“某些团里不能确定的操作”包括了打印当前的所有元素,使当前行的序号递增1,如果一页内的所有行都已经打印,则另起新一页。为了做到这些,很显然我们需要记住当前的行号;因此,我们声明一个局部静态变量row来存储当前行号。

我们如何做到打印当前行的所有元素?乍一想似乎漫无头绪,实际上如果看待问题的方式恰当,也就是俗话所说的“思路对了”,则相当简单,我们知道,对于序号为row的行,其第1个元素就是buffer[row],并且buffer[row]肯定存在。因为元素buffer[row]属于第1列,如果它不存在,则我们根本不可通if语句的条件判断。我们还知道,同一行中的相邻元素在缓冲区中是相隔NROWS个元素排列的。最后,我们知道指针bufptr指向的位置刚好在缓冲区中最后一个已占用元素之后。因此,我们可以通过下面这个循环语句来打印缓冲区属于当前行的所有元素(注意,当前行的最后一个元素不在缓冲区,所以是“缓冲区属于当前行的所有元素”,而不是“当前行所有元素”):

这里为了简洁起见,我们用buffer+row代替了&buffer[row];

剩下的“暂时不能确定的操作”就行简单了:打印当输入数值(即当前行的最后一个元素),打印换行符以结束当前行,如果是一页的最后一行还要另起新的一页:

因此,最后的print函数看上去就像这样:

现在我们接近大功告成了:只需要编写函数flush,它的作用是打印缓冲区中所有剩余的元素。要做到这一点,基本机制与函数ptrint中打印当前行所有元素类似,只需要将其作为内循环,在其上另外套一个外循环(作用是遍历一页中的每一行):

函数flush的这个版本显得有些太中规中矩、平白无奇了;如果最后一页包括仅仅一列甚至是不完全的一列,函数flush依然会打印出全部的一页,只不过没有元素的地方都是空白而已。事实上,即使最后一页为空,函数flush仍然还会全部打印出来,只不过一页全是空白而已。从技术上说,这种做法虽然也满足了问题定义中的要求,但却不符合程序美学的观点。如果没有数值可供打印,就应该立即停止打印。我们可以通过计算缓冲区中有多少项来做到这一点。如果缓冲区中什么也没有,我们并不需要开始新一页。

未经允许不得转载:TacuLee » C陷阱与缺陷之边界计算与不对称边界(下)

赞 (0)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址