//
// array.h - CKit
//
// (c) 2009 TJ Holowaychuk <tj@vision-media.ca> (MIT Licensed)
//
#ifndef __CKIT_ARRAY__
#define __CKIT_ARRAY__
#include "ckit.h"
#define CKIT_ARRAY(N, T) CKIT_ARRAY_INIT(N, T, free)
#define CKIT_ARRAY_INIT(N, T, F) \
\
typedef struct { \
int len, max; \
T *vals; \
} N; \
\
/* \
* Allocate new N. \
* \
* @api public \
*/ \
\
N * \
N##_new() { \
N *self = (N *) CKIT_MALLOC(sizeof(N)); \
self->len = 0, self->max = 0; \
self->vals = NULL; \
return self; \
} \
\
/* \
* Push _val_ onto _self_. \
* \
* @api public \
*/ \
\
N * \
N##_push(N *self, T val) { \
if (self->len == self->max) \
self->max = self->max ? self->max << 1 : 2, \
self->vals = (T *) CKIT_REALLOC(self->vals, self->max * sizeof(T)); \
self->vals[self->len++] = val; \
return self; \
} \
\
/* \
* Slice _self_ at _beg_ to _len_. \
* \
* Array_slice(array, 0, 3); \
* Array_slice(array, 5, 10); \
* Array_slice(array, 1, -1); \
* Array_slice(array, -5, -1); \
* \
* @api public \
*/ \
\
N * \
N##_slice(N *self, register int beg, register int len) { \
N *slice = N##_new(); \
if (beg < 0) beg = self->len + 1 -(-beg+1); \
if (len < 0) len = self->len + 2 -(-len+1); \
if (beg < 0) beg = 0; \
if (len < 0) len = 1; \
if (self->len && len != 0) \
for (; len > 0 && beg < self->len; --len, ++beg) \
if (self->vals[beg]) \
N##_push(slice, self->vals[beg]); \
return slice; \
} \
\
/* \
* Return elements after _i_. \
* \
* @api public \
*/ \
\
N * \
N##_from(N *self, const int i) { \
return N##_slice(self, i, -1); \
} \
\
/* \
* Return elements upto _i_. \
* \
* @api public \
*/ \
\
N * \
N##_to(N *self, int i) { \
return N##_slice(self, 0, ++i); \
} \
\
/* \
* Return last _n_ elements. \
* \
* @api public \
*/ \
\
N * \
N##_last_n(N *self, int n) { \
return N##_slice(self, -n, n); \
} \
\
/* \
* Select from _self_ with _callback_. Returns \
* a new array of values which evaluate to 1. \
* \
* @api public \
*/ \
\
N * \
N##_select(N *self, int (* callback)()) { \
N *selected = N##_new(); \
for (int i = 0; i < self->len; ++i) \
if (callback(i, self->vals[i])) \
N##_push(selected, self->vals[i]); \
return selected; \
} \
\
/* \
* Map _self_ with _callback_. Returns a new array \
* of mapped values. \
* \
* @api public \
*/ \
\
N * \
N##_map(N *self, void *(* callback)()) { \
N *map = N##_new(); \
for (int i = 0; i < self->len; ++i) \
N##_push(map, callback(i, self->vals[i])); \
return map; \
} \
\
/* \
* Find an element in _self_ using _callback_. When _callback_ \
* evaluates to 1, the value will be returned, otherwise NULL. \
* \
* @api public \
*/ \
\
T \
N##_find(N *self, int (* callback)()) { \
for (int i = 0; i < self->len; ++i) \
if (callback(i, self->vals[i])) \
return self->vals[i]; \
return NULL; \
} \
\
/* \
* Check if an element in _self_ will evaluate to 1 \
* when passed to _callback_. \
* \
* @api public \
* @see Array_find() \
*/ \
\
int \
N##_any(N *self, int (* callback)()) { \
return !! N##_find(self, callback); \
} \
\
/* \
* Return the last element in _self_. \
* \
* @api public \
*/ \
\
T \
N##_last(N *self) { \
return self->vals[self->len - 1]; \
} \
\
/* \
* Pop an element off the end of _self_'s stack. \
* \
* @api public \
*/ \
\
T \
N##_pop(N *self) { \
return self->len ? \
self->vals[--self->len] : \
NULL; \
} \
\
/* \
* Merge _self_ with _other_ array. \
* \
* @api public \
*/ \
\
N * \
N##_merge(N *self, N *other) { \
for (int i = 0; i < other->len; ++i) \
N##_push(self, other->vals[i]); \
return self; \
} \
\
/* \
* Unshift _val_ onto _self_'s stack, prepending it. \
* \
* @api public \
*/ \
\
N * \
N##_unshift(N *self, T val) { \
*self = *N##_merge(N##_push(N##_new(), val), self); \
return self; \
} \
\
/* \
* Delete element at index _i_ from _self_. \
* \
* @api public \
*/ \
\
T \
N##_delete_at(N *self, int i) { \
register int len = self->len; \
if (i > -1 && i < len) { \
--self->len; \
T val = self->vals[i]; \
for (int j = i + 1; j < len; ++j, ++i) \
self->vals[i] = self->vals[j]; \
return val; \
} \
return NULL; \
} \
\
/* \
* Remove duplicate values from _self_ using _callback_ for comparison. \
* \
* Array_unique(array, strcmp); \
* \
* @api public \
*/ \
\
N * \
N##_unique(N *self, int (* callback)()) { \
for (int i = 0; i < self->len; ++i) \
for (int j = 0; j < self->len; ++j) \
if (i != j && callback(self->vals[i], self->vals[j]) == 0) \
N##_delete_at(self, i); \
return self; \
} \
\
/* \
* Sort _self_ with comparison _callback_. \
* \
* static int \
* compare_string(void *p1, void *p2) { \
* return strcmp(* (char * const *) p1, * (char * const *) p2); \
* } \
* \
* Array_sort(array, compare_string); \
* \
* @api public \
*/ \
\
N * \
N##_sort(N *self, int (* callback)(const void *, const void *)) { \
qsort(self->vals, self->len - 1, sizeof(T), callback); \
return self; \
} \
\
/* \
* Create a union of _self_ and _other_ array. Merging \
* and removing duplicates using _callback_ for comparison. \
* \
* @api public \
*/ \
\
N * \
N##_union(N *self, N *other, int (* callback)()) { \
return N##_unique(N##_merge(self, other), callback); \
} \
\
/* \
* Shift an element off the beginning of _self_'s stack. \
* \
* @api public \
*/ \
\
T \
N##_shift(N *self) { \
return N##_delete_at(self, 0); \
} \
\
/* \
* Destroy _self_. \
* \
* @api public \
*/ \
\
void \
N##_destroy(N *self) { \
for (int i = 0; i < self->len; ++i) \
F(self->vals[i]); \
if (self) free(self); \
}
#endif
Refactorings
No refactoring yet !
Ants
October 19, 2009, October 19, 2009 03:34, permalink
Your usage of the idiom:
for(int i = 0; i < self->len; ++i) doWork();
seems to indicate that you are actually writing 'C++' code rather than standard ANSI 'C'.
This raises the question: why not simple use STL instead of rolling your own?
Tj Holowaychuk
October 19, 2009, October 19, 2009 15:16, permalink
I dont know any C++ (well a tiny bit). that is ansi c99 no?
Ants
October 19, 2009, October 19, 2009 21:02, permalink
Ah, good point about C99. I've got a lame compiler that only implements a small subset of C99 features, and mixing code and declarations in not one of them. :-(
Tj Holowaychuk
October 19, 2009, October 19, 2009 21:17, permalink
ah lame. as far as i know this is the only exception
Ants
October 23, 2009, October 23, 2009 08:14, permalink
Yeah, since I've got a lame compiler, I'll just give you a set of comments about the code. (I really should take time to download a real modern C compiler like gcc, or the Intel C compiler.)
Maybe the gcc compiler is smarter than the VS compiler, but won't the code below be broken when I try to build because all the CarArray_* functions will be defined both in CarArray.c and main.c? Shouldn't you have two macros instead: CKIT_ARRAY_DECLARE() that just declares the functions in CarArray.h, and CKIT_ARRAY_IMPLEMENT() that actually implements the functions in CarArray.c?
Anyway other comments about the macros:
- N##_new() and N##_push() don't check for failed CKIT_MALLOC() or CKIT_REALLOC(), respectively.
- For consistency, there should be CKIT_FREE macro defined.
- N##_delete() calls F(self->vals[i]), but each of the self->vals[i] items were not allocated.
- N##_delete() should call CKIT_FREE(self->vals) to delete the value array before calling CKIT_FREE(self).
- If the individual self->vals[i] items were meant to be allocated, then CKIT_ARRAY_INIT() should take an M parameter that is paired with the F parameter. (M == malloc and F == free by default for simple arrays.)
- If the individual self->vals[i] times were meant to be allocated, N##_push() should use sizeof(T*) rather than sizeof(T).
- If the individual self->vals[i] times were meant to be allocated, N##_push() should do the following on line 46:
self->vals[self->len] = M(sizeof(T))
if (!self->vals[self->len)
abort();
*self->vals[self->len++] = val;
- If the individual self->vals[i] times were meant to be allocated, N##_delete_at() and N##_pop() should use F() on the self->vals[i] item being deleted.
- There doesn't seem to be a N##_compact() that frees up the excess allocated items. Imagine quickly adding 1000 items, and then popping the first 900. You'll be sitting around with an array that is occupying space for 1024 items, but you are only using 100 items.
- N##_last() returns the last item in the array, but there is no corresponding N##_first() or N##_get_at() to return the first item, or the i-th item. Right now it looks like the only way to get the i-th item is to use N##_delete_at().
- In various places, your comments say "when _callback_ evaluates to 1", but the code actually performs the action on non-zero.
- In most places where you take a callback parameter, you should put in the parameter types for the callback function so that compiler can give you warnings about mismatched types for parameters.
- N##_sort(), you actually specified the parameters for the callback, but it would have been better to actually specify that the parameters were const T *, rather than const void *, then if needed, do a cast inside the function to the type that qsort() really wants. Let the compiler help you find potential errors.
- N##_map() takes a callback that returns a void *. Shouldn't it return T?
#ifndef __Car_h__
#define __Car_h__
typedef struct
{
char Make[128];
char Model[128];
int Year;
} Car;
#endif // __Car_h__
#ifndef __CarArray_h__ #define __CarArray_h__ #include "array.h" #include "car.h" CKIT_ARRAY(CarArray, Car *) // Various callbacks for CarArray and Car: int CarArray_Sort_Ascending_Callback(const Car * carA, const Car * carB); int CarArray_Sort_Descending_Callback(const Car * carA, const Car * carB); int CarArray_Compare(const Car * carA, const Car * carB); #endif // __Car_h__
#include "CarArray.h"
int CarArray_Sort_Ascending_Callback(const Car * carA, const Car * carB)
{
return CarArray_Compare(carA, carB);
}
int CarArray_Sort_Descending_Callback(const Car * carA, const Car * carB)
{
return - CarArray_Compare(carA, carB);
}
int CarArray_Compare(const Car * carA, const Car * carB);
{
// TODO: Compare cars
}
#include "CarArray.h"
im no c pro. may be some memory management issues. from my project "CKit" at http://github.com/visionmedia/ckit