Использование stdio для чтения и сортировки данных по каналам в Linux

Question

Как видно из заголовка, мне нужно написать небольшую программу для чтения данных из стандартного ввода, сортировки и отправки в стандартный вывод. Программа должна принимать 1 аргумент, который говорит, какова длина одной записи (в байтах). Вот как я это проверяю:

printf 'D\x00C\x00\x00B\x00A' | ./binsort 2 | od -c

Вышеприведенное должно вывести что-то вроде:

0000000  \0   A  \0   B   C  \0   D  \0
0000010

Вот что у меня есть (binsort.c):

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

using namespace std;


void print_usage()
{
        printf("%s\n", "Usage: ");
}


int compare (const void * a, const void * b) // the compare function for qsort... might need some work
{
  return ( *(int*)a - *(int*)b );
}


int main(int argc, char *argv[])
{
        if (argc != 2 || stdin == NULL) // check for argument and piped input
        {
                print_usage();
                exit(EXIT_FAILURE);
        }

        int entry_size = atoi(argv[1]);

        if (entry_size <= 0 || entry_size >= INT_MAX) // check for valid range of entry size
        {
                print_usage();
                exit(EXIT_FAILURE);
        }

        char *input = new char[entry_size]; // to hold single record

        while (fgets(input, entry_size, stdin) != NULL)
        {
                printf("%s", input); // output single record we just read
        }

        exit(EXIT_SUCCESS);
}

Затем скомпилируйте с g++ binsort.c -o binsort.

Выше компилируется, но не выводит данные, которые printf отправил ему. Он должен выводить его в виде 2-байтовых фрагментов ... как D\0 C\0 \0B \0A ... но это не так.

Я думаю об использовании qsort для сортировки массива, выделенного malloc/realloc. Тем не менее, у меня никогда не было опыта с этим, в действительности, я несколько дней ломал голову над этой маленькой утилитой. Кто-нибудь может помочь?

P.S. Люди спрашивали, если это домашнее задание ... Это не так - разработчики в моей компании хотят использовать это для отладки выходных данных своего проекта.

Answer 1

Не используйте scanf() и printf(). Они должны использоваться с текстовыми данными. Поскольку вы имеете дело с двоичными данными, вместо этого вы хотите использовать низкоуровневые функции fread() и fwrite(). Поскольку вы не знаете, сколько всего данных, вам придется использовать динамическую структуру данных (например, массив с изменяемым размером) для хранения входных данных. Вы не можете обрабатывать данные в режиме онлайн - вы должны прочитать их все, отсортировать, а затем записать обратно. Ваша функция сортировки также неверна - вы сравниваете только первые 4 байта каждой записи, что неправильно, если размер записи отличается от 4 байтов. Вместо этого используйте memcmp().

Это должно работать:

char *input = NULL;
size_t input_size = 0;
int num_items = 0;
int entry_size;

int compare_func(const void *e1, const void *e2)
{
  return memcmp(e1, e2, entry_size);
}

int main(int argc, char **argv)
{
   // ...
  char *datum = malloc(entry_size);  // check for NULL
  input_size = 4096;
  input = malloc(input_size);  // check for NULL

  while(1)
  {
    if(fread(datum, 1, entry_size, stdin) < entry_size)
      break;
    size_t new_size = (num_items + 1) * entry_size;
    if(new_size > input_size)
    {
      input = realloc(input, input_size * 2);  // check for NULL
      input_size *= 2;
    }
    memcpy(input + num_items * entry_size, datum, entry_size);
    num_items++;
  }

  qsort(input, num_items, entry_size, compare_func);

  fwrite(input, entry_size, num_items, stdout);

  return 0;
}

Answer 2

P.S. Люди спрашивали, если это домашнее задание ... Это не так - разработчики в моей компании хотят использовать это для отладки выходных данных своего проекта.

Если это не домашняя работа, и это под Linux, почему бы не использовать включенную "sort" программу?

например:.

% printf 'D\x00C\x00\x00B\x00A' | sort -z | od -c
0000000  \0   A  \0   B  \0   C  \0   D  \0
0000011

FSF / GNU sort предлагает опцию -z:

-z, --zero-terminated
        end lines with 0 byte, not newline

---

---

Изменено, чтобы добавить:

Хорошо, учитывая, как вы все еще хотите свой собственный код ...

И, учитывая, как никто еще не опубликовал подход, основанный на STL.

Обратите внимание на использование struct FUNCTOR для сравнения (через stl :: sort ()). И, если хотите, вы всегда можете использовать ostream_iterator (cout, "\ n") вместо этого, чтобы сделать вещи немного более понятными для человека ..

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

   /* ifstream won't set EOF-state until we try to read past the end-of-file.*/
   /* (Makes for lots of grief trying to read in files...)                   */
inline bool
IsStreamStillGood( istream & theStream )
{
  return theStream && (theStream . peek() != EOF);
}

template<class TYPE> inline void DELETE( TYPE * x)
{
  delete x;
  x = (TYPE *) NULL;
}

struct FUNCTOR
{
  bool operator()(const string & x, const string & y) { return x < y; }
};


int
main(int argc, char **argv)
{
  istream *       stream;
  vector<string>  v;

  UASSERT( argc, >, 1 );

  const int recordSize = atoi( argv[1] );
  char      buffer [ recordSize + 1 ];

  UASSERT( recordSize, >, 0 );


  if ( argc > 2 )
    stream = new ifstream( argv[2] );
  else
    stream = & cin;


  while ( IsStreamStillGood( * stream ) )
  {
    stream-> read( buffer, recordSize );
    v.push_back( string( buffer, stream->gcount() ) );
  }

  UASSERT( v.back().size(), ==, size_t(recordSize) );


  FUNCTOR functor;
  sort( v.begin(), v.end(), functor );

  copy( v.begin(), v.end(), ostream_iterator<string>(cout) );


  if ( argc > 2 )
    DELETE(stream);
}

---

---

Изменено (еще раз), чтобы добавить:

Вопрос относительно использования строк в вашем подходе STL: так как на входе есть потенциально нулевые символы ('\ 0'), не перепутаются ли строки из-за этого? Кто-то предложил использовать char [], но я подозреваю, что возникнет та же проблема

Если у меня есть char c [10]; , я могу сказать: c [0] = '\ 0'; . То же самое для c [1] или c [9] . Я могу иметь столько нулевых символов в этом массиве, сколько захочу. (Конечно, в зависимости от размера массива.)

Теперь, когда используется c в качестве c-строки, возникает вопрос о том, как долго это будет. Это 1 символ в длину или 9? Обычно в Си это определяется тем, где появляется первый символ NULL.

Такие вещи, как printf (% s) , scanf (% s) , strncat () , strncpy () , strncmp () и т. Д. Не очень довольны символами NULL ('\ 0'), встроенными в наш массив двоичных данных.

Но C ++ std :: string самостоятельно отслеживает длину. По крайней мере, кажется, и это разрешает такие вещи, как: myString.append (10, '\ 0');

Итак, используя stream-> read (buffer, recordSize) , мы читаем в заданном количестве символов (байтов). Нам действительно все равно, являются ли они пустыми ('\ 0') или нет. Все хорошо. Просто дайте мне recordSize количество байтов.

Создавая с помощью v.push_back (string (buffer, stream-> gcount ())) , мы отталкиваем новую строку, содержащую stream-> gcount () chars ( байт). И снова нам все равно, являются ли они пустыми ('\ 0') или нет. Нам просто нужны все stream-> gcount () байтов.

Сортировка использует functor, который использует operator <(const string &, const string &), который использует string :: compare (), который снова будет использовать длину строки и не заботится о том, какие данные на самом деле содержатся в строка. Нули ('\ 0') просто отлично. </p>

Теперь, если мы попытаемся использовать v.back (). C_str (), тогда у нас нет длины, поэтому нулевые значения приведут нас в замешательство. Но пока мы используем строковый объект (например, v.back ()), содержащий как данные, так и длину, у нас все хорошо.

Что приводит нас к выводу. И снова мы выводим строку, а не myString.c_str (), поэтому все символы в строке печатаются. Нули ('\ 0') включены.

Answer 3

printf интерпретирует \0 в вашем потоке как завершающий символ.

Используйте read() и write() вместо:

    int res;
    int count;
    while (1) {
            count = 0;
            while(count < entry_size) {
                    res = read(STDIN_FILENO, input + count, entry_size - count);
                    if (res <= 0)
                            exit(errno);
                    count += res;
            }
            count = 0;
            while(res) {
                    res = write(STDOUT_FILENO, input + count, entry_size - count);
                    if (res < 0)
                            exit(errno);
                    count += res;
            }
    }

Answer 4

Несколько моментов, которые могут помочь (я предполагаю, что это домашнее задание, поэтому оно имеет педагогическую структуру):

• Вам нужно будет где-то вставить данные во время их накопления. А поскольку вы не знаете, сколько будет впереди, динамическое распределение будет необходимо. Здесь много вариантов: динамические массивы, связанные списки, хеш-таблицы и т. Д. ad nauseum ... Выберите тот, который будет работать для вас (см. Ниже).

• Как только вы получите его, вам нужно будет его отсортировать. Или , вы можете сохранить его отсортированным в первую очередь. Вы знаете структуру данных, которая может управлять этим?

• Как только он отсортирован, вы просто выплевываете его на другом конце.

Легко, нет?

---

По поводу комментария:

• У вас есть K & R? Или какой-то другой основной текст на c или c++? Вы захотите один. И вы хотите выбрать один или другой язык и придерживаться его. Если вы привыкли к программированию ОО в другом контексте, используйте c++. Если вы тоже не знаете, используйте c++.

• Если вы используете c ++, контейнер STL позаботится о динамическом хранилище для вас. Самым простым было бы использовать std::vector<char[2]> (используя размер из аргумента командной строки) и вызывать сортировку <algorithm>.

• Другие люди указали, что вам нужно сделать бинарный ввод-вывод. Это важно, потому что ни ваш ввод, ни ваш вывод не структурированы как текстовый ввод-вывод.

Answer 5

fgets и fprintf имеют дело со строками (которые в C являются массивами символов, заканчивающимися специальным символом \ 0).

Используйте fread и fwrite для двоичных данных. qsort хорош, за исключением того, что вашей функции сравнения нужно сравнивать побайтно для байтов entry_size, а не просто приводить от void к int, что небезопасно и, вероятно, некорректно.

Answer 6

Спасибо всем за отличные предложения! Просто для справки, здесь завершено binsort.c, которое делает то, что ожидается.

#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <limits.h>

using namespace std;


int num_items = 0;
size_t input_size = 0;
int entry_size = 0;


void print_usage()
{
        printf("%s\n", "Usage: <binary data> | ./binsort [RECORD_LENGTH]");
        printf("%s\n", "For example: printf 'D\\x00C\\x00\\x00B\\x00A' | ./binsort 2 | od -c");
}


int compare (const void * a, const void * b)
{
        return memcmp(a, b, entry_size);
}


int main(int argc, char *argv[])
{
        if (argc != 2 || stdin == NULL)
        {
                print_usage();
                exit(EXIT_FAILURE);
        }

        entry_size = atoi(argv[1]);

        if (entry_size <= 0 || entry_size >= INT_MAX)
        {
                print_usage();
                exit(EXIT_FAILURE);
        }

        char *input = NULL;
        char *datum = (char*) malloc(entry_size);
        if (datum == NULL)
                exit(EXIT_FAILURE);

        while(1)
        {
                int read_size = fread(datum, 1, entry_size, stdin);

                if (read_size == 0)
                        break;

                if(read_size < entry_size)
                {
                        while(read_size < entry_size)
                        {
                                memcpy(datum, '\0', 1);
                                read_size++;
                        }
                        break;
                }

                size_t new_size = (num_items + 1) * entry_size;
                if(new_size > input_size)
                {
                        input = (char*) realloc(input, new_size);
                        if (input == NULL)
                                exit(EXIT_FAILURE);
                        input_size = new_size;
                }
                memcpy(input + num_items * entry_size, datum, entry_size);
                num_items++;
        }

        qsort(input, num_items, entry_size, compare);

        fwrite(input, entry_size, num_items, stdout);

        exit(EXIT_SUCCESS);
}