diff options
| -rw-r--r-- | libavutil/crc.c | 73 | ||||
| -rw-r--r-- | libavutil/lfg.c | 34 | ||||
| -rw-r--r-- | libavutil/log.c | 82 | ||||
| -rw-r--r-- | libavutil/random_seed.c | 28 | ||||
| -rw-r--r-- | libavutil/rational.c | 110 | ||||
| -rw-r--r-- | libavutil/tree.c | 196 |
6 files changed, 287 insertions, 236 deletions
diff --git a/libavutil/crc.c b/libavutil/crc.c index 44719ffaee..ee925d6b8a 100644 --- a/libavutil/crc.c +++ b/libavutil/crc.c @@ -56,32 +56,34 @@ static AVCRC av_crc_table[AV_CRC_MAX][257]; * @param ctx_size size of ctx in bytes * @return <0 on failure */ -int av_crc_init(AVCRC *ctx, int le, int bits, uint32_t poly, int ctx_size){ +int av_crc_init(AVCRC *ctx, int le, int bits, uint32_t poly, int ctx_size) +{ unsigned i, j; uint32_t c; - if (bits < 8 || bits > 32 || poly >= (1LL<<bits)) + if (bits < 8 || bits > 32 || poly >= (1LL << bits)) return -1; - if (ctx_size != sizeof(AVCRC)*257 && ctx_size != sizeof(AVCRC)*1024) + if (ctx_size != sizeof(AVCRC) * 257 && ctx_size != sizeof(AVCRC) * 1024) return -1; for (i = 0; i < 256; i++) { if (le) { for (c = i, j = 0; j < 8; j++) - c = (c>>1)^(poly & (-(c&1))); + c = (c >> 1) ^ (poly & (-(c & 1))); ctx[i] = c; } else { for (c = i << 24, j = 0; j < 8; j++) - c = (c<<1) ^ ((poly<<(32-bits)) & (((int32_t)c)>>31) ); + c = (c << 1) ^ ((poly << (32 - bits)) & (((int32_t) c) >> 31)); ctx[i] = av_bswap32(c); } } - ctx[256]=1; + ctx[256] = 1; #if !CONFIG_SMALL - if(ctx_size >= sizeof(AVCRC)*1024) + if (ctx_size >= sizeof(AVCRC) * 1024) for (i = 0; i < 256; i++) - for(j=0; j<3; j++) - ctx[256*(j+1) + i]= (ctx[256*j + i]>>8) ^ ctx[ ctx[256*j + i]&0xFF ]; + for (j = 0; j < 3; j++) + ctx[256 *(j + 1) + i] = + (ctx[256 * j + i] >> 8) ^ ctx[ctx[256 * j + i] & 0xFF]; #endif return 0; @@ -92,9 +94,10 @@ int av_crc_init(AVCRC *ctx, int le, int bits, uint32_t poly, int ctx_size){ * @param crc_id ID of a standard CRC * @return a pointer to the CRC table or NULL on failure */ -const AVCRC *av_crc_get_table(AVCRCId crc_id){ +const AVCRC *av_crc_get_table(AVCRCId crc_id) +{ #if !CONFIG_HARDCODED_TABLES - if (!av_crc_table[crc_id][FF_ARRAY_ELEMS(av_crc_table[crc_id])-1]) + if (!av_crc_table[crc_id][FF_ARRAY_ELEMS(av_crc_table[crc_id]) - 1]) if (av_crc_init(av_crc_table[crc_id], av_crc_table_params[crc_id].le, av_crc_table_params[crc_id].bits, @@ -112,46 +115,50 @@ const AVCRC *av_crc_get_table(AVCRCId crc_id){ * * @see av_crc_init() "le" parameter */ -uint32_t av_crc(const AVCRC *ctx, uint32_t crc, const uint8_t *buffer, size_t length){ - const uint8_t *end= buffer+length; +uint32_t av_crc(const AVCRC *ctx, uint32_t crc, + const uint8_t *buffer, size_t length) +{ + const uint8_t *end = buffer + length; #if !CONFIG_SMALL - if(!ctx[256]) { - while(((intptr_t) buffer & 3) && buffer < end) - crc = ctx[((uint8_t)crc) ^ *buffer++] ^ (crc >> 8); + if (!ctx[256]) { + while (((intptr_t) buffer & 3) && buffer < end) + crc = ctx[((uint8_t) crc) ^ *buffer++] ^ (crc >> 8); - while(buffer<end-3){ - crc ^= av_le2ne32(*(const uint32_t*)buffer); buffer+=4; - crc = ctx[3*256 + ( crc &0xFF)] - ^ctx[2*256 + ((crc>>8 )&0xFF)] - ^ctx[1*256 + ((crc>>16)&0xFF)] - ^ctx[0*256 + ((crc>>24) )]; + while (buffer < end - 3) { + crc ^= av_le2ne32(*(const uint32_t *) buffer); buffer += 4; + crc = ctx[3 * 256 + ( crc & 0xFF)] ^ + ctx[2 * 256 + ((crc >> 8 ) & 0xFF)] ^ + ctx[1 * 256 + ((crc >> 16) & 0xFF)] ^ + ctx[0 * 256 + ((crc >> 24) )]; } } #endif - while(buffer<end) - crc = ctx[((uint8_t)crc) ^ *buffer++] ^ (crc >> 8); + while (buffer < end) + crc = ctx[((uint8_t) crc) ^ *buffer++] ^ (crc >> 8); return crc; } #ifdef TEST #undef printf -int main(void){ +int main(void) +{ uint8_t buf[1999]; int i; - int p[4][3]={{AV_CRC_32_IEEE_LE, 0xEDB88320, 0x3D5CDD04}, - {AV_CRC_32_IEEE , 0x04C11DB7, 0xC0F5BAE0}, - {AV_CRC_16_ANSI , 0x8005, 0x1FBB }, - {AV_CRC_8_ATM , 0x07, 0xE3 },}; + int p[4][3] = { { AV_CRC_32_IEEE_LE, 0xEDB88320, 0x3D5CDD04 }, + { AV_CRC_32_IEEE , 0x04C11DB7, 0xC0F5BAE0 }, + { AV_CRC_16_ANSI , 0x8005 , 0x1FBB }, + { AV_CRC_8_ATM , 0x07 , 0xE3 } + }; const AVCRC *ctx; - for(i=0; i<sizeof(buf); i++) - buf[i]= i+i*i; + for (i = 0; i < sizeof(buf); i++) + buf[i] = i + i * i; - for(i=0; i<4; i++){ + for (i = 0; i < 4; i++) { ctx = av_crc_get_table(p[i][0]); - printf("crc %08X =%X\n", p[i][1], av_crc(ctx, 0, buf, sizeof(buf))); + printf("crc %08X = %X\n", p[i][1], av_crc(ctx, 0, buf, sizeof(buf))); } return 0; } diff --git a/libavutil/lfg.c b/libavutil/lfg.c index 7fab806f8c..227af68993 100644 --- a/libavutil/lfg.c +++ b/libavutil/lfg.c @@ -27,19 +27,21 @@ #include "intreadwrite.h" #include "attributes.h" -void av_cold av_lfg_init(AVLFG *c, unsigned int seed){ - uint8_t tmp[16]={0}; +void av_cold av_lfg_init(AVLFG *c, unsigned int seed) +{ + uint8_t tmp[16] = { 0 }; int i; - for(i=8; i<64; i+=4){ - AV_WL32(tmp, seed); tmp[4]=i; - av_md5_sum(tmp, tmp, 16); - c->state[i ]= AV_RL32(tmp); - c->state[i+1]= AV_RL32(tmp+4); - c->state[i+2]= AV_RL32(tmp+8); - c->state[i+3]= AV_RL32(tmp+12); + for (i = 8; i < 64; i += 4) { + AV_WL32(tmp, seed); + tmp[4] = i; + av_md5_sum(tmp, tmp, 16); + c->state[i ] = AV_RL32(tmp); + c->state[i + 1] = AV_RL32(tmp + 4); + c->state[i + 2] = AV_RL32(tmp + 8); + c->state[i + 3] = AV_RL32(tmp + 12); } - c->index=0; + c->index = 0; } void av_bmg_get(AVLFG *lfg, double out[2]) @@ -47,9 +49,9 @@ void av_bmg_get(AVLFG *lfg, double out[2]) double x1, x2, w; do { - x1 = 2.0/UINT_MAX*av_lfg_get(lfg) - 1.0; - x2 = 2.0/UINT_MAX*av_lfg_get(lfg) - 1.0; - w = x1*x1 + x2*x2; + x1 = 2.0 / UINT_MAX * av_lfg_get(lfg) - 1.0; + x2 = 2.0 / UINT_MAX * av_lfg_get(lfg) - 1.0; + w = x1 * x1 + x2 * x2; } while (w >= 1.0); w = sqrt((-2.0 * log(w)) / w); @@ -63,7 +65,7 @@ void av_bmg_get(AVLFG *lfg, double out[2]) int main(void) { - int x=0; + int x = 0; int i, j; AVLFG state; @@ -71,8 +73,8 @@ int main(void) for (j = 0; j < 10000; j++) { START_TIMER for (i = 0; i < 624; i++) { -// av_log(NULL,AV_LOG_ERROR, "%X\n", av_lfg_get(&state)); - x+=av_lfg_get(&state); + //av_log(NULL, AV_LOG_ERROR, "%X\n", av_lfg_get(&state)); + x += av_lfg_get(&state); } STOP_TIMER("624 calls of av_lfg_get"); } diff --git a/libavutil/log.c b/libavutil/log.c index 4d2b539dee..2969355969 100644 --- a/libavutil/log.c +++ b/libavutil/log.c @@ -35,104 +35,116 @@ static int flags; #if defined(_WIN32) && !defined(__MINGW32CE__) #include <windows.h> -static const uint8_t color[] = {12,12,12,14,7,7,7}; +static const uint8_t color[] = { 12, 12, 12, 14, 7, 7, 7 }; static int16_t background, attr_orig; static HANDLE con; #define set_color(x) SetConsoleTextAttribute(con, background | color[x]) #define reset_color() SetConsoleTextAttribute(con, attr_orig) #else -static const uint8_t color[]={0x41,0x41,0x11,0x03,9,9,9}; -#define set_color(x) fprintf(stderr, "\033[%d;3%dm", color[x]>>4, color[x]&15) +static const uint8_t color[] = { 0x41, 0x41, 0x11, 0x03, 9, 9, 9 }; +#define set_color(x) fprintf(stderr, "\033[%d;3%dm", color[x] >> 4, color[x]&15) #define reset_color() fprintf(stderr, "\033[0m") #endif -static int use_color=-1; +static int use_color = -1; #undef fprintf -static void colored_fputs(int level, const char *str){ - if(use_color<0){ +static void colored_fputs(int level, const char *str) +{ + if (use_color < 0) { #if defined(_WIN32) && !defined(__MINGW32CE__) CONSOLE_SCREEN_BUFFER_INFO con_info; con = GetStdHandle(STD_ERROR_HANDLE); - use_color = (con != INVALID_HANDLE_VALUE) && !getenv("NO_COLOR") && !getenv("AV_LOG_FORCE_NOCOLOR"); + use_color = (con != INVALID_HANDLE_VALUE) && !getenv("NO_COLOR") && + !getenv("AV_LOG_FORCE_NOCOLOR"); if (use_color) { GetConsoleScreenBufferInfo(con, &con_info); attr_orig = con_info.wAttributes; background = attr_orig & 0xF0; } #elif HAVE_ISATTY - use_color= !getenv("NO_COLOR") && !getenv("AV_LOG_FORCE_NOCOLOR") && - (getenv("TERM") && isatty(2) || getenv("AV_LOG_FORCE_COLOR")); + use_color = !getenv("NO_COLOR") && !getenv("AV_LOG_FORCE_NOCOLOR") && + (getenv("TERM") && isatty(2) || + getenv("AV_LOG_FORCE_COLOR")); #else - use_color= getenv("AV_LOG_FORCE_COLOR") && !getenv("NO_COLOR") && !getenv("AV_LOG_FORCE_NOCOLOR"); + use_color = getenv("AV_LOG_FORCE_COLOR") && !getenv("NO_COLOR") && + !getenv("AV_LOG_FORCE_NOCOLOR"); #endif } - if(use_color){ + if (use_color) { set_color(level); } fputs(str, stderr); - if(use_color){ + if (use_color) { reset_color(); } } -const char* av_default_item_name(void* ptr){ - return (*(AVClass**)ptr)->class_name; +const char *av_default_item_name(void *ptr) +{ + return (*(AVClass **) ptr)->class_name; } void av_log_default_callback(void* ptr, int level, const char* fmt, va_list vl) { - static int print_prefix=1; + static int print_prefix = 1; static int count; static char prev[1024]; char line[1024]; static int is_atty; - AVClass* avc= ptr ? *(AVClass**)ptr : NULL; - if(level>av_log_level) + AVClass* avc = ptr ? *(AVClass **) ptr : NULL; + if (level > av_log_level) return; - line[0]=0; + line[0] = 0; #undef fprintf - if(print_prefix && avc) { + if (print_prefix && avc) { if (avc->parent_log_context_offset) { - AVClass** parent= *(AVClass***)(((uint8_t*)ptr) + avc->parent_log_context_offset); - if(parent && *parent){ - snprintf(line, sizeof(line), "[%s @ %p] ", (*parent)->item_name(parent), parent); + AVClass** parent = *(AVClass ***) (((uint8_t *) ptr) + + avc->parent_log_context_offset); + if (parent && *parent) { + snprintf(line, sizeof(line), "[%s @ %p] ", + (*parent)->item_name(parent), parent); } } - snprintf(line + strlen(line), sizeof(line) - strlen(line), "[%s @ %p] ", avc->item_name(ptr), ptr); + snprintf(line + strlen(line), sizeof(line) - strlen(line), "[%s @ %p] ", + avc->item_name(ptr), ptr); } vsnprintf(line + strlen(line), sizeof(line) - strlen(line), fmt, vl); - print_prefix = strlen(line) && line[strlen(line)-1] == '\n'; + print_prefix = strlen(line) && line[strlen(line) - 1] == '\n'; #if HAVE_ISATTY - if(!is_atty) is_atty= isatty(2) ? 1 : -1; + if (!is_atty) + is_atty = isatty(2) ? 1 : -1; #endif - if(print_prefix && (flags & AV_LOG_SKIP_REPEATED) && !strncmp(line, prev, sizeof line)){ + if (print_prefix && (flags & AV_LOG_SKIP_REPEATED) && + !strncmp(line, prev, sizeof line)) { count++; - if(is_atty==1) + if (is_atty == 1) fprintf(stderr, " Last message repeated %d times\r", count); return; } - if(count>0){ + if (count > 0) { fprintf(stderr, " Last message repeated %d times\n", count); - count=0; + count = 0; } - colored_fputs(av_clip(level>>3, 0, 6), line); + colored_fputs(av_clip(level >> 3, 0, 6), line); av_strlcpy(prev, line, sizeof line); } -static void (*av_log_callback)(void*, int, const char*, va_list) = av_log_default_callback; +static void (*av_log_callback)(void*, int, const char*, va_list) = + av_log_default_callback; void av_log(void* avcl, int level, const char *fmt, ...) { - AVClass* avc= avcl ? *(AVClass**)avcl : NULL; + AVClass* avc = avcl ? *(AVClass **) avcl : NULL; va_list vl; va_start(vl, fmt); - if(avc && avc->version >= (50<<16 | 15<<8 | 2) && avc->log_level_offset_offset && level>=AV_LOG_FATAL) - level += *(int*)(((uint8_t*)avcl) + avc->log_level_offset_offset); + if (avc && avc->version >= (50 << 16 | 15 << 8 | 2) && + avc->log_level_offset_offset && level >= AV_LOG_FATAL) + level += *(int *) (((uint8_t *) avcl) + avc->log_level_offset_offset); av_vlog(avcl, level, fmt, vl); va_end(vl); } @@ -154,7 +166,7 @@ void av_log_set_level(int level) void av_log_set_flags(int arg) { - flags= arg; + flags = arg; } void av_log_set_callback(void (*callback)(void*, int, const char*, va_list)) diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c index ee71542652..51ca99b26d 100644 --- a/libavutil/random_seed.c +++ b/libavutil/random_seed.c @@ -40,24 +40,24 @@ static int read_random(uint32_t *dst, const char *file) static uint32_t get_generic_seed(void) { - clock_t last_t=0; - int bits=0; - uint64_t random=0; + clock_t last_t = 0; + int bits = 0; + uint64_t random = 0; unsigned i; - float s=0.000000000001; + float s = 0.000000000001; - for(i=0;bits<64;i++){ - clock_t t= clock(); - if(last_t && fabs(t-last_t)>s || t==(clock_t)-1){ - if(i<10000 && s<(1<<24)){ - s+=s; - i=t=0; - }else{ - random= 2*random + (i&1); + for (i = 0; bits < 64; i++) { + clock_t t = clock(); + if (last_t && fabs(t - last_t) > s || t == (clock_t) -1) { + if (i < 10000 && s < (1 << 24)) { + s += s; + i = t = 0; + } else { + random = 2 * random + (i & 1); bits++; } } - last_t= t; + last_t = t; } #ifdef AV_READ_TIME random ^= AV_READ_TIME(); @@ -65,7 +65,7 @@ static uint32_t get_generic_seed(void) random ^= clock(); #endif - random += random>>32; + random += random >> 32; return random; } diff --git a/libavutil/rational.c b/libavutil/rational.c index ac5111b896..3e62e1b0fd 100644 --- a/libavutil/rational.c +++ b/libavutil/rational.c @@ -33,75 +33,86 @@ #include "mathematics.h" #include "rational.h" -int av_reduce(int *dst_num, int *dst_den, int64_t num, int64_t den, int64_t max){ - AVRational a0={0,1}, a1={1,0}; - int sign= (num<0) ^ (den<0); - int64_t gcd= av_gcd(FFABS(num), FFABS(den)); - - if(gcd){ - num = FFABS(num)/gcd; - den = FFABS(den)/gcd; +int av_reduce(int *dst_num, int *dst_den, + int64_t num, int64_t den, int64_t max) +{ + AVRational a0 = { 0, 1 }, a1 = { 1, 0 }; + int sign = (num < 0) ^ (den < 0); + int64_t gcd = av_gcd(FFABS(num), FFABS(den)); + + if (gcd) { + num = FFABS(num) / gcd; + den = FFABS(den) / gcd; } - if(num<=max && den<=max){ - a1= (AVRational){num, den}; - den=0; + if (num <= max && den <= max) { + a1 = (AVRational) { num, den }; + den = 0; } - while(den){ - uint64_t x = num / den; - int64_t next_den= num - den*x; - int64_t a2n= x*a1.num + a0.num; - int64_t a2d= x*a1.den + a0.den; + while (den) { + uint64_t x = num / den; + int64_t next_den = num - den * x; + int64_t a2n = x * a1.num + a0.num; + int64_t a2d = x * a1.den + a0.den; - if(a2n > max || a2d > max){ - if(a1.num) x= (max - a0.num) / a1.num; - if(a1.den) x= FFMIN(x, (max - a0.den) / a1.den); + if (a2n > max || a2d > max) { + if (a1.num) x = (max - a0.num) / a1.num; + if (a1.den) x = FFMIN(x, (max - a0.den) / a1.den); - if (den*(2*x*a1.den + a0.den) > num*a1.den) - a1 = (AVRational){x*a1.num + a0.num, x*a1.den + a0.den}; + if (den * (2 * x * a1.den + a0.den) > num * a1.den) + a1 = (AVRational) { x * a1.num + a0.num, x * a1.den + a0.den }; break; } - a0= a1; - a1= (AVRational){a2n, a2d}; - num= den; - den= next_den; + a0 = a1; + a1 = (AVRational) { a2n, a2d }; + num = den; + den = next_den; } av_assert2(av_gcd(a1.num, a1.den) <= 1U); *dst_num = sign ? -a1.num : a1.num; *dst_den = a1.den; - return den==0; + return den == 0; } -AVRational av_mul_q(AVRational b, AVRational c){ - av_reduce(&b.num, &b.den, b.num * (int64_t)c.num, b.den * (int64_t)c.den, INT_MAX); +AVRational av_mul_q(AVRational b, AVRational c) +{ + av_reduce(&b.num, &b.den, + b.num * (int64_t) c.num, + b.den * (int64_t) c.den, INT_MAX); return b; } -AVRational av_div_q(AVRational b, AVRational c){ - return av_mul_q(b, (AVRational){c.den, c.num}); +AVRational av_div_q(AVRational b, AVRational c) +{ + return av_mul_q(b, (AVRational) { c.den, c.num }); } -AVRational av_add_q(AVRational b, AVRational c){ - av_reduce(&b.num, &b.den, b.num * (int64_t)c.den + c.num * (int64_t)b.den, b.den * (int64_t)c.den, INT_MAX); +AVRational av_add_q(AVRational b, AVRational c) { + av_reduce(&b.num, &b.den, + b.num * (int64_t) c.den + + c.num * (int64_t) b.den, + b.den * (int64_t) c.den, INT_MAX); return b; } -AVRational av_sub_q(AVRational b, AVRational c){ - return av_add_q(b, (AVRational){-c.num, c.den}); +AVRational av_sub_q(AVRational b, AVRational c) +{ + return av_add_q(b, (AVRational) { -c.num, c.den }); } -AVRational av_d2q(double d, int max){ +AVRational av_d2q(double d, int max) +{ AVRational a; #define LOG2 0.69314718055994530941723212145817656807550013436025 int exponent; int64_t den; if (isnan(d)) - return (AVRational){0,0}; + return (AVRational) { 0,0 }; if (isinf(d)) - return (AVRational){ d<0 ? -1:1, 0 }; + return (AVRational) { d < 0 ? -1 : 1, 0 }; exponent = FFMAX( (int)(log(fabs(d) + 1e-20)/LOG2), 0); den = 1LL << (61 - exponent); av_reduce(&a.num, &a.den, (int64_t)(d * den + 0.5), den, max); @@ -127,7 +138,7 @@ int av_nearer_q(AVRational q, AVRational q1, AVRational q2) int av_find_nearest_q_idx(AVRational q, const AVRational* q_list) { int i, nearest_q_idx = 0; - for(i=0; q_list[i].den; i++) + for (i = 0; q_list[i].den; i++) if (av_nearer_q(q, q_list[i], q_list[nearest_q_idx]) > 0) nearest_q_idx = i; @@ -138,16 +149,19 @@ int av_find_nearest_q_idx(AVRational q, const AVRational* q_list) int main(void) { AVRational a,b; - for(a.num=-2; a.num<=2; a.num++){ - for(a.den=-2; a.den<=2; a.den++){ - for(b.num=-2; b.num<=2; b.num++){ - for(b.den=-2; b.den<=2; b.den++){ - int c= av_cmp_q(a,b); - double d= av_q2d(a) == av_q2d(b) ? 0 : (av_q2d(a) - av_q2d(b)); - if(d>0) d=1; - else if(d<0) d=-1; - else if(d != d) d= INT_MIN; - if(c!=d) av_log(0, AV_LOG_ERROR, "%d/%d %d/%d, %d %f\n", a.num, a.den, b.num, b.den, c,d); + for (a.num = -2; a.num <= 2; a.num++) { + for (a.den = -2; a.den <= 2; a.den++) { + for (b.num = -2; b.num <= 2; b.num++) { + for (b.den = -2; b.den <= 2; b.den++) { + int c = av_cmp_q(a,b); + double d = av_q2d(a) == av_q2d(b) ? + 0 : (av_q2d(a) - av_q2d(b)); + if (d > 0) d = 1; + else if (d < 0) d = -1; + else if (d != d) d = INT_MIN; + if (c != d) + av_log(0, AV_LOG_ERROR, "%d/%d %d/%d, %d %f\n", a.num, + a.den, b.num, b.den, c,d); } } } diff --git a/libavutil/tree.c b/libavutil/tree.c index 067e5b096e..e614f72cd8 100644 --- a/libavutil/tree.c +++ b/libavutil/tree.c @@ -21,22 +21,24 @@ #include "log.h" #include "tree.h" -typedef struct AVTreeNode{ +typedef struct AVTreeNode { struct AVTreeNode *child[2]; void *elem; int state; -}AVTreeNode; +} AVTreeNode; const int av_tree_node_size = sizeof(AVTreeNode); -void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){ - if(t){ - unsigned int v= cmp(key, t->elem); - if(v){ - if(next) next[v>>31]= t->elem; - return av_tree_find(t->child[(v>>31)^1], key, cmp, next); - }else{ - if(next){ +void *av_tree_find(const AVTreeNode *t, void *key, + int (*cmp)(void *key, const void *b), void *next[2]) +{ + if (t) { + unsigned int v = cmp(key, t->elem); + if (v) { + if (next) next[v >> 31] = t->elem; + return av_tree_find(t->child[(v >> 31) ^ 1], key, cmp, next); + } else { + if (next) { av_tree_find(t->child[0], key, cmp, next); av_tree_find(t->child[1], key, cmp, next); } @@ -46,41 +48,43 @@ void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const v return NULL; } -void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){ - AVTreeNode *t= *tp; - if(t){ - unsigned int v= cmp(t->elem, key); +void *av_tree_insert(AVTreeNode **tp, void *key, + int (*cmp)(void *key, const void *b), AVTreeNode **next) +{ + AVTreeNode *t = *tp; + if (t) { + unsigned int v = cmp(t->elem, key); void *ret; - if(!v){ - if(*next) + if (!v) { + if (*next) return t->elem; - else if(t->child[0]||t->child[1]){ - int i= !t->child[0]; + else if (t->child[0] || t->child[1]) { + int i = !t->child[0]; void *next_elem[2]; av_tree_find(t->child[i], key, cmp, next_elem); - key= t->elem= next_elem[i]; - v= -i; - }else{ - *next= t; - *tp=NULL; + key = t->elem = next_elem[i]; + v = -i; + } else { + *next = t; + *tp = NULL; return NULL; } } - ret= av_tree_insert(&t->child[v>>31], key, cmp, next); - if(!ret){ - int i= (v>>31) ^ !!*next; - AVTreeNode **child= &t->child[i]; - t->state += 2*i - 1; - - if(!(t->state&1)){ - if(t->state){ + ret = av_tree_insert(&t->child[v >> 31], key, cmp, next); + if (!ret) { + int i = (v >> 31) ^ !!*next; + AVTreeNode **child = &t->child[i]; + t->state += 2 * i - 1; + + if (!(t->state & 1)) { + if (t->state) { /* The following code is equivalent to if((*child)->state*2 == -t->state) rotate(child, i^1); rotate(tp, i); with rotate(): - static void rotate(AVTreeNode **tp, int i){ + static void rotate(AVTreeNode **tp, int i) { AVTreeNode *t= *tp; *tp= t->child[i]; @@ -92,54 +96,62 @@ void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const voi } but such a rotate function is both bigger and slower */ - if((*child)->state*2 == -t->state){ - *tp= (*child)->child[i^1]; - (*child)->child[i^1]= (*tp)->child[i]; - (*tp)->child[i]= *child; - *child= (*tp)->child[i^1]; - (*tp)->child[i^1]= t; - - (*tp)->child[0]->state= -((*tp)->state>0); - (*tp)->child[1]->state= (*tp)->state<0 ; - (*tp)->state=0; - }else{ - *tp= *child; - *child= (*child)->child[i^1]; - (*tp)->child[i^1]= t; - if((*tp)->state) t->state = 0; - else t->state>>= 1; - (*tp)->state= -t->state; + if (( *child )->state * 2 == -t->state) { + *tp = (*child)->child[i ^ 1]; + (*child)->child[i ^ 1] = (*tp)->child[i]; + (*tp)->child[i] = *child; + *child = ( *tp )->child[i ^ 1]; + (*tp)->child[i ^ 1] = t; + + (*tp)->child[0]->state = -((*tp)->state > 0); + (*tp)->child[1]->state = (*tp)->state < 0; + (*tp)->state = 0; + } else { + *tp = *child; + *child = (*child)->child[i ^ 1]; + (*tp)->child[i ^ 1] = t; + if ((*tp)->state) t->state = 0; + else t->state >>= 1; + (*tp)->state = -t->state; } } } - if(!(*tp)->state ^ !!*next) + if (!(*tp)->state ^ !!*next) return key; } return ret; - }else{ - *tp= *next; *next= NULL; - if(*tp){ - (*tp)->elem= key; + } else { + *tp = *next; + *next = NULL; + if (*tp) { + (*tp)->elem = key; return NULL; - }else + } else return key; } } -void av_tree_destroy(AVTreeNode *t){ - if(t){ +void av_tree_destroy(AVTreeNode *t) +{ + if (t) { av_tree_destroy(t->child[0]); av_tree_destroy(t->child[1]); av_free(t); } } -void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*cmp)(void *opaque, void *elem), int (*enu)(void *opaque, void *elem)){ - if(t){ - int v= cmp ? cmp(opaque, t->elem) : 0; - if(v>=0) av_tree_enumerate(t->child[0], opaque, cmp, enu); - if(v==0) enu(opaque, t->elem); - if(v<=0) av_tree_enumerate(t->child[1], opaque, cmp, enu); +void av_tree_enumerate(AVTreeNode *t, void *opaque, + int (*cmp)(void *opaque, void *elem), + int (*enu)(void *opaque, void *elem)) +{ + if (t) { + int v = cmp ? cmp(opaque, t->elem) : 0; + if (v >= 0) + av_tree_enumerate(t->child[0], opaque, cmp, enu); + if (v == 0) + enu(opaque, t->elem); + if (v <= 0) + av_tree_enumerate(t->child[1], opaque, cmp, enu); } } @@ -147,64 +159,68 @@ void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*cmp)(void *opaque, voi #include "lfg.h" -static int check(AVTreeNode *t){ - if(t){ - int left= check(t->child[0]); - int right= check(t->child[1]); +static int check(AVTreeNode *t) +{ + if (t) { + int left = check(t->child[0]); + int right = check(t->child[1]); - if(left>999 || right>999) + if (left>999 || right>999) return 1000; - if(right - left != t->state) + if (right - left != t->state) return 1000; - if(t->state>1 || t->state<-1) + if (t->state>1 || t->state<-1) return 1000; - return FFMAX(left, right)+1; + return FFMAX(left, right) + 1; } return 0; } -static void print(AVTreeNode *t, int depth){ +static void print(AVTreeNode *t, int depth) +{ int i; - for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " "); - if(t){ + for (i = 0; i < depth * 4; i++) av_log(NULL, AV_LOG_ERROR, " "); + if (t) { av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t->state, t->elem); - print(t->child[0], depth+1); - print(t->child[1], depth+1); - }else + print(t->child[0], depth + 1); + print(t->child[1], depth + 1); + } else av_log(NULL, AV_LOG_ERROR, "NULL\n"); } -static int cmp(void *a, const void *b){ - return (uint8_t*)a-(const uint8_t*)b; +static int cmp(void *a, const void *b) +{ + return (uint8_t *) a - (const uint8_t *) b; } -int main(void){ +int main (void) +{ int i; void *k; - AVTreeNode *root= NULL, *node=NULL; + AVTreeNode *root = NULL, *node = NULL; AVLFG prng; av_lfg_init(&prng, 1); - for(i=0; i<10000; i++){ + for (i = 0; i < 10000; i++) { int j = av_lfg_get(&prng) % 86294; - if(check(root) > 999){ + if (check(root) > 999) { av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i); print(root, 0); return -1; } av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j); - if(!node) - node= av_mallocz(av_tree_node_size); - av_tree_insert(&root, (void*)(j+1), cmp, &node); + if (!node) + node = av_mallocz(av_tree_node_size); + av_tree_insert(&root, (void *) (j + 1), cmp, &node); j = av_lfg_get(&prng) % 86294; { - AVTreeNode *node2=NULL; + AVTreeNode *node2 = NULL; av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j); - av_tree_insert(&root, (void*)(j+1), cmp, &node2); - k= av_tree_find(root, (void*)(j+1), cmp, NULL); - if(k) + av_tree_insert(&root, (void *) (j + 1), cmp, &node2); + k = av_tree_find(root, (void *) (j + 1), cmp, NULL); + if (k) av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i); } } |