Delphi, Asm, C, WinAPI, PHP, ..., FAQ Опции

[-=CHE@TER=-]

Недавно я обновил свою функцию basename() которую использовал в программах для получения имени файла из полного пути. Обновил, добавив туда помимо проверки на символы "\" и "/", также на символ ":".
По идее, не совсем правильно искать этот символ по всей строке, ну да ладно.
Кто-нибудь спросит "а что, собственно, случилось?" на что я поведаю такую историю.

Давным-давно, когда DOS и прочие операционные системы только появились, не было каталогов (они же папки, они же директории) и все файлы были навалены в корень диска. Вернее, даже, дисковода, потому что жёстких дисков тогда тоже не было - было два дисковода A: и B:, где в первом, как правило, держали дискету с программой, а во втором дискету с файлами этой программой созданными. Поэтому, чтобы обратиться к файлу на другом дисководе, писали так (команда type выводит файл на экран):
type B:TEXTFILE.TXT
Т.е. указывали диск, затем двоеточие, и только потом имя файла.
Шло время и в DOS появились те самые каталоги-папки-директории, где разделитель был символ "\".
Так что путь теперь записывался так:
type B:\TEXTFILE.TXT
Однако, в целях обратной совместимости, запись с указанием файла в корне диска без последующего символа "\" так и осталась. Даже после того как вышел Windows и много ещё чего стряслось.
Поэтому даже сегодня можно написать:
type B:TEMP\TEXTFILE.TXT
И оно будет работать на Windows XP. А вот на Windows 7 использование такого способа уже не работает. Подозреваю, что начиная с Vista убрали обратную совместимость.
Добавлю, что в файловых системах NTFS двоеточие после имени файла используется для указания имени потока файла:
C:\Temp\TEXTFILE.TXT:stream_name

[-=CHE@TER=-]

Короче, я тут несколько вечеров убил одну ошибку отлавливая, так что решил про неё написать.
Долго не мог понять что не так, но потом уже принципиально захотелось разобраться в чём же дело.

Для начала функция быстрой сортировки quick sort (упрощена, сортирует массив arr[] состоящий из int'ов):

CODE

/* my_qsort_int(list, 0, count - 1); */
void my_qsort_int(int *arr, int low, int high) {
int i, j, k, pivot;
  i = low;
  j = high;
  pivot = arr[(low + high) / 2];
  while (i <= j) {
    while (arr[i] < pivot) { i++; }
    while (arr[j] > pivot) { j--; }
    if (i <= j) {
      k = arr[i];
      arr[i] = arr[j];
      arr[j] = k;
      i++;
      j--;
    }
  }
  if (low < j) { my_qsort_int(arr, low, j); }
  if (i < high) { my_qsort_int(arr, i, high); }
}

А теперь представьте, что у вас есть кусок памяти с фиксированными структурами, которые нужно отсортировать, выглядящий вот так:
FILE_003.DAT####FILE_001.DAT####FILE_002.DAT####...
И так далее. Где 12 символов - это имя файла (DOS 8.3), а #### - 4 байта размер файла.

CODE

#pragma pack(push, 1)
typedef struct {
  char name[12];
  long size;
} fileitem;
#pragma pack(pop)

Задача: отсортировать этот кусок памяти по имени файлов.
Для этого перепишем функцию выше и получится что-то такое:

CODE

/* my_qsort_ptr((char *) list, sizef(list[0]), 0, count - 1); */
void my_qsort_ptr(char *list, size_t ilen, unsigned int l, unsigned int r) {
unsigned int i, j, k;
char *a, *b, *p, c;
  i = l;
  j = r;
  p = &list[((l + r) / 2) * ilen];
  a = &list[i * ilen];
  b = &list[j * ilen];
  while (i <= j) {
    while (strncmp(a, p, 12) < 0) {
      i++;
      a += ilen;
    }
    while (strncmp(b, p, 12) > 0) {
      j--;
      b -= ilen;
    }
    if (i <= j) {
      for (k = 0; k < ilen; k++) {
        c = *a;
        *a = *b;
        *b = c;
        a++;
        b++;
      }
      b -= (ilen * 2);
      i++;
      j--;
    }
  }
  if (l < j) { my_qsort_ptr(list, ilen, l, j); }
  if (i < r) { my_qsort_ptr(list, ilen, i, r); }
}

Внимание, вопрос: кто знает где тут ошибка?
Подсказка: функция написана правильно, там нехватает кое-какого дополнительного важного кода.

Когда я написал эту функцию, то долго тупил не понимая, почему у меня на выходе частично отсортированный массив. Т.е. он такими кусками отсортированный, между которыми то тут, то там торчат имена файлов, которых в этом месте алфавитной сортировки быть не должно.
Давайте ещё раз посмотрим на первую функцию, в частности на выбор серединного элемента:

CODE

pivot = arr[(low + high) / 2];

pivot - переменная типа int, а, значит, в неё складывается значение элемента, относительно которого мы сравниваем все остальные.
Во второй же функции:

CODE

p = &list[((l + r) / 2) * ilen];

p - это указатель на адрес начала памяти, где лежит нужный элемент.
Поняли в чём прикол? Когда в первой функции элементы массива меняются местами, то pivot остаётся каким был. Во второй же функции указатель по прежнему указывает на старый адрес, но вот элемент там может быть уже другим! В результате чего сортировка "сходит с ума", когда элемент, относительно которого она выполнялась, внезапно, сменился.
Чтобы поправить вторую функцию нужно после условия "if (i <= j) {" сразу же написать:

CODE

if (p == a) { p = b; } else { if (p == b) { p = a; } }

Таким образом мы перемещаем указатель вслед за элементом, на который он указывал. В данном случае на противоположный, потому что "a" и "b" меняются местами.

Ещё несколько мыслей.
Почему с такой ошибкой обычно не сталкиваются при сортировке? Потому что обычно сортируется массив из указателей на элементы. Т.е. при выполнении условий меняются местами не сами данные, а только указатели на них. Как-то так (копипаст строчек с инициализацией чтобы была понятна суть):

CODE

char *buffer;
char **list;
  ...
  list[0] = &buffer[0];
  list[1] = &buffer[16];
  list[2] = &buffer[32];
  ...
  qsort(list, ...);

Но почему я не сделал массив с указателями, а сортировал именно данные?
Как известно сортировка бывает либо быстрой, либо занимает меньше память.
Перемещение данных из одного места памяти в другой не быстрая операция (особенно, если каждый элемент весьма немало занимает), но зато не требует дополнительной памяти под индекс для сортировки и использования.
А так как я писал программу реального режима DOS, где, как мы помним, "640 килобайт должно было хватить всем", то принял решение сэкономить, чтобы весь список точно в память влез.
Ну, да, сам себе попутно проблем создал, однако, с другой стороны, не было бы этого сообщения и интересных наблюдений.
Ах, да, писал я на Turbo Pascal (одну свою старую программу 2002 года откопал и решил чутка обновить), а там нет, как в сях, библиотечной функции qsort(), так что пришлось её самому делать. Это потом я код на C портировал, чтобы удобно отлаживать можно было и разобраться что же там не так происходит.