Назови пять компонентов и три стадии исполнения.

Архитектура фон Неймана основана на хранении команд и данных в общей адресуемой памяти. Основные компоненты: процессор с арифметико логическим устройством, устройством управления и регистрами; память; устройства ввода и вывода; связи между ними. Счётчик команд указывает, откуда взять следующую инструкцию. Цикл работы включает выборку, декодирование и исполнение. Команды обычно идут последовательно, а переходы меняют порядок. Обмен процессора с памятью ограничивает производительность — это узкое место фон Неймана.

Загрузить два числа из памяти → сложить в АЛУ → сохранить результат.

Не путай память с процессором. У современных CPU кэши команд и данных могут быть раздельными, хотя модель памяти программы остаётся общей.

Почему ветвление может замедлить конвейер?

Конвейер делит исполнение команды на стадии, например выборку, декодирование, выполнение, доступ к памяти и запись результата. Стадии разных команд перекрываются во времени. После заполнения конвейера повышается пропускная способность, но задержка одной команды не обязана уменьшаться. Мешают конфликты по данным, ресурсам и управлению. Используют остановки, перенаправление результатов и предсказание переходов. Ошибка предсказания требует сбросить неверно начатые команды и теряет такты.

Пять стадий не означают пять команд за такт: простой конвейер в идеале завершает одну команду за такт.

Конвейеризация и суперскалярность — разные способы ускорения.

Чем регистр флагов отличается от регистра общего назначения?

Регистры дают быстрый доступ к операндам и состоянию процессора. Регистры общего назначения хранят числа, адреса и промежуточные результаты. Счётчик команд хранит адрес следующей инструкции, указатель стека — положение вершины стека. Регистр флагов содержит признаки результата, например нуль, перенос и знак, а также управляющие биты. Сегментные регистры x86 связаны с сегментной организацией памяти. Это классификация по назначению, а не универсальная иерархия скоростей. В иерархии хранения регистры находятся ближе к вычислениям, чем кэши и ОЗУ.

После сравнения чисел условный переход использует флаги.

Устройство сегментных регистров зависит от архитектуры и режима CPU.

Назови два фактора производительности кроме частоты.

Тактовая частота — число тактов процессора в секунду, измеряемое в герцах. При прочих равных повышение частоты уменьшает время выполнения. Приближённо время CPU равно числу инструкций, умноженному на среднее число тактов на инструкцию и делённому на частоту. Производительность также зависит от архитектуры, IPC, кэшей, памяти, параллелизма и ограничений мощности. Поэтому сравнивать разные процессоры только по гигагерцам некорректно.

Если программа требует 6 миллиардов тактов, при 3 ГГц это около 2 секунд CPU, при неизменных остальных условиях.

1 ГГц не означает миллиард выполненных инструкций в секунду.

Зачем нужна таблица векторов?

Прерывание передаёт управление обработчику события с сохранением состояния, необходимого для продолжения программы. Аппаратные прерывания поступают от устройств, например таймера или контроллера ввода. Программные вызываются специальной инструкцией; исключения возникают при исполнении команд, например при делении на ноль или нарушении доступа. Номер события позволяет найти обработчик через таблицу векторов или дескрипторов прерываний. Обработчик обслуживает событие, после чего возможен возврат к программе либо её завершение. Системные вызовы могут использовать отдельные инструкции входа в ядро.

Таймер даёт ОС возможность переключить выполняемый поток.

Не всякое исключение позволяет продолжить сбойную инструкцию без исправления причины.

Почему обычная функция библиотеки не всегда является системным вызовом?

Режимы привилегий ограничивают допустимые инструкции и доступ к памяти и устройствам. В x86 предусмотрены кольца 0–3: кольцо 0 наиболее привилегированное, кольцо 3 наименее привилегированное. Типичная ОС использует их для ядра и пользовательских программ. Для защищённой операции приложение выполняет системный вызов, а ядро проверяет аргументы и права. Нарушение защиты вызывает исключение. Такое разделение обеспечивает изоляцию, устойчивость и безопасность системы.

Программа просит ядро открыть файл, а не напрямую управляет контроллером диска.

Кольца 1 и 2 существуют в x86, но обычно не нужны обычной схеме ядро плюс приложения.

Почему counter++ остаётся опасным при когерентных кэшах?

Кэш уменьшает среднюю задержку доступа к памяти за счёт временной и пространственной локальности. Данные переносятся блоками — строками кэша. L1 обычно самый маленький и быстрый, L2 больше, L3 обычно ещё больше и нередко общий для нескольких ядер. При попадании данные берутся из кэша, при промахе — из следующего уровня. Когерентность поддерживает согласованность копий одной области памяти у разных ядер, например инвалидируя старые копии при записи. Когерентность сама по себе не делает составные операции потокобезопасными.

Последовательный обход массива часто использует соседние элементы уже загруженной строки кэша.

Когерентность не заменяет мьютекс и не гарантирует нужный порядок всех операций программы.

В чём отличие от обычного конвейера?

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

Пока одна команда ждёт чтение памяти, независимое сложение может быть выполнено.

Внеочередное выполнение не разрешает игнорировать истинную зависимость результата одной команды от другой.

Чем страница отличается от сегмента?

Виртуальная память отделяет адресное пространство процесса от физической памяти, обеспечивая изоляцию, защиту и гибкое размещение. При страничной организации виртуальная память делится на страницы одинакового размера, физическая — на кадры; отображение задаётся таблицами страниц. При сегментации используются логические области переменного размера, например код и данные, с базой, границей и правами. Страничная организация избегает необходимости одного непрерывного физического блока, но может давать внутреннюю фрагментацию. Вытеснение на диск — возможная часть системы, а не определение виртуальной памяти.

Две соседние виртуальные страницы могут лежать в несоседних физических кадрах.

Виртуальная память — не просто дополнительная память на диске.

Что меняется при трансляции, а что остаётся?

MMU преобразует виртуальный адрес в физический. Адрес разбивается на номер виртуальной страницы и смещение. TLB кэширует недавние трансляции; при промахе выполняется обход таблиц страниц аппаратурой или с участием ОС, в зависимости от архитектуры. Запись таблицы содержит номер кадра и признаки присутствия, доступа и изменения. После проверки прав физический адрес получается из номера кадра и исходного смещения. Если страница отсутствует или доступ запрещён, возникает исключение page fault, которое обрабатывает ОС.

Страница 4096 байт, адрес 0x1234: страница 1, смещение 0x234. Если её кадр 9, физический адрес 0x9234.

Промах TLB не равен page fault: запись может существовать в таблице страниц.

Что учитывает Clock?

Алгоритм замещения выбирает страницу для вытеснения, когда необходимо освободить физический кадр. FIFO удаляет страницу, загруженную раньше остальных; LRU — ту, к которой дольше всего не обращались; Clock приближает оценку недавнего использования через бит обращения. Оптимальный алгоритм вытеснил бы страницу с самым далёким будущим обращением, но будущее неизвестно, поэтому это эталон сравнения. Изменённую страницу может потребоваться записать в хранилище. Слишком частые вытеснения вызывают thrashing — система тратит большую часть времени на подкачку.

При кадрах [1,2,3] и загрузке 4 FIFO вытесняет 1, если она была загружена первой.

LRU и FIFO могут выбирать разные страницы: возраст загрузки не равен давности обращения.

Потеря 3 КБ внутри выделенной страницы — какая фрагментация?

Внутренняя фрагментация возникает, когда выделенный блок больше полезных данных, например последняя страница заполнена частично. Внешняя возникает между занятыми блоками переменного размера: суммарно свободной памяти достаточно, но подходящего непрерывного блока нет. Внутренние потери уменьшают подбором размеров блоков и классов выделения. С внешней фрагментацией борются объединением соседних свободных блоков, компактированием там, где допустимо перемещение, и страничной организацией. Эти меры имеют компромиссы по скорости и служебным расходам.

Нужен блок 10 КБ, а свободны два несоседних по 6 КБ — пример внешней фрагментации.

Страничная память не устраняет все потери: последний кадр может быть заполнен частично, а куча имеет собственный аллокатор.

Возвращает ли free память ОС немедленно?

malloc выделяет запрошенное число байтов без инициализации, calloc выделяет массив и обнуляет его байты. realloc изменяет размер блока, может переместить его и сохраняет старые данные в пределах меньшего размера. При неудаче realloc с ненулевым размером возвращает NULL, а старый блок остаётся действительным. free освобождает блок; free(NULL) допустим. Это функции библиотеки, а не прямые системные вызовы. Аллокатор управляет аренами и свободными блоками и при необходимости запрашивает память у ОС; в Linux для этого могут использоваться brk и mmap. Каждый malloc не обязан обращаться к ядру.

int *tmp = realloc(p, bytes); if (tmp != NULL) p = tmp; Размер bytes заранее проверен и больше нуля.

Нельзя сразу писать p = realloc(p, bytes): при неудаче теряется единственный адрес старого блока. Здесь не используется realloc(p, 0).

Чем утечка отличается от висячего указателя?

Утечка памяти — сохранение выделенной памяти после того, как она перестала быть нужна, без возможности или намерения своевременно её освободить. Типичная причина — потеря последнего указателя или пропуск free на ветке ошибки. Valgrind Memcheck отслеживает обращения к памяти и сообщает, в частности, об утечках и недопустимых доступах. AddressSanitizer добавляет проверки при компиляции и помогает найти выходы за границы, use after free и другие ошибки. Обнаружение утечек через LeakSanitizer зависит от платформы и настроек. Отсутствие отчёта не доказывает отсутствие ошибок на непроверенных путях.

clang -std=c11 -g -fsanitize=address -fno-omit-frame-pointer main.c -o app В Linux: valgrind --leak-check=full ./app

Valgrind обычно используют в Linux, в Windows можно работать через подходящую Linux среду. Поддержка санитайзеров зависит от сборки компилятора.

Можно ли вернуть указатель на malloc блок?

Стек обычно используется для кадров вызовов, служебных данных и автоматических локальных объектов. Их время жизни управляется областью выполнения, а выделение часто сводится к изменению указателя стека. Куча предоставляет динамические блоки, временем жизни которых управляют malloc и free. Она удобна, когда размер известен только во время работы или данные должны пережить вызов функции. Выделение в куче обычно сложнее, но доступ к данным определяется также кэшами и расположением; сам адрес в куче не означает обязательно медленный доступ. Стандарт C задаёт длительности хранения, а не обязательное физическое размещение на стеке.

В int *p = malloc(10 * sizeof *p) локальный p и выделенный блок имеют разное время жизни.

Нельзя возвращать адрес обычной локальной переменной: объект исчезнет после выхода из функции.

Почему нельзя всегда вычислять размер структуры сложением полей?

Выравнивание — требование к адресам объектов данного типа, например кратность четырём для некоторой реализации int. Правильное выравнивание позволяет выполнять доступ эффективно, а на некоторых архитектурах необходимо для его корректности. Компилятор вставляет padding между полями и в конце структур, чтобы элементы массива структур также были выровнены. Поэтому sizeof структуры может превышать сумму размеров полей. Перестановка полей иногда уменьшает потери. Нарушение требований типа при доступе через указатель может дать неопределённое поведение.

struct { char c; int x; }; часто занимает 8 байтов при char=1, int=4 и выравнивании int=4, но это не универсальная гарантия C.

Упаковка структуры может уменьшить размер, но усложнить или замедлить доступ.

Что происходит при P, когда разрешений нет?

Семафор — примитив синхронизации с неотрицательным числом доступных разрешений и атомарными операциями P и V. P, или wait, получает разрешение, уменьшая счётчик, либо блокируется до его появления. V, или post, возвращает разрешение и позволяет ожидающему потоку продолжить. Счётный семафор ограничивает число одновременных пользователей ресурса, двоичный моделирует доступность одного разрешения. Конкретное внутреннее представление счётчика зависит от реализации. Атомарность операций необходима, чтобы два потока не получили одно разрешение.

Семафор с начальным значением 3 допускает до трёх одновременных пользователей ресурса.

Обычный int и операция -- не образуют корректный семафор между потоками.

Кто имеет право unlock обычного мьютекса?

Мьютекс обеспечивает взаимное исключение и имеет понятие владельца: освобождать обычный мьютекс должен захвативший его поток. Двоичный семафор имеет два логических состояния доступности и обычно не связывает разрешение с владельцем; один поток может ждать, другой сигнализировать. Оба могут ограничивать вход в критическую секцию, но семафор также удобен для передачи события между потоками. Поддержка наследования приоритетов и другие свойства зависят от реализации. Для защиты общего объекта обычно выбирают мьютекс, для учёта ресурсов или передачи разрешений — семафор.

Поток производителя делает post после подготовки данных, потребитель выполняет wait.

Обычный счётный семафор с начальным значением 1 не всегда принудительно ограничен единицей: лишние post могут увеличить счётчик.

Перечисли четыре условия без подсказки.

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

Все потоки сначала берут A, потом B — цикл A→B→A не возникнет.

В исходном списке написано «по Коберну»; общепринятое название — условия Коффмана. Четыре условия описывай уверенно, спорить о фамилии не требуется.

Почему два разных мьютекса не защищают один счётчик?

Критическая секция — участок программы, обращающийся к разделяемым данным, для которого необходимо согласованное выполнение. Взаимное исключение обеспечивает, что защищаемое действие выполняется только одним участником одновременно. Используют мьютексы, спинлоки, семафоры, а для подходящих отдельных операций — атомарные типы. Все конкурирующие обращения должны следовать одному протоколу защиты. Секцию стараются делать короткой, избегая длительного ожидания и несогласованного порядка вложенных замков.

lock(m); counter++; unlock(m); Все потоки используют один и тот же m.

Защитить только запись недостаточно, если другие потоки читают тот же неатомарный объект без синхронизации.

Кто хранит факт наличия работы — cv или очередь?

Условная переменная используется вместе с мьютексом и предикатом над общими данными. wait атомарно отпускает мьютекс и начинает ожидание, а перед возвратом вновь захватывает его. Условие проверяют в цикле while, потому что возможны ложные пробуждения и изменение состояния другим потоком. signal будит одного ожидающего, broadcast — всех. В отличие от семафора, условная переменная не накапливает разрешения: состояние хранится в защищаемых данных.

lock(m); while (empty) wait(cv, m); take_item(); unlock(m); Это псевдокод.

if вместо while не гарантирует истинность условия после пробуждения.

Достаточно ли атомарных чтения и записи для атомарного увеличения?

Race condition — зависимость корректности результата от непредсказуемого порядка выполнения. Data race в модели C возникает при конфликтующих действиях разных потоков над одной областью памяти, когда хотя бы одно действие — неатомарная запись и нет требуемого отношения синхронизации. Такая гонка данных приводит к неопределённому поведению. Защита: мьютексы, подходящие атомарные операции, разделение владения или передача сообщений. Атомарность отдельных обращений не всегда устраняет логическую гонку составной операции.

Проверить, что очередь не пуста, и удалить элемент нужно как одно согласованное действие.

volatile не делает counter++ атомарным и не создаёт межпоточную синхронизацию.

Зачем turn, если уже есть два флага?

Алгоритм Петерсона обеспечивает взаимное исключение для двух участников с флагами желания войти и переменной очереди. Участник i устанавливает flag[i], уступает очередь j и ждёт, пока flag[j] истинен и turn равен j. После секции он сбрасывает свой флаг. При классических предположениях атомарных обращений и последовательной согласованности достигаются взаимное исключение, прогресс и ограниченное ожидание. В современном C обычные общие переменные дают гонку данных; для учебной реализации требуются атомарные объекты с подходящим порядком памяти, например sequential consistency. volatile этого не исправляет.

Псевдокод: flag[i]=true; turn=j; while(flag[j] && turn==j) {} critical_section(); flag[i]=false;

Классический алгоритм предназначен для двух потоков и использует активное ожидание.

Чем отличаются p++, (*p)++ и *p++?

Указатель — объект, хранящий адрес другого объекта или функции. В выражении &var получают адрес var, а *ptr обозначает объект по адресу ptr, если указатель действителен. ptr++ перемещает указатель к следующему элементу его типа, а не увеличивает хранимое число. В C нет ссылок как отдельного типа языка; для сравнения, ссылка C++ обычно служит псевдонимом существующего объекта, должна быть инициализирована и не переназначается как указатель. Указатель можно переназначить и присвоить ему NULL.

int x=7; int *p=&x; *p=9; Теперь x равен 9. Выражение (*p)++ увеличило бы x.

Нельзя выполнять p++ и затем разыменовывать его, если p указывал на одиночный x: там нет второго элемента.

Прочитай int (*pred)(int) словами.

Указатель на функцию хранит адрес функции совместимого типа и позволяет вызывать её косвенно. Объявление int (*pred)(int) задаёт указатель на функцию с аргументом int и результатом int. Вызов pred(x) эквивалентен (*pred)(x). Такие указатели применяют для обратных вызовов, предикатов, обработчиков событий и таблиц операций. Тип аргументов и возвращаемого значения должен соответствовать вызываемой функции. Скобки в объявлении существенны: int *f(int) объявляет функцию, возвращающую указатель.

int positive(int x) { return x > 0; } Затем find_if(a, n, positive).

Передают positive, а не positive(3): второе уже вызывает функцию и даёт число.

Можно ли читать *(a+n) при длине n?

К указателю на элемент массива можно прибавлять и вычитать целое число в границах того же массива, включая позицию сразу за его концом. Смещение на k соответствует k элементам, а не k байтам. Указатель за концом допустим как граница, но его нельзя разыменовывать. Разность двух указателей внутри одного массива даёт число элементов и имеет тип ptrdiff_t, если результат представим. Складывать два указателя нельзя. Арифметика void* не входит в стандартный C; для обхода байтов используют unsigned char*.

Если sizeof(int)=4, то p+3 соответствует смещению на 12 байтов. *(a+2) обозначает третий элемент.

Нельзя даже формировать указатель a-1, чтобы потом сравнить его с a. NULL+0 также не является допустимым способом получить границу массива.

Защитит ли volatile int counter операцию counter++?

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

volatile sig_atomic_t stop; может применяться как простой флаг в обработчике сигнала при соблюдении ограничений C.

volatile не означает «значение обязательно каждый раз берётся из физической ОЗУ, минуя кэш».

Чем #ifdef отличается от обычного if?

Препроцессор выполняет обработку директив до компиляции C. #include включает содержимое заголовка, #define определяет объектный или функциональный макрос, #if, #ifdef и #endif управляют условной компиляцией. Защита от повторного включения строится через include guards. Макрос подставляет токены и не является обычной типизированной функцией, поэтому аргументы и всё выражение заключают в скобки и избегают аргументов с побочными эффектами. Для простых вычислений функция часто безопаснее макроса.

#define SQR(x) ((x) * (x)) Для SQR(2+3) получится 25, но SQR(i++) опасен.

Даже правильно расставленные скобки не устраняют повторное вычисление аргумента макроса.

Почему «у меня один раз работало» не оправдывает UB?

Неопределённое поведение — ситуация, для которой стандарт C не устанавливает требований к поведению программы. Примеры: выход за границы массива при доступе, разыменование NULL, использование освобождённой памяти, повторный free, переполнение знакового целого, деление целого на ноль и гонка данных. Компилятор вправе исходить из того, что корректная программа не совершает UB, поэтому последствия не ограничены местом ошибки. Предотвращение: проверка границ и времени жизни, контроль диапазонов, предупреждения компилятора, тесты и санитайзеры.

int a[3]; a[3]=1; — выход за границы: разрешены индексы 0, 1, 2.

Беззнаковая арифметика вычисляется по модулю диапазона; её переполнение само по себе не UB, но может испортить размер выделяемого блока.

Кто очищает стек в типичном x86 cdecl и stdcall?

Соглашение о вызовах определяет передачу аргументов и результата, сохранение регистров и очистку стека. В типичных 32 битных соглашениях Microsoft x86 cdecl передаёт аргументы через стек справа налево, стек очищает вызывающая функция. stdcall использует похожую передачу, но очищает стек вызываемая функция. fastcall передаёт часть подходящих аргументов через регистры, остальные через стек. Эти детали зависят от платформы и ABI. На Windows x64 действует отдельное соглашение с первыми четырьмя аргументами в соответствующих регистрах; переносить туда таблицу x86 буквально нельзя.

Для Microsoft x86 fastcall первые два подходящих целочисленных аргумента обычно передаются через ECX и EDX.

Слова caller и callee означают вызывающую и вызываемую функции соответственно.

void print_reverse(int *arr, size_t n) {
    if (n == 0) { putchar('\n'); return; }
    int *p = arr + n;
    while (p != arr) {
        --p;
        printf("%d", *p);
        if (p != arr) putchar(' ');
    }
    putchar('\n');
}

void copy_array(int *dest, const int *src, size_t n) {
    while (n > 0) {
        *dest++ = *src++;
        --n;
    }
}

while (m > 0 && n > 0) {
    if (*a <= *b) { *out++ = *a++; --m; }
    else { *out++ = *b++; --n; }
}
while (m > 0) { *out++ = *a++; --m; }
while (n > 0) { *out++ = *b++; --n; }

int is_palindrome(const int *arr, size_t n) {
    if (n < 2) return 1;
    const int *left = arr, *right = arr + n - 1;
    while (left < right) {
        if (*left != *right) return 0;
        ++left;
        --right;
    }
    return 1;
}

int get(const int *mat, size_t rows, size_t cols,
        size_t i, size_t j) {
    assert(i < rows && j < cols);
    (void)rows;
    return *(mat + i * cols + j);
}

if (*p > *(p + 1)) {
    int tmp = *p;
    *p = *(p + 1);
    *(p + 1) = tmp;
    changed = 1;
}

unsigned long long factorial(int n) {
    if (n < 0 || n > 20) { errno = ERANGE; return 0; }
    unsigned long long result = 1;
    for (int i = 2; i <= n; ++i)
        result *= (unsigned long long)i;
    return result;
}

unsigned long long a = 0, b = 1;
for (int i = 2; i <= n; ++i) {
    unsigned long long next = a + b;
    a = b;
    b = next;
}
return b;

while (y != 0) {
    unsigned rem = x % y;
    x = y;
    y = rem;
}
if (x > INT_MAX) { errno = ERANGE; return 0; }
return (int)x;

unsigned q = x / u;
if (q > (unsigned)INT_MAX / y) {
    errno = ERANGE;
    return 0;
}
return (int)(q * y);

int is_prime(int n) {
    if (n < 2) return 0;
    for (int d = 2; d <= n / d; ++d)
        if (n % d == 0) return 0;
    return 1;
}

int k = 0;
while (n % d == 0) { n /= d; ++k; }
if (k != 0) {
    if (!first) printf(" * ");
    printf("%d^%d", d, k);
    first = 0;
}

long long result = 1;
while (exp > 0) {
    if (exp % 2 != 0) result *= base;
    exp /= 2;
    if (exp > 0) base *= base;
}
return result;

int sum = 0;
do {
    sum += (int)(x % 10);
    x /= 10;
} while (x != 0);
return sum;

char *out = bits;
do {
    *out++ = (char)('0' + n % 2);
    n /= 2;
} while (n != 0);
*out = '\0';
while (out != bits) putchar(*--out);
putchar('\n');

int *find_if(int *arr, size_t n, int (*pred)(int)) {
    while (n > 0) {
        if (pred(*arr)) return arr;
        ++arr;
        --n;
    }
    return NULL;
}

size_t filter(int *arr, size_t n, int (*pred)(int),
              int *result) {
    size_t count = 0;
    while (n > 0) {
        if (pred(*arr)) {
            *result++ = *arr;
            ++count;
        }
        ++arr;
        --n;
    }
    return count;
}

int *partition(int *arr, size_t n, int (*pred)(int)) {
    int *boundary = arr;
    while (n > 0) {
        if (pred(*arr)) {
            int tmp = *boundary;
            *boundary = *arr;
            *arr = tmp;
            ++boundary;
        }
        ++arr;
        --n;
    }
    return boundary;
}

unsigned char c = (unsigned char)*s++;
if (c >= 'A' && c <= 'Z')
    c = (unsigned char)(c - 'A' + 'a');
if (c < 'a' || c > 'z') continue;

do {
    unsigned digit = x % 10;
    if (result > (limit - digit) / 10) {
        errno = ERANGE;
        return 0;
    }
    result = result * 10 + digit;
    x /= 10;
} while (x != 0);

char expected = c == ')' ? '(' : c == ']' ? '[' : '{';
if (top == 0 || *(stack + top - 1) != expected) {
    ok = 0;
    break;
}
--top;

void replace_char(char *str, char old_char, char new_char) {
    while (*str != '\0') {
        if (*str == old_char) *str = new_char;
        ++str;
    }
}

int binary_search(const int *arr, size_t n, int target) {
    size_t left = 0, right = n;
    while (left < right) {
        size_t mid = left + (right - left) / 2;
        int value = *(arr + mid);
        if (value == target) {
            if (mid > INT_MAX) { errno = ERANGE; return -1; }
            return (int)mid;
        }
        if (value < target) left = mid + 1;
        else right = mid;
    }
    return -1;
}