new friend of sys/queue.h and sys/tree.h
Pawel Wieczorek
wieczyk at trzask.int.pl
Wed Jul 11 08:22:03 UTC 2007
Hi,
I did something like sys/queue.h and sys/tree.h: sys/bds.h
bds - Basic Data Structures.
Hash table are basic data structure, it is good to have it in kernel,
but i did not see some easy to use framework like sys/queue.h in our kernel.
At current time it have only hash table and multi-value hash table,
but i want to add in near future something else.
I did not done full documentation how to use it(yet),
but i did two examples. One is how to use it user-space
and one how to use it in kernel-space.
I tested code on "cc" on OpenSolaris (because cc on sunos is more
pedantic) and "cc" "c++" "c89" "c99" on FreeBSD 6.2-RELEASE.
I develop sys/bds.h for my private usage, but i think it can be used in
freebsd kernel programming, because is safe, easy to use and similar to
sys/queue.h.
I am waiting for comments...
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bdsm.tar
Type: application/octet-stream
Size: 50176 bytes
Desc: not available
Url : http://lists.freebsd.org/pipermail/freebsd-arch/attachments/20070711/dfb1a8af/bdsm.obj
-------------- next part --------------
/*-
* Copyright (c) 2007 Pawel Wieczorek <wieczyk at gmail.com>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
*/
#ifndef SYS_BDS_H
#define SYS_BDS_H
/*
* This file contain basic data structures. They are similar to structures
* in sys/queue.h, please read documentation for it first.
*
* !! Include sys/queue.h before this file.
*
* A map ( dictionary, hash-table, associative array ) structure is headed
* by MAP_HEAD macro. This structure contains table of lists represented
* by SLIST structure from sys/queue.h. The length of table is typed by user
* as prime-number-parameter in HEAD macro. Structures are used to
* decrase time of item access . User had to specify a structure
* which will be user as key.
* The initializer (MAP_INIT) need pointers to hash-function, key-copy and
* key-compare routines. Memory addresses of then them will be stored
* in data structure for later usage. Please see definition of bds_* types
* in this file for more information.
* A multi map structure is headed by MMAP_HEAD macro to reduce lines of code
*.(less probality to make bug). It is identical to
* single map with difference that can store many variables for this same key.
* For this feature it is implementing additional macro: _LOOKUP_FOREACH
* (and _SAFE version).
* In implementation the MAP and MMAP are identical, it have different names
* for logical seperation. It is also using internal template for generate
* another internal names for MAP and MMAP, in this way compiler can generate
* error when programmer will use for example MAP macro on MMAP structure.
*
* MAP MMAP
* _HEAD + +
* _HEAD_INITIALIZER - -
* _ENTRY + +
* _INIT + +
* _EMPTY + +
* _FIRST - -
* _NEXT - -
* _PREV - -
* _LAST - -
* _KEY + +
* _FOREACH + +
* _FOREACH_SAFE + +
* _FOREACH_REVERSE - -
* _FOREACH_REVERSE_SAFE - -
* _INSERT + +
* _INSERT_HEAD - -
* _INSERT_BEFORE - -
* _INSERT_AFTER - -
* _INSERT_TAIL - -
* _CONCAT - -
* _REMOVE_HEAD - -
* _REMOVE + +
* _LOOKUP + +
* _LOOKUP_FOREACH - +
* _LOOKUP_FOREACH_SAFE - +
*
* Implementation notes
* --------------------
*
*/
typedef unsigned int bds_hash_func_t( const void *key );
typedef int bds_key_cmp_func_t ( const void *key1, const void *key2 );
typedef void bds_key_cp_func_t( void *keydst, const void *keysrc );
/*
* Generic map template
*/
#define _tMAP_PRIME_TINY 49
#define _tMAP_PRIME_SMALL 149
#define _tMAP_PRIME_MEDIUM 977
#define _tMAP_PRIME_LARGE 1277
#define _tMAP_PRIME_HUGE 2459
#define _tMAP_LOOKUP_FROM_LIST(head, list,key,var,field,_tfield) do { \
int _hifound = 0; \
SLIST_FOREACH(var, list, field._tfield ) { \
if ( head->cmpfunc(key,&var->field.keycopy) ) { \
_hifound = 1; \
break; \
} \
} \
if ( !_hifound ) var = NULL; \
} while(0)
#define _tMAP_INSERT_INTO_LIST(head,list,key,var,field,_tfield) do { \
head->cpfunc(&(var->field.keycopy),key); \
head->count++; \
SLIST_INSERT_HEAD( list, var, field._tfield ); \
} while(0)
#define _tMAP_LIST(head,i) &((head)->list[i])
#define _tMAP_LENGTH(head) (sizeof((head)->list)/sizeof((head)->list[0]))
#define _tMAP_INDEX(head,key) (((head)->hfunc(key))%_tMAP_LENGTH(head))
#define _tMAP_HEAD(name,type,prime) \
struct name { \
unsigned int tmp_i; \
struct type *tmp_v; \
int count; \
bds_hash_func_t *hfunc; \
bds_key_cmp_func_t *cmpfunc; \
bds_key_cp_func_t *cpfunc; \
SLIST_HEAD(,type) list[prime]; \
}
#define _tMAP_ENTRY(type,keytype,_tfield) \
struct { \
SLIST_ENTRY(type) _tfield; \
struct keytype keycopy; \
}
#define _tMAP_INIT(head,_hfunc,_cmpfunc,_cpfunc) do { \
unsigned int _hil; \
(head)->hfunc = (bds_hash_func_t*)_hfunc; \
(head)->cmpfunc = (bds_key_cmp_func_t*)_cmpfunc; \
(head)->cpfunc = (bds_key_cp_func_t*)_cpfunc; \
(head)->count = 0; \
for ( _hil = 0; _hil < _tMAP_LENGTH(head); _hil++ ) { \
SLIST_INIT( _tMAP_LIST(head,_hil) ); \
} \
} while(0)
#define _tMAP_EMPTY(head) ((head)->count == 0)
#define _tMAP_KEY(var,field) (&(var)->field.keycopy)
#define _tMAP_INSERT(head, key, var, field,_tfield ) do { \
unsigned int _hil = _tMAP_INDEX(head,key); \
_tMAP_INSERT_INTO_LIST((head), _tMAP_LIST(head,_hil), \
key,var,field,_tfield); \
} while(0)
#define _tMAP_FOREACH(var, head, field,_tfield) \
for ( (head)->tmp_i = 0; \
(head)->tmp_i < _tMAP_LENGTH(head); \
(head)->tmp_i++ ) \
SLIST_FOREACH(var, _tMAP_LIST(head,(head)->tmp_i), field._tfield)
#define _tMAP_FOREACH_SAFE(var, head, field, _tfield ) \
for ( (head)->tmp_i = 0; \
(head)->tmp_i < _tMAP_LENGTH(head); \
(head)->tmp_i++ ) \
SLIST_FOREACH_SAFE(var, _tMAP_LIST(head,(head)->tmp_i), field._tfield,(head)->tmp_v )
#define _tMAP_REMOVE( head, var, type, field, _tfield ) do { \
int _hil = _tMAP_INDEX(head, &(var)->field.keycopy); \
SLIST_REMOVE( _tMAP_LIST(head,_hil), var, type,field._tfield );\
} while(0)
#define _tMAP_LOOKUP( head, key, var, field,_tfield ) do { \
unsigned int _hil = _tMAP_INDEX(head,key); \
_tMAP_LOOKUP_FROM_LIST( (head), _tMAP_LIST(head,_hil), \
key, var, field, _tfield); \
} while(0)
#define _tMAP_LOOKUP_FOREACH(h, key, var,field,_tfield) \
SLIST_FOREACH(var, _tMAP_LIST(h,_tMAP_INDEX(h,key)), field._tfield)\
if ( (h)->cmpfunc(key,&var->field.keycopy) )
#define _tMAP_LOOKUP_FOREACH_SAFE(h, k, d,f, _tfield) \
SLIST_FOREACH_SAFE(d, _tMAP_LIST(h,_tMAP_INDEX(h,k)), f._tfield,(h)->tmp_v)\
if ( (h)->cmpfunc(k,&d->f.keycopy) )
/*
* Map definitions
*/
#define _MAP_LFIELD mpfld
#define MAP_HEAD(name,type,prime) \
_tMAP_HEAD(name,type,prime)
#define MAP_ENTRY(type,keytype) \
_tMAP_ENTRY(type,keytype,_MAP_LFIELD)
#define MAP_KEY(var,field) \
_tMAP_KEY(var,field)
#define MAP_INIT(head,_hfunc,_cmpfunc,_cpfunc) \
_tMAP_INIT(head,_hfunc,_cmpfunc,_cpfunc)
#define MAP_EMPTY(head) \
_tMAP_EMPTY(head)
#define MAP_FOREACH( var, head, field) \
_tMAP_FOREACH( var, head, field,_MAP_LFIELD)
#define MAP_FOREACH_SAFE( var, head, field ) \
_tMAP_FOREACH_SAFE( var, head, field, _MAP_LFIELD )
#define MAP_REMOVE( head, var, type, field ) \
_tMAP_REMOVE( head, var, type, field,_MAP_LFIELD )
#define MAP_REMOVE_BY_KEY( head, key, type, field ) \
_tMAP_REMOVE_BY_KEY( head, key, type, field,_MAP_LFIELD )
#define MAP_LOOKUP( head, key, var, field ) \
_tMAP_LOOKUP( head, key, var, field,_MAP_LFIELD )
#define MAP_INSERT(head, key, var, field ) \
_tMAP_INSERT(head, key, var, field,_MAP_LFIELD )
/*
* Multi map definitions
*/
#define _MMAP_LFIELD mmpfld
#define MMAP_HEAD(name,type,prime) \
_tMAP_HEAD(name,type,prime)
#define MMAP_ENTRY(type,keytype) \
_tMAP_ENTRY(type,keytype,_MMAP_LFIELD)
#define MMAP_KEY(var,field) \
_tMAP_KEY(var,field)
#define MMAP_INIT(head,_hfunc,_cmpfunc,_cpfunc) \
_tMAP_INIT(head,_hfunc,_cmpfunc,_cpfunc)
#define MMAP_EMPTY(head) \
_tMAP_EMPTY(head)
#define MMAP_FOREACH( var, head, field) \
_tMAP_FOREACH( var, head, field,_MMAP_LFIELD)
#define MMAP_FOREACH_SAFE( var, head, field ) \
_tMAP_FOREACH_SAFE( var, head, field,_MMAP_LFIELD )
#define MMAP_REMOVE( head, var, type, field ) \
_tMAP_REMOVE( head, var, type, field,_MMAP_LFIELD )
#define MMAP_REMOVE_BY_KEY( head, key, type, field ) \
_tMAP_REMOVE_BY_KEY( head, key, type, field,_MMAP_LFIELD )
#define MMAP_LOOKUP( head, key, var, field ) \
_tMAP_LOOKUP( head, key, var, field,_MMAP_LFIELD )
#define MMAP_LOOKUP_FOREACH( head, key, var, field ) \
_tMAP_LOOKUP_FOREACH( head, key, var, field,_MMAP_LFIELD )
#define MMAP_LOOKUP_FOREACH_SAFE( head, key, var, field ) \
_tMAP_LOOKUP_FOREACH_SAFE( head, key, var, field,_MMAP_LFIELD )
#define MMAP_INSERT(head, key, var, field ) \
_tMAP_INSERT(head, key, var, field,_MMAP_LFIELD )
#endif /* SYS_BDS_H */
More information about the freebsd-arch
mailing list