mouse's Blog

mouse

分类

未分类

堆排序

/home/wuhao/projects/base64/heap.c

struct phy_heap {
	void **table;/* table[0] is the size of the table. */
	unsigned long length;
	void *(*alloc)(unsigned int);
	void  (*free)(void *);
	int	 (*compare)(void *,void*);
};
#define	PHY_IS_ROOT(i)	((i)==1)
#define	PHY_LCHILD(i)	(2*(i))
#define	PHY_RCHILD(i)	(2*(i)+1)
#define	PHY_PARENT(c)	((c)/2)
#define	PHY_HAS_LCHILD(i,len)	(PHY_LCHILD(i)<=len)
#define	PHY_HAS_RCHILD(i,len)	(PHY_RCHILD(i)<=len)
#define	PHY_CAPACITY(_heap)	((unsigned long)_heap->table[0])

#define	PHY_SWAP(p1,p2)	({void *tmp=(p1);(p1)=(p2);(p2)=tmp;})

struct phy_heap *phy_heap_init(unsigned long capacity,
			void *(*_alloc)(unsigned int),
			void  (*_free)(void *),
			int (*_compare)(void *, void *)){
	struct phy_heap *heap = _alloc(sizeof(struct phy_heap));
	if(!heap){
		goto out1;
	}
	heap->table		= _alloc(capacity*sizeof(void*));
	if(!heap->table){
		goto out2;
	}
	heap->length	= 0;
	heap->alloc		= _alloc;
	heap->free		= _free;
	heap->compare	= _compare;
	heap->table[0]	= (void *)capacity;
	return heap;
out2:
	_free(heap);
out1:
	return (void*)0;

}
void phy_heap_destroy(struct phy_heap *heap){
	heap->free(heap->table);
	heap->free(heap);
}
static void filterup(struct phy_heap *heap,unsigned int cur){
	unsigned int parent = PHY_PARENT(cur);
	while(!PHY_IS_ROOT(cur) &&
		heap->compare(heap->table[cur],heap->table[parent])<0){

		PHY_SWAP(heap->table[cur],heap->table[parent]);
		cur = parent;
		parent = PHY_PARENT(cur);
	}
}
static void filterdown(struct phy_heap *heap,unsigned int cur){
	while(PHY_HAS_LCHILD(cur,heap->length)){
		unsigned int l = PHY_LCHILD(cur);
		if(PHY_HAS_RCHILD(cur,heap->length)){
			/* heap has two children */
			
			unsigned int r = PHY_RCHILD(cur);
			unsigned int min_child = heap->compare(heap->table[l],	heap->table[r])<0
										? l	: r;
			if(heap->compare(heap->table[cur],heap->table[min_child])<=0){
				break;
			}
			PHY_SWAP(heap->table[cur],heap->table[min_child]);
			cur = min_child;
			continue;
		}
		/* here, the cur node has only one left child */
		if(heap->compare(heap->table[cur],heap->table[l])<=0){
			break;
		}
		PHY_SWAP(heap->table[cur],heap->table[l]);
		cur = l;			
	}
}
int phy_heap_add(struct phy_heap *heap,void *item){
	if(!heap){
		/* invalid point */
		return -1;
	}
	if(heap->length+2 >= PHY_CAPACITY(heap)){
		/* no room */
		return -2;
	}
	heap->table[++heap->length] = item;
	filterup(heap,heap->length);
	return 0;
}
int phy_heap_adds(struct phy_heap *heap,void **items, unsigned int size){
	unsigned int i=0;
	if(!heap){
		/* invalid point */
		return -1;
	}
	if(heap->length+size >= PHY_CAPACITY(heap)-1){
		/* no room */
		return -2;
	}
	while(i<size){
		heap->table[++heap->length]=items[i++];
		filterup(heap,heap->length);
	}
	return 0;
}

void *phy_heap_del(struct phy_heap *heap){
	void *val;
	if(!heap || heap->length<1){
		return (void *)0;
	}
	val = heap->table[1];
	heap->table[1] = heap->table[heap->length--];
	filterdown(heap,1);
	return val;
}

base64编解码--C语言

/** for some variable base64 code,
    just change the correspond macro.
*/
#define BASE64_62        '+'
#define BASE64_63        '/'
#define    BASE64_PAD_CHAR    '='

#define    BASE64_PADDING_CODE    64
#define BASE64_INVALID_CODE    128

/** ERRORS: */
#define    EB64_BAD_ARG    1
#define    EB64_BAD_CODE    2
    

const static unsigned char base64[] = {
    'A','B','C','D','E','F','G','H',
    'I','J','K','L','M','N','O','P',
    'Q','R','S','T','U','V','W','X',
    'Y','Z','a','b','c','d','e','f',
    'g','h','i','j','k','l','m','n',
    'o','p','q','r','s','t','u','v',
    'w','x','y','z','0','1','2','3',
    '4','5','6','7','8','9',BASE64_62,BASE64_63,
};

#ifdef    __GNUC__
unsigned char inline get_base64_index(unsigned char c){
    switch(c){
        case 'A'...'Z'    : return c-'A';
        case 'a'...'z'    : return c-'a'+26;
        case '0'...'9'    : return c-'0'+52;
        case BASE64_62        : return 62;
        case BASE64_63        : return 63;
        case BASE64_PAD_CHAR        : return BASE64_PADDING_CODE;
    }
    return BASE64_INVALID_CODE;
}
#else        
unsigned char inline get_base64_index(unsigned char c){
    if(c>='A' && c<='Z'){
        return c-'A';
    }
    if(c>='a' && c<='z'){
        return c-'a'+26;
    }
    if(c>='0' && c<='9'){
        return c-'0'+52;
    }
    if(c==BASE64_62){
        return 62;
    }
    if(c==BASE64_63){
        return 63;
    }
    if(c==BASE64_PAD_CHAR){
        return BASE64_PADDING_CODE;
    }
    return BASE64_INVALID_CODE;
}
#endif

int encode_base64(unsigned char *dst, unsigned long dlen, unsigned char *src, unsigned long slen){
    unsigned long z = (slen-1)/3 + 1;
    unsigned long i,j;
    if(!dst || !src || !slen || z * 4 > dlen){
        return -EB64_BAD_ARG;
    }
    z = (slen/3)*3;
    for(i=0,j=0; j<z; j=j+3){
        dst[i++] = base64[src[j]>>2];
        dst[i++] = base64[((src[j]<<4)&0x3f)|(src[j+1]>>4)];
        dst[i++] = base64[((src[j+1]<<2)&0x3f)|(src[j+2]>>6)];
        dst[i++] = base64[src[j+2]&0x3f];
    }
    z = slen % 3;
    if(!z){
        return i;
    }
    // z=1 or z=2
    dst[i++] = base64[src[j]>>2];
    dst[i++] = (z==1 ? base64[((src[j]<<4)&0x3f)] : base64[((src[j]<<4)&0x3f)|(src[j+1]>>4)]);
    dst[i++] = (unsigned char)(z==2 ? base64[((src[j+1]<<2)&0x3f)] : BASE64_PAD_CHAR);
    /* the last char must be padding, i.e. z always less than or equal to 2. */
    //dst[i++] = (unsigned char)(z>2 ? base64[src[j+2]&0x3f] : BASE64_PAD_CHAR);
    dst[i++]    = (unsigned char)BASE64_PAD_CHAR;
    return i;
}

int decode_base64(unsigned char *dst,  unsigned long dlen, unsigned char *src, unsigned long slen){
    unsigned long z = slen/4;
    unsigned long len = z*3;
    unsigned int i,j=0,k=0;
    unsigned char b1,b2,b3,b4;
    if(!dst || !src || slen%4 || dlen<len){
        /* invalid argument */
        return -EB64_BAD_ARG;
    }
    if(src[slen-1]==BASE64_PAD_CHAR){
        z=z-1;
    }
    for(i=0;i<z;i++){
        b1=get_base64_index(src[j++]);
        b2=get_base64_index(src[j++]);
        b3=get_base64_index(src[j++]);
        b4=get_base64_index(src[j++]);
        if((b1 | b2 | b3 | b4)>=BASE64_PADDING_CODE){
            /* invalid code */
            return -EB64_BAD_CODE;
        }
        dst[k++]    = (b1<<2)|(b2>>4);
        dst[k++]    = (b2<<4)|(b3>>2);
        dst[k++]    = ((b3<<6)&0xc0)|b4;    
    }
    if(src[len-1]!=BASE64_PAD_CHAR){
        return k;
    }
    b1=get_base64_index(src[j++]);
    b2=get_base64_index(src[j++]);
    b3=get_base64_index(src[j++]);
    b4=get_base64_index(src[j++]);
    /* check the last four characters:
        the first two character must be normal code;
        the third character can be either normal code or padding code, i.e. not invalid code;
        and the last character must be padding code, because the last source character indicate it.
     */
    if((b1 | b2)>=BASE64_PADDING_CODE || b3==BASE64_INVALID_CODE || b4!=BASE64_PADDING_CODE){ 
        /* invalid code */
        return -EB64_BAD_CODE;
    }
    /* there at least exist one code. */
    dst[k++]    = (b1<<2)|(b2>>4);
    if(b3 != BASE64_PADDING_CODE){ /* only one BASE64_PAD_CHAR */
        dst[k++]    = (b2<<4)|(b3>>2);
    }
    return k;

}

调试专用头文件

#ifndef	_PHY_DEBUG_H
#define	_PHY_DEBUG_H

#if defined(PHY_DEBUG)
	#if	defined(__KERNEL__)
		#include <linux/kernel.h>
		#define		phy_debug_print(a1,...)		printk(KERN_ALERT a1,##__VA_ARGS__)
		#define		PHY_ASSERT_BUGON(exp)	({if(!(exp)){\
						phy_debug_print("error: line %d, file %s  assertion failed\n",\
						__LINE__,__FILE__);return -1;}})
	#else /* user space, e.g. printf... */
		#include <stdio.h>
		#include <stdlib.h>
		#define		phy_debug_print(a1,...)		printf(a1,##__VA_ARGS__)
		#define		PHY_ASSERT_BUGON(exp)	({if(!(exp)){\
						phy_debug_print("error: line %d, file %s assertion failed\n",\
						__LINE__,__FILE__);\
						exit(1);}})

	#endif /* end __KERNEL__ */
#else /* not defined PHY_DEBUG, e.g. in userspace */
	#define		phy_debug_print(a1,...)
	#define		PHY_ASSERT_BUGON(exp)
#endif /* PHY_DEBUG */
#endif /* _PHY_DEBUG_H */