An Expandable Array ADT - Grinnell-CSC207/adt-exploration GitHub Wiki

Instructions: Find a project that includes an implementation of expandable arrays in C. I would prefer that you find it on Github, but you can look elsewhere on the Internet. Skim through the implementation and then answer the following questions. After answering a question, put your initials in brackets after your answer. (If you see an answer that does not differ substantially from what you might write, you are allowed to put the word "ditto" and your initials in brackets after the previous answer.)

Implementations of Expandable Arrays

Please give the name and URL of the project you've found. Also indicate where we can find the implementation of expandable arrays within that project.

*The project's name is [DynamicArray] (https://github.com/XeresRazor/DynamicArray/blob/master/DynamicArray/DynamicArray.h), a header file that holds a library of procedures used for the creation of a dynamic, expandable array of any data type. [HB]

  • The project's name is vec (an obvious abbreviation for vector, which are mutable ADTs). To find the expandable array implementation, open the vec/src folder. It contains the source file containing the code for the core functions and a header file which lists the the functions that can be used. [SZ]

  • The project I found is called klib. It is a lightweight C library that is supposed to work independently, so you can get any of its components without having to download the whole project. One if its components is called kvec which is a "generic dynamic array", meaning that it can be expanded. [NK]

  • The project name is [c-arraylist] https://github.com/frenchtoast747/c-arraylist . The implementation of the expandable array can be found in the source file, ‘arraylist.c’. The source file requires a header file, ‘arraylist.h’ which is also found in the package.[AOA]

  • A project called prog contains examples of programs. The implementation of an expandable array example can be found on Github as Adding dynamic array example or from its original source on stackoverflow as C dynamically growing array. The example uses pointers to create an expandable array. [ZC]

  • The project I found is called CMU Sphinx working towards speech recognition. One instance of expandable arrays can be found in their multisphinx sub-project. [EF]

  • An Expandable C Array implementation I found is called vector.c from HappyBearSoftware. The full vector.c "class" with functions is seen partway through the page with implementation of several of the functions below it. [PS]

  • I ended up looking at a project which goes by the name of array. The project includes some documentation and implementation examples along with the actual code which is needed in order to make use of the ADT created in the project. The only files one needs to implement the expandable array are array.h and array.c. The array which is created will be an array of unsigned uintptr_t integers. [WR]

  • I found a project called dynarr which is "a simple and easy to use dynamic array implementation for C, similar to the C++ std::vector class." To find the implementation of the dynamic arrays go to the dynarr.c subdirectory. [NS]

  • The project's name is cArray. The array.c file shows the implementation of expandable arrays. [CMV]

  • The project that I found is the Make File from [eddmann] (http://eddmann.com/posts/implementing-a-dynamic-vector-array-in-c/). To find the expandable array, you can go the vector_resize function under The Implementation File. Vector is defined as a struct in the header file. Vector_resize uses pointers and an integer to expand the array. [LG]

  • The project I found is called dynamic arrays in c. The implementation of an expandable array can be found in array.c. [CM]

  • The project I found is called [levawc] (https://github.com/dale48/levawc). The expandable array is found in multiple places but I am especially looking at bitree.c. [AK]

  • The project I found is called [dynamicArray] (https://github.com/luxigo/dynamicArray). The implementation of an expandable array can be found in dynamicArray.c [TP]

  • The project I found is called bigsort and the dynamic array implementation can be found in src, called expand_array.c [HZ]

  • The project I found is called [vector] (https://github.com/ox/vector), it implements a dynamic array, which is used in main.c, and implemented in vector.c It grows and shrinks as necessary or as specified by the programmer. [CG]

  • I found an implementation of dynamic arrays by Troy D. Hanson called utarray. The source code can be found at utarray.h. It has built in capabilities for integers and strings and allows users to define their own types of arrays (for structures). [ZW]

  • The array.c project highlights one of the numerous ways to create a dynamic array in C. All the files for the project exist on the link to the page. The implementation for the dynamic array can be found in the array.c file and it is used in the main.c file. [LAB]

  • Ditto on [NS]'s addition. dynarr has a very strait forward implementation of a dynamic array, as well as having a very easy way of the client to use it (with dynarr_alloc and dynarr_push functions). One thing I will add is that even though I know the concept of the push function, looking at the code, I have no idea how it actually manipulates the array. [YK]

  • The project I found is called Formal Languages by Igor Naumov link. The implementation of expandable arrays can be found by going to the path formal_languages/task1/dynamic_array/dynamic_array.c. It is tested in the file dynamic_array_test.c in the same directory. [AS]

  • Found a class project that some student had written for their computer science class related to dynamic arrays. It is called dynamicArray.c written by John Zeller (https://github.com/JohnLZeller/Classes/blob/master/CS261/Assign2/dynamicArray.c). This project shows implementation of the various functions used for a dynamic array (ditto on YK addition). Implementations can be seen right on the page! [AHD]

  • Found a project by the name of [bigsort] (https://github.com/Tim-B/bigsort/tree/b651b80b9b088e24eb77a43163f65362fa63c042/src) by Tim-B. the implementation of an expandable array is in the file called expand_array.c. [EE]

Important Functions

Describe one or two operations (functions, procedures, methods, subroutines, whatever you want to call them) that client programmers can use. (The client may be another part of the same program.) Our goal is to get a large list of possible operations (or variants of similar operations) that we can compare and contrast.

  • The DAHeaderCreate operation allows the user to actually create the array, with a count of zero elements and a null value for the allocated slot of memory. The DAHeaderAddValue function doubles the size of the array if the number of elements in it ever exceeds the size of the previously existing array. [HB]

  • An expected operation would be the ability to add elements at the end of the array. This is provided through vec_push(v, val). It takes in an initialized vector (using vec_init()) as the first argument, and the value to append as the second argument. [SZ]

  • Another interesting operation is the vec_remove(v, val) method. It iterates through the array, and deletes the first instance of val in the array. If val does not exist, then the operation simply doesn't do anything. [SZ]

  • To create an array, you have to first call kvec_t(type), which creates an array that can hold a specific type. For example if you said kvec_t(char) my-array;, you would be declaring an dynamic array that could hold chars.[NK]

  • Another interesting implementation is kv_resize(type, v, s) , which re-sizes the vector v of type type to size s.[NK]

  • The main operations are to increase the size of the array when an item is added and it exceeds the size of the array (in the function insertArray) and to reset the array when everything is completed (in the function freeArray). insertArray takes a pointer to an array and an item to be added. It checks whether the amount used in the array is equal to the size of the array. If it is, the size of the array doubles and memory is reallocated to fit the enlarged array. Then the new item is added onto the array. If the amount used in the array is not equal to the size of the array, the item is just added onto the array. freeArray takes a pointer to an array. It is called to deallocate memory for the array. The array is set to NULL and the amount used and the size of the array is set to zero. [ZC]

  • Another important operation is that of finding an item within the array at an index without changing the array. The sync_array_get function first checks if the index is valid - if it is not returns 0 and if it is returns 1 after using memcpy to copy the element into a waiting section of memory. [EF]

  • In the implementation I found, the main functions are vector_init, which initializes the vector, and vector_append, which appends a given value to the end of the vector. The append function depends on a function called vector_double_capacity_if_full, which doubles the capacity of the vector if it's full using C's realloc function. [PS]

  • The two operations that I found most interesting were ‘newArrayList’ and the ‘ArrayList_realloc’. ‘newArrayList’ is important because it is the operation that the client programmer would use to initialize the array. I found 'newArrayList' interesting because the operation’s parameter was ‘size_t data_size’ which suggests to me that a client must have an idea of how big the initial array is in terms of the amount of bytes in memory the array will occupy. Furthermore, I found the ‘ArrayList_realloc’ operation interesting because it seemed that the programmer is using a mechanism of multiplying the initial array size by 2, each time the initial array is full. This was odd because i thought of situations where the new elements being added to the resized array might not necessarily occupy all the space allocated during the resizing process.[AOA]

  • The main functions in the implementation I found are the array_new method, which creates a new array, the array_putint function, which allows you to actually populate (and expand if needed) the array, the array_getint method, which allows you to get values from the array, and the array_newcap method, which allows you to change the size of the array directly. [WR]

  • One of the functions I found void* array_put_auto(Array a, size_t i, void * elem) automatically resizes the array if given an index that is greater than the current fixed size of the array. It will truncate the size of the array if it is smaller than the current fixed size. When the array is expanded, it will write the new memory with 0's. [CMV]

  • To create an resizable array of any number of uintptr_t integers, you call the array_new(size_t cap) method. I believe the uintptr_t datatype is an unsigned integer which occupies the same space in memory as a pointer (http://pubs.opengroup.org/onlinepubs/009695399/basedefs/stdint.h.html). The size_t datatype is an unsigned integer which is usually used to represent the size of data structures (http://stackoverflow.com/questions/2550774/what-is-size-t-in-c). The parameter cap you pass to the method is the number of uintptr_t integers you want to initially allocate space for. First, array_new allocates memory for a new Array structure using calloc. Then, array_new allocates space elsewhere in memory for an array of cap intptr_t integers, again using calloc. Next, a pointer to memory which was just allocated for the uintptr_t integers is stored in the Array structure. Finally, a pointer to the Array structure is returned. [WR]

  • An important operation is vector_add. In this function, vector_resize is called in order to create more space. More space is needed so that another item can be added to the vector. Vector_delete is also an important operation because it also utilizes the vector_resize function. When an item is deleted off of a list, the size of the vector decreases. [LG]

  • void *dynarr_alloc allows for the creation of a dynamic array, e.g. int *arr = dynarr_alloc(0, sizeof *arr);, which can be added to using the void *dynarr_push(void *da, void *item) function. void *dynarr_pop(void *da) removes the frontmost element in the array, downsizes the array, using void *dynarr_resize(void *da, int elem), and returns the removed element. [NS]

  • One important operation is resizeArray, which doubles the size of an array. It does this by first defining newSize to be twice the size of the original array, and then using realloc to change the size of the memory block for the array to newSize. Another important operation is addElement, which adds a new element to the end of an array. This function makes use of the function resizeArray if the array is not big enough to hold a new element. Once the array has been resized, or if the array was not full to begin with, the new element is added. [CM]

  • An important operation that I saw was BITREEdestroy, which destroys all the nodes in a particular part of the Bitree.There are also other operations BITREEinsleft and BITREEinsright which add information to one side of the Bitree or another. It seems important for which side the information is added. There is even a comparison function which compares one part of the tree to another. What I find quite interesting about this system is code is the use of recursive programming. [AK]

  • A useful operation I found is *dynamicArray_pop which returns the last element in the array and then removes the element from the array. If the array is empty the operation will return NULL. [TP]

  • Another useful operation that I found is *dynamicArray_push which appends item to the the array. [TP]

  • Operations that seemed important include expand_array_put and expand_array_free. These functions seem important because they deal most closely with the dynamic necessities of expandable arrays. It is necessary to not only be able to add more elements to an array, which is done with expand_array_put, but also to free up space when there are fewer elements in an expandable array, as done with expand_array_free. If the given array is too small to add more elements, expand_array_put uniformly doubles the size of the array to include more space. This seems like it wouldn't be as useful once arrays in use became really big, but it works for smaller arrays[HZ]

  • Operations that were critical to vector include vector_new(vector), which creates a new vector (what the author calls the expandable arrays), vector_destroy(vector), which destroys the specified vector, vector_push(vector, elem), which adds elem to vector, calling the other function vector_resize(vector) as necessary to resize it. Vector_resize works by using some logic, if the population of the array is equal to the current length, it doubles the length and reallocates the memory as necessary.[CG]

  • I thought the resizeArray method was very important as well as creative (from my point of view). resizeArray takes a parameter (which is a pointer) of type, ArrayData. One of the fields of ArrayData is the "size". resizeArrray doubles the initial "size" of the array by first multiplying the initial "size" of the array by sizeof(int) (which I think will vary but by standard 32-bit compilers should be 4 bytes) then by 2. It then reallocates space in memory with the new size created and stores it in the "pointer" field of the ArrayData element. It the "cleans the buffer" using fflush(stdout) the finally multiply the array size by 2 and store it as the "size" of the array. [LAB] Ditto. I find it interesting that the size is always doubled when the limit is reached, I assumed that the size would be increased at a more "as needed" basis. [EE]

  • utarray defines an "insert" operation that takes an array, an element to be inserted, and an index of where you want to insert the element. utarray also defines "push" and "pop" operations to add an remove elements from the array, an initialization function, and a function to free the memory, among others. [ZW]

  • jtsiombI really like the 'pop' procedure given to retrieve the description stored within the last part of the array. It is basicly a queue procedure. [YZ]

  • The important function in the code is dynamic_array_realloc which takes the pointer to an array and a new capacity (proposed length of the array) as inputs. It performs a few checks using an if statement to see if the new capacity is reasonable after which it uses the realloc function to allocate more memory to the array. The other functions seems pretty standard. dynamic_array_set takes a pointer to an array, an index and a value and after performing a few checks, it updates the array.[AS]

  • One operation a client programmer may use to work with a dynamic array is freeDynArr, which takes the parameter of an array already existing and checks to see if the array is greater than 0, then to delete the entirety of it so that the memory can be freed. While this is a simple operation, I believe this is an excellent variant from the other operations indicated in this section that seem to only delete one element in the array. [AHD]

Comments on Implementations of Expandable Arrays

What did you learn from reading the code?

  • This library basically uses realloc when a user wants to add more data to the array (see: vec.c -> vec_expand_). An interesting thing to note is that the core functionality for a dynamic array here is served by a couple of functions. The rest (swapping, searching, sorting etc.) are applied the same way as they would be on a regular, fixed-size array. Also, the vector itself is a struct, containing two fields - data and length, which is pretty neat way to keep track of the size as it avoids using a function call for checking on the length size. [SZ]

  • kvec also uses realloc when the user tries to add space to their array. I'm a bit confused on why realloc is being used over malloc, but I assume it is to be more efficient so that old memory can be recycled rather than new memory being allocated. Another thing I learned is that when copying an array, memcpy is used, which is a function I was unaware of. It is used in this way: memcpy((v1).a, (v0).a, sizeof(type) * (v0).n); where v0 and v1 are the arrays, a is the memory address of the vector, and type is what the original array holds. [NK] [ditto on the memcpy EF]

  • As mentioned by SZ and NK above, realloc was also used in the function, insertArray, when an item exceeds the size of the array. realloc can resize the memory block pointed to by a pointer that was called by malloc or calloc, as the example Adding dynamic array example did when initializing a beginning array. I consulted realloc for its definition. [ZC]

  • My code similarly uses realloc rather than the more recognizable (to me at least) malloc, though only when the size of the array is changed. When the array is initially created malloc is still used. I'm not familiar with realloc, but I'm guessing it might be a better option when handling data structures that already have memory slots allocated to it. [HB]

  • I learnt from my implementation (and other implementations i saw) that in most cases, authors prefer to form a new 'data type' mainly by using a ‘struct' to hold all the relevant data that describes the expendable array. These 'type definitions' helps the client to envision the arraylist (expandable array) as some particular type of data and hence makes it easier for the client programmer to use. Also despite the varying nature of the operations used, it seemed to me that what was most important were the operations to create the ‘expandable array’ and also the operations to expand the array in my case ‘ArrayList_realloc’.I have learnt that from my implementation that the author was probably trying to write exactly a ‘C’ version of the java type ‘ArrayList’.[AOA]

  • As mentioned several times above, the Expandable array implementation that I found uses the realloc command to expand the array when needed. I had no idea what realloc did, but the fact that it expands the memory block pointed to makes sense for the context. Also, it is interesting to me that expandable arrays seem to do away with the array insertion that we were used to in 161 (e.g. like array[1] = 3) in favor of using an insertion function. This seems like it would be easier to consistently maintain the array, but may make it more confusing to use array algorithms that require the index to be used. [PS] [ditto LG]

  • Similarly to some of those who posted above, a lot of what I learnt was related to new datatypes and methods that I did not know existed in C before. For instance, when I was looking through the array_newcap method, I learnt that memmove is a method which takes a starting location, ending location and length, and copies length bytes from the starting location to the ending location (http://stackoverflow.com/questions/4415910/memcpy-vs-memmove). Additionally, I found out that, as in c#, one can use the conditional operator (?:) to speed up the writing of if statements. [WR]

  • As mentioned many times above, the project I found uses realloc to resize the array. malloc is used for the initial allocation of space for the array, so it makes sense that realloc would be used since it is just resizing memory blocks initially allocated with a call to malloc. [NS][ditto HZ][ditto AS]

  • As mentioned by almost everyone above, I learned about using realloc to implement expandable arrays. It is interesting to consider how often an array is resized in different implementations. In the project I looked at, the array size was doubled each time it was resized, decreasing the frequency at which it would need to be resized compared to the frequency for, say, an implementation in which the array size increased by a constant each time it was resized. [CM]

  • Differing from everyone else, realloc was not used in the project I was looking at. malloc is used to make everything, and recursive procedures are called to implement the expandable part of the array and moving it from one "subtree" to another. [AK]

  • Like everyone else, my project used malloc, realloc and calloc. It makes sense to use realloc; the purpose of expanding the size of the array is re-allocating memory to a pointer that already has memory allocated to it and making that allocation larger in size. [CMV]

  • YET ANOTHER PROJECT THAT USES realloc, vector uses it to expand it's array as necessary, for the reasons stated above, reallocating memory to allow for new slots in the array. The author wonders if it's "morally correct", because the behavior in vector_resize is if realloc returns NULL, then the program destroys the vector that was to be resized, and prints an error. Honestly, I think this behavior is pretty weird and nonstandard. [CG]

  • utarray does use realloc in its reserve function (which is then used when pushing or inserting elements.) Some utarray functions used C functions I've never seen before and don't quite understand: memset and memmove. I feel like this implementation is more maximalist than minimalist as it allows users to work with many types of data, and has many functions (pop, push, insert, reserve, length, resize, sort, etc.). However, this makes it more complicated than other programs and (at least for me) more difficult to understand. [ZW]

  • The project, as per the design, used the minimalist approach and also abstracted the implementations making it much easier to read. To talk of how it implements the "dynamic array", I think "dynamism" of the array implemented in the project I analyzed rests on the realloc function. My thoughts on realloc, of course, can be related to several sentiments shared by others who came across the function in their work. Narrowing down, for thought on realloc [ditto NK] [LAB]

  • Similarly to much of the class, the project that I found used realloc. It also used calloc but did not use malloc. Aside from the operation dynamicArray_fitIndex the operations have very similar implementations to their possible counterparts in normal arrays. [TP]

  • It is really hard to read where and when the memory is being accessed and allocated. I viewed a couple codes and some of them had a memory set for the next expansion of an array, but others waited until it was necessary. What is more efficient? [YK]

  • Like most of the students in class the code I looked at used malloc for initialization of the array and then used realloc to expand. The only thing interesting in the code was the usage of custom error messages which I think would help narrow any errors encountered when using malloc and realloc. [AS]

  • The project I read was simple and easy to read, so I was familiar with many of the operations implemented. One thing that I took out of this project though was the concept of maximalist vs. minimalist design, where the user implemented very similar operations, although with slight differences. For example, John Zeller wrote two delete operations called freeDynArr and deleteDynArr, where in one case, the size of the array had been checked and the size and capacity of the array had been set to zero, whereas in the the other, memory had be deallocated and freed. Which operation is better? Although I am not 100% sure, I believe that the second case would be more appropriate for arrays that will always have elements while the first might be more appropriate in a setting where the client programmer may want to test if the array even has elements within. [AHD]

  • The project I looked at had an incredibly sparse implementation, it only allowed the user to initialize, add to, and free an array. I agree with the other commenters as to the use of realloc, which must have a more efficient use, although I read in 213 reading that we must free that data up again at some point. This simple, easy to understand implementation fails to have the procedures that most others would, but for the project it is exactly what is needed. I guess I learned that if you don't need it at all don't put it in. Also what I mentioned in the second response on the doubling the size when the limit is reached.

Collaboration

If you talked to other people, please acknowledge them here. Initials suffice.

[SR edited SZ's contributions (although without SZ's permission)]