#define N (5)

int a[N];

a[0]=3;
a[1]=5;
a[2]=7;
a[3]=9;

i=2; //В эту позицию надо вставить элемент

memmove(a+(i+1),a+i,sizeof(int)*(N-1-i)); //Сдвиг элементов 2,3 на позиции 3,4 - копирование a[2],a[3] в a[3],a[4]
a[i]=6;

memmove(a+(i+1), a+i, sizeof(int)*(N-1-i));

memmove(a+i, a+(i+1), sizeof(int)*(N-1-i));

typedef struct А_S
{
    int id;
    char message[128];
}А;

А а[512];

memmove( a+(i*sizeof(A)+1),  a+(i*sizeof(A)),  sizeof(int)*(N-1-i));

memmove( a+(i+1),  a+i,  sizeof(A)*(N-1-i));

#define MESSAGE_ARR_SIZE 128

typedef struct TEST_MESSAGE_S
{
    int id;
    char data[20];
}TEST_MESSAGE;

TEST_MESSAGE messages[MESSAGE_ARR_SIZE8];

int found;
int glob_pos;

int BinarySearch(TEST_MESSAGE a[], int pos, int key, int *found)
{
    int first = 0;
    int last = pos;
    int mid;
    
    if (pos == 0)  //empty array
    {
        *found = 0;
        return 0;
    }
    else if (a[0].id > key)
    {
        *found = 0;
        return 0;
    }
    else if (a[pos - 1].id < key)
    {
        *found = 0;
        return pos;
    }
    
    while (first < last)
    {
        mid = first + (last - first) / 2;

        if (key <= a[mid].id)
            last = mid;
        else
            first = mid + 1;
    }

    if (a[last].id == key)
    {
        *found = 1;
        return last;
    }
    else
    {
                *found = 0;
        return last;
    }
}

void InsertElement(int id, char msg[])
{
    int idx;
    
    idx = BinarySearch(messages, glob_pos, id, &found);
    
    if (found)  //command NEW but the element exists - issue UPDATE
    {
        UpdateElement(idx, msg);
    }
    else //element not found - add one
    {
        memmove(messages+(idx+1), messages+idx, sizeof(TEST_MESSAGE)*glob_pos-1-idx);
        messages[idx].id = id;
        memcpy(messages[idx].data,  msg, sizeof(msg);

        
       if (glob_pos < MESSAGE_ARR_SIZE)
           glob_pos++;
    }
}

void DeleteElement(int id)
{
     int idx;
    
    idx = BinarySearch(messages, glob_pos, id, &found);
    
    if (found)
    {
       memmove(messages+idx, messages+(idx+1), sizeof(TEST_MESSAGE)*glob_pos-1-idx);
      
       if (glob_pos > 0)
           glob_pos--;
    }
}

memmove(messages+(idx+1), messages+idx, sizeof(TEST_MESSAGE)*glob_pos-1-idx);

memmove(messages+(idx+1), messages+idx, sizeof(TEST_MESSAGE)*glob_pos-idx);

void InsertElement(int id, char *msg)
{
    int idx;
    int size;
    
    idx = BinarySearch(messages, glob_pos, id, &found);
    
    if (found)  //command NEW but the element exists - issue UPDATE
    {
        UpdateElement(idx, msg);
    }
    else //element not found - add one
    {
        memmove(messages+(idx+1), messages+idx, sizeof(TEST_MESSAGE)*(glob_pos-idx));   //glob_pos-1-idx
        
        messages[idx].id = id;

        size = sizeof(msg);
        memcpy(messages[idx].data, msg, size);
        
      if (glob_pos < MESSAGE_ARR_SIZE)
        glob_pos++;
    }
}

memcpy(messages[idx].data, msg, sizeof(messages[0].data));

#define MESSAGE_ARR_SIZE 128

typedef struct TEST_MESSAGE
{
union
{
char data[20];
struct TEST_MESSAGE *next;
};
}TEST_MESSAGE;


typedef struct
{
int id;
TEST_MESSAGE *p;
}TEST_MESSAGE_P;

TEST_MESSAGE *MsgFreeQ;

TEST_MESSAGE messages[MESSAGE_ARR_SIZE];
TEST_MESSAGE_P msg_p[MESSAGE_ARR_SIZE];


int found;
int glob_pos;

int BinarySearch(TEST_MESSAGE_P *a, int pos, int key, int *found)
{
int first = 0;
int last = pos;
int mid;

if (pos == 0) //empty array
{
*found = 0;
return 0;
}
else if (a[0].id > key)
{
*found = 0;
return 0;
}
else if (a[pos - 1].id < key)
{
*found = 0;
return pos;
}

while (first < last)
{
mid = first + (last - first) / 2;

if (key <= a[mid].id)
last = mid;
else
first = mid + 1;
}

if (a[last].id == key)
{
*found = 1;
return last;
}
else
{
*found = 0;
return last;
}
}

TEST_MESSAGE *AllocMessage(void)
{
TEST_MESSAGE *p=MsgFreeQ;
if (p) MsgFreeQ=p->next;
return p;
}


void FreeMessage(TEST_MESSAGE *p)
{
p->next=MsgFreeQ;
MsgFreeQ=p;
}

void InitMessageQ()
{
for(unsigned int i=0; i<MESSAGE_ARR_SIZE; i++)
{
FreeMessage(messages+i);
}
}

void InsertElement(int id, char msg[])
{
int idx;

idx = BinarySearch(msg_p, glob_pos, id, &found);

if (found) //command NEW but the element exists - issue UPDATE
{
UpdateElement(idx, msg);
}
else //element not found - add one
{
TEST_MESSAGE *nm=AllocMessage();
if (nm)
{
memmove(msg_p+(idx+1), msg_p+idx, sizeof(TEST_MESSAGE_P)*(glob_pos-1-idx));
msg_p[idx].id = id;
msg_p[idx].p=nm;
memcpy(nm->data, msg, sizeof(nm->data));
if (glob_pos < MESSAGE_ARR_SIZE) glob_pos++;
}
}
}

void DeleteElement(int id)
{
int idx;

idx = BinarySearch(msg_p, glob_pos, id, &found);

if (found)
{
FreeMessage(msg_p[idx]->p);
memmove(msg_p+idx, msg_p+(idx+1), sizeof(TEST_MESSAGE_P)*(glob_pos-1-idx));

if (glob_pos > 0)
glob_pos--;
}
}

void InsertElement(int id, char msg[])
{
    int idx;
    
    idx = BinarySearch(msg_p, glob_pos, id, &found);
    
    if (found)  //command NEW but the element exists - issue UPDATE
    {
        UpdateElement(idx, msg);
    }
    else //element not found - add one
    {
        TEST_MESSAGE *nm=AllocMessage();
        if (!nm) nm=msg_p[MESSAGE_ARR_SIZE-1].p; //Если не удалось аллоцировать новый элемент - заменяем последний
        memmove(msg_p+(idx+1), msg_p+idx, sizeof(TEST_MESSAGE_P)*(glob_pos-1-idx));
        msg_p[idx].id = id;
        msg_p[idx].p=nm;
        memcpy(nm->data,  msg, sizeof(nm->data));
        if (glob_pos < MESSAGE_ARR_SIZE) glob_pos++;
    }
}