123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725 |
- /*
- *
- * Copyright (c) 2011, Jue Ruan <ruanjue@gmail.com>
- *
- *
- * This program is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 3 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program. If not, see <http://www.gnu.org/licenses/>.
- */
-
- #ifndef __LIST_RJ_H
- #define __LIST_RJ_H
- #include <stdlib.h>
- #include <string.h>
- #include <stdint.h>
- #include <stdio.h>
- #include "sort.h"
- #include "mem_share.h"
- /**
- * Heap macros
- */
- //ary, size and cap must be explict variable, not expression
- #define array_heap_push(ary, size, cap, e_type, id, cmp_expr)\
- do { \
- e_type _pp_, _p_; \
- _p_ = (e_type)(id); \
- size_t i, j; \
- i = (size); \
- e_type a, b; \
- if((size_t)((size) + 1) > (size_t)(cap)){ \
- if((size_t)((size) + 1) < 0xFFFFFFFFU){ \
- (cap) = roundup_power2((size) + 1); \
- } else { \
- (cap) = (((size) + 1 + 0xFFFFFFFLLU - 1LLU) / 0xFFFFFFFLLU) * 0xFFFFFFFLLU; \
- } \
- (ary) = realloc((ary), sizeof(e_type) * (cap)); \
- if((ary) == NULL){ \
- fprintf(stderr, " -- Out of memory, try to allocate %llu bytes in %s, -- %s:%d --\n", (unsigned long long)(sizeof(e_type) * (cap)), __FUNCTION__, __FILE__, __LINE__); \
- print_backtrace(stderr, 20); \
- exit(1); \
- } \
- } \
- (ary)[(size)++] = _p_; \
- while(i){ \
- j = (i - 1) >> 1; \
- a = (ary)[i]; b = (ary)[j]; \
- if((cmp_expr) >= 0) break; \
- _pp_ = (ary)[i]; (ary)[i] = (ary)[j]; (ary)[j] = _pp_; \
- i = j; \
- } \
- } while(0)
- #define array_heap_remove(ary, len, cap, e_type, _idx, cmp_expr)\
- do { \
- e_type _pp_; \
- size_t swap, idx; \
- idx = (size_t)(_idx); \
- (ary)[idx] = (ary)[--(len)]; \
- e_type a, b; \
- while((size_t)((idx << 1) + 1) < (size_t)(len)){ \
- swap = idx; \
- a = (ary)[swap]; b = (ary)[(idx << 1) + 1]; \
- if((cmp_expr) > 0) swap = (idx << 1) + 1; \
- if(((idx << 1) + 2) < (size_t)(len)){ \
- a = (ary)[swap]; b = (ary)[(idx << 1) + 2]; \
- if((cmp_expr) > 0) swap = (idx << 1) + 2; \
- } \
- if(swap == idx) break; \
- _pp_ = (ary)[idx]; (ary)[idx] = (ary)[swap]; (ary)[swap] = _pp_; \
- idx = swap; \
- } \
- } while(0)
- #define array_heap_replace(ary, len, cap, e_type, _idx, _val, cmp_expr)\
- do { \
- e_type _pp_; \
- size_t swap, idx; \
- idx = (size_t)(_idx); \
- (ary)[idx] = _val; \
- e_type a, b; \
- while((size_t)((idx << 1) + 1) < (size_t)(len)){ \
- swap = idx; \
- a = (ary)[swap]; b = (ary)[(idx << 1) + 1]; \
- if((cmp_expr) > 0) swap = (idx << 1) + 1; \
- if(((idx << 1) + 2) < (size_t)(len)){ \
- a = (ary)[swap]; b = (ary)[(idx << 1) + 2]; \
- if((cmp_expr) > 0) swap = (idx << 1) + 2; \
- } \
- if(swap == idx) break; \
- _pp_ = (ary)[idx]; (ary)[idx] = (ary)[swap]; (ary)[swap] = _pp_; \
- idx = swap; \
- } \
- } while(0)
- #define array_heap_pop(ary, len, cap, e_type, cmp_expr) \
- ({ \
- e_type _ret_; \
- if(len){ _ret_ = ary[0]; array_heap_remove(ary, len, cap, e_type, 0, cmp_expr); } \
- else memset(&_ret_, 0xFFU, sizeof(e_type)); \
- _ret_; \
- })
- /**
- * List
- */
- #define define_list_core(list_type, e_type, size_type, inc_size) \
- \
- typedef struct { e_type* buffer; union { size_type size; size_type length; }; size_type cap; size_type off; u4i mem_zero:1, n_head:31; } list_type; \
- \
- static inline size_t list_type##_obj_desc_cnt(void *list, int idx){ \
- if(idx == 0) return ((list_type*)list)->size * sizeof(e_type); \
- else return 0; \
- } \
- \
- static inline void list_type##_obj_desc_post_load(void *obj, size_t aux_data){ \
- list_type *list; \
- UNUSED(aux_data); \
- list = (list_type*)obj; \
- list->cap = list->size; \
- } \
- \
- static const obj_desc_t list_type##_obj_desc = {.tag = TOSTR(_list_##list_type), .size = sizeof(list_type), .n_child = 1, .mem_type = {1}, .addr = {offsetof(list_type, buffer)}, .desc = {(struct obj_desc_t*)&OBJ_DESC_DATA}, .cnt = list_type##_obj_desc_cnt, .post = list_type##_obj_desc_post_load}; \
- \
- static inline void adv_##list_type##_init(list_type *list, size_type init_size, int mem_zero, u4i n_head){ \
- if(init_size == 0) init_size = 2; \
- list->size = 0; \
- list->off = 0; \
- list->cap = init_size; \
- list->mem_zero = mem_zero; \
- list->n_head = n_head; \
- if(n_head){ \
- list->buffer = (e_type*)calloc(list->cap + n_head, sizeof(e_type)); \
- list->buffer += n_head; \
- } else { \
- list->buffer = (e_type*)calloc(list->cap, sizeof(e_type)); \
- } \
- } \
- \
- static inline list_type* adv_init_##list_type(size_type init_size, int mem_zero, u4i n_head){ \
- list_type *list = (list_type*)malloc(sizeof(list_type)); \
- adv_##list_type##_init(list, init_size, mem_zero, n_head); \
- return list; \
- } \
- \
- static inline list_type* init_##list_type(size_type init_size){ \
- return adv_init_##list_type(init_size, 0, 0); \
- } \
- \
- static inline void list_type##_init(list_type *list, size_type init_size){ \
- adv_##list_type##_init(list, init_size, 0, 0); \
- } \
- \
- static inline int head_sl_##list_type(list_type *list, size_type len){ \
- if(list->n_head < len) return 0; \
- list->buffer -= len; \
- list->n_head -= len; \
- list->cap += len; \
- if(list->size) list->size += len; \
- return 1; \
- } \
- \
- static inline int head_sr_##list_type(list_type *list, size_type len){ \
- if(list->cap < len) return 0; \
- list->buffer += len; \
- list->n_head += len; \
- list->cap -= len; \
- if(list->size > len) list->size -= len; \
- else list->size = 0; \
- return 1; \
- } \
- \
- static inline void renew_##list_type(list_type *list, size_type init_size){ \
- if(list->buffer) free(list->buffer - list->n_head); \
- adv_##list_type##_init(list, init_size, list->mem_zero, list->n_head); \
- } \
- \
- static inline size_type count_##list_type(list_type *list){ return list->size; } \
- \
- static inline void clear_##list_type(list_type *list){ list->size = 0; list->off = 0; } \
- \
- static inline void zeros_##list_type(list_type *list){ memset(list->buffer, 0, list->cap * sizeof(e_type)); } \
- \
- static inline void encap_##list_type(list_type *list, size_type n){ \
- list->cap = encap_list((void**)&list->buffer, sizeof(e_type), list->size, list->cap, n, list->mem_zero, list->n_head); \
- } \
- \
- static inline void recap_##list_type(list_type *list, size_type n){ \
- if((size_t)n == (size_t)list->cap) return; \
- list->cap = n; \
- if(list->size > n) list->size = n; \
- list->buffer = realloc(list->buffer - list->n_head, (list->cap + list->n_head) * sizeof(e_type)) + list->n_head; \
- } \
- \
- static inline void pack_##list_type(list_type *list){ \
- return recap_##list_type(list, list->size); \
- } \
- \
- static inline void encap_and_zeros_##list_type(list_type *list, size_type n){ \
- if(((size_t)list->size) + ((size_t)n) <= (size_t)list->cap){ \
- } else { \
- if((size_t)(list->size + n) != ((size_t)list->size) + ((size_t)n)){ \
- fprintf(stderr, " -- elements size exceed %s's data type %s in %s -- %s:%d --\n", #list_type, #size_type, __FUNCTION__, __FILE__, __LINE__); \
- print_backtrace(stderr, 20); \
- fflush(stderr); \
- exit(1); \
- } \
- while(list->size + n > list->cap){ \
- if(list->cap < inc_size){ \
- list->cap <<= 1; \
- } else { \
- list->cap += inc_size; \
- } \
- } \
- list->buffer = realloc(list->buffer, list->cap * sizeof(e_type)); \
- } \
- memset(list->buffer + list->size, 0, n * sizeof(e_type)); \
- } \
- \
- static inline void clear_and_encap_##list_type(list_type *list, size_type n){ \
- list->size = 0; \
- list->off = 0; \
- encap_##list_type(list, n); \
- } \
- \
- static inline void clear_and_inc_##list_type(list_type *list, size_type n){ \
- list->size = 0; \
- list->off = 0; \
- encap_##list_type(list, n); \
- list->size = n; \
- } \
- \
- static inline void trunc_##list_type(list_type *list, size_type size){ \
- if(size > count_##list_type(list)) size = count_##list_type(list); \
- list->size -= size; \
- } \
- \
- static inline void set_##list_type##_size(list_type *list, size_type size){ list->size = size; } \
- \
- static inline void inc_##list_type(list_type *list, size_type size){ \
- encap_##list_type(list, size); \
- list->size += size; \
- } \
- \
- static inline void lazy_push_##list_type(list_type *list, e_type e){ list->buffer[list->size ++] = e; } \
- \
- static inline void push_##list_type(list_type *list, e_type e){ \
- encap_##list_type(list, 1); \
- list->buffer[list->size++] = e; \
- } \
- \
- static inline e_type* ring_ref_##list_type(list_type *list, size_type idx){ \
- idx = (list->off + idx) % list->cap; \
- return list->buffer + idx; \
- } \
- \
- static inline void ring_push_##list_type(list_type *list, e_type e){ \
- size_type idx; \
- idx = (list->off + list->size) % list->cap; \
- list->buffer[idx] = e; \
- if(list->size < list->cap){ \
- list->size ++; \
- } \
- } \
- \
- static inline e_type* ring_peer_##list_type(list_type *list){ \
- if(list->size){ \
- return list->buffer + list->size - 1; \
- } else return NULL; \
- } \
- \
- static inline e_type* ring_pop_##list_type(list_type *list){ \
- size_type idx; \
- if(list->size){ \
- list->size --; \
- idx = (list->off + list->size) % list->cap; \
- return list->buffer + idx; \
- } else return NULL; \
- } \
- \
- static inline void ring_shift_##list_type(list_type *list, e_type e){ \
- list->off = (list->off + list->cap - 1) % list->cap; \
- list->buffer[list->off] = e; \
- if(list->size < list->cap){ \
- list->size ++; \
- } \
- } \
- \
- static inline e_type* ring_unshift_##list_type(list_type *list){ \
- size_type idx; \
- if(list->size){ \
- list->size --; \
- list->off = (list->off + 1) % list->cap; \
- idx = (list->off + list->size) % list->cap; \
- return list->buffer + idx; \
- } else return NULL; \
- } \
- \
- static inline int fpush_##list_type(list_type *list, FILE *inp){ \
- int ret; \
- encap_##list_type(list, 1); \
- ret = fread(list->buffer + list->size, sizeof(e_type), 1, inp); \
- if(ret == 1) list->size ++; \
- return ret; \
- } \
- \
- static inline e_type* peer_##list_type(list_type *list){ \
- if(count_##list_type(list)){ \
- return list->buffer + list->size - 1; \
- } else return NULL; \
- } \
- \
- static inline e_type* head_##list_type(list_type *list){ \
- if(list->size) return list->buffer; \
- else return NULL; \
- } \
- \
- static inline e_type* tail_##list_type(list_type *list){ \
- if(list->size) return list->buffer + list->size - 1; \
- else return NULL; \
- } \
- static inline int pop_##list_type(list_type *list, e_type*e){ \
- if(count_##list_type(list)){ \
- list->size --; \
- *e = list->buffer[list->size]; \
- return 1; \
- } else return 0; \
- } \
- \
- static inline int fpop_##list_type(list_type *list, FILE *oup){ \
- if(list->size){ \
- fwrite(list->buffer + list->size - 1, sizeof(e_type), 1, oup); \
- list->size --; \
- return 1; \
- } else { \
- return 0; \
- } \
- } \
- \
- static inline void insert_##list_type(list_type *list, size_type idx, e_type e){ \
- if(idx > list->size) return; \
- encap_##list_type(list, 1); \
- if(idx == list->size){ \
- list->buffer[list->size] = e; \
- } else { \
- memmove(list->buffer + idx + 1, list->buffer + idx, (list->size - idx) * sizeof(e_type)); \
- list->buffer[idx] = e; \
- } \
- list->size ++; \
- } \
- \
- static inline void insert_array_##list_type(list_type *list, size_type idx, e_type *es, size_type size){ \
- if(idx > list->size) return; \
- encap_##list_type(list, size); \
- if(idx == list->size){ \
- } else { \
- memmove(list->buffer + idx + size, list->buffer + idx, (list->size - idx) * sizeof(e_type)); \
- } \
- memcpy(list->buffer + idx, es, size * sizeof(e_type)); \
- list->size += size; \
- } \
- \
- static inline void remove_##list_type(list_type *list, size_type idx){ \
- if(idx >= list->size) return; \
- if(idx + 1 < list->size){ \
- memmove(list->buffer + idx, list->buffer + idx + 1, (list->size - idx - 1) * sizeof(e_type)); \
- } \
- list->size --; \
- } \
- \
- static inline void remove_array_##list_type(list_type *list, size_type off, size_type len){ \
- if(off >= list->size) return; \
- if(off + len < list->size){ \
- memmove(list->buffer + off, list->buffer + off + len, (list->size - off - len) * sizeof(e_type)); \
- list->size -= len; \
- } else { \
- list->size = off; \
- } \
- } \
- \
- static inline void set_##list_type(list_type *list, size_type idx, e_type e){ list->buffer[idx] = e; } \
- \
- static inline e_type get_##list_type(list_type *list, size_type idx){ return list->buffer[idx]; } \
- \
- static inline e_type* ref_##list_type(list_type *list, size_type idx){ return list->buffer + idx; } \
- \
- static inline size_type offset_##list_type(list_type *list, e_type *e){ return e - list->buffer; } \
- \
- static inline e_type* next_ref_##list_type(list_type *list){ encap_##list_type(list, 1); list->size ++; return list->buffer + list->size - 1; } \
- \
- static inline e_type* ref_next_##list_type(list_type *list){ list->size ++; return list->buffer + list->size - 1; } \
- \
- static inline e_type* as_array_##list_type(list_type *list){ return list->buffer; } \
- \
- static inline void reverse_##list_type(list_type *list){ \
- size_type i, j; \
- e_type t; \
- if(count_##list_type(list) == 0) return; \
- i = 0; \
- j = count_##list_type(list) - 1; \
- while(i < j){ \
- t = get_##list_type(list, i); \
- set_##list_type(list, i, get_##list_type(list, j)); \
- set_##list_type(list, j, t); \
- i ++; \
- j --; \
- } \
- } \
- \
- static inline void sub_reverse_##list_type(list_type *list, size_type beg, size_type end){ \
- size_type i, j; \
- e_type t; \
- if(end <= beg) return; \
- i = beg; \
- j = end - 1; \
- while(i < j){ \
- t = get_##list_type(list, i); \
- set_##list_type(list, i, get_##list_type(list, j)); \
- set_##list_type(list, j, t); \
- i ++; \
- j --; \
- } \
- } \
- \
- static inline void append_##list_type(list_type *list1, list_type *list2){ \
- encap_##list_type(list1, count_##list_type(list2)); \
- memcpy(list1->buffer + list1->size, list2->buffer, sizeof(e_type) * list2->size); \
- list1->size += list2->size; \
- } \
- \
- static inline void append_array_##list_type(list_type *list1, e_type *ary, size_type size){ \
- if(size == 0) return; \
- encap_##list_type(list1, size); \
- memcpy(list1->buffer + list1->size, ary, sizeof(e_type) * size); \
- list1->size += size; \
- } \
- \
- static inline size_type write_##list_type(list_type *list, FILE *out){ \
- return fwrite(list->buffer, sizeof(e_type), count_##list_type(list), out); \
- } \
- \
- static inline size_type dump_##list_type(list_type *list, FILE *out){ \
- fwrite(&list->size, sizeof(size_type), 1, out); \
- fwrite(list->buffer, sizeof(e_type), list->size, out); \
- return sizeof(size_type) + sizeof(e_type) * list->size; \
- } \
- \
- static inline size_t mem_size_##list_type(list_type *list){ \
- return ((sizeof(list_type) + 7) / 8) * 8 + (list->size * sizeof(e_type) + 7) / 8 * 8; \
- } \
- \
- static inline size_t mem_dump_##list_type(list_type *list, FILE *out, void *addr){ \
- list_type clone; \
- size_t size; \
- b1i i, v; \
- size = mem_size_##list_type(list); \
- clone.size = list->size; \
- clone.cap = list->size; \
- clone.buffer = addr + (sizeof(list_type) + 7) / 8 * 8; \
- fwrite(&clone, sizeof(list_type), 1, out); \
- v = 0; \
- for(i=(sizeof(list_type) + 7) / 8 * 8 - sizeof(list_type);i>0;i--) fwrite(&v, 1, 1, out); \
- fwrite(list->buffer, sizeof(e_type), list->size, out); \
- for(i=(sizeof(e_type) * list->size + 7) / 8 * 8 - sizeof(e_type) * list->size;i>0;i--) fwrite(&v, 1, 1, out); \
- return size; \
- } \
- \
- static inline list_type* load_##list_type(FILE *inp){ \
- list_type *list; \
- size_type n; \
- list = (list_type*)malloc(sizeof(list_type)); \
- if((n = fread(&list->size, sizeof(size_type), 1, inp)) != 1){ \
- free(list); return NULL; \
- } \
- list->cap = list->size; \
- list->buffer = (e_type*)malloc(sizeof(e_type) * list->cap); \
- if(list->buffer == NULL){ \
- fprintf(stderr, " Out of memory in load_%s \n", #list_type); fflush(stderr); exit(1); \
- print_backtrace(stderr, 20); \
- } \
- if((n = fread(list->buffer, sizeof(e_type), list->size, inp)) != list->size){ \
- print_backtrace(stderr, 20); \
- free(list->buffer); free(list); return NULL; \
- } \
- return list; \
- } \
- \
- static inline void free_##list_type(list_type *list){ if(list){ free(list->buffer - list->n_head); free(list); } } \
- \
- static inline void list_type##_free(list_type *list){ free(list->buffer); list->buffer = NULL; } \
- #define define_list_ext(list_type, e_type, size_type, cmp_func) \
- static inline size_type delete_##list_type(list_type *list, e_type e){ \
- size_type i, ret; \
- ret = 0; \
- for(i=list->size;i>0;i--){ \
- if(cmp_func(list->buffer[i-1], e, NULL) == 0){ \
- if(i < list->size){ \
- memmove(list->buffer + i - 1, list->buffer + i, (list->size - i) * sizeof(e_type)); \
- } \
- list->size --; \
- ret ++; \
- } \
- } \
- return ret; \
- } \
- \
- static inline size_type occ_##list_type(list_type *list, e_type e){ \
- size_type i, n; \
- for(i=0,n=0;i<list->size;i++){ \
- if(cmp_func(list->buffer[i], e, NULL) == 0) n++; \
- } \
- return n; \
- } \
- \
- static inline size_type replace_##list_type(list_type *list, e_type from, e_type to){ \
- size_type i, ret; \
- ret = 0; \
- for(i=0;i<list->size;i++){ \
- if(cmp_func(list->buffer[i], from, NULL) == 0){ \
- list->buffer[i] = to; \
- ret ++; \
- } \
- } \
- return ret; \
- } \
- \
- static inline size_type locate_##list_type(list_type *list, e_type e, size_type start){ \
- size_type i; \
- for(i=start;i<list->size;i++){ \
- if(cmp_func(list->buffer[i], e, NULL) == 0) return i; \
- } \
- return i; \
- } \
- \
- define_quick_sort(sort_##list_type##_core, e_type, cmp_func); \
- \
- static inline void sort_##list_type(list_type *list){ sort_##list_type##_core(ref_##list_type(list, 0), count_##list_type(list), NULL); }
- #define define_list(name, e_type) define_list_core(name, e_type, size_t, 0xFFFFFU)
- #define native_number_cmp(e1, e2, obj) (((e1) == (e2))? 0 : (((e1) < (e2))? -1 : 1))
- #define define_native_list(name, e_type) \
- define_list_core(name, e_type, size_t, 0xFFFFFU); \
- define_list_ext(name, e_type, size_t, native_number_cmp);
- define_native_list(u8list, u1i);
- define_native_list(u1v, u1i);
- define_native_list(u16list, u2i);
- define_native_list(u2v, u2i);
- define_native_list(u32list, u4i);
- define_native_list(u4v, u4i);
- define_native_list(u64list, u8i);
- define_native_list(u8v, u8i);
- define_native_list(b8list, b1i);
- define_native_list(b1v, b1i);
- define_native_list(b16list, b2i);
- define_native_list(b2v, b2i);
- define_native_list(b32list, b4i);
- define_native_list(b4v, b4i);
- define_native_list(b64list, b8i);
- define_native_list(b8v, b8i);
- define_native_list(f4v, f4i);
- define_native_list(f8v, f8i);
- define_list(vplist, void*);
- define_list(cplist, char*);
- // mem_share for deep dump of cplist
- static inline size_t cplist_deep_obj_desc_cnt(void *list, int idx){
- if(idx == 0) return ((cplist*)list)->size;
- else return 1;
- }
- static const obj_desc_t cplist_deep_obj_desc = {.tag = "cplist_deep_dump", .size = sizeof(cplist), .n_child = 1, .mem_type = {3}, .addr = {offsetof(cplist, buffer)}, .desc = {(struct obj_desc_t*)&OBJ_DESC_CHAR_ARRAY}, .cnt = cplist_deep_obj_desc_cnt, .post=NULL};
- #define define_recycle_list_array(name, list_type) \
- typedef struct { \
- vplist *array; \
- vplist *dustbin; \
- } name; \
- \
- static inline name* init_##name(){ \
- name *g; \
- g = (name*)malloc(sizeof(name)); \
- g->buffer = init_vplist(4); \
- g->dustbin = init_vplist(4); \
- return g; \
- } \
- \
- static inline void free_##name(name *g){ \
- list_type *v; \
- size_t i; \
- for(i=0;i<g->array->size;i++){ \
- v = (list_type*)get_vplist(g->array, i); \
- if(v) free_##list_type(v); \
- } \
- for(i=0;i<g->dustbin->size;i++){ \
- v = (list_type*)get_vplist(g->dustbin, i); \
- if(v) free_##list_type(v); \
- } \
- free_vplist(g->array); \
- free_vplist(g->dustbin); \
- free(g); \
- } \
- \
- static inline list_type* fetch_##name(name *g){ \
- list_type *v; \
- if(g->dustbin->size) v = (list_type*)g->dustbin->buffer[--g->dustbin->size]; \
- else v = init_##list_type(4); \
- return v; \
- } \
- \
- static inline void recyc_##name(name *g, list_type *v){ \
- push_vplist(g->dustbin, v); \
- } \
- \
- static inline void recyc_all_##name(name *g, vplist *vs){ \
- append_vplist(g->dustbin, vs); \
- vs->size = 0; \
- }
- // e.g. define_recycle_list(u8r, u8i, u8i, *a = 0, NULL)
- // u8r, when increase an element, set the to 0 (*a = 0), when free it, do nothing (NULL)
- #define define_recycle_list(list_type, e_type, size_type, e_init, e_free) \
- typedef struct { \
- e_type *buffer; \
- size_type size, cap; \
- size_type *recyc; \
- size_type rsize, rcap; \
- u8i userdata; \
- } list_type; \
- \
- static inline list_type* init_##list_type(size_type size){ \
- list_type *list; \
- if(size < 2) size = 2; \
- list = malloc(sizeof(list_type)); \
- list->size = 0; \
- list->cap = size; \
- list->buffer = calloc(size, sizeof(e_type)); \
- list->recyc = calloc(2, sizeof(size_type)); \
- list->rsize = 0; \
- list->rcap = 2; \
- list->userdata = 0; \
- return list; \
- } \
- \
- static inline void free_##list_type(list_type *list){ \
- e_type* a; \
- size_type i; \
- for(i=0;i<list->size;i++){ \
- a = list->buffer + i; \
- UNUSED(e_free); \
- } \
- UNUSED(a); \
- free(list->buffer); \
- free(list->recyc); \
- free(list); \
- } \
- \
- static inline void encap_##list_type(list_type *list, size_type inc){ \
- if(list->rsize >= inc) return; \
- inc -= list->rsize; \
- list->cap = encap_list((void**)&list->buffer, sizeof(e_type), list->size, list->cap, inc, 0, 0); \
- } \
- \
- static inline size_type fetch_##list_type(list_type *list){ \
- e_type* a; \
- if(list->rsize){ \
- return list->recyc[--list->rsize]; \
- } \
- list->cap = encap_list((void**)&list->buffer, sizeof(e_type), list->size, list->cap, 1, 0, 0); \
- a = list->buffer + list->size; \
- UNUSED(e_init); \
- UNUSED(a); \
- return list->size ++; \
- } \
- \
- static inline e_type* ref_##list_type(list_type *list, size_type idx){ \
- return list->buffer + idx; \
- } \
- \
- static inline size_type offset_##list_type(list_type *list, e_type *e){ \
- return e - list->buffer; \
- } \
- \
- static inline void recyc_##list_type(list_type *list, size_type idx){ \
- list->rcap = encap_list((void**)&list->recyc, sizeof(size_type), list->rsize, list->rcap, 1, 0, 0); \
- list->recyc[list->rsize++] = idx; \
- } \
- \
- static inline e_type* pop_##list_type(list_type *list){ \
- size_type idx; \
- idx = fetch_##list_type(list); \
- return ref_##list_type(list, idx); \
- } \
- \
- static inline void push_##list_type(list_type *list, e_type* e){ \
- recyc_##list_type(list, offset_##list_type(list, e)); \
- } \
- \
- static inline void recyc_all_##list_type(list_type *list){ \
- size_type i; \
- list->rsize = 0; \
- list->rcap = encap_list((void**)&list->recyc, sizeof(size_type), list->rsize, list->rcap, list->size, 0, 0); \
- for(i=0;i<list->size;i++){ \
- list->recyc[i] = i; \
- } \
- list->rsize = list->size; \
- }
- # endif
|