Динамическая реализация массива в C


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

Заголовочный файл для реализации( dyn_array.з)

#ifndef TYPE_H
#define TYPE int
#define TYPE_SIZE sizeof(int)
#endif

#ifndef STDDEF_H
#include <stddef.h>
#endif

#ifndef STDBOOL_H
#include <stdbool.h>
#endif

#ifndef INIT_BUFFER_SIZE
#define INIT_BUFFER_SIZE 2
#endif


typedef struct DynArray
{
        TYPE *data;
        size_t size;
        size_t capicity;
}DynArray;


bool DynArray_init(DynArray *self);
TYPE DynArray_getElement(const DynArray *self, size_t pos);
bool DynArray_setElement(DynArray *self, size_t pos, TYPE value);
size_t DynArray_getSize(const DynArray *self);
bool DynArray_pushBack(DynArray *self, TYPE value);
TYPE DynArray_removeElement(DynArray *self, size_t pos);

dyn_array.с

#include "dyn_array.h"
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
#include <assert.h>
#include <stdio.h>






/*Allocate an pool of memory to store data upto N elements
 * 
 * @param capicity
 *  capacity for the data pool 
 *
 * @returns 
 *  Pointer to a memory area of type TYPE with given number
 *  */


TYPE * __DynArray_createDataPool(size_t capicity)
{
    if (capicity != 0)
    {
        size_t bytesize =  TYPE_SIZE * capicity;
        TYPE *tmp = malloc(bytesize);
        if (!tmp)
            return NULL;
        tmp = memset(tmp, 0x00, bytesize);
        return tmp;
    }
    return NULL;
}

/*Initilize an DynArray
 * 
 * @param  self
 *      A pointer to an DynArray struct
 *
 * @returns
 *  true if initilization is successful or false if initlization is
 *  unsuccessful (possible reason - out of memory or bad pointer)
 *
 *  
 * */
bool DynArray_init(DynArray *self)
{
    if (self)
    {
        self->size = 0;
        self->data = __DynArray_createDataPool(INIT_BUFFER_SIZE);
        if (!self->data)
            return false;
        self->capicity = INIT_BUFFER_SIZE;
        return true;
    }
    return false;
}

/**
 *returns the element at a given index
 *
 * @param index
 *      index of the element that need to be read
 *
 * @returns
 *      value of the element at given index,
 *      assert Fails if the it's called with an invalid index
 *      and NDEBUG is not defined.
 *
 **/

TYPE DynArray_getElement(const DynArray *self, size_t index)
{
    assert(index < (self->size));
    return self->data[index];
}

/* double the capicity of an array
 *
 * */
bool __DynArray_expendArray(DynArray *self)
{
    if (self)
    {
        TYPE *tmp = __DynArray_createDataPool(2*(self->capicity));
        if (!tmp)
            return false;
        size_t byteToCopy = TYPE_SIZE* (self->size);
        tmp = memcpy(tmp, self->data, byteToCopy);
        free(self->data);
        self->data = NULL;
        self->data =  tmp;
        self->capicity = 2*(self->capicity);
        return true;

    }
    return false;
}

bool __DynArray_shrinkArray(DynArray *self, size_t capicity)
{
    TYPE *tmp = __DynArray_createDataPool(capicity);
    if (!tmp)
        return false;
    size_t byteToCopy = TYPE_SIZE*(self->size);
    tmp = memcpy(tmp, self->data, byteToCopy);
    free(self->data);
    self->data = tmp;
    self->capicity = capicity;
    return true;
}

/* push an element to last of the array
 *
 * @param self
 *      pointer to the DynArray struct
 *
 * @param value
 *      Value that need to be pushed
 *
 * @returns 
 *      true if push is successfule otherwise false
 * */

bool DynArray_pushBack(DynArray *self, TYPE value)
{
    if ((self->size) == (self->capicity))
    {
        bool res =  __DynArray_expendArray(self);
        if(!res)
            return false;
    }
    self->data[self->size] = value;
    self->size += 1;
    return true;
}
/*
 *
 * returns the current size of elements in array
 * @param self
 *      pointer to a DynArray struct
 *
 * @returns
 *      current size of the array
*/


size_t DynArray_getSize(const DynArray *self)
{
    return self->size;
}

/*remove the element at a given index
 *
 *@param self
 *      pointer to the DynArray struct
 *@param index
        index of the element that needs to be removed
        (If the index is greater then the element in array then the return value is undefined)
 *
 * @returns
 *      element that's is removed from the given index
 * */

TYPE DynArray_removeElement(DynArray *self, size_t index)
{
    assert(index < self->size);
    if (self->size < (self->capicity/4))
    {
        __DynArray_shrinkArray(self,(self->capicity/2));
    }
    TYPE indexValue = self->data[index];
    for (size_t i = index; i < (self->size - 1); i++)
        self->data[i] = self->data[i+1];
    self->size -= 1;
    return indexValue;
}


169
6
задан 13 апреля 2018 в 04:04 Источник Поделиться
Комментарии
1 ответ

Есть пара мелких орфографических ошибок, что я заметил:


  • capacityне capicity

  • expandArrayне expendArray

Включают предохранитель

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

В верхней части заголовка вы должны добавить это:

#ifndef H_DYNARRAY
#define H_DYNARRAY

и последняя строка должна быть:

#endif

Это защитит его от быть включены более чем один раз, так что вы можете include "dyn_array.h" на содержание ваших сердцах.

STDDEF_H и STDBOOL_H

Нет необходимости определять эти — стандартные заголовки содержат уже включают в себя охранников.

calloc

Вместо malloc + memsetрассмотрите возможность использования calloc:

TYPE * __DynArray_createDataPool(size_t capacity)
{
if (capacity == 0) {
return NULL;
}
return calloc(capacity, TYPE_SIZE);
}

Если происходит сбой выделения, calloc возвращает значение null.

Есть немного больше информации о calloc здесь: https://stackoverflow.com/a/2688522

realloc

Же, как и выше — вместо malloc + memcpy + freeрассмотрите возможность использования realloc вместо. Вы можете ознакомиться с man 3 reallocно в основном:

bool __DynArray_expandArray(DynArray *self)
{
if (!self) {
return false;
}

TYPE *tmp = realloc(self->data, TYPE_SIZE * self->capacity * 2);
if (tmp == NULL) {
return false;
}

// Fill new memory with zeros
memset(tmp + self->capacity, 0, self->capacity);

self->data = tmp;
self->capacity *= 2;
return true;
}

Примечание: realloc не инициализировать новую память с нуля, поэтому, если это важно, вы хотите, чтобы вручную очистить ее.

5
ответ дан 13 апреля 2018 в 12:04 Источник Поделиться