ArrayLists in C


/ Published in: C
Save to your folder(s)

includes files:
arraylist.c
arraylist.h


Copy this code and paste it in your HTML
  1. arraylist.c
  2. ============
  3. /* gok-predictor.c
  4. *
  5. * Copyright 2002 Sun Microsystems, Inc.,
  6. * Copyright 2002 University Of Toronto
  7. *
  8. * This library is free software; you can redistribute it and/or
  9. * modify it under the terms of the GNU Library General Public
  10. * License as published by the Free Software Foundation; either
  11. * version 2 of the License, or (at your option) any later version.
  12. *
  13. * This library is distributed in the hope that it will be useful,
  14. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16. * Library General Public License for more details.
  17. *
  18. * You should have received a copy of the GNU Library General Public
  19. * License along with this library; if not, write to the
  20. * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  21. * Boston, MA 02111-1307, USA.
  22. */
  23.  
  24. #include <string.h>
  25. #include "arraylist.h"
  26.  
  27. /*
  28.   constants
  29. */
  30. #define ARRAYLIST_INITIAL_CAPACITY 10
  31. #define ARRAYLIST_CAPACITY_DELTA 10
  32.  
  33. static const size_t object_size = sizeof(Object);
  34.  
  35.  
  36. /*
  37.   structures
  38. */
  39. struct Arraylist_Struct {
  40. int _current_capacity;
  41. Object *_data;
  42. int _size;
  43. const Boolean (*_equals)();
  44. };
  45.  
  46.  
  47. /*
  48.   private function declarations
  49. */
  50. static void *checked_malloc(const size_t size);
  51.  
  52.  
  53. void arraylist_free(const Arraylist list)
  54. {
  55. free(list->_data);
  56. free(list);
  57. }
  58.  
  59. Arraylist arraylist_create(const Boolean (*equals)(const Object object_1, const Object object_2))
  60. {
  61. Arraylist list;
  62.  
  63. #ifdef GOK_DEBUG
  64. list = malloc(sizeof(struct Arraylist_Struct));
  65. #else
  66. list = checked_malloc(sizeof(struct Arraylist_Struct));
  67. #endif
  68. list->_current_capacity = ARRAYLIST_INITIAL_CAPACITY;
  69. #ifdef GOK_DEBUG
  70. list->_data = malloc(object_size * list->_current_capacity);
  71. #else
  72. list->_data = checked_malloc(object_size * list->_current_capacity);
  73. #endif
  74. list->_size = 0;
  75. list->_equals = equals;
  76.  
  77. return list;
  78. }
  79.  
  80. Boolean arraylist_add(const Arraylist list, Object object)
  81. {
  82. int old_size = arraylist_size(list);
  83. int new_capacity;
  84. Object *new_data;
  85.  
  86. (list->_size)++;
  87. if (old_size == list->_current_capacity)
  88. {
  89. new_capacity = list->_current_capacity + ARRAYLIST_CAPACITY_DELTA;
  90. #ifdef GOK_DEBUG
  91. new_data = malloc(object_size * new_capacity);
  92. #else
  93. new_data = checked_malloc(object_size * new_capacity);
  94. #endif
  95. memcpy(new_data, list->_data, object_size * old_size);
  96. free(list->_data);
  97. (list->_data) = new_data;
  98. list->_current_capacity = new_capacity;
  99. }
  100. (list->_data)[old_size] = object;
  101. return TRUE;
  102. }
  103.  
  104. Boolean arraylist_remove(const Arraylist list, const Object object)
  105. {
  106. int length = arraylist_size(list);
  107. int last_index = length - 1;
  108. int new_size, new_capacity;
  109. int index;
  110.  
  111. for (index = 0; index < length; index++)
  112. {
  113. if ((*list->_equals)(arraylist_get(list, index), object))
  114. {
  115. (list->_size)--;
  116. if (index < last_index)
  117. {
  118. memmove(list->_data + index, list->_data + index + 1, object_size * (last_index - index));
  119. new_size = list->_size;
  120. new_capacity = list->_current_capacity - ARRAYLIST_CAPACITY_DELTA;
  121. if (new_capacity > new_size)
  122. {
  123. list->_data = realloc(list->_data, object_size * new_capacity);
  124. list->_current_capacity = new_capacity;
  125. }
  126. }
  127. return TRUE;
  128. }
  129. }
  130. return FALSE;
  131. }
  132.  
  133. Boolean arraylist_contains(const Arraylist list, const Object object)
  134. {
  135. return (arraylist_index_of(list, object) > -1);
  136. }
  137.  
  138. int arraylist_index_of(const Arraylist list, const Object object)
  139. {
  140. int length = arraylist_size(list);
  141. int index;
  142.  
  143. for (index = 0; index < length; index++)
  144. {
  145. if ((*list->_equals)(arraylist_get(list, index), object))
  146. {
  147. return index;
  148. }
  149. }
  150. return -1;
  151. }
  152.  
  153. Boolean arraylist_is_empty(const Arraylist list)
  154. {
  155. return (0 == arraylist_size(list));
  156. }
  157.  
  158. int arraylist_size(const Arraylist list)
  159. {
  160. return list->_size;
  161. }
  162.  
  163. Object arraylist_get(const Arraylist list, const int index)
  164. {
  165. return list->_data[index];
  166. }
  167.  
  168. void arraylist_clear(const Arraylist list)
  169. {
  170. list->_data = realloc(list->_data, object_size * ARRAYLIST_INITIAL_CAPACITY);
  171. list->_current_capacity = ARRAYLIST_INITIAL_CAPACITY;
  172. list->_size = 0;
  173. }
  174.  
  175. void arraylist_sort(const Arraylist list, const int (*compare)(const Object object_1, const Object object_2))
  176. {
  177. qsort(list->_data,
  178. arraylist_size(list),
  179. sizeof(Object),
  180. (int (*)())compare);
  181. }
  182.  
  183. static void *checked_malloc(const size_t size)
  184. {
  185. void *data;
  186.  
  187. data = malloc(size);
  188. if (data == NULL)
  189. {
  190. fprintf(stderr, "\nOut of memory.\n");
  191. fflush(stderr);
  192. exit(EXIT_FAILURE);
  193. }
  194.  
  195. return data;
  196. }
  197.  
  198.  
  199. arraylist.h
  200. =============
  201. /* gok-predictor.h
  202. *
  203. * Copyright 2002 Sun Microsystems, Inc.,
  204. * Copyright 2002 University Of Toronto
  205. *
  206. * This library is free software; you can redistribute it and/or
  207. * modify it under the terms of the GNU Library General Public
  208. * License as published by the Free Software Foundation; either
  209. * version 2 of the License, or (at your option) any later version.
  210. *
  211. * This library is distributed in the hope that it will be useful,
  212. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  213. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  214. * Library General Public License for more details.
  215. *
  216. * You should have received a copy of the GNU Library General Public
  217. * License along with this library; if not, write to the
  218. * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  219. * Boston, MA 02111-1307, USA.
  220. */
  221.  
  222. #ifndef __defined_arraylist_h
  223. #define __defined_arraylist_h
  224.  
  225. #include <stdlib.h>
  226. #include <stdio.h>
  227.  
  228.  
  229. /*
  230.   constants
  231. */
  232. #undef TRUE
  233. #define TRUE 1
  234.  
  235. #undef FALSE
  236. #define FALSE 0
  237.  
  238.  
  239. /*
  240.   type definitions
  241. */
  242. #undef Boolean
  243. #define Boolean short unsigned int
  244.  
  245. #undef Object
  246. #define Object void*
  247.  
  248. typedef struct Arraylist_Struct *Arraylist;
  249.  
  250.  
  251. /*
  252.   function declarations
  253. */
  254. void arraylist_free(const Arraylist list);
  255. Arraylist arraylist_create(const Boolean (*equals)(const Object object_1, const Object object_2));
  256. Boolean arraylist_add(const Arraylist list, Object object);
  257. Boolean arraylist_remove(const Arraylist list, const Object object);
  258. Boolean arraylist_contains(const Arraylist list, const Object object);
  259. int arraylist_index_of(const Arraylist list, const Object object);
  260. Boolean arraylist_is_empty(const Arraylist list);
  261. int arraylist_size(const Arraylist list);
  262. Object arraylist_get(const Arraylist list, const int index);
  263. void arraylist_clear(const Arraylist list);
  264. void arraylist_sort(const Arraylist list, const int (*compare)(const Object object_1, const Object object_2));
  265.  
  266.  
  267. #endif /* __defined_arraylist_h */

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.