diff options
| -rw-r--r-- | EXAMPLE.md | 53 | ||||
| -rw-r--r-- | stc/cdefs.h | 2 | ||||
| -rw-r--r-- | stc/cmap.h | 21 | ||||
| -rw-r--r-- | stc/cstring.h | 6 | ||||
| -rw-r--r-- | stc/cvector.h | 9 |
5 files changed, 62 insertions, 29 deletions
@@ -29,46 +29,69 @@ void person_destroy(struct Person* p) { cstring_destroy(&p->surname);
}
-int person_compare(struct Person* x, struct Person* y) {
+
+```
+In order to use it as a CMap key, provide a "view" of your class, that owns no resources (e.g. CStrings):
+```
+struct PersonView
+{
+ const char* name;
+ const char* surname;
+ int age;
+};
+struct PersonView person_getView(struct Person* p) {
+ return (struct PersonView) {p->name.str, p->surname.str, p->age};
+}
+struct Person person_fromView(struct PersonView pv) {
+ return (struct Person) {cstring_make(pv.name), cstring_make(pv.surname), pv.age};
+}
+int personview_compare(const struct PersonView* x, const struct PersonView* y) {
int c;
- c = strcmp(x->name.str, y->name.str); if (c != 0) return c;
- c = strcmp(x->surname.str, y->surname.str); if (c != 0) return c;
+ c = strcmp(x->name, y->name); if (c != 0) return c;
+ c = strcmp(x->surname, y->surname); if (c != 0) return c;
return memcmp(&x->age, &y->age, sizeof(x->age));
}
```
Here is a simple hash function that combines the three member's hashes:
```
-size_t person_hash(const struct Person* p, size_t ignore) {
+size_t personview_hash(const struct PersonView* pv, size_t ignore) {
// Compute individual hash values for name, surname and age
// http://stackoverflow.com/a/1646913/126995
size_t res = 17;
- res = res * 31 + c_defaultHash(p->name.str, cstring_size(p->name));
- res = res * 31 + c_defaultHash(p->surname.str, cstring_size(p->surname));
- res = res * 31 + c_defaultHash(&p->age, sizeof(p->age));
+ res = res * 31 + c_defaultHash(pv->name, strlen(pv->name));
+ res = res * 31 + c_defaultHash(pv->surname, strlen(pv->surname));
+ res = res * 31 + c_defaultHash(&pv->age, sizeof(pv->age));
return res;
}
```
-With this in place, you can instantiate a CMap with Person => CString:
+With this in place, we can declare a CMap with Person => CString:
```
-#include <stc/CMap.h>
-declare_CMap(ex, struct Person, CString, cstring_destroy, person_hash, person_compare, person_destroy);
+#include <stdio.h>
+#include "stc/CMap.h"
+declare_CMap(ex, struct Person, CString, cstring_destroy,
+ personview_hash, personview_compare, person_destroy,
+ struct PersonView, person_getView, person_fromView);
+```
+Note we use struct PersonView to put keys in the map, but is stored as struct Person.
+````
int main()
{
CMap_ex m6 = cmap_ex_init;
- cmap_ex_put(&m6, person_make("John", "Doe", 12), cstring_make("example"));
- cmap_ex_put(&m6, person_make("Mary", "Sue", 21), cstring_make("another"));
- // ...
+ cmap_ex_put(&m6, (struct PersonView){"John", "Doe", 24}, cstring_make("dead"));
+ cmap_ex_put(&m6, (struct PersonView){"Jane", "Doe", 21}, cstring_make("another"));
+ cmap_ex_put(&m6, (struct PersonView){"John", "Travolta", 66}, cstring_make("actor"));
+
c_foreach (it, cmap_ex, m6) {
if (cstring_equals(it.item->key.name, "John"))
printf("%s %s %d -> %s\n", it.item->key.name.str, it.item->key.surname.str, it.item->key.age,
it.item->value.str);
}
-
+
cmap_ex_destroy(&m6);
}
```
-It will automatically use person_hash() as defined above for the hash value calculations, and the person_compare() for equality checks.
+CMap will automatically use personview_hash() as defined above for the hash value calculations, and the personview_compare() for equality checks.
The cmap_ex_destroy() function will free CStrings name, surname and the value for each item in the map, in addition to the CMap hash table itself.
diff --git a/stc/cdefs.h b/stc/cdefs.h index 3aa8136e..b201dd59 100644 --- a/stc/cdefs.h +++ b/stc/cdefs.h @@ -47,7 +47,7 @@ #define c_swap(T, x, y) { T __t = x; x = y; y = __t; }
#define c_defaultInitRaw(x) (x)
-#define c_defaultGetRaw(x) (x)
+#define c_defaultGetRaw(ptr) (*(ptr))
#define c_noCompare(x, y) 0
#define c_defaultCompare(x, y) (*(x) == *(y) ? 0 : *(x) < *(y) ? -1 : 1)
#define c_defaultEquals(x, y) (memcmp(x, y, sizeof(*(y))) == 0)
@@ -140,12 +140,13 @@ cmap_##tag##_setShrinkLimitFactor(CMap_##tag* self, double limit) { \ } \
\
static inline size_t \
-cmap_##tag##_bucket(CMap_##tag* self, cmap_##tag##_rawkey_t* const rawKey, uint32_t* hxPtr) { \
- uint32_t hash = keyHashRaw(rawKey, sizeof(cmap_##tag##_rawkey_t)), hx = (hash & cmapentry_HASH) | cmapentry_USED; \
+cmap_##tag##_bucket(CMap_##tag* self, cmap_##tag##_rawkey_t* const rawKeyPtr, uint32_t* hxPtr) { \
+ uint32_t hash = keyHashRaw(rawKeyPtr, sizeof(cmap_##tag##_rawkey_t)), hx = (hash & cmapentry_HASH) | cmapentry_USED; \
size_t cap = cvector_capacity(self->_table); \
size_t idx = cmap_reduce(hash, cap); \
CMapEntry_##tag* slot = self->_table.data; \
- while (slot[idx].hashx && (slot[idx].hashx != hx || !keyEqualsRaw((RawKey* const) keyGetRaw(&slot[idx].key), rawKey))) { \
+ cmap_##tag##_rawkey_t r; \
+ while (slot[idx].hashx && (slot[idx].hashx != hx || !keyEqualsRaw((r = keyGetRaw(&slot[idx].key), &r), rawKeyPtr))) { \
if (++idx == cap) idx = 0; \
} \
*hxPtr = hx; \
@@ -183,12 +184,13 @@ cmap_##tag##_put(CMap_##tag* self, cmap_##tag##_rawkey_t rawKey, Value value) { e->value = value; \
return e; \
} \
-/* \
+ \
static inline CMapEntry_##tag* \
cmap_##tag##_insert(CMap_##tag* self, CMapEntry_##tag entry) { \
cmap_##tag##_expand(self); \
uint32_t hx; \
- size_t idx = cmap_##tag##_bucket(self, (RawKey* const) keyGetRaw(&entry.key), &hx); \
+ cmap_##tag##_rawkey_t r = keyGetRaw(&entry.key); \
+ size_t idx = cmap_##tag##_bucket(self, &r, &hx); \
CMapEntry_##tag* e = &self->_table.data[idx]; \
if (e->hashx) \
valueDestroy(&e->value); \
@@ -200,7 +202,7 @@ cmap_##tag##_insert(CMap_##tag* self, CMapEntry_##tag entry) { \ e->value = entry.value; \
return e; \
} \
-*/ \
+ \
static inline size_t \
cmap_##tag##_reserve(CMap_##tag* self, size_t size) { \
size_t oldcap = cvector_capacity(self->_table), newcap = 1 + (size / 2) * 2; \
@@ -212,9 +214,10 @@ cmap_##tag##_reserve(CMap_##tag* self, size_t size) { \ \
CMapEntry_##tag* e = vec.data, *slot = self->_table.data; \
uint32_t hx; \
+ cmap_##tag##_rawkey_t r; \
for (size_t i = 0; i < oldcap; ++i, ++e) \
if (e->hashx) \
- slot[ cmap_##tag##_bucket(self, (RawKey* const) keyGetRaw(&e->key), &hx) ] = *e; \
+ slot[ cmap_##tag##_bucket(self, (r = keyGetRaw(&e->key), &r), &hx) ] = *e; \
free(_cvector_alloced(vec.data)); /* not cvector_destroy() here */ \
return newcap; \
} \
@@ -231,11 +234,13 @@ cmap_##tag##_erase(CMap_##tag* self, cmap_##tag##_rawkey_t rawKey) { \ CMapEntry_##tag* slot = self->_table.data; \
if (! slot[i].hashx) \
return false; \
+ cmap_##tag##_rawkey_t r; \
do { /* deletion from hash table without tombstone */ \
if (++j == cap) j = 0; /* j %= cap; is slow */ \
if (! slot[j].hashx) \
break; \
- k = cmap_reduce(keyHashRaw((RawKey* const) keyGetRaw(&slot[j].key), sizeof(cmap_##tag##_rawkey_t)), cap); \
+ k = cmap_reduce(keyHashRaw((r = keyGetRaw(&slot[j].key), &r), \
+ sizeof(cmap_##tag##_rawkey_t)), cap); \
if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \
slot[i] = slot[j], i = j; \
} while (true); \
diff --git a/stc/cstring.h b/stc/cstring.h index 454ff48c..99ab4e81 100644 --- a/stc/cstring.h +++ b/stc/cstring.h @@ -293,9 +293,11 @@ cstring_temp(const char* str) { /* CVector / CMap API functions: */
-#define cstring_getRaw(x) (&(x)->str)
+#define cstring_getRaw(x) ((x)->str)
#define cstring_compareRaw(x, y) strcmp(*(x), *(y))
#define cstring_equalsRaw(x, y) (strcmp(*(x), *(y)) == 0)
-static inline uint32_t cstring_hashRaw(const char* const* str, size_t ignored) { return c_defaultHash(*str, strlen(*str)); }
+static inline uint32_t cstring_hashRaw(const char* const* sPtr, size_t ignored) {
+ return c_defaultHash(*sPtr, strlen(*sPtr));
+}
#endif
diff --git a/stc/cvector.h b/stc/cvector.h index 069a335e..4bbc55cf 100644 --- a/stc/cvector.h +++ b/stc/cvector.h @@ -47,7 +47,7 @@ extern void qsort(void *base, size_t nitems, size_t size, int (*compar)(const vo #define declare_CVector_6(tag, Value, valueDestroy, valueCompare, ValueRaw, valueGetRaw) \
- \
+typedef ValueRaw cvector_##tag##_rawvalue_t; \
typedef struct CVector_##tag { \
Value* data; \
} CVector_##tag; \
@@ -118,7 +118,9 @@ cvector_##tag##_erase(CVector_##tag* self, size_t pos, size_t size) { \ \
static inline int \
cvector_##tag##_sortCompare(const void* x, const void* y) { \
- return valueCompare(valueGetRaw((const Value *) x), valueGetRaw((const Value *) y)); \
+ cvector_##tag##_rawvalue_t rx = valueGetRaw((const Value *) x); \
+ cvector_##tag##_rawvalue_t ry = valueGetRaw((const Value *) y); \
+ return valueCompare(&rx, &ry); \
} \
\
static inline void \
@@ -130,8 +132,9 @@ cvector_##tag##_sort(CVector_##tag* self) { \ static inline size_t \
cvector_##tag##_find(CVector_##tag cv, ValueRaw rawValue) { \
size_t n = cvector_size(cv); \
+ cvector_##tag##_rawvalue_t r; \
for (size_t i = 0; i < n; ++i) { \
- if (valueCompare(valueGetRaw(&cv.data[i]), &rawValue) == 0) return i; \
+ if (valueCompare((r = valueGetRaw(&cv.data[i]), &r), &rawValue) == 0) return i; \
} \
return c_npos; \
} \
|