2.58. Рассмотрим программу, копирующую строку саму в себя:
#include <stdio.h>
#include <string.h>
char string[] = "abcdefghijklmn";
void main(void){
memcpy(string+2, string, 5);
printf("%s\n", string);
exit(0);
символов строки... В чем дело? Дело в том, что когда
области источника (src) и получателя (dst) перекрываются, то в некий момент *src
берется из УЖЕ перезаписанной ранее области, то есть испорченной! Вот программа,
иллюстрирующая эту проблему:
#include <stdio.h>
#include <string.h>
#include <ctype.h>
char string[] = "abcdefghijklmn";
char *src = &string[0];
char *dst = &string[2];
int n = 5;
void show(int niter, char *msg){
register length, i;
printf("#%02d %s\n", niter, msg);
length = src-string;
putchar('\t');
for(i=0; i < length+3; i++) putchar(' ');
putchar('S'); putchar('\n');
printf("\t...%s...\n", string);
length = dst-string;
putchar('\t');
for(i=0; i < length+3; i++) putchar(' ');
putchar('D'); putchar('\n');
}
void main(void){
int iter = 0;
while(n-- > 0){
show(iter, "перед");
*dst++ = toupper(*src++);
show(iter++, "после");
}
exit(0);
}
Она печатает:
#00 перед
S
...abcdefghijklmn...
D
#00 после
S
...abAdefghijklmn...
D
#01 перед
S
...abAdefghijklmn...
D
#01 после
S
...abABefghijklmn...
D
#02 перед
S
...abABefghijklmn...
D
#02 после
S
...abABAfghijklmn...
D
#03 перед
S
...abABAfghijklmn...
D
#03 после
S
...abABABghijklmn...
D
#04 перед
S
...abABABghijklmn...
D
#04 после
S
...abABABAhijklmn...
D
Отрезки НЕ перекрываются, если один из них лежит либо целиком левее, либо целиком
правее другого (n - длина обоих отрезков).
dst src src dst
######## @@@@@@@@ @@@@@@@@ ########
dst+n <= src или src+n <= dst
dst <= src-n или dst >= src+n
Отрезки перекрываются в случае
! (dst <= src - n || dst >= src + n) =
(dst > src - n && dst < src + n)
При этом опасен только случай dst > src. Таким образом опасная ситуация описывается
условием
src < dst && dst < src + n
(если dst==src, то вообще ничего не надо делать). Решением является копирование "от
хвоста к голове":
void bcopy(register char *src, register char *dst,
register int n){
if(dst >= src){
dst += n-1;
src += n-1;
while(--n >= 0)
*dst-- = *src--;
}else{
while(n-- > 0)
*dst++ = *src++;
}
}
Или, ограничиваясь только опасным случаем:
void bcopy(register char *src, register char *dst,
register int n){
if(dst==src || n <= 0) return;
if(src < dst && dst < src + n) {
dst += n-1;
src += n-1;
while(--n >= 0)
*dst-- = *src--;
}else memcpy(dst, src, n);
}
Программа
#include <stdio.h>
#include <string.h>
#include <ctype.h>
char string[] = "abcdefghijklmn";
char *src = &string[0];
char *dst = &string[2];
int n = 5;
void show(int niter, char *msg){
register length, i;
printf("#%02d %s\n", niter, msg);
length = src-string;
putchar('\t');
for(i=0; i < length+3; i++) putchar(' ');
putchar('S'); putchar('\n');
printf("\t...%s...\n", string);
length = dst-string;
putchar('\t');
for(i=0; i < length+3; i++) putchar(' ');
putchar('D'); putchar('\n');
}
void main(void){
int iter = 0;
if(dst==src || n <= 0){
printf("Ничего не надо делать\n");
return;
}
< dst && dst < src + n) {
dst += n-1;
src += n-1;
while(--n >= 0){
show(iter, "перед");
*dst-- = toupper(*src--);
show(iter++, "после");
}
}else
while(n-- > 0){
show(iter, "перед");
*dst++ = toupper(*src++);
show(iter++, "после");
}
exit(0);
}
Печатает
#00 перед
S
...abcdefghijklmn...
D
#00 после
S
...abcdefEhijklmn...
D
#01 перед
S
...abcdefEhijklmn...
D
#01 после
S
...abcdeDEhijklmn...
D
#02 перед
S
...abcdeDEhijklmn...
D
#02 после
S
...abcdCDEhijklmn...
D
#03 перед
S
...abcdCDEhijklmn...
D
#03 после
S
...abcBCDEhijklmn...
D
#04 перед
S
...abcBCDEhijklmn...
D
#04 после
S
...abABCDEhijklmn...
D
Теперь bcopy() - удобная функция для копирования и сдвига массивов, в частности мас-
сивов указателей. Пусть у нас есть массив строк (выделенных malloc-ом):
char *lines[NLINES];
Тогда циклическая перестановка строк выглядит так:
void scrollUp(){
char *save = lines[0];
bcopy((char *) lines+1, /* from */
(char *) lines, /* to */
sizeof(char *) * (NLINES-1));
lines[NLINES-1] = save;
}
void scrollDown(){
char *save = lines[NLINES-1];
bcopy((char *) &lines[0], /* from */
(char *) &lines[1], /* to */
sizeof(char *) * (NLINES-1));
lines[0] = save;
}
Возможно, что написание по аналогии функции для копирования массивов элементов типа
(void *) - обобщенных указателей - может оказаться еще понятнее и эффективнее. Такая
функция - memmove - стандартно существует в UNIX SVR4. Заметьте, что порядок аргу-
ментов в ней обратный по отношению к bcopy. Следует отметить, что в SVR4 все функции
mem... имеют указатели типа (void *) и счетчик типа size_t - тип для количества байт
(вместо unsigned long); в частности длина файла имеет именно этот тип (смотри систем-
ные вызовы lseek и stat).
#include <sys/types.h>
void memmove(void *Dst, const void *Src,
register size_t n){
register caddr_t src = (caddr_t) Src,
dst = (caddr_t) Dst;
if(dst==src || n <= 0) return;
if(src < dst && dst < src + n) {
dst += n-1;
src += n-1;
while(--n >= 0)
*dst-- = *src--;
}else memcpy(dst, src, n);
}
caddr_t - это тип для указателей на БАЙТ, фактически это (unsigned char *). Зачем
вообще понадобилось использовать caddr_t? Затем, что для
void *pointer;
int n;
значение
pointer + n
не определено и невычислимо, ибо sizeof(void) не имеет смысла - это не 0, а просто
ошибка, диагностируемая компилятором!
2.59. Еще об опечатках: вот что бывает, когда вместо знака `=' печатается `-' (на
клавиатуре они находятся рядом...).
#include <stdio.h>
#include <strings.h>
char *strdup(const char *s){
extern void *malloc();
return strcpy((char *)malloc(strlen(s)+1), s);
}
char *ptr;
void main(int ac, char *av[]){
ptr - strdup("hello"); /* подразумевалось ptr = ... */
*ptr = 'H';
printf("%s\n", ptr);
free(ptr);
exit(0);
}
Дело в том, что запись (а часто и чтение) по *pointer, где pointer==NULL, приводит к
аварийному прекращению программы. В нашей программе ptr осталось равным NULL - указа-
телем в никуда. В операционной системе UNIX на машинах с аппаратной защитой памяти,
страница памяти, содержащая адрес NULL (но уже во время
выполнения программы). Это ОЧЕНЬ частая ошибка - запись по адресу NULL. MS DOS в
таких случаях предпочитает просто зависнуть, и вы бываете вынуждены играть аккорд из
трех клавиш - Ctrl/Alt/Del, так и не поняв в чем дело.
2.60. Раз уж речь зашла о функции strdup (кстати, это стандартная функция), приведем
еще одну функцию для сохранения строк.
char *savefromto(register char *from, char *upto)
{
char *ptr, *s;
if((ptr = (char *) malloc(upto - from + 1)) == NULL)
return NULL;
for(s = ptr; from < upto; from++)
*s++ = *from;
*s = '\0';
return ptr;
}
Сам символ (*upto) не сохраняется, а заменяется на '\0'.
2.61. Упрощенный аналог функции printf.
<stdio.h>
#include <ctype.h>
#include <varargs.h>
#include <errno.h>
#include <string.h>
extern int errno; /* код системной ошибки, формат %m */
/* чтение значения числа */
#define GETN(n,fmt) \
n = 0; \
while(isdigit(*fmt)){ \
n = n*10 + (*fmt - '0'); \
fmt++; \
}
void myprintf - влево */
zero, /* ширина поля начинается с 0 */
glong; /* требуется длинное целое */
1; fmt++; }
if(*fmt == '*'){
width = va_arg(ap, int);
if(width < 0){ width = -width; sign = -sign; }
fmt++;
}else{
GETN(width, fmt);
}
width *= sign;
if(*fmt == '.'){
if(*++fmt == '*'){
prec = va_arg(ap, int); fmt++;
}else{
GETN(prec, fmt);
}
}else prec = (-1); /* произвольно */
if( *fmt == 'l' ){
glong = 1; fmt++;
}
код ошибки в строку-расшифровку */
case 'u':
prUnsigned(width,
glong ? va_arg(ap, unsigned long) :
(unsigned long) va_arg(ap, unsigned int),
10 /* base */, zero); break;
case 'd':
prInteger(width,
glong ? va_arg(ap, long) : (long) va_arg(ap, int),
10 /* base */, zero); break;
case 'o':
prUnsigned(width,
glong ? va_arg(ap, unsigned long) :
(unsigned long) va_arg(ap, unsigned int),
8 /* base */, zero); break;
case 'x':
prUnsigned(width,
glong ? va_arg(ap, unsigned long) :
(unsigned long) va_arg(ap, unsigned int),
16 /* base */, zero); break;
case 'X':
prUnsigned(width,
glong ? va_arg(ap, unsigned long) :
(unsigned long) va_arg(ap, unsigned int),
-16 /* base */, zero); break;
case 'b':
prUnsigned(width,
glong ? va_arg(ap, unsigned long) :
(unsigned long) va_arg(ap, unsigned int),
2 /* base */, zero); break;
case 'a': /* address */
prUnsigned(width,
(long) (char *) va_arg(ap, char *),
16 /* base */, zero); break;
case 'A': /* address */
prUnsigned(width,
(long) (char *) va_arg(ap, char *),
-16 /* base */, zero); break;
case 'r':
prRoman(width, prec, va_arg(ap, int)); break;
case '%':
putchar('%'); break;
default:
putchar(c); break;
}
}
out:
va_end(ap);
}
/* --------------------------------------------------------- */
int strnlen(s, maxlen) char *s;
{
register n;
for( n=0; *s && n < maxlen; n++, s++ );
return n;
}
/* Печать строки */
static prStr(width, prec, s) char *s;
{
int ln; /* сколько символов выводить */
int toLeft = 0; /* к какому краю прижимать */
if(s == NULL){ pr( "(NULL)", 6); return; }
/* Измерить длину и обрубить длинную строку.
* Дело в том, что строка может не иметь \0 на конце, тогда
* strlen(s) может привести к обращению в запрещенные адреса */
ln = (prec > 0 ? strnlen(s, prec) : strlen(s));
/* ширина поля */
if( ! width ) width = (prec > 0 ? prec : ln);
if( width < 0){ width = -width; toLeft = 1; }
if( width > ln){
/* дополнить поле пробелами */
if(toLeft){ pr(s, ln); prSpace(width - ln, ' '); }
else { prSpace(width - ln, ' '); pr(s, ln); }
} else { pr(s, ln); }
}
/* Печать строки длиной l */
static pr(s, ln) register char *s; register ln;
{
for( ; ln > 0 ; ln-- )
putchar( *s++ );
}
/* Печать n символов c */
static prSpace(n, c) register n; char c;{
for( ; n > 0 ; n-- )
putchar( c );
}
/* --------------------------------------------------------- */
static char *ds;
/* Римские цифры */
static prRoman(w,p,n){
char bd[60];
ds = bd;
if( n < 0 ){ n = -n; *ds++ = '-'; }
prRdig(n,6);
*ds = '\0';
prStr(w, p, bd);
}
static prRdig(n, d){
if( !n ) return;
if( d ) prRdig( n/10, d - 2);
tack(n%10, d);
}
static tack<= n && n <= 3 ){
repeat(n, im[d+2]); return;
}
if( n == 4 )
*ds++ = im[d+2];
if( n == 4 || n == 5 ){
*ds++ = im[d+1]; return;
}
if( 6 <= n && n <= 8 ){
*ds++ = im[d+1];
repeat(n - 5, im[d+2] );
return;
}
/* n == 9 */
*ds++ = im[d+2]; *ds++ = im[d];
}
static repeat(n, c) char c;
{ while( n-- > 0 ) *ds++ = c; }
/* --------------------------------------------------------- */
static char aChar = 'A';
static prInteger(w, n, base, zero) long n;
{
/* преобразуем число в строку */
char bd[128];
int neg = 0; /* < 0 */
if( n < 0 ){ neg = 1; n = -n; }
if( base < 0 ){ base = -base; aChar = 'A'; }
else { aChar = 'a'; }
ds = bd; prUDig( n, base ); *ds = '\0';
/* Теперь печатаем строку */
prIntStr( bd, w, zero, neg );
}
static prUnsigned(w, n, base, zero) unsigned long n;
{
char bd[128];
if( base < 0 ){ base = -base; aChar = 'A'; }
else { aChar = 'a'; }
ds = bd; prUDig( n, base ); *ds = '\0';
/* Теперь печатаем строку */
prIntStr( bd, w, zero, 0 );
}
static prUDig( n, base ) unsigned long n;
{
unsigned long aSign;
if((aSign = n/base ) > 0 )
prUDig( aSign, base );
aSign = n % base;
*ds++ = (aSign < 10 ? '0' + aSign : aChar + (aSign - 10));
}
static prIntStr( s, width, zero, neg ) char *s;
{
int ln; /* сколько символов выводить */
int toLeft = 0; /* к какому краю прижимать */
ln = strlen(s); /* длина строки s */
< 0 ){ width = -width; toLeft = 1; }
> ln){
if(toLeft){ pr(s, ln); prSpace(width - ln, ' '); }
else { prSpace(width - ln, zero ? '0' : ' '); pr(s, ln); }
} else { pr(s, ln); }
}else{ /* Отрицательное число */
if(width > ln){
/* Надо заполнять оставшуюся часть поля */
} else {
putchar('-'); prSpace(width - ln, '0'); pr(s, ln);
}
}
} else { putchar('-'); pr(s, ln); }
}
}
/* --------------------------------------------------------- */
main(){
int i, n;
static char s[] = "Hello, world!\n";
static char p[] = "Hello, world";
long t = 7654321L;
myprintf( "%%abc%Y\n");
myprintf( "%s\n", "abs" );
myprintf( "%5s|\n", "abs" );
myprintf( "%-5s|\n", "abs" );
myprintf( "%5s|\n", "xyzXYZ" );
myprintf( "%-5s|\n", "xyzXYZ" );
myprintf( "%5.5s|\n", "xyzXYZ" );
myprintf( "%-5.5s|\n", "xyzXYZ" );
myprintf( "%r\n", 444 );
myprintf( "%r\n", 999 );
myprintf( "%r\n", 16 );
myprintf( "%r\n", 18 );
myprintf( "%r\n", 479 );
myprintf( "%d\n", 1234 );
myprintf( "%d\n", -1234 );
myprintf( "%ld\n", 97487483 );
myprintf( "%2d|%2d|\n", 1, -3 );
myprintf( "%-2d|%-2d|\n", 1, -3 );
myprintf( "%02d|%2d|\n", 1, -3 );
myprintf( "%-02d|%-2d|\n", 1, -3 );
myprintf( "%5d|\n", -12 );
myprintf( "%05d|\n", -12 );
myprintf( "%-5d|\n", -12 );
myprintf( "%-05d|\n", -12 );
for( i = -6; i < 6; i++ )
myprintf( "width=%2d|%0*d|%0*d|%*d|%*d|\n", i,
i, 123, i, -123, i, 123, i, -123);
myprintf( "%s at location %a\n", s, s );
myprintf( "%ld\n", t );
n = 1; t = 1L;
for( i=0; i < 34; i++ ){
myprintf( "for %2d |%016b|%d|%u|\n\t |%032lb|%ld|%lu|\n",
i, n, n, n, t, t, t );
n *= 2;
t *= 2;
}
myprintf( "%8x %8X\n", 7777, 7777 );
myprintf( "|%s|\n", p );
myprintf( "|%10s|\n", p );
myprintf( "|%-10s|\n", p );
myprintf( "|%20s|\n", p );
myprintf( "|%-20s|\n", p );
myprintf( "|%20.10s|\n", p );
myprintf( "|%-20.10s|\n", p );
myprintf( "|%.10s|\n", p );
}
Выдача этой программы:
%abcY
abs
abs|
abs |
xyzXYZ|
xyzXYZ|
xyzXY|
xyzXY|
CDXLIV
CMXCIX
XVI
XVIII
CDLXXIX
1234
-1234
97487483
1|-3|
1 |-3|
01|-3|
1 |-3|
-12|
-0012|
-12 |
-12 |
width=-6|123 |-123 |123 |-123 |
width=-5|123 |-123 |123 |-123 |
width=-4|123 |-123|123 |-123|
width=-3|123|-123|123|-123|
width=-2|123|-123|123|-123|
width=-1|123|-123|123|-123|
width= 0|123|-123|123|-123|
width= 1|123|-123|123|-123|
width= 2|123|-123|123|-123|
width= 3|123|-123|123|-123|
width= 4|0123|-123| 123|-123|
width= 5|00123|-0123| 123| -123|
Hello, world!
at location 400980
7654321
for 0 |0000000000000001|1|1|
|00000000000000000000000000000001|1|1|
for 1 |0000000000000010|2|2|
|00000000000000000000000000000010|2|2|
for 2 |0000000000000100|4|4|
|00000000000000000000000000000100|4|4|
for 3 |0000000000001000|8|8|
|00000000000000000000000000001000|8|8|
for 4 |0000000000010000|16|16|
|00000000000000000000000000010000|16|16|
for 5 |0000000000100000|32|32|
|00000000000000000000000000100000|32|32|
for 6 |0000000001000000|64|64|
|00000000000000000000000001000000|64|64|
for 7 |0000000010000000|128|128|
|00000000000000000000000010000000|128|128|
for 8 |0000000100000000|256|256|
|00000000000000000000000100000000|256|256|
for 9 |0000001000000000|512|512|
|00000000000000000000001000000000|512|512|
for 10 |0000010000000000|1024|1024|
|00000000000000000000010000000000|1024|1024|
for 11 |0000100000000000|2048|2048|
|00000000000000000000100000000000|2048|2048|
for 12 |0001000000000000|4096|4096|
|00000000000000000001000000000000|4096|4096|
for 13 |0010000000000000|8192|8192|
|00000000000000000010000000000000|8192|8192|
for 14 |0100000000000000|16384|16384|
|00000000000000000100000000000000|16384|16384|
for 15 |1000000000000000|32768|32768|
|00000000000000001000000000000000|32768|32768|
for 16 |10000000000000000|65536|65536|
|00000000000000010000000000000000|65536|65536|
for 17 |100000000000000000|131072|131072|
|00000000000000100000000000000000|131072|131072|
for 18 |1000000000000000000|262144|262144|
|00000000000001000000000000000000|262144|262144|
for 19 |10000000000000000000|524288|524288|
|00000000000010000000000000000000|524288|524288|
for 20 |100000000000000000000|1048576|1048576|
|00000000000100000000000000000000|1048576|1048576|
for 21 |1000000000000000000000|2097152|2097152|
|00000000001000000000000000000000|2097152|2097152|
for 22 |10000000000000000000000|4194304|4194304|
|00000000010000000000000000000000|4194304|4194304|
for 23 |100000000000000000000000|8388608|8388608|
|00000000100000000000000000000000|8388608|8388608|
for 24 |1000000000000000000000000|16777216|16777216|
|00000001000000000000000000000000|16777216|16777216|
for 25 |10000000000000000000000000|33554432|33554432|
|00000010000000000000000000000000|33554432|33554432|
for 26 |100000000000000000000000000|67108864|67108864|
|00000100000000000000000000000000|67108864|67108864|
for 27 |1000000000000000000000000000|134217728|134217728|
|00001000000000000000000000000000|134217728|134217728|
for 28 |10000000000000000000000000000|268435456|268435456|
|00010000000000000000000000000000|268435456|268435456|
for 29 |100000000000000000000000000000|536870912|536870912|
|00100000000000000000000000000000|536870912|536870912|
for 30 |1000000000000000000000000000000|1073741824|1073741824|
|01000000000000000000000000000000|1073741824|1073741824|
for 31 |10000000000000000000000000000000|-2147483648|2147483648|
|10000000000000000000000000000000|-2147483648|2147483648|
for 32 |0000000000000000|0|0|
|00000000000000000000000000000000|0|0|
for 33 |0000000000000000|0|0|
|00000000000000000000000000000000|0|0|
1e61 1E61
|Hello, world|
|Hello, world|
|Hello, world|
| Hello, world|
|Hello, world |
| Hello, wor|
|Hello, wor |
|Hello, wor|
2.62. Рассмотрим программу суммирования векторов:
int A[1024], B[1024], C[1024];
...
for(i=0; i < 1024; i++) C[i] = A[i] + B[i];
А почему бы не
for(i=1024-1; i >=0 ; --i) ...;
А почему бы не в произвольном порядке?
foreach i in (0..1023) ...;
в том порядке, в котором вы ему велели. Только самые сов-
ременные компиляторы на многопроцессорных системах умеют автоматически распараллели-
вать такие циклы. Сам язык Си не содержит средств указания параллельности (разве что
снова - библиотеки и системные вызовы для этого).
[Назад] [Содержание] [Вперед]
| Главная |