Date: Wed, 11 Jul 2007 10:09:32 +0000 From: Pawel Wieczorek <wieczyk@trzask.int.pl> To: freebsd-arch@freebsd.org Subject: new friend of sys/queue.h and sys/tree.h Message-ID: <4694AC5C.9040107@trzask.int.pl> In-Reply-To: <20070710.205751.-1962670861.imp@bsdimp.com> References: <20070708081511.GX1221@funkthat.com> <200707101833.l6AIX0xl049962@ambrisko.com> <20070710.205751.-1962670861.imp@bsdimp.com>
next in thread | previous in thread | raw e-mail | index | archive | help
[-- Attachment #1 --]
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...
[-- Attachment #2 --]
bdsm 000755 001751 001750 00000000000 10645124276 012577 5 ustar 00wieczyk konta 000000 000000 bdsm/Makefile 000755 001751 001750 00000000172 10645123743 014317 0 ustar 00wieczyk konta 000000 000000 SUBDIR=example0 example1
load:
cd example1/dev; make load
copy:
cp example1/util/bdsctl .
.include<bsd.subdir.mk>
bdsm/man 000755 001751 001750 00000000000 10644177742 013357 5 ustar 00wieczyk konta 000000 000000 bdsm/sys 000755 001751 001750 00000000000 10645124733 013413 5 ustar 00wieczyk konta 000000 000000 bdsm/example0 000755 001751 001750 00000000000 10645124344 014306 5 ustar 00wieczyk konta 000000 000000 bdsm/example1 000755 001751 001750 00000000000 10645022507 014305 5 ustar 00wieczyk konta 000000 000000 bdsm/README 000644 000000 001750 00000001213 10645124176 013012 0 ustar 00root konta 000000 000000 Example usage of sys/bds.h
==========================
To compile type:
# make
example0/ Small programm which allow test
one structure used by MAP and MMAP.
After compilation you can execute
example0/example0 binary.
example1 Small kernel module and utility programm
which allow test MAP on kernel side.
After compilation you should type
# make load copy
to load module into kernel and copy bdsctl
utility to your current direcotry.
Run utility
# ./bdsctl
...and have fun.
WARNING: Because kernel module is using
printf(9) routine, please
be on first terminal on console
or watch dmesg.
bdsm/example1/dev 000755 001751 001750 00000000000 10645124371 015065 5 ustar 00wieczyk konta 000000 000000 bdsm/example1/Makefile 000755 001751 001750 00000000051 10645030725 016024 0 ustar 00wieczyk konta 000000 000000 SUBDIR=dev util
.include<bsd.subdir.mk>
bdsm/example1/util 000755 001751 001750 00000000000 10645124603 015262 5 ustar 00wieczyk konta 000000 000000 bdsm/example1/util/Makefile 000644 001751 001750 00000000115 10645037242 017000 0 ustar 00wieczyk konta 000000 000000 PROG=bdsctl
SRCS=main.c
CFLAGS=-I../.. -I../dev
MAN=
.include<bsd.prog.mk>
bdsm/example1/util/main.c 000644 001751 001750 00000007000 10645124565 016435 0 ustar 00wieczyk konta 000000 000000 /*-
* Copyright (c) 2007 Pawel Wieczorek <wieczyk@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.
*
*/
#include <sys/param.h>
#include <sys/proc.h>
#include <sys/ioctl.h>
#include "sys/bds.h"
#include "kbds.h"
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <stdio.h>
#include <assert.h>
int __fd;
void
opendev()
{
__fd = open("/dev/bds",O_RDWR);
assert( __fd != -1 );
}
#define FL_FIRST 0x01
#define FL_LAST 0x02
#define FL_ID 0x04
#define FL_PRINT 0x08
#define FL_REMOVE 0x10
#define FL_RESET 0x20
#define C_INSERT (FL_FIRST|FL_LAST)
#define C_PRINT (FL_PRINT)
#define C_LOOKUP (FL_ID)
#define C_RESET (FL_RESET)
#define C_REMOVE (FL_REMOVE)
void
usage()
{
printf("bdsctl -f [first] -l [last]i # add new person into kernel citizen registry\n");
printf("bsdctl -i [id] # lookup KCR for ID\n");
printf("bsdctl -p # request kernel to print KCR\n");
printf("bsdctl -r # reset KCR\n");
printf("bsdctl -d [id] # remove from KCR person with id\n");
printf("WARNING: for 'add' 'reset' commands kernel is printing output by printf(9)\n");
}
int
main(int argc, char **argv)
{
char ch;
struct kperson k;
int id;
int flag = 0;
while ( (ch = getopt(argc,argv,"f:l:i:d:rph")) != -1 )
switch (ch) {
case 'f':
flag |= FL_FIRST;
strncpy(k.first,optarg,FIRST_MAX-1);
break;
case 'l':
flag |= FL_LAST;
strncpy(k.last,optarg,LAST_MAX-1);
break;
case 'i':
flag |= FL_ID;
id = strtol(optarg,NULL,10);
break;
case 'd':
flag |= FL_REMOVE;
id = strtol(optarg,NULL,10);
break;
case 'r':
flag |= FL_RESET;
break;
case 'p':
flag |= FL_PRINT;
break;
default:
case 'h':
usage();
return(0);
}
if (flag == 0) {
usage();
return(-1);
}
opendev();
if ( flag == C_INSERT ) {
ioctl(__fd, BDSIOSPERSON, &k );
printf("Inserted with id %u\n",k.id);
} else if ( flag == C_PRINT ) {
ioctl(__fd, BDSIOCKPRINT );
} else if ( flag == C_LOOKUP ) {
k.id = id;
ioctl(__fd, BDSIOGPERSON,&k );
if ( k.id == -1 ) {
printf("Not found\n");
} else {
printf("%.4u %s %s\n",k.id,k.first,k.last);
}
} else if ( flag == C_RESET ) {
ioctl(__fd, BDSIOCKRESET );
} else if ( flag == C_REMOVE ) {
printf("x %lu %u\n",BDSIOCREMOVE,id);
ioctl(__fd, BDSIOCREMOVE,&id );
} else
usage();
return (0);
}
bdsm/example1/dev/Makefile 000755 001751 001750 00000000114 10645036042 016600 0 ustar 00wieczyk konta 000000 000000 KMOD= bds
SRCS= bds.c hash_support.c
CFLAGS= -I../..
.include <bsd.kmod.mk>
bdsm/example1/dev/bds.c 000755 001751 001750 00000012574 10645124704 016074 0 ustar 00wieczyk konta 000000 000000 /*-
* Copyright (c) 2007 Pawel Wieczorek <wieczyk@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.
*
*/
#include <sys/param.h>
#include <sys/uio.h>
#include <sys/proc.h>
#include <sys/systm.h>
#include <sys/kernel.h>
#include <sys/ioccom.h>
#include <sys/conf.h>
#include <sys/module.h>
#include <sys/malloc.h>
#include "sys/bds.h"
#include "kbds.h"
struct citizen_registry citizen_registry;
/*-------------------------------------------------------------------
* Data management
*/
MALLOC_DEFINE(M_KCRENTRY, "Kernel Citizen Registry Entry", "");
static void kcr_add( struct kperson *k );
static void kcr_get( struct kperson *k );
static void kcr_print(void);
static void kcr_remove( int id );
static void kcr_reset(void);
void
kcr_add( struct kperson *param )
{
static int _id = 0x7461;
struct key_id kid;
struct kperson *pcopy;
param->id = kid.id = _id++;
param->first[FIRST_MAX-1] = 0;
param->last[LAST_MAX-1] = 0;
pcopy = (struct kperson *) malloc( sizeof(*pcopy), M_KCRENTRY, M_WAITOK );
memcpy(pcopy,param,sizeof(*pcopy));
MAP_INSERT( &citizen_registry, &kid, pcopy, citreg_entry );
}
void
kcr_get( struct kperson *param )
{
struct key_id kid;
struct kperson *pcopy;
kid.id = param->id;
MAP_LOOKUP( &citizen_registry, &kid, pcopy, citreg_entry );
if ( pcopy ) {
memcpy(param,pcopy,sizeof(*pcopy));
} else {
param->id = -1;
}
}
void
kcr_print()
{
struct kperson *k;
printf("\n-----Kernel Citizen Registry------------\n");
MAP_FOREACH( k, &citizen_registry, citreg_entry ) {
printf("%.4u %s %s\n",k->id,k->first,k->last);
}
printf("----------------------------------------\n");
}
void
kcr_remove(int id )
{
struct kperson *person;
struct key_id kid;
kid.id = id;
MAP_LOOKUP( &citizen_registry, &kid, person, citreg_entry );
if ( person ) {
MAP_REMOVE( &citizen_registry, person, kperson, citreg_entry );
free(person,M_KCRENTRY);
} else {
printf("No person with id %i\n",id);
}
}
void
kcr_reset()
{
struct kperson *person;
MAP_FOREACH_SAFE( person, &citizen_registry, citreg_entry ) {
MAP_REMOVE( &citizen_registry, person, kperson, citreg_entry );
free(person,M_KCRENTRY);
}
}
/*-------------------------------------------------------------------
* Device
*/
static int bdsdev_open(struct cdev *dev, int flag, int otyp, struct thread *td);
static int bdsdev_close(struct cdev *dev, int flag, int otyp, struct thread *td);
static int bdsdev_ioctl(struct cdev *dev, u_long cmd, caddr_t arg, int mode, struct thread *td);
static int bdsdev_write(struct cdev *dev, struct uio *uio, int ioflag);
static int bdsdev_read(struct cdev *dev, struct uio *uio, int ioflag);
int
bdsdev_open(struct cdev *dev, int flag, int otyp, struct thread *td)
{
return (0);
}
int
bdsdev_close(struct cdev *dev, int flag, int otyp, struct thread *td)
{
return (0);
}
int
bdsdev_ioctl(struct cdev *dev, u_long cmd, caddr_t arg, int mode,
struct thread *td)
{
int error = 0;
union {
caddr_t arg;
struct kperson *person;
int *id;
} ARG;
ARG.arg = arg;
switch(cmd) {
case BDSIOSPERSON:
kcr_add(ARG.person);
break;
case BDSIOGPERSON:
kcr_get(ARG.person);
break;
case BDSIOCKPRINT:
kcr_print();
break;
case BDSIOCKRESET:
kcr_reset();
break;
case BDSIOCREMOVE:
kcr_remove(*ARG.id);
break;
default:
error = EINVAL;
break;
}
return (error);
}
int
bdsdev_write(struct cdev *dev, struct uio *uio, int ioflag)
{
return(ENOTSUP);
}
int
bdsdev_read(struct cdev *dev, struct uio *uio, int ioflag)
{
return(ENOTSUP);
}
/*-------------------------------------------------------------------
* Module
*/
static struct cdevsw bds_bdsdevsw = {
.d_version = D_VERSION,
.d_open = bdsdev_open,
.d_close = bdsdev_close,
.d_read = bdsdev_read,
.d_write = bdsdev_write,
.d_ioctl = bdsdev_ioctl,
.d_name = "bds"
};
static struct cdev *sdev;
static int
bdsdev_load(module_t mod, int cmd, void *arg)
{
int err = 0;
switch (cmd) {
case MOD_LOAD:
hash_init(&citizen_registry);
sdev = make_dev(&bds_bdsdevsw, 0, UID_ROOT, GID_WHEEL, 0600, "bds");
break;
case MOD_UNLOAD:
kcr_reset();
destroy_dev(sdev);
break;
default:
err = EOPNOTSUPP;
break;
}
return(err);
}
DEV_MODULE(bdsdev, bdsdev_load, NULL);
bdsm/example1/dev/hash_support.c 000755 001751 001750 00000003744 10645026050 020035 0 ustar 00wieczyk konta 000000 000000 /*-
* Copyright (c) 2007 Pawel Wieczorek <wieczyk@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.
*
*/
#include <sys/param.h>
#include <sys/queue.h>
#include "sys/bds.h"
#include "kbds.h"
static unsigned int key_id_hash( const struct key_id *k );
static int key_id_cmp( const struct key_id *k1, const struct key_id *k2 );
static void key_id_cp( struct key_id *dst, const struct key_id *src );
static unsigned int
key_id_hash( const struct key_id *k )
{
return(k->id);
}
static int
key_id_cmp( const struct key_id *k1, const struct key_id *k2 )
{
return( k1->id == k2->id );
}
static void
key_id_cp( struct key_id *dst, const struct key_id *src )
{
dst->id = src->id;
}
void
hash_init( struct citizen_registry *h )
{
MAP_INIT(h,key_id_hash,key_id_cmp,key_id_cp);
}
bdsm/example1/dev/kbds.h 000755 001751 001750 00000003662 10645124631 016251 0 ustar 00wieczyk konta 000000 000000 /*-
* Copyright (c) 2007 Pawel Wieczorek <wieczyk@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 K_BDS_H
#define K_BDS_H
struct key_id {
int id;
};
#define FIRST_MAX 100
#define LAST_MAX 100
struct kperson {
int id;
char first[FIRST_MAX];
char last[FIRST_MAX];
MAP_ENTRY(kperson,key_id) citreg_entry;
};
#define BDSIOSPERSON _IOWR('p', 1, struct kperson)
#define BDSIOGPERSON _IOWR('p', 2, struct kperson)
#define BDSIOCKPRINT _IO('c',3)
#define BDSIOCKRESET _IO('c',4)
#define BDSIOCREMOVE _IOW('p',5,int)
#ifdef _KERNEL
/* Kernel world, kernel citizens ]=;] */
MAP_HEAD( citizen_registry, kperson, 13 );
void hash_init( struct citizen_registry *h );
#endif /* _KERNEL */
#endif /* K_BDS_H */
bdsm/example0/Makefile 000755 001751 001750 00000000132 10645124336 016025 0 ustar 00wieczyk konta 000000 000000 CC=cc
PROG=example0
SRCS=main.c hash_support.c
CFLAGS= -I..
MAN=
.include<bsd.prog.mk>
bdsm/example0/main.c 000755 001751 001750 00000015601 10645122730 015460 0 ustar 00wieczyk konta 000000 000000 /*-
* Copyright (c) 2007 Pawel Wieczorek <wieczyk@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.
*
*/
#include <sys/queue.h>
#include "sys/bds.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "example0.h"
struct workers_by_id wrks_by_id;
struct workers_by_last wrks_by_last;
/*===================================================================
* Data management routines
*/
static void
worker_add( struct worker *worker )
{
static int _key = 0x1234;
struct key_id kid;
struct key_last klast;
worker->id = _key++;
kid.id = worker->id;
MAP_INSERT(&wrks_by_id, &kid, worker, hash_by_id );
strcpy(klast.last,worker->last);
MMAP_INSERT(&wrks_by_last,&klast, worker, hash_by_last );
}
static struct worker *
worker_lookup( int id )
{
struct worker *worker;
struct key_id k;
k.id = id;
MAP_LOOKUP(&wrks_by_id, &k, worker, hash_by_id );
return (worker);
}
static int
worker_remove_by_last( const char * last )
{
struct worker *worker;
struct key_last klast;
strcpy(klast.last,last);
MMAP_LOOKUP_FOREACH_SAFE( &wrks_by_last, &klast, worker, hash_by_last ) {
MAP_REMOVE(&wrks_by_id,worker,worker,hash_by_id );
MMAP_REMOVE(&wrks_by_last,worker,worker,hash_by_last);
printf("%.4u %-15s %-15s %.2u %-15s\n",worker->id,worker->first,worker->last,worker->age,worker->city);
}
return(0);
}
static int
worker_remove( int id )
{
struct worker *worker;
worker = worker_lookup( id );
if ( worker == NULL ) return(-1);
MAP_REMOVE(&wrks_by_id,worker,worker,hash_by_id );
MMAP_REMOVE(&wrks_by_last,worker,worker,hash_by_last);
free(worker);
return(1);
}
static void
worker_list_by_last(const char *last)
{
struct worker *worker;
struct key_last klast;
strcpy(klast.last,last);
MMAP_LOOKUP_FOREACH( &wrks_by_last, &klast, worker, hash_by_last) {
printf("%.4u %-15s %-15s %.2u %-15s\n",worker->id,worker->first,worker->last,worker->age,worker->city);
}
}
static void
worker_list()
{
struct worker *worker;
MAP_FOREACH( worker, &wrks_by_id, hash_by_id) {
printf("%.4u %-15s %-15s %.2u %-15s\n",worker->id,worker->first,worker->last,worker->age,worker->city);
}
}
/*===================================================================
* User interface handlers
*/
static int __get(char *k,char *data, int len);
#define __GET( kom, d, l ) if (__get(kom,d,l) ) return;
static void ui_insert();
static void ui_select_id();
static int
__get(char *k,char *data, int len)
{
int n;
printf("%s: ",k);
fflush(stdout);
data[0] = 0;
fpurge(stdin);
if ( fgets(data,len,stdin) == NULL ) return(1);
n = strlen(data);
if ( n > 1 )
data[n-1] = 0;
return(0);
}
static void
ui_list()
{
worker_list();
}
static void
ui_select_id()
{
struct worker *worker;
char id[10];
int _id;
__GET("ID",id,sizeof(id));
_id = strtol(id,NULL,10);
worker = worker_lookup(_id);
if ( worker == NULL ) {
printf("Error: cannot find worker with id %.4u\n",_id);
return;
}
printf("Found: %.4u %-15s %-15s %.2u %-15s\n",worker->id,worker->first,worker->last,worker->age,worker->city);
}
static void
ui_select_last()
{
char last[LAST_MAX];
__GET("Last",last,sizeof(last));
worker_list_by_last(last);
}
static void
ui_remove_id()
{
char id[10];
int _id;
__GET("ID",id,sizeof(id));
_id = strtol(id,NULL,10);
if ( worker_remove(_id) ) {
printf("Error: no user with this id\n");
} else {
printf("Removed\n");
}
}
static void
ui_remove_last()
{
char last[LAST_MAX];
__GET("Last",last,sizeof(last));
worker_remove_by_last(last);
}
static void
ui_insert()
{
struct worker *worker;
struct worker temp;
char age[10];
puts("==> Adding new worker into memory");
__GET("First name",temp.first,sizeof(temp.first));
__GET("Last name",temp.last,sizeof(temp.last));
__GET("Age",age,sizeof(age));
__GET("City",temp.city,sizeof(temp.city));
temp.age = strtol(age,NULL,10);
worker = (struct worker*) malloc( sizeof(*worker));
memcpy(worker,&temp,sizeof(*worker));
worker_add(worker);
printf("Added with id %.4u\n",worker->id);
}
/*===================================================================
* Main menu
*/
enum option_v {
OP_INVALID,
OP_QUIT,
OP_INSERT,
OP_LIST,
OP_SELECT_ID,
OP_SELECT_LAST,
OP_REMOVE_ID,
OP_REMOVE_LAST
};
struct option {
const char *text;
enum option_v value;
};
static enum option_v find_option(char c);
static enum option_v get_option_from_user(void);
struct option options[] = {
{ "Quit", OP_QUIT },
{ "Insert new person to memory", OP_INSERT },
{ "List persons from memort", OP_LIST },
{ "Check person ID", OP_SELECT_ID },
{ "Show persons by last name", OP_SELECT_LAST },
{ "Remove by ID", OP_REMOVE_ID },
{ "Remove by last", OP_REMOVE_LAST },
{ NULL, OP_INVALID },
};
static enum option_v
find_option(char c)
{
struct option *op = options;
while ( op->text && c-- ) {
op++;
}
return (op->value);
}
static enum option_v
get_option_from_user()
{
char c;
fpurge(stdin);
c = fgetc(stdin) - '0';
if ( feof(stdin) ) {
return (OP_QUIT);
}
return (find_option(c));
}
static int
main_menu()
{
int i;
int r = 1;
struct option *op = options;
printf("-----\n");
for (i = 0; op->text; i++,op++ ) {
printf(" - %.1u %s\n",i,op->text);
}
printf("\nPress option number key and hit enter: ");
switch ( get_option_from_user() ) {
case OP_QUIT:
r = 0;
break;
case OP_INSERT:
ui_insert();
break;
case OP_LIST:
ui_list();
break;
case OP_SELECT_ID:
ui_select_id();
break;
case OP_SELECT_LAST:
ui_select_last();
break;
case OP_INVALID:
break;
case OP_REMOVE_ID:
ui_remove_id();
break;
case OP_REMOVE_LAST:
ui_remove_last();
break;
}
return (r);
}
int
main()
{
id_hash_init(&wrks_by_id);
last_hash_init(&wrks_by_last);
while ( main_menu() );
return (0);
}
bdsm/example0/hash_support.c 000755 001751 001750 00000004473 10645001315 017253 0 ustar 00wieczyk konta 000000 000000 /*-
* Copyright (c) 2007 Pawel Wieczorek <wieczyk@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.
*
*/
#include <sys/queue.h>
#include "sys/bds.h"
#include <stdio.h>
#include <string.h>
#include "example0.h"
static unsigned int
key_id_hash( const struct key_id *k )
{
return(k->id);
}
static int
key_id_cmp( const struct key_id *k1, const struct key_id *k2 )
{
return( k1->id == k2->id );
}
static void
key_id_cp( struct key_id *dst, const struct key_id *src )
{
dst->id = src->id;
}
void
id_hash_init( struct workers_by_id *hash )
{
MAP_INIT(hash,key_id_hash,key_id_cmp,key_id_cp);
}
static unsigned int
key_last_hash( const struct key_last *k )
{
int h = 29;
const char *p;
for ( p = k->last; *p != '\0'; p++ ) {
h += *p;
}
return (h);
}
static int
key_last_cmp( const struct key_last *k1, const struct key_last *k2 )
{
return (strcasecmp(k1->last,k2->last) == 0);
}
static void
key_last_cp( struct key_last *dst, const struct key_last *src )
{
strcpy(dst->last,src->last);
}
void
last_hash_init( struct workers_by_last *hash )
{
MMAP_INIT(hash,key_last_hash,key_last_cmp,key_last_cp);
}
bdsm/example0/example0.h 000755 001751 001750 00000003630 10644771317 016265 0 ustar 00wieczyk konta 000000 000000 /*-
* Copyright (c) 2007 Pawel Wieczorek <wieczyk@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 EXAMPLE_0
#define EXAMPLE_0
#define PRIME_NUMBER 13
#define FIRST_MAX 120
#define LAST_MAX 120
#define CITY_MAX 120
struct key_id {
int id;
};
struct key_last {
char last[LAST_MAX];
};
struct worker {
int id;
char first[FIRST_MAX];
char last[LAST_MAX];
int age;
char city[CITY_MAX];
MAP_ENTRY(worker,key_id) hash_by_id;
MMAP_ENTRY(worker,key_last) hash_by_last;
};
MAP_HEAD(workers_by_id,worker,PRIME_NUMBER);
MMAP_HEAD(workers_by_last,worker,PRIME_NUMBER);
void id_hash_init( struct workers_by_id *table );
void last_hash_init( struct workers_by_last *table );
#endif
bdsm/sys/bds.h 000755 001751 001750 00000022703 10645124724 014422 0 ustar 00wieczyk konta 000000 000000 /*-
* Copyright (c) 2007 Pawel Wieczorek <wieczyk@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 */
[-- Attachment #3 --]
/*-
* Copyright (c) 2007 Pawel Wieczorek <wieczyk@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 */
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?4694AC5C.9040107>