Богатырев Андрей. Хрестоматия по программированию на Си в Unix

sprintf( buf, " '%c'", c );
}else if( ! isprint( c ))
sprintf( buf, "\\%3o", c );
else sprintf( buf, " %c ", c );
return buf;
}

main( argc, argv ) char **argv; {
FILE *fp;

if( argc == 1 ) process( stdin );
else{ argv++; argc--;
while( *argv ){
printf( "----- FILE %s -----\n", *argv );
if((fp = fopen( *argv, "r" )) == NULL ){
printf( "Can not open\n" );
}else{ process( fp ); fclose( fp ); }
argv++; argc--;
}
}
exit(0);
}

/* обработать файл с поинтером fp */
process( fp ) FILE *fp;
{ register i; int c; int n;

/* зачистка счетчиков */
for( i=0; i < 256; i++ ) cnt[i] = 0L;
for( i=0; i < 8 ; i++ ) bcnt[i] = 0;

while( ( c=getc(fp)) != EOF ){
c &= 0377;
/* подсчитать букву */
cnt[ c ] ++;
/* подсчет битов */
for( i=0; i < 8; i++ )
if( c & masks[i] )
bcnt[ i ] ++;
}
/* выдача результатов в COL колонок */
#define COL 4
printf( "\tASCII map\n" );
for( n=i=0; i < 256; i++ ){
/* if( cnt[i] == 0l ) continue; */
printf( "%s %5ld |", pr(i), cnt[i] );

if( ++n == COL ){ n = 0; putchar('\n'); }
/* или if((i % COL) == (COL-1)) putchar('\n'); */
}
printf( "\n\tBITS map\n" );
for( i=7; i >=0 ; i-- ) printf( "%6d ", i );
putchar( '\n' );
for( i=7; i >=0 ; i-- )
printf( "%6ld ", bcnt[i] );
putchar( '\n' ); putchar( '\n' );
}

/* Пример 3 */

/* Центрирование строк текста. Пример на работу с указателями. */
/* Входные строки не должны содержать табуляций */
/* Вызов: a.out < входной_файл */

#include <stdio.h>
extern char *gets();
#define WIDTH 60 /* ширина листа */
main(){
char rd[81]; register char *s;
char *head, /* начало текста */
*tail; /* конец текста */
register int len, i;
int shift; /* отступ */

/* Читать со стандартного ввода в rd по одной строке,
* пока файл не кончится. При вводе с клавиатуры конец файла
* обозначается нажатием клавиш CTRL+D
*/
while( gets( rd ) != NULL ){
if( !*rd ){
/* Строка пуста */
putchar( '\n' ); continue;
}
/* пропуск пробелов в начале строки */
for( s = rd; *s == ' ' ; s++ );
if( ! *s ){
/* Строка состоит только из пробелов */
putchar( '\n' ); continue;
}
head = s;

/* встать на конец строки */
while( *s ) s++;

/* искать последний непробел */
s--;
while( *s == ' ' && s != rd ) s--;
tail = s;

/* Длина текста */ len = (tail-head) + 1;
/* разность указателей - целое */
shift = (WIDTH - len)/2;
if(shift < 0 ){
fprintf(stderr, "Строка длиннее чем %d\n", WIDTH );
shift = 0;
}
/* Печать результата */
for( i=0; i < shift; i++ ) putchar( ' ' );

while( head <= tail ) putchar( *head++ );
putchar( '\n' );
}
}

/* Пример 4 */
/* Предварительная разметка текста для nroff */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h> /* прототип strchr() */
#include <locale.h>
FILE *fout = stdout; /* канал вывода */

/* Состояния вывода */
#define SPACE 0 /* пробелы */
#define TEXT 1 /* текст */
#define PUNCT 2 /* знаки препинания */

#define UC(c) ((unsigned char)(c))

/* Вывод строки текста из буфера */
void putstr (FILE *fp, unsigned char *s) {
/* Punct - знаки препинания, требующие приклеивания к
* концу предыдущего слова.
* PunctS - знаки, всегда требующие после себя пробела.
* PunctN - знаки, которые могут следовать за знаком
* препинания без пробела.
*/
static char Punct [] = ",:;!?.)" ;
static char PunctS[] = ",:;" ;
static char PunctN[] = " \t\"'" ;
#define is(c, set) (strchr(set, UC(c)) != NULL)
int c, state = TEXT, cprev = 'X';

while ((c = *s) != '\0') {
/* Пробелы */
if(isspace(c)) state = SPACE;

/* Знаки препинания. Пробелы перед ними игнорируются.
*/ else if(is(c, Punct)){
switch(state){
case SPACE: if(is(cprev, Punct ) && cprev==c && c != ')')
putc(' ', fp);
/* а просто пробелы - игнорировать */ break;
case PUNCT: if(is(cprev, PunctS)) putc(' ', fp); break;
}
putc(cprev = c, fp); /* выводим сам знак */
state = PUNCT;
} else {
/* Несколько пробелов сворачиваем в один */
switch(state){
case SPACE: putc(' ', fp); break;
case PUNCT: if(!is(c, PunctN)) putc(' ', fp); break;
}
putc(cprev = c, fp); /* сама буква */
state = TEXT;
if(c == '\\') putc('e', fp);
}
s++;
} /* пробелы в конце строки просто игнорируются */
putc ('\n', fp);
}
/* Обработать файл с именем name */
void proceed (char *name) {
FILE *fp;
static unsigned char inp[2048];
/* достаточно большой буфер ввода */

if (strcmp(name, "-") == 0 ) fp = stdin;
else if ((fp = fopen (name, "r")) == NULL) {
fprintf (stderr, "Cannot read %s\n", name);
return;
}
while (fgets (inp, sizeof inp, fp) != NULL) {
register unsigned char *s, *p;
int len = strlen (inp);
if (len && inp[len - 1] == '\n')
inp[--len] = '\0';
if (!*inp) {
/* .sp N - пропуск N пустых строк */
space: fprintf (fout, ".sp 1\n");
continue;
}

/* обрезать концевые пробелы */
for(p = NULL, s = inp; *s; ++s){
if (!isspace (*s)) p = s;
}
if(p) p[1] = '\0';
else goto space;
/* p указывает на последний непробел */

/* Удалить переносы слов в конце строки: перенос - это
минус, прижатый к концу слова */
if (*p == '-' && p != inp /* не в начале строки */
&& isalnum(UC(p[-1])) /* после буквы */
){ int c; *p = '\0'; /* затереть перенос */
/* Читаем продолжение слова из начала следующей строки */
while (isspace (c = getc (fp)));
ungetc (c, fp);
while ((c = getc (fp)) != '\n' && !isspace (c))
*p++ = c;
*p = '\0';
if (c != '\n' ){ /* прочли пробел */
/* вычитываем ВСЕ пробелы */
while (isspace(c = getc (fp)));
if(c != '\n') ungetc (c, fp);
}
}
/* .pp - директива начала абзаца. */
if (isspace (*inp)) {
fprintf (fout, ".pp\n");
for (s = inp; isspace (*s); s++);
putstr (fout, s);
}
else {
if (*inp == '.' || *inp == '\'')
fprintf (fout, "\\&");
putstr (fout, inp);
}
}
if( fp != stdin ) fclose (fp);
}

int main (int argc, char *argv[]) {
int i;
setlocale(LC_ALL, "");
for (i = 1; i < argc; i++)
proceed (argv[i]);
return 0; /* exit code */
}

/* Пример 5 */

/* Программа, распечатывающая слова в строках файла в обратном порядке */

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <locale.h>
#define MAXL 255 /* макс. длина строки */

/* Если бы мы не включили ctype.h, то мы должны были бы определить
* #define isspace(c) ((c) == ' ' || (c) == '\t' || (c) == '\f')
*/
main ( argc, argv ) char **argv;{
setlocale(LC_ALL, "");
if( argc == 1 ){
/* программа вызвана без аргументов */
munch( "" );
}else{
/* аргументы программы - имена файлов */
while( argv[ 1 ] ){
munch( argv[1] );
argv++;
argc--;
}
}
total(); exit(0);
}

/* обработать файл с именем name */
munch( name ) char *name;
{
char l[MAXL]; /* буфер для очередной строки */
int len; /* длина этой строки */
char *words[50]; /* таблица полей строки */
char **s; /* служебная */
int nwords; /* число слов в строке */

FILE *fp;

if( name == NULL || !*name )
fp = stdin; /* стандартный ввод */
else
if( (fp = fopen( name, "r" )) == NULL ){
fprintf( stderr, "Не могу открыть файл %s\n",
name );
return;
}

printf( "----------------------------%s----\n", name );
while( fgets( l, MAXL, fp ) != NULL ){
len = strlen( l );
if( len && l[len-1] == '\n' )
l[--len] = '\0' ;

if( nwords = parse( l, words)){
/* распечатка слов в обратном порядке */
for( --nwords; nwords >= 0; nwords-- ){
printf( "%s ", words[ nwords] );
add( words[ nwords ] );
}
}
putchar ('\n');
}
if( fp != stdin ) fclose( fp );
}

/* разобрать строку на слова */
parse( s, tabl )
register unsigned char *s;
unsigned char *tabl[];
{
char eol = 0;
int nwords = 0;

while ( !eol ){

/* пропустить пробелы и табуляции */
while(isspace(*s)) s++;

if( !*s ) /* строка кончилась */
break;

*tabl++ = s; nwords++;
/* начало очередного слова */

/* пока не пробел и не конец строки */
while( *s && !isspace(*s))s++;

/* указатель стоит на символе, следующем за словом */
if( ! *s ) eol ++;

*s = '\0';
/* закрыли Слово, начинаем Дело */
s++;
}

*tabl = NULL;
return nwords;
}

/* построение таблицы слов, встречающихся в файле */
#define MAXWORDS 1024

struct W{
int ctr; /* число вхождений слова */
char *wrd; /* слово */
}w [MAXWORDS]; /* таблица */
int busy = 0 ; /* занято в таблице */

extern char *malloc();

/* Добавить слово в таблицу */
add( word ) char *word;
{
register i;
static alert = 1;

/* нет ли уже слова в таблице ? */
/* если есть - просто увеличить счетчик */
for( i = 0; i < busy ; i++ ){
if( !strcmp( word, w[i].wrd )){
w[i].ctr++;
return;
}
}

if( busy >= MAXWORDS ){
if( alert ){
fprintf( stderr, "Переполнение таблицы слов\7\n");
alert = 0;
}
return;
}

/* нет, слова нет. Заносим: */
w[busy].wrd = malloc( strlen( word ) + 1 );
/* 1 байт под символ \0 */

if( w[busy].wrd == NULL ){
fprintf( stderr, "Мало памяти\n");

busy = MAXWORDS+1; /* якобы переполнение */
return;
}
w[busy].ctr = 1;
strcpy( w[busy].wrd, word );
busy++;
}

compare( a, b ) struct W *a, *b;
{
return strcoll( a-> wrd, b-> wrd );
/* strcoll сравнивает слова в алфавитном порядке */
}

/* выдача всех слов, встреченных в тексте, и числа их вхождений */
total(){
register i;

/* сортируем слова по алфавиту */
qsort( w, busy, sizeof(struct W), compare );
printf( "-----|-----------ИТОГ---------------\n");

for( i=0; i < busy; i++ )
printf( "%4d | %s\n",
w[i].ctr,
w[i].wrd
);
}

/* Пример 6 */

/* Сортировка букв в строке методом "пузырька" (bubble sort) */
#define YES 1
#define NO 0

bsort(s) char *s;
{
register i; /* индекс сравниваемой буквы */
register need = YES; /* надо ли продолжать сортировку ? */

while( need ){
need = NO; /* не надо */

for(i=0; s[i+1]; i++ )
/* условие цикла: мы сравниваем i-ую и i+1-ую буквы,
* поэтому и проверяем наличие i+1ой буквы
*/
if( s[i] > s[i+1] ){ /* в неверном порядке */
swap( &s[i], &s[i+1] ); /* переставить */
need = YES; /* что-то изменилось: надо будет
* повторить просмотр массива букв */
}
}
}

/* А вот вариант сортировки, написанный с указателями */
bpsort(s) char *s;
{
register char *p; register need = YES;

while( need ){
need = NO;
for( p = s; p[1] != '\0' ; p++ )
if( *p > *(p+1) ){
swap( p, p+1 ); need = YES;
}
}
}

/* обмен двух букв, находящихся по адресам s1 и s2 */
swap( s1, s2 ) register char *s1, *s2;
{
char tmp; /* temporary */
tmp = *s1; *s1 = *s2; *s2 = tmp;
}

char sample1[] = "Homo homini lupus est - ergo bibamus!";
char sample2[ sizeof sample1 ]; /* массив такого же размера */
main(){
strcpy( sample2, sample1 ); /* скопировать */
bsort ( sample1 ); printf( "%s\n", sample1 );
bpsort( sample2 ); printf( "%s\n", sample2 );
}

/* Пример 7 */
/* Работа с хэш-таблицей. Часть функций написана так, чтобы
* быть независимой от типов ключа и значения и легко
* подвергаться модификации.
*/
#include <stdio.h>
#include <string.h> /* prototype for strchr() */
extern void *malloc(unsigned size);
/* типы ключа и значения: в нашем случае это строки */
typedef unsigned char uchar;
typedef uchar *VAL; typedef uchar *KEY;

/* Для использования следует реализовать операции
int HASHFUNC(KEY); int EQKEY(KEY, KEY);
void FREEVAL(VAL); void SETVAL(VAL, VAL);
void FREEKEY(KEY); void SETKEY(KEY, KEY);
*/
#define HASHSIZE 21 /* размер таблицы: очень хорошо 2**n */

uchar *strudup(const uchar *s){ /* создание копии строки в "куче" */
uchar *p = (uchar *) malloc(strlen(s)+1); strcpy(p, s); return p;
}
/* одна из возможных хэш-функций */
unsigned int hash; /* последнее вычисленное значение хэш-функции */
int HASHFUNC(KEY key){
unsigned int i = 0; uchar *keysrc = key;
while(*key){
i = (i << 1)|(i >> 15); /* ROL */
i ^= *key++;
}
hash = i % HASHSIZE;
printf( "hash(%s)=%d\n", keysrc, hash); /* отладка */
return hash;
}
#define EQKEY(s1, s2) (strcmp(s1, s2) == 0)
#define FREEKEY(s) free(s)
#define FREEVAL(s) free(s)
#define SETVAL(at,s) at = strudup(s)
#define SETKEY(at,s) at = strudup(s)
#define KEYFMT "%s"
#define VALFMT "%s"

/* ================== типо-независимая часть ================= */
struct cell {
struct cell *next; /* ссылка на очередной элемент */
KEY key; /* ключ */
VAL val; /* значение */
} *hashtable[ HASHSIZE ]; /* хэш-таблица */

/* получение значения по ключу */
struct cell *get(KEY key){
struct cell *p;
for(p = hashtable[HASHFUNC(key)]; p; p = p->next)
if(EQKEY(p->key, key))
return p;
return NULL; /* отсутствует */
}

/* занести пару ключ:значение в таблицу */
void set(KEY key, VAL val){
struct cell *p;

/* проверить - не было ли звена с таким ключом */
if((p = get(key)) == NULL){ /* не было */
if(!(p = (struct cell *) malloc(sizeof(*p)))) return;
SETKEY(p->key, key);
p->next = hashtable[hash]; /* hash вычислено в get() */
hashtable[hash] = p;
} else /* уже было: изменить значение */
FREEVAL(p->val);
SETVAL(p->val, val);
}

/* удаление по ключу */
int del(KEY key){
int indx = HASHFUNC(key);
struct cell *p, *prev = NULL;

if((p = hashtable[indx]) == NULL) return 0;
for( ;p ;prev = p, p=p->next)
if(EQKEY(p->key, key)){
FREEVAL(p->val); FREEKEY(p->key);
if( p == hashtable[indx] ) /* голова списка */
hashtable[indx] = p->next;
else prev->next = p->next;
free((void *) p ); return 1; /* удален */
}
return 0; /* не было такого */
}

/* распечатать пару ключ:значение */
void printcell(struct cell *ptr){
putchar('(');
printf( KEYFMT, ptr->key ); putchar(',');
printf( VALFMT, ptr->val ); putchar(')');
}

/* распечатка таблицы (для отладки) */
void printtable(){
register i; struct cell *p;
printf("----TABLE CONTENTS----\n");
for(i=0; i < HASHSIZE; i++)
if((p = hashtable[i]) != NULL){
printf( "%d: ", i);
for(; p; p=p->next)
printcell(p), putchar(' ');
putchar('\n');
}
}

/* итератор */
struct celliter {
int index; struct cell *ptr;
};
/* выдать очередное значение */
struct cell *nextpair(struct celliter *ci){
struct cell *result;
while((result = ci->ptr) == NULL){
if( ++(ci->index) >= HASHSIZE )
return NULL; /* больше нет */
ci->ptr = hashtable[ci->index];
}
ci->ptr = result->next; return result;
}
/* инициализация итератора */
struct cell *resetiter(struct celliter *ci){
ci->index = (-1); ci->ptr = NULL;
return nextpair(ci); /* первое значение */
}
/* =========================================================== */

void main(){ /* таблица из имен и размеров файлов текущего каталога */
struct celliter ci; struct cell *cl;
char key[40], value[40]; struct cell *val;
extern FILE *popen(); FILE *fp; char *s ;

/* popen() читает вывод команды, заданной в 1-ом аргументе */
fp = popen( "ls -s", "r" );
while( fscanf( fp, "%s%s", value, key) == 2 )
set(key, value);
pclose(fp); /* popen() надо закрывать pclose(); */

for(;;){
printf( "-> " ); /* приглашение */
if( !gets( key )) break; /* EOF */
if( *key == '-' ){ /* -КЛЮЧ :удалить */
printf( del( key+1 ) ? "OK\n" : "нет такого\n");
continue;
}
if( !*key || !strcmp(key, "=")){ /* = :распечатать таблицу*/
printtable(); continue;
}
if(s = strchr(key, '=')){ /* КЛЮЧ=ЗНАЧЕНИЕ :добавить */
*s++ = '\0';
set(key, s); continue;
}
if((val = get( key )) == NULL) /* КЛЮЧ :найти значение */
printf( "нет такого ключа\n");
else{ printf( "значение "); printf(VALFMT, val->val);
putchar('\n');
}
}
/* распечатка таблицы при помощи итератора */
for( cl = resetiter(&ci) ; cl ; cl = nextpair(&ci))
printcell(cl), putchar('\n');
}

/* Пример 8 */

/* Пример маленькой базы данных.
* Данные хранятся БЕЗ дубликатов.
* Надо заметить, что используется плохой (неэффективный)
* алгоритм доступа - линейный поиск.
*/
#include <stdio.h>

/* Все записи в базе имеют фиксированный размер */
#define VLEN 20
#define KEY_FREE (-13) /* ключ свободного места. Он выбран
произвольно, но не должен встречаться в качестве входных данных */

struct data{
short b_key; /* ключ */
char b_val[VLEN]; /* строка-значение */
};

char BASEF[] = ".base" ; /* имя файла базы */
FILE *fbase; /* pointer на базу */
struct data tmp; /* вспомогательная переменная */

void
initBase (void){
/* fopen: r read (чтение)
* w write (запись), файл пересоздается.
* (создается, если не было, если был - опустошается).
* r+ чтение и запись (файл уже существует).
* w+ чтение и запись (создается пустой файл).
* a append (запись в конец файла), создать если нет:
* имеется в виду, что КАЖДАЯ операция записи сначала
* ставит указатель записи на конец файла.
* В MS DOS нетекстовый файл НЕОБХОДИМО открывать как
* rb wb rb+ wb+ ab+ иначе ничего не будет работать.
*/
if(( fbase = fopen( BASEF, "r+" )) == NULL ){
if(( fbase = fopen( BASEF, "w+" )) == NULL ){
fprintf( stderr, "Не могу открыть базу данных %s\n",
BASEF );
exit(1);
}
fprintf( stderr, "База создана\n" );
}
}

void
closeBase (void){
fclose( fbase );
}
/* Учтите, что если вы записываете в файл структуры, то в файле
не будет разделения на строки - файл НЕТЕКСТОВЫЙ! Поэтому и
читать такой файл можно только структурами: read(), fread()
(но не scanf-ом и не fgets-ом)
*/

/* Поиск по ключу .
Выдать (-1), если записи с данным ключом нет,
иначе - номер слота, где содержится запись с данным ключом.
*/
int
bget (int key)
{
int n;

/* последовательно просмотреть весь файл */
rewind( fbase );
/* в начало файла. Равно fseek(fbase, 0L, 0); */

n = 0 ;
/* int сколько_элементов_массива_действительно_считано =
* fread( адрес_массива_куда_считывать,
* размер_одного_элемента_массива,
* сколько_элементов_считывать_в_массив, канал );
* Заметьте, что количество данных задается НЕ в байтах,
* а в 'штуках'
*/
while( fread( &tmp, sizeof( tmp ), 1, fbase ) == 1 ){
if( tmp.b_key == key )
return n;
n++;
}
return (-1); /* не найдено */
}

/* модифицировать запись с индексом ind */
void
bmod (
int ind,
int key, /* новый ключ */
char *val /* новое значение */
)
{
struct data new;

fseek( fbase, (long) sizeof( struct data ) * ind, 0 );
new.b_key = key;
strncpy( new.b_val, val, VLEN );
/* int сколько_элементов_массива_действительно_записано =
* fwrite( адрес_массива_который_записывать,
* размер_одного_элемента_массива,
* сколько_элементов_массива_записывать, канал );
*/
if( fwrite( &new, sizeof new , 1, fbase ) != 1 )
fprintf( stderr, "Ошибка записи.\n" );
}

/* удаление записи по ключу */
int
bdel (int key){
int ind = bget( key );
if( ind == -1 )
return (-1); /* записи с таким ключом нет */
bmod( ind, KEY_FREE, "" ); /* записать признак свободного места */
return 0;
}

/* Служебная процедура дописи к концу файла */
void
bappend (int key, char *val)
{
struct data new;

/* встать на конец файла */
fseek( fbase, 0L, 2 );

/* и записать новую структуру в конец */
new.b_key = key;
strncpy( new.b_val, val, VLEN );
fwrite( &new, sizeof( struct data ) , 1, fbase );
}

/* добавление новой записи. Если запись с таким ключом уже есть -
выдать ошибку
*/
int
bput (int key, char *val)
{
int i = bget( key );
if( i != -1 )
return (-1); /* запись уже есть */

/* найти свободное место */
i = bget( KEY_FREE );
if( i == -1 ) { /* нет свободных мест */
bappend( key, val );
return 0;
}
/* иначе свободное место найдено.
* Заменяем дырку на полезную информацию */
bmod( i, key, val );
}

/* распечатать всю базу данных подряд */
void
bprint (void){
int n;
int here = 0;

rewind( fbase );
n = 0;
printf( "-номер--ключ-------значение-----------------\n" );
while( fread( &tmp, sizeof tmp, 1, fbase ) == 1 ){
if( tmp.b_key == KEY_FREE ){
n++;
continue;
}
printf( "#%-2d| %6d\t| %s\n", n, tmp.b_key, tmp.b_val );
here ++; n++;
}
printf( "--------------------------------------------\n" );
printf( "Длина базы:%d Занято:%d\n\n", n, here );
}

/* замена поля val у записи с ключом key */
int
bchange (int key, char *val)
{
int ind;

ind = bget( key );
if( ind == -1 ){
/* запись с таким ключом не существует */
/* Добавить как новую запись */
bput( key, val );
return 0;
}
bmod( ind, key, val );
return 1;
}

/* Аналогичная функция, но использующая другой способ.
* Кроме того, если такой ключ отсутствует - ничего не делается
*/
int
bchg (int key, char *val)
{
struct data d;

rewind( fbase ); /* в начало файла */
while( fread( &d, sizeof d, 1, fbase ) == 1 ){
/* поиск ключа */
if( d.b_key == key ){
/* вернуться назад от текущей позиции */
fseek( fbase, - (long) sizeof d, 1 );
/* не годится (long)-sizeof d !!! */

d.b_key = key;
strncpy( d.b_val, val, VLEN );
fwrite( &d, sizeof d, 1, fbase );

/* между fread и fwrite должен быть
* хоть один fseek. (магическое заклинание!)
*/
fseek( fbase, 0L, 1); /* никуда не сдвигаться */
return 0; /* сделано */
}
}
return (-1); /* такого ключа не было */
}

/* Пример */
void
main (void){
int i;

initBase();
bprint();
bdel( 8 );

printf( "Создаем базу данных\n" );
bput( 1, "строка 1" );
bput( 2, "строка 2" );
bput( 3, "строка 3" );
bput( 4, "строка 4" );
bprint();

printf( "Удаляем записи с ключами 1 и 3\n" );
bdel( 1 );
bdel( 3 );
bprint();

printf( "Добавляем записи 5, 6 и 7\n" );
bput( 5, "строка 5" );
bput( 6, "строка 6" );
bput( 7, "строка 7" );
bprint();

printf( "Заменяем строку в записи с ключом 2\n" );
bchange( 2, "новая строка 2" );
bprint();

printf( "Заменяем строку в записи с ключом 4\n" );
bchg( 4, "новая строка 4" );
bprint();

printf( "Заменяем строку в записи с ключом 6 и ключ 6 на 8\n" );
i = bget( 6 );
printf( "Сейчас запись с ключом 6 содержит \"%s\"\n",
tmp.b_val );
bmod( i, 8, "Новая строка 6/8" );
bprint();

closeBase();
}

/* Пример 9 */
/* Вставка/удаление строк в файл */
#include <stdio.h>

#define INSERT_BEFORE 1 /* Вставить строку перед указанной */
#define INSERT_AFTER 2 /* Вставить строку после указанной */
#define DELETE 3 /* Удалить строку */
#define REPLACE 4 /* Заменить строку */

/* К каждой строке linenum должно относиться не более 1 операции !!! */
struct lineop {
char op; /* Операция */
long linenum; /* Номер строки в файле (с 0) */
char *str; /* Строка (или NULL для DELETE) */
};

long lineno; /* номер текущей строки */
int fileChange (char *name, /* имя файла */
struct lineop ops[], /* задание */
int nops /* число элементов в массиве ops[] */
){
FILE *fin, *fout;
static char TMPNAME[] = " ? ";
char buffer[BUFSIZ];
register i;
struct lineop tmpop;

if ((fin = fopen (name, "r")) == NULL)
return (-1);
if ((fout = fopen (TMPNAME, "w")) == NULL) {
fclose (fin); return (-1);
}
lineno = 0L;
while (fgets (buffer, BUFSIZ, fin) != NULL) {
if( nops ) for (i = 0; i < nops; i++)
if (lineno == ops[i].linenum) {
switch (ops[i].op) {
case DELETE: /* удалить */
break;
case INSERT_BEFORE: /* вставить перед */
fprintf (fout, "%s\n", ops[i].str);
fputs (buffer, fout);
break;
case INSERT_AFTER: /* вставить после */
fputs (buffer, fout);
fprintf (fout, "%s\n", ops[i].str);
break;
case REPLACE: /* заменить */
fprintf (fout, "%s\n", ops[i].str);
break;
}
/* переставить выполненную операцию в конец массива и забыть */
tmpop = ops[nops-1]; ops[nops-1] = ops[i]; ops[i] = tmpop;
nops--; goto next;
}
/* иначе строка не числится в массиве ops[] : скопировать */
fputs (buffer, fout);
next:
lineno++;
}
fclose (fin); fclose (fout); rename (TMPNAME, name);
return nops; /* число несделанных операций (0 - все сделано) */
}

struct lineop myops[] = {
{ DELETE, 2L, NULL },
{ INSERT_BEFORE, 0L, "inserted before 0" },
{ INSERT_BEFORE, 10L, "inserted before 10" },
{ INSERT_AFTER, 5L, "inserted after 5" },
{ DELETE, 6L, NULL },
{ INSERT_AFTER, 8L, "inserted after 8" },
{ INSERT_AFTER, 12L, "inserted after 12" },
{ REPLACE, 3L, "3 replaced" }
};

void main( void ){
int n;
n = fileChange( "aFile", myops, sizeof(myops)/sizeof(struct lineop));
printf( "Строк в файле: %ld; осталось операций: %d\n", lineno, n);
}
/*
исходный файл получившийся файл
line 0 inserted before 0
line 1 line 0
line 2 line 1
line 3 3 replaced
line 4 line 4
line 5 line 5
line 6 inserted after 5
line 7 line 7
line 8 line 8
line 9 inserted after 8
line 10 line 9
inserted before 10
line 10
Строк в файле: 11; осталось операций: 1
*/

/* Пример 10 */

/* Проблема: позволить делать вызов free(ptr)
* на данные, не отводившиеся malloc()-ом.
* Решение: вести список всех данных,
* отведенных malloc()ом.
* Возможно также отслеживание диапазона адресов,
* но последнее является машинно-зависимым решением.
*
* При большом количестве файлов эта программа - неплохой тест
* производительности машины!
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _cell {
void *addr;
struct _cell *next;
} Cell;

typedef struct _entry {
int length;
int used;
Cell *list;
} Entry;

/* Хэшированная таблица */
#define NENTRIES 64
Entry aTab[NENTRIES];

/* Хэш-функция от адреса */
int aHash(void *addr){
unsigned long x = (unsigned long) addr;
x >>= 3; /* деление на 8, так как адреса из malloc()
обычно четные,
поскольку выровнены на границу double */
return(x % NENTRIES);
/* Тут к месту напомнить, что вычисление остатка от деления на степень двойки
* можно соптимизировать:
* x % (2**N) = x & 0b0001.....1 (N двоичных единиц)
* К примеру, x % 64 = x & 0x3F; (6-ая степень двойки)
*/
}

/* Выделить память, записать адрес в таблицу */
void *aCalloc(int n, int m){
void *ptr = calloc(n, m);
Entry *ep = &aTab[ aHash(ptr) ];
Cell *p;

for(p=ep->list; p; p=p->next)
if(p->addr == NULL){
/* Свободная ячейка: переиспользовать */
p->addr = ptr;
ep->used++;
return ptr;
}
/* Нет свободных, завести новую */
p = (Cell *) calloc(1, sizeof(Cell));
p->addr = ptr;
p->next = ep->list;
ep->list = p;
ep->length++;
ep->used++;
return ptr;
}

/* Освободить память */
int aFree(void *ptr){
Entry *ep = &aTab[ aHash(ptr) ];
Cell *p;

for(p=ep->list; p; p=p->next)
if(p->addr == ptr){
free(ptr);
p->addr = NULL;
/* Ячейка не удаляется, но метится как свободная */
ep->used--;
return 1;
}
/* Нет, такой указатель не отводился.
* Не делать free()
*/
return 0;
}

/* Выдать статистику об использовании хэша */
void aStat(){
int i;
int len_all;
int used_all;

for(i=len_all=used_all=0; i < NENTRIES; i++){
len_all += aTab[i].length;
used_all += aTab[i].used;

printf("%d/%d%s", aTab[i].used, aTab[i].length,
i==NENTRIES-1 ? "\n":" ");
}
printf("%d/%d=%g%%\n",
used_all, len_all,
(double)used_all * 100 / len_all);
}

/* ТЕСТ =================================================================*/

Cell *text;

/* Прочитать файл в память */
void fileIn(char *name){
char buf[10000];
FILE *fp;

if((fp = fopen(name, "r")) == NULL){
printf("Cannot read %s\n", name);
return;
}
while(fgets(buf, sizeof buf, fp) != NULL){
char *s;
Cell *p;

s = (char *) aCalloc(1, strlen(buf)+1);
strcpy(s, buf);

p = (Cell *) aCalloc(sizeof(Cell), 1);
p->addr = s;
p->next = text;
text = p;
}
fclose(fp);
}

/* Уничтожить текст в памяти */
void killAll(){
Cell *ptr, *nxtp;

ptr = text;
while(ptr){
nxtp = ptr->next;
if(!aFree(ptr->addr)) printf("No free(1)\n");
if(!aFree(ptr)) printf("No free(2)\n");
ptr = nxtp;
}
}

/* Удалить из текста строки, начинающиеся с определенной буквы */
void randomKill(int *deleted){
unsigned char c = rand() % 256;
Cell *ptr, *prevp;
unsigned char *s;

retry:
prevp = NULL; ptr = text;
while(ptr){
s = (unsigned char *) ptr->addr;
if(*s == c){ /* нашел */
if(!aFree(s)) printf("No free(3)\n");

/* исключить из списка */
if(prevp) prevp->next = ptr->next;
else text = ptr->next;

if(!aFree(ptr)) printf("No free(4)\n");

/* Заведомо неправильный free
if(!aFree(ptr+1)) printf("No free(5)\n");
*/

(*deleted)++;

goto retry;
}
prevp = ptr;
ptr = ptr->next;
}
}

int main(int ac, char *av[]){
int i, r, d;
char buffer[4098];

srand(time(NULL));
for(i=1; i < ac; i++){
printf("File: %s\n", av[i]);
fileIn(av[i]);
aStat();

d = 0;
for(r=0; r < 128; r++) randomKill(&d);
printf("%d lines deleted\n", d);
aStat();
}
killAll();
aStat();

if(!aFree(buffer))
printf("buffer[] - не динамическая переменная.\n");

return 0;
}

/* Пример 11 */

/* Пакет для ловли наездов областей выделенной памяти
* друг на друга,
* а также просто повреждений динамически отведенной памяти.
*/
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h> /* O_RDWR */
#include <sys/types.h>
#include <ctype.h>
#include <locale.h>

#define CHECKALL
/*
----------------- <--------- ptr
| red_zone | головная "пограничная зона"
-----------------
| byte[0] |
| ... |
| byte[size-1] |
| placeholder |
----------------- выровнено на границу RedZoneType
| red_zone | хвостовая "пограничная зона"
-----------------

Основные идеи состоят в следующем:
1) Перед и после области данных строится зона,
заполненная заранее известным "узором".
Если ее содержимое изменилось, испорчено -
значит мы где-то разрушили нашу память.
2) Ведется таблица всех отведенных malloc()-ом сегментов памяти;
для экономии места эта таблица вынесена в файл (но зато это
очень медленно).
3) Мы не можем пользоваться библиотекой STDIO для обменов с файлом,
потому что эта библиотека сама использует malloc() и буфера
могут быть разрушены.
*/

typedef char *RedZoneType; /* выравнивание на границу указателя */
/* Можно выравнивать на границу double:
typedef double RedZoneType;
*/

/* Сегмент, выделяемый в оперативной памяти */
typedef struct _allocFrame {
RedZoneType red_zone; /* головная "пограничная зона" */
RedZoneType stuff[1]; /* место для данных */
/* хвостовая "пограничная зона" безымянна */
} AllocFrame;

const int RedZoneTypeSize = sizeof(RedZoneType);

/* Запись, помещаемая в таблицу всех выделенных malloc()ом
* областей памяти.
*/
typedef struct _memFileRecord {
AllocFrame *ptr; /* адрес */
size_t size, adjsize; /* размер выделенной области */
/* (0,0) - означает "сегмент освобожден" */
int serial;
} MemFileRecord;

char red_table[] = {
0x01, 0x03, 0x02, 0x04,
0x11, 0x13, 0x12, 0x14,
0x21, 0x23, 0x22, 0x24,
0x31, 0x33, 0x32, 0x34
};
char free_table[] = {
'F', 'r', 'e', 'e', 'p', 't', 'r', '\0',
'F', 'r', 'e', 'e', 'p', 't', 'r', '\0'
};

/* Файл для хранения таблицы указателей */
static int mem_fd = (-1);
#define PTABLE "PointerTable.bin"

#define NRECORDS 256
MemFileRecord memrecords[NRECORDS];
/* ============================================================= */
void MEMputTableRecord(AllocFrame *newptr, AllocFrame *oldptr,
size_t size, size_t adjsize);
void MEMputTableRecordKilled(AllocFrame *ptr);
void MEMerasePreviousRecords(AllocFrame *ptr);
int MEMcheckRecord(MemFileRecord *rec);
int MEMcheck_consistency(AllocFrame *ptr);
void MEMmakeRedZones(char *cptr, size_t size, size_t adjsize);
void MEMopenFd();
/* ============================================================= */
/* Этим следует пользоваться вместо стандартных функций */
void *MEMmalloc (size_t size);
void *MEMrealloc(void *ptr, size_t size);
void *MEMcalloc (size_t n, size_t size);
void MEMfree (void *ptr);

void MEMcheckAll(); /* это можно вызывать в середине программы */
/* ============================================================= */
void MEMopenFd(){
if(mem_fd < 0){
close(creat(PTABLE, 0644)); /* создать файл */
mem_fd = open(PTABLE, O_RDWR); /* чтение+запись */
unlink(PTABLE); /* только для M_UNIX */

atexit(MEMcheckAll);
setlocale(LC_ALL, "");
}
}

/* Поместить запись в таблицу всех указателей на
* выделенные области памяти.
*/
void MEMputTableRecord(AllocFrame *newptr, /* для записи */
AllocFrame *oldptr, /* для стирания */
size_t size, /* размер данных */
size_t adjsize /* размер всей записи с зонами */
){
MemFileRecord memrecord;
static int serial = 0;

memrecord.ptr = newptr;
memrecord.size = size;
memrecord.adjsize = adjsize;
memrecord.serial = serial++;

MEMopenFd();
#ifdef CHECKALL
/* стереть прежние записи про этот адрес */
MEMerasePreviousRecords(oldptr);
#endif
lseek(mem_fd, 0L, SEEK_END); /* в конец */
write(mem_fd, &memrecord, sizeof memrecord); /* добавить */
}

/* Сделать запись об уничтожении области памяти */
void MEMputTableRecordKilled(AllocFrame *ptr){
/* Пометить как size=0, adjsize=0 */
MEMputTableRecord(ptr, ptr, 0, 0);
}

/* Коды ответа функции проверки */
#define OK 0 /* все хорошо */
#define DAMAGED 1 /* повреждена "погранзона" */
#define FREED 2 /* эта память уже освобождена */
#define NOTHERE (-1) /* нет в таблице */

/* Проверить сохранность "пограничных зон" */
int MEMcheckRecord(MemFileRecord *rec){
int code = OK;
char *cptr;
register i;
AllocFrame *ptr = rec->ptr;
size_t size = rec->size;
size_t adjsize = rec->adjsize;

if(size == 0 && adjsize == 0){
printf("%p [%p] -- сегмент уже освобожден, "
"record=#%d.\n",
&ptr->stuff[0], ptr,
rec->serial
);
return FREED;
}
cptr = (char *) ptr;
for(i=0; i < adjsize; i++){
if(i < RedZoneTypeSize || i >= RedZoneTypeSize + size ){
/* головная погранзона ИЛИ хвостовая погранзона */
if( cptr[i] != red_table[ i % RedZoneTypeSize ] ){
printf("%p [%p] -- испорчен байт %4d [%4d]"
"= 0x%02X '%c' record=#%d size=%lu.\n",
&ptr->stuff[0], ptr,
i - RedZoneTypeSize, i,
cptr[i] & 0xFF,
isprint(cptr[i] & 0xFF) ? cptr[i] & 0xFF : '?',
rec->serial, size
);
code = DAMAGED;
}
}
}
for(i=0; i < RedZoneTypeSize; i++)
if(cptr[i] == free_table[i]){
printf("%p -- уже освобождено?\n", ptr);
code = FREED;
}
if(code != OK) putchar('\n');
return code;
}

/* Проверить сохранность памяти по указателю ptr. */
int MEMcheck_consistency(AllocFrame *ptr){
MemFileRecord mr_found;
int nrecords, i, found = 0;
size_t size;

MEMopenFd();

/* Ищем запись в таблице указателей */
lseek(mem_fd, 0L, SEEK_SET); /* перемотать в начало */
for(;;){
size = read(mem_fd, memrecords, sizeof memrecords);
nrecords = size / sizeof(memrecords[0]);

if(nrecords <= 0) break;

for(i=0; i < nrecords; i++)
if(memrecords[i].ptr == ptr){
/* Мы ищем последнюю запись про память
* с таким адресом, поэтому
* вынуждены прочитать ВЕСЬ файл.
*/
mr_found = memrecords[i];
found++;
}
}
if(found) {
return MEMcheckRecord(&mr_found);
} else {
printf("%p -- запись в таблице отсутствует.\n", ptr);
return NOTHERE;
}
}

/* Уничтожить все прежние записи про ptr, прописывая их adjsize=0 */
void MEMerasePreviousRecords(AllocFrame *ptr){
int nrecords, i, found;
size_t size;

MEMopenFd();
lseek(mem_fd, 0L, SEEK_SET); /* перемотать в начало */
for(;;){
found = 0;
size = read(mem_fd, memrecords, sizeof memrecords);
nrecords = size / sizeof(memrecords[0]);

if(nrecords <= 0) break;

for(i=0; i < nrecords; i++)
if(memrecords[i].ptr == ptr){
memrecords[i].adjsize = 0;
/* memrecords[i].size = 0; */
found++;
}
if(found){
lseek(mem_fd, -size, SEEK_CUR); /* шаг назад */
write(mem_fd, memrecords, size); /* перезаписать */
}
}
}

void MEMcheckAll(){
#ifdef CHECKALL
int nrecords, i;
size_t size;

printf("Проверка всех указателей -------------\n");