data.h

CFL是Unix下的通用抽象库,以简化Unix下的系统软件开发,CFL库中包含几个分组的函数和宏

/* ----------------------------------------------------------------------------
   CFL - A C Foundation Library
   Copyright (C) 1994-2003 Mark A Lindner

   This file is part of CFL.
   
   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.
   
   This library 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
   Library General Public License for more details.
   
   You should have received a copy of the GNU Library General Public
   License along with this library; if not, write to the Free
   Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  ----------------------------------------------------------------------------
*/

#ifndef __cfl_data_h
#define __cfl_data_h

#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */

#include <cfl/defs.h>

/* ----------------------------------------------------------------------------
 * linked lists
 * ----------------------------------------------------------------------------
 */

typedef struct c_link_t
  {
  void *data;
  struct c_link_t *next;
  struct c_link_t *prev;
  } c_link_t;

#define C_link_next(L) ((L)->next)
#define C_link_prev(L) ((L)->prev)
#define C_link_data(L) ((L)->data)

typedef struct c_linklist_t
  {
  c_link_t *head;
  c_link_t *tail;
  c_link_t *p;
  size_t size;
  void (*destructor)(void *);
  } c_linklist_t;

#define C_linklist_head(L) ((L)->head)
#define C_linklist_tail(L) ((L)->tail)
#define C_linklist_size(L) ((L)->size)

extern c_linklist_t *C_linklist_create(void);
extern void C_linklist_destroy(c_linklist_t *l);

extern c_bool_t C_linklist_set_destructor(c_linklist_t *l,
                                          void (*destructor)(void *));

extern c_bool_t C_linklist_store(c_linklist_t *l, const void *data);

extern void *C_linklist_restore(c_linklist_t *l);

extern c_bool_t C_linklist_search(c_linklist_t *l, const void *data);

extern c_bool_t C_linklist_move(c_linklist_t *l, int where);
extern c_bool_t C_linklist_delete(c_linklist_t *l);

extern c_bool_t C_linklist_store_r(c_linklist_t *l, const void *data,
                                   c_link_t **p);

extern void *C_linklist_restore_r(c_linklist_t *l, c_link_t **p);

extern c_bool_t C_linklist_search_r(c_linklist_t *l, const void *data,
                                    c_link_t **p);

extern c_bool_t C_linklist_delete_r(c_linklist_t *l, c_link_t **p);
extern c_bool_t C_linklist_move_r(c_linklist_t *l, int where, c_link_t **p);


#define C_LINKLIST_HEAD 0
#define C_LINKLIST_TAIL 1
#define C_LINKLIST_NEXT 2
#define C_LINKLIST_PREV 3

#define C_linklist_move_head(L) C_linklist_move((L), C_LINKLIST_HEAD)
#define C_linklist_move_tail(L) C_linklist_move((L), C_LINKLIST_TAIL)
#define C_linklist_move_next(L) C_linklist_move((L), C_LINKLIST_NEXT)
#define C_linklist_move_prev(L) C_linklist_move((L), C_LINKLIST_PREV)
#define C_linklist_istail(L) ((L)->p ? FALSE : TRUE)
#define C_linklist_ishead(L) (((L)->p == (L)->head) ? TRUE : FALSE)
#define C_linklist_length(L) ((L)->size)

#define C_linklist_move_head_r(L, P) \
  C_linklist_move_r((L), C_LINKLIST_HEAD, (P))
#define C_linklist_move_tail_r(L, P) \
  C_linklist_move_r((L), C_LINKLIST_TAIL, (P))
#define C_linklist_move_next_r(L, P) \
  C_linklist_move_r((L), C_LINKLIST_NEXT, (P))
#define C_linklist_move_prev_r(L, P) \
  C_linklist_move_r((L), C_LINKLIST_PREV, (P))
#define C_linklist_istail_r(L, P) \
  (*(P) ? FALSE : TRUE)
#define C_linklist_ishead_r(L, P) \
  ((*(P) == (L)->head) ? TRUE : FALSE)

/* ----------------------------------------------------------------------------
 * stacks
 * ----------------------------------------------------------------------------
 */

typedef c_linklist_t c_stack_t;

#define C_stack_create() C_linklist_create()
#define C_stack_destroy(S) C_linklist_destroy(S)

#define C_stack_set_destructor(S, D) \
  C_linklist_set_destructor((S), (D))

extern c_bool_t C_linklist_push(c_linklist_t *l, const void *data);
extern void *C_linklist_pop(c_linklist_t *l);
extern void *C_linklist_peek(c_linklist_t *l);

#define C_stack_push(S, D) C_linklist_push((S), (D))
#define C_stack_pop(S) C_linklist_pop(S)
#define C_stack_peek(S) C_linklist_peek(S)

#define C_stack_depth(S) C_linklist_length(S)

/* ----------------------------------------------------------------------------
 * queues
 * ----------------------------------------------------------------------------
 */

typedef c_linklist_t c_queue_t;

#define C_queue_create() C_linklist_create()
#define C_queue_destroy(Q) C_linklist_destroy(Q)

#define C_queue_set_destructor(Q, D) \
  C_linklist_set_destructor((Q), (D))

extern c_bool_t C_linklist_enqueue(c_linklist_t *l, const void *data);

#define C_queue_enqueue(Q, D) C_linklist_enqueue((Q), (D))

#define C_queue_dequeue(Q) C_linklist_pop(Q)

#define C_queue_length(Q) C_linklist_length(Q)

/* ----------------------------------------------------------------------------
 * dynamic arrays
 * ----------------------------------------------------------------------------
 */

typedef struct c_darray_t
  {
  void *mem;
  uint_t resize;
  size_t elemsz;
  uint_t size;
  uint_t isize;
  uint_t bot;
  uint_t del_count;
  char *free_list;
  uint_t iresize;
  } c_darray_t;

#define C_darray_size(A) ((A)->bot - (A)->del_count)
#define C_darray_last(A) ((A)->bot)

#define C_DARRAY_MAX_RESIZE 100

extern c_darray_t *C_darray_create(uint_t resize, size_t elemsz);
extern void C_darray_destroy(c_darray_t *a);

extern void *C_darray_store(c_darray_t *a, const void *data, uint_t *index);
extern void *C_darray_restore(c_darray_t *a, uint_t index);
extern c_bool_t C_darray_delete(c_darray_t *a, uint_t index);

extern c_darray_t *C_darray_load(const char *path);
extern c_bool_t C_darray_save(c_darray_t *a, const char *path);
extern c_darray_t *C_darray_defragment(c_darray_t *a);
extern c_bool_t C_darray_iterate(c_darray_t *a,
                                 c_bool_t (*iter)(void *elem, uint_t index,
                                                  void *hook),
                                 uint_t index, void *hook);

/* ----------------------------------------------------------------------------
 * dynamic strings
 * ----------------------------------------------------------------------------
 */

typedef struct c_dstring_t
  {
  char *mem;
  off_t p;
  off_t len;
  uint_t blk;
  uint_t blocksz;
  } c_dstring_t;

#define C_dstring_length(D) ((D)->len)

#define C_DSTRING_SEEK_ABS 0
#define C_DSTRING_SEEK_REL 1
#define C_DSTRING_SEEK_END 2

#define C_DSTRING_MIN_BLOCKSZ 80
#define C_DSTRING_LOAD_BLOCKSZ 4096

extern c_dstring_t *C_dstring_create(uint_t blocksz);
extern char *C_dstring_destroy(c_dstring_t *d);

extern c_bool_t C_dstring_putc(c_dstring_t *d, char c);
extern c_bool_t C_dstring_puts(c_dstring_t *d, const char *s);
extern c_bool_t C_dstring_puts_len(c_dstring_t *d, const char *s, size_t len);
extern char C_dstring_getc(c_dstring_t *d);
extern char *C_dstring_gets(c_dstring_t *d, char *s, size_t len, char termin);

extern c_bool_t C_dstring_seek(c_dstring_t *d, off_t where, int whence);
extern c_bool_t C_dstring_trunc(c_dstring_t *d, off_t length);
extern c_dstring_t *C_dstring_load(const char *path, uint_t blocksz);
extern c_bool_t C_dstring_save(c_dstring_t *d, const char *path);

#define C_dstring_ungetc(D) C_dstring_seek((D), -1L, C_DSTRING_SEEK_REL)
#define C_dstring_rewind(D) C_dstring_seek((D),  0L, C_DSTRING_SEEK_ABS)
#define C_dstring_append(D) C_dstring_seek((D),  0L, C_DSTRING_SEEK_END)

/* ----------------------------------------------------------------------------
 * hash tables
 * ----------------------------------------------------------------------------
 */

typedef struct c_tag_t
  {
  char *key;
  void *data;
  } c_tag_t;

#define C_tag_key(T) ((T)->key)
#define C_tag_data(T) ((T)->data)

typedef struct c_hashtable_t
  {
  uint_t buckets;
  c_linklist_t **table;
  size_t size;
  void (*destructor)(void *);
  } c_hashtable_t;

#define C_hashtable_size(H) ((H)->size)

extern c_hashtable_t *C_hashtable_create(uint_t buckets);
extern void C_hashtable_destroy(c_hashtable_t *h);

extern c_bool_t C_hashtable_set_destructor(c_hashtable_t *h,
                                           void (*destructor)(void *));

extern c_bool_t C_hashtable_set_hashfunc(uint_t (*func)(const char *s,
                                                        uint_t modulo));

extern c_bool_t C_hashtable_store(c_hashtable_t *h, const char *key,
                                  const void *data);
extern void *C_hashtable_restore(c_hashtable_t *h, const char *key);
extern c_bool_t C_hashtable_delete(c_hashtable_t *h, const char *key);

extern char **C_hashtable_keys(c_hashtable_t *h, uint_t *len);

/* ----------------------------------------------------------------------------
 * string heaps
 * ----------------------------------------------------------------------------
 */

struct c_strheap_ent
  {
  uint_t offset;
  size_t len;
  char flags;
  };

typedef struct c_strheap_t
  {
  char *mem;
  struct c_strheap_ent *index;
  uint_t blk;
  uint_t iblk;
  uint_t bot;
  uint_t blocksz;
  size_t size;
  char flags;
  } c_strheap_t;

#define C_strheap_size(H) ((H)->size)

extern c_strheap_t *C_strheap_create(uint_t blocksz);
extern void C_strheap_destroy(c_strheap_t *h);

extern uint_t C_strheap_store(c_strheap_t *h, const char *s);
extern char *C_strheap_restore(c_strheap_t *h, uint_t index);
extern c_bool_t C_strheap_delete(c_strheap_t *h, uint_t index);

extern c_strheap_t *C_strheap_load(const char *path);
extern c_bool_t C_strheap_save(c_strheap_t *h, const char *path);

#define C_STRHEAP_MIN_BLOCKSZ 64

/* ----------------------------------------------------------------------------
 * b-trees
 * ----------------------------------------------------------------------------
 */

//#define C_BTREE_ORDER 50
//#define C_BTREE_NKEYS 100

typedef unsigned long long c_id_t;

typedef struct c_datum_t
  {
  c_id_t key;
  void *value;
  } c_datum_t;

#define C_datum_key(D) \
  (D)->key

#define C_datum_value(D) \
  (D)->value

typedef struct c_btree_node_t
  {
  uint_t count;
//  c_datum_t keys[C_BTREE_NKEYS];
  c_datum_t *keys;
//  struct c_btree_node_t *children[C_BTREE_NKEYS + 1];
  struct c_btree_node_t **children;
  } c_btree_node_t;

typedef struct c_btree_t
  {
  c_btree_node_t *root;
  uint_t order;
  uint_t nkeys;
  void (*destructor)(void *);
  } c_btree_t;

extern c_btree_t *C_btree_create(uint_t order);
extern void C_btree_destroy(c_btree_t *tree);

extern c_bool_t C_btree_set_destructor(c_btree_t *tree,
                                       void (*destructor)(void *));

extern c_bool_t C_btree_store(c_btree_t *tree, c_id_t key, const void *data);
extern void *C_btree_restore(c_btree_t *tree, c_id_t key);

extern c_bool_t C_btree_delete(c_btree_t *tree, c_id_t key);

extern c_bool_t C_btree_iterate(c_btree_t *btree,
                                c_bool_t (*consumer)(void *elem, void *hook),
                                void *hook);

#define C_btree_order(T) \
  ((T)->order)

#ifdef __cplusplus
}
#endif /* __cplusplus */

#endif /* __cfl_data_h */

/* end of library header */