123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240 |
- extern "C" {
- struct name { \
- struct type *zip_root; \
- }
- struct { \
- struct type *zip_left; \
- struct type *zip_right; \
- unsigned char rank; \
- }
- void name
- void name
- struct type *name
- struct type *name
- struct type *name
- typedef void (*name
- void name
- enum ZIP_CMP {
- ZIP_CMP_LESS = -1,
- ZIP_CMP_EQ = 0,
- ZIP_CMP_MORE = 1
- };
- static __inline
- static inline
- unsigned char
- ZIP_FFS32(unsigned int v) {
- unsigned int t = 1;
- unsigned char r = 1;
- if(v == 0) return 0;
- while((v & t) == 0) {
- t = t << 1; r++;
- }
- return r;
- }
- static struct type * \
- __
- if(!root) { \
- ZIP_LEFT(elm, field) = NULL; \
- ZIP_RIGHT(elm, field) = NULL; \
- return elm; \
- } \
- if((cmp)(&(elm)->keyfield, &(root)->keyfield) == ZIP_CMP_LESS) { \
- if(__##name##_ZIP_INSERT(ZIP_LEFT(root, field), elm) == elm) { \
- if(ZIP_RANK(elm, field) < ZIP_RANK(root, field)) { \
- ZIP_LEFT(root, field) = elm; \
- } else { \
- ZIP_LEFT(root, field) = ZIP_RIGHT(elm, field); \
- ZIP_RIGHT(elm, field) = root; \
- return elm; \
- } \
- } \
- } else { \
- if(__##name##_ZIP_INSERT(ZIP_RIGHT(root, field), elm) == elm) { \
- if(ZIP_RANK(elm, field) <= ZIP_RANK(root, field)) { \
- ZIP_RIGHT(root, field) = elm; \
- } else { \
- ZIP_RIGHT(root, field) = ZIP_LEFT(elm, field); \
- ZIP_LEFT(elm, field) = root; \
- return elm; \
- } \
- } \
- } \
- return root; \
- } \
- \
- void \
- name##_ZIP_INSERT(struct name *head, struct type *elm, \
- unsigned char rank) { \
- ZIP_RANK(elm, field) = rank; \
- ZIP_ROOT(head) = __##name##_ZIP_INSERT(ZIP_ROOT(head), elm); \
- } \
- \
- static struct type * \
- __##name##ZIP(struct type *x, struct type *y) { \
- if(!x) return y; \
- if(!y) return x; \
- if(ZIP_RANK(x, field) < ZIP_RANK(y, field)) { \
- ZIP_LEFT(y, field) = __##name##ZIP(x, ZIP_LEFT(y, field)); \
- return y; \
- } \
- ZIP_RIGHT(x, field) = __##name##ZIP(ZIP_RIGHT(x, field), y); \
- return x; \
- } \
- \
- static struct type * \
- __##name##_ZIP_REMOVE(struct type *root, struct type *elm) { \
- if(root == elm) \
- return __##name##ZIP(ZIP_LEFT(root, field), \
- ZIP_RIGHT(root, field)); \
- enum ZIP_CMP eq = (cmp)(&(elm)->keyfield, &(root)->keyfield); \
- if(eq == ZIP_CMP_LESS) { \
- struct type *left = ZIP_LEFT(root, field); \
- if(elm == left) \
- ZIP_LEFT(root, field) = \
- __##name##ZIP(ZIP_LEFT(left, field), \
- ZIP_RIGHT(left, field)); \
- else \
- __##name##_ZIP_REMOVE(left, elm); \
- } else { \
- struct type *right = ZIP_RIGHT(root, field); \
- if(elm == right) \
- ZIP_RIGHT(root, field) = \
- __##name##ZIP(ZIP_LEFT(right, field), \
- ZIP_RIGHT(right, field)); \
- else \
- __##name##_ZIP_REMOVE(right, elm); \
- } \
- return root; \
- } \
- \
- void \
- name##_ZIP_REMOVE(struct name *head, struct type *elm) { \
- ZIP_ROOT(head) = __##name##_ZIP_REMOVE(ZIP_ROOT(head), elm); \
- } \
- \
- static struct type * \
- __##name##_ZIP_FIND(struct type *root, const keytype *key) { \
- if(!root) \
- return NULL; \
- enum ZIP_CMP eq = (cmp)(key, &(root)->keyfield); \
- if(eq == ZIP_CMP_EQ) { \
- return root; \
- } \
- if(eq == ZIP_CMP_LESS) { \
- return __##name##_ZIP_FIND(ZIP_LEFT(root, field), key); \
- } \
- return __##name##_ZIP_FIND(ZIP_RIGHT(root, field), key); \
- } \
- \
- struct type * \
- name##_ZIP_FIND(struct name *head, const keytype *key) { \
- return __##name##_ZIP_FIND(ZIP_ROOT(head), key); \
- } \
- \
- struct type * \
- name##_ZIP_MIN(struct name *head) { \
- struct type *cur = ZIP_ROOT(head); \
- if(!cur) return NULL; \
- while(ZIP_LEFT(cur, field)) { \
- cur = ZIP_LEFT(cur, field); \
- } \
- return cur; \
- } \
- \
- struct type * \
- name##_ZIP_MAX(struct name *head) { \
- struct type *cur = ZIP_ROOT(head); \
- if(!cur) return NULL; \
- while(ZIP_RIGHT(cur, field)) { \
- cur = ZIP_RIGHT(cur, field); \
- } \
- return cur; \
- } \
- \
- static void \
- __##name##_ZIP_ITER(struct type *elm, name##_cb cb, void *data) { \
- if(!elm) \
- return; \
- __##name##_ZIP_ITER(ZIP_LEFT(elm, field), cb, data); \
- __##name##_ZIP_ITER(ZIP_RIGHT(elm, field), cb, data); \
- cb(elm, data); \
- } \
- \
- void \
- name##_ZIP_ITER(struct name *head, name##_cb cb, void *data) { \
- __##name##_ZIP_ITER(ZIP_ROOT(head), cb, data); \
- }
- #ifdef __cplusplus
- } /* extern "C" */
- #endif
- #endif /* ZIPTREE_H_ */
|