Функция memmove () с O (1) сложностью времени

Question

Мне задали этот вопрос сегодня во время интервью, и я озадачен. Я пытался поискать в Google, но не нашел ничего, что могло бы помочь. Вся информация, которую я могу найти, говорит, что memcpy и memmove имеют O (n) время, и я не могу найти реализацию, которая была бы O (1).

Код вопроса C приведен ниже:

Функция memcpy () копирует n байтов из области памяти sr c в область памяти dest. Области памяти не должны перекрываться. Предположим, что прототип для memcpy ():

void memcpy (void * dest, const void * sr c, size_t n);

Цель этого упражнения - создать реализация memcpy (), устойчивая к перекрытию областей памяти. То есть, если область памяти назначения перекрывает источник, то часть области памяти источника может быть перезаписана. Функция для реализации будет иметь следующий прототип:

void rti_memmove (void * dest, const void * sr c, size_t n);

Вы не можете использовать mallo c () в решении, однако, можно использовать memcpy ().

Пример ниже:

Строка "Mem addrs" представляет адреса указателя / памяти.

Строка «Content» представляет значение, сохраненное в адресах памяти / указателя до вызова rti_memmove ().

Строка ниже «rti_memmove (D, S, 5)» представляет данные по адресам памяти / указателя после вызова функция rti_memmove ().

D = адрес назначения

S = адрес источника

n = количество байтов для перемещения

n = 5      S     D
Mem addrs  1  2  3  4  5  6  7  8  9
Content:   a  b  c  d  e  f  g  h  i
rti_memmove(D, S, 5);
Content:   a  b  c  d  c  d  e  f  g 

Поскольку мы имеем дело с системами реального времени, memmove должен иметь постоянное время выполнения (то есть временная сложность O (1)).

Ответ, который я придумал, приведен ниже:

#include <stdio.h>

void rti_memmove(void *dest, const void *src, size_t n) 
{
  int i;

  if(src < dest)
  {
    for(i = n-1; i >= 0; i--)
    {
       *(dest+i) = *(src+i);
    }
  }
  else if(src > dest)
  {
    for(i = 0; i < n; i++)
    {
       *(dest+i) = *(src+i);
    }
  }
  else //src == dest
  {
    return;
  }

} /* rti_memmove() */

Однако, этот ответ O (n), и интервьюер спросил меня, как я это сделаю O (1) , Я не мог / не могу придумать ответ. Мы обсуждали, возможно ли оптимизировать его с помощью memcpy () для неперекрывающихся байтов и для l oop для перекрывающихся байтов (обратите внимание, что memcpy () имеет неопределенное поведение при копировании пересекающейся памяти). Мы также обсуждали использование какого-либо буфера фиксированной длины для memcpy () данных sr c, перед тем как использовать memcpy () для копирования из буфера в место назначения. Но это было бы неэффективно.

В настоящее время моя единственная идея (после поиска в Google и обдумывания проблемы) - ограничить значение параметра n указанным значением c. Например, если бы у меня был оператор if if (n>512) return;, то при максимальном значении функция имела бы значение для l oop с временем O (512) -> O (1) и имела бы предсказуемое максимальное время выполнения, потенциально соответствующее реальному времени. требование к расписанию, чтобы быть постоянным.

TL; DR Как заставить вышеуказанный код работать за O (1) время, следуя перечисленным требованиям.