Bug#390694: [arm] Internal consistency failure while building OpenSER 1.1.0-3

[Julien BLACHE <jblache@debian.org>]

Package: gcc-4.1
Version: 4.1.1-13
Severity: important

Hi,

gcc-4.1 bails out with an error while build OpenSER 1.1.0-3 on arm, see
 <http://buildd.debian.org/fetch.php?&pkg=openser&ver=1.1.0-3%2Bb1&arch=arm&stamp=1159765150&file=log&as=raw>

I was able to reproduce the problem on leisner.d.o, using gcc-4.1 4.1.1-13
(the buildd used 4.1.1-14).

leisner% gcc -fPIC -DPIC -Wall -g -O2 -g -Wcast-align     -DNAME='"openser"' -DVERSION='"1.1.0-notls"' -DARCH='"arm"' -DOS='"linux"' -DCOMPILER='"gcc 4.1.2"' -D__CPU_arm -D__OS_linux -D__SMP_yes -DCFG_DIR='"/etc/openser/"' -DPKG_MALLOC -DSHM_MEM  -DSHM_MMAP -DUSE_IPV6 -DUSE_MCAST -DUSE_TCP -DDISABLE_NAGLE -DHAVE_RESOLV_RES -DF_MALLOC -DSTATISTICS  -DFAST_LOCK -DADAPTIVE_WAIT -DADAPTIVE_WAIT_LOOPS=1024  -DHAVE_GETHOSTBYNAME2 -DHAVE_UNION_SEMUN -DHAVE_SCHED_YIELD -DHAVE_MSG_NOSIGNAL -DHAVE_MSGHDR_MSG_CONTROL -DHAVE_ALLOCA_H -DHAVE_TIMEGM -DHAVE_SIGIO_RT -DHAVE_SELECT -DXJ_EXTRA_DEBUG -I/usr/local/include -c tree234.c -o tree234.o
In file included from ../../mem/../locking.h:66,
                 from ../../mem/../statistics.h:102,
                 from ../../mem/shm_mem.h:33,
                 from tree234.c:37:
../../mem/../lock_alloc.h: In function 'lock_set_alloc':
../../mem/../lock_alloc.h:70: warning: cast increases required alignment of target type
tree234.c: In function 'delpos234_internal':
tree234.c:927: fatal error: internal consistency failure
compilation terminated.
Preprocessed source stored into /tmp/ccqbPZpP.out file, please attach this to your bugreport.


The ccqbPZpP.out file is attached to this bugreport.

Note that the build succeeds when building at -O1 instead of -O2, so this
is probably an optimisation bug.

Thanks,

JB.

// /usr/lib/gcc/arm-linux-gnu/4.1.2/cc1 -quiet -I/usr/local/include -DPIC -DNAME="openser" -DVERSION="1.1.0-notls" -DARCH="arm" -DOS="linux" -DCOMPILER="gcc 4.1.2" -D__CPU_arm -D__OS_linux -D__SMP_yes -DCFG_DIR="/etc/openser/" -DPKG_MALLOC -DSHM_MEM -DSHM_MMAP -DUSE_IPV6 -DUSE_MCAST -DUSE_TCP -DDISABLE_NAGLE -DHAVE_RESOLV_RES -DF_MALLOC -DSTATISTICS -DFAST_LOCK -DADAPTIVE_WAIT -DADAPTIVE_WAIT_LOOPS=1024 -DHAVE_GETHOSTBYNAME2 -DHAVE_UNION_SEMUN -DHAVE_SCHED_YIELD -DHAVE_MSG_NOSIGNAL -DHAVE_MSGHDR_MSG_CONTROL -DHAVE_ALLOCA_H -DHAVE_TIMEGM -DHAVE_SIGIO_RT -DHAVE_SELECT -DXJ_EXTRA_DEBUG tree234.c -quiet -dumpbase tree234.c -auxbase-strip tree234.o -g -g -O2 -Wall -Wcast-align -fPIC -o - -frandom-seed=0
# 1 "tree234.c"
# 1 "/home/jblache/openser-1.1.0/modules/jabber//"
# 1 "<built-in>"
# 1 "<command line>"
# 1 "tree234.c"
# 32 "tree234.c"
# 1 "/usr/include/stdio.h" 1 3 4
# 28 "/usr/include/stdio.h" 3 4
# 1 "/usr/include/features.h" 1 3 4
# 308 "/usr/include/features.h" 3 4
# 1 "/usr/include/sys/cdefs.h" 1 3 4
# 309 "/usr/include/features.h" 2 3 4
# 331 "/usr/include/features.h" 3 4
# 1 "/usr/include/gnu/stubs.h" 1 3 4
# 332 "/usr/include/features.h" 2 3 4
# 29 "/usr/include/stdio.h" 2 3 4





# 1 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 1 3 4
# 214 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 3 4
typedef unsigned int size_t;
# 35 "/usr/include/stdio.h" 2 3 4

# 1 "/usr/include/bits/types.h" 1 3 4
# 28 "/usr/include/bits/types.h" 3 4
# 1 "/usr/include/bits/wordsize.h" 1 3 4
# 29 "/usr/include/bits/types.h" 2 3 4


# 1 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 1 3 4
# 32 "/usr/include/bits/types.h" 2 3 4


typedef unsigned char __u_char;
typedef unsigned short int __u_short;
typedef unsigned int __u_int;
typedef unsigned long int __u_long;


typedef signed char __int8_t;
typedef unsigned char __uint8_t;
typedef signed short int __int16_t;
typedef unsigned short int __uint16_t;
typedef signed int __int32_t;
typedef unsigned int __uint32_t;




__extension__ typedef signed long long int __int64_t;
__extension__ typedef unsigned long long int __uint64_t;







__extension__ typedef long long int __quad_t;
__extension__ typedef unsigned long long int __u_quad_t;
# 129 "/usr/include/bits/types.h" 3 4
# 1 "/usr/include/bits/typesizes.h" 1 3 4
# 130 "/usr/include/bits/types.h" 2 3 4






__extension__ typedef __u_quad_t __dev_t;
__extension__ typedef unsigned int __uid_t;
__extension__ typedef unsigned int __gid_t;
__extension__ typedef unsigned long int __ino_t;
__extension__ typedef __u_quad_t __ino64_t;
__extension__ typedef unsigned int __mode_t;
__extension__ typedef unsigned int __nlink_t;
__extension__ typedef long int __off_t;
__extension__ typedef __quad_t __off64_t;
__extension__ typedef int __pid_t;
__extension__ typedef struct { int __val[2]; } __fsid_t;
__extension__ typedef long int __clock_t;
__extension__ typedef unsigned long int __rlim_t;
__extension__ typedef __u_quad_t __rlim64_t;
__extension__ typedef unsigned int __id_t;
__extension__ typedef long int __time_t;
__extension__ typedef unsigned int __useconds_t;
__extension__ typedef long int __suseconds_t;

__extension__ typedef int __daddr_t;
__extension__ typedef long int __swblk_t;
__extension__ typedef int __key_t;


__extension__ typedef int __clockid_t;


__extension__ typedef int __timer_t;


__extension__ typedef long int __blksize_t;




__extension__ typedef long int __blkcnt_t;
__extension__ typedef __quad_t __blkcnt64_t;


__extension__ typedef unsigned long int __fsblkcnt_t;
__extension__ typedef __u_quad_t __fsblkcnt64_t;


__extension__ typedef unsigned long int __fsfilcnt_t;
__extension__ typedef __u_quad_t __fsfilcnt64_t;

__extension__ typedef int __ssize_t;



typedef __off64_t __loff_t;
typedef __quad_t *__qaddr_t;
typedef char *__caddr_t;


__extension__ typedef int __intptr_t;


__extension__ typedef unsigned int __socklen_t;
# 37 "/usr/include/stdio.h" 2 3 4









typedef struct _IO_FILE FILE;





# 62 "/usr/include/stdio.h" 3 4
typedef struct _IO_FILE __FILE;
# 72 "/usr/include/stdio.h" 3 4
# 1 "/usr/include/libio.h" 1 3 4
# 32 "/usr/include/libio.h" 3 4
# 1 "/usr/include/_G_config.h" 1 3 4
# 14 "/usr/include/_G_config.h" 3 4
# 1 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 1 3 4
# 326 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 3 4
typedef long int wchar_t;
# 355 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 3 4
typedef unsigned int wint_t;
# 15 "/usr/include/_G_config.h" 2 3 4
# 24 "/usr/include/_G_config.h" 3 4
# 1 "/usr/include/wchar.h" 1 3 4
# 48 "/usr/include/wchar.h" 3 4
# 1 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 1 3 4
# 49 "/usr/include/wchar.h" 2 3 4

# 1 "/usr/include/bits/wchar.h" 1 3 4
# 51 "/usr/include/wchar.h" 2 3 4
# 76 "/usr/include/wchar.h" 3 4
typedef struct
{
  int __count;
  union
  {
    wint_t __wch;
    char __wchb[4];
  } __value;
} __mbstate_t;
# 25 "/usr/include/_G_config.h" 2 3 4

typedef struct
{
  __off_t __pos;
  __mbstate_t __state;
} _G_fpos_t;
typedef struct
{
  __off64_t __pos;
  __mbstate_t __state;
} _G_fpos64_t;
# 44 "/usr/include/_G_config.h" 3 4
# 1 "/usr/include/gconv.h" 1 3 4
# 28 "/usr/include/gconv.h" 3 4
# 1 "/usr/include/wchar.h" 1 3 4
# 48 "/usr/include/wchar.h" 3 4
# 1 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 1 3 4
# 49 "/usr/include/wchar.h" 2 3 4
# 29 "/usr/include/gconv.h" 2 3 4


# 1 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 1 3 4
# 32 "/usr/include/gconv.h" 2 3 4





enum
{
  __GCONV_OK = 0,
  __GCONV_NOCONV,
  __GCONV_NODB,
  __GCONV_NOMEM,

  __GCONV_EMPTY_INPUT,
  __GCONV_FULL_OUTPUT,
  __GCONV_ILLEGAL_INPUT,
  __GCONV_INCOMPLETE_INPUT,

  __GCONV_ILLEGAL_DESCRIPTOR,
  __GCONV_INTERNAL_ERROR
};



enum
{
  __GCONV_IS_LAST = 0x0001,
  __GCONV_IGNORE_ERRORS = 0x0002
};



struct __gconv_step;
struct __gconv_step_data;
struct __gconv_loaded_object;
struct __gconv_trans_data;



typedef int (*__gconv_fct) (struct __gconv_step *, struct __gconv_step_data *,
       __const unsigned char **, __const unsigned char *,
       unsigned char **, size_t *, int, int);


typedef wint_t (*__gconv_btowc_fct) (struct __gconv_step *, unsigned char);


typedef int (*__gconv_init_fct) (struct __gconv_step *);
typedef void (*__gconv_end_fct) (struct __gconv_step *);



typedef int (*__gconv_trans_fct) (struct __gconv_step *,
      struct __gconv_step_data *, void *,
      __const unsigned char *,
      __const unsigned char **,
      __const unsigned char *, unsigned char **,
      size_t *);


typedef int (*__gconv_trans_context_fct) (void *, __const unsigned char *,
       __const unsigned char *,
       unsigned char *, unsigned char *);


typedef int (*__gconv_trans_query_fct) (__const char *, __const char ***,
     size_t *);


typedef int (*__gconv_trans_init_fct) (void **, const char *);
typedef void (*__gconv_trans_end_fct) (void *);

struct __gconv_trans_data
{

  __gconv_trans_fct __trans_fct;
  __gconv_trans_context_fct __trans_context_fct;
  __gconv_trans_end_fct __trans_end_fct;
  void *__data;
  struct __gconv_trans_data *__next;
};



struct __gconv_step
{
  struct __gconv_loaded_object *__shlib_handle;
  __const char *__modname;

  int __counter;

  char *__from_name;
  char *__to_name;

  __gconv_fct __fct;
  __gconv_btowc_fct __btowc_fct;
  __gconv_init_fct __init_fct;
  __gconv_end_fct __end_fct;



  int __min_needed_from;
  int __max_needed_from;
  int __min_needed_to;
  int __max_needed_to;


  int __stateful;

  void *__data;
};



struct __gconv_step_data
{
  unsigned char *__outbuf;
  unsigned char *__outbufend;



  int __flags;



  int __invocation_counter;



  int __internal_use;

  __mbstate_t *__statep;
  __mbstate_t __state;



  struct __gconv_trans_data *__trans;
};



typedef struct __gconv_info
{
  size_t __nsteps;
  struct __gconv_step *__steps;
  __extension__ struct __gconv_step_data __data [];
} *__gconv_t;
# 45 "/usr/include/_G_config.h" 2 3 4
typedef union
{
  struct __gconv_info __cd;
  struct
  {
    struct __gconv_info __cd;
    struct __gconv_step_data __data;
  } __combined;
} _G_iconv_t;

typedef int _G_int16_t __attribute__ ((__mode__ (__HI__)));
typedef int _G_int32_t __attribute__ ((__mode__ (__SI__)));
typedef unsigned int _G_uint16_t __attribute__ ((__mode__ (__HI__)));
typedef unsigned int _G_uint32_t __attribute__ ((__mode__ (__SI__)));
# 33 "/usr/include/libio.h" 2 3 4
# 53 "/usr/include/libio.h" 3 4
# 1 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stdarg.h" 1 3 4
# 43 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stdarg.h" 3 4
typedef __builtin_va_list __gnuc_va_list;
# 54 "/usr/include/libio.h" 2 3 4
# 166 "/usr/include/libio.h" 3 4
struct _IO_jump_t; struct _IO_FILE;
# 176 "/usr/include/libio.h" 3 4
typedef void _IO_lock_t;





struct _IO_marker {
  struct _IO_marker *_next;
  struct _IO_FILE *_sbuf;



  int _pos;
# 199 "/usr/include/libio.h" 3 4
};


enum __codecvt_result
{
  __codecvt_ok,
  __codecvt_partial,
  __codecvt_error,
  __codecvt_noconv
};
# 267 "/usr/include/libio.h" 3 4
struct _IO_FILE {
  int _flags;




  char* _IO_read_ptr;
  char* _IO_read_end;
  char* _IO_read_base;
  char* _IO_write_base;
  char* _IO_write_ptr;
  char* _IO_write_end;
  char* _IO_buf_base;
  char* _IO_buf_end;

  char *_IO_save_base;
  char *_IO_backup_base;
  char *_IO_save_end;

  struct _IO_marker *_markers;

  struct _IO_FILE *_chain;

  int _fileno;



  int _flags2;

  __off_t _old_offset;



  unsigned short _cur_column;
  signed char _vtable_offset;
  char _shortbuf[1];



  _IO_lock_t *_lock;
# 315 "/usr/include/libio.h" 3 4
  __off64_t _offset;





  void *__pad1;
  void *__pad2;

  int _mode;

  char _unused2[15 * sizeof (int) - 2 * sizeof (void *)];

};


typedef struct _IO_FILE _IO_FILE;


struct _IO_FILE_plus;

extern struct _IO_FILE_plus _IO_2_1_stdin_;
extern struct _IO_FILE_plus _IO_2_1_stdout_;
extern struct _IO_FILE_plus _IO_2_1_stderr_;
# 354 "/usr/include/libio.h" 3 4
typedef __ssize_t __io_read_fn (void *__cookie, char *__buf, size_t __nbytes);







typedef __ssize_t __io_write_fn (void *__cookie, __const char *__buf,
     size_t __n);







typedef int __io_seek_fn (void *__cookie, __off64_t *__pos, int __w);


typedef int __io_close_fn (void *__cookie);
# 406 "/usr/include/libio.h" 3 4
extern int __underflow (_IO_FILE *) __attribute__ ((__nothrow__));
extern int __uflow (_IO_FILE *) __attribute__ ((__nothrow__));
extern int __overflow (_IO_FILE *, int) __attribute__ ((__nothrow__));
extern wint_t __wunderflow (_IO_FILE *) __attribute__ ((__nothrow__));
extern wint_t __wuflow (_IO_FILE *) __attribute__ ((__nothrow__));
extern wint_t __woverflow (_IO_FILE *, wint_t) __attribute__ ((__nothrow__));
# 444 "/usr/include/libio.h" 3 4
extern int _IO_getc (_IO_FILE *__fp) __attribute__ ((__nothrow__));
extern int _IO_putc (int __c, _IO_FILE *__fp) __attribute__ ((__nothrow__));
extern int _IO_feof (_IO_FILE *__fp) __attribute__ ((__nothrow__));
extern int _IO_ferror (_IO_FILE *__fp) __attribute__ ((__nothrow__));

extern int _IO_peekc_locked (_IO_FILE *__fp) __attribute__ ((__nothrow__));





extern void _IO_flockfile (_IO_FILE *) __attribute__ ((__nothrow__));
extern void _IO_funlockfile (_IO_FILE *) __attribute__ ((__nothrow__));
extern int _IO_ftrylockfile (_IO_FILE *) __attribute__ ((__nothrow__));
# 474 "/usr/include/libio.h" 3 4
extern int _IO_vfscanf (_IO_FILE * __restrict, const char * __restrict,
   __gnuc_va_list, int *__restrict) __attribute__ ((__nothrow__));
extern int _IO_vfprintf (_IO_FILE *__restrict, const char *__restrict,
    __gnuc_va_list) __attribute__ ((__nothrow__));
extern __ssize_t _IO_padn (_IO_FILE *, int, __ssize_t) __attribute__ ((__nothrow__));
extern size_t _IO_sgetn (_IO_FILE *, void *, size_t) __attribute__ ((__nothrow__));

extern __off64_t _IO_seekoff (_IO_FILE *, __off64_t, int, int) __attribute__ ((__nothrow__));
extern __off64_t _IO_seekpos (_IO_FILE *, __off64_t, int) __attribute__ ((__nothrow__));

extern void _IO_free_backup_area (_IO_FILE *) __attribute__ ((__nothrow__));
# 73 "/usr/include/stdio.h" 2 3 4
# 86 "/usr/include/stdio.h" 3 4


typedef _G_fpos_t fpos_t;




# 138 "/usr/include/stdio.h" 3 4
# 1 "/usr/include/bits/stdio_lim.h" 1 3 4
# 139 "/usr/include/stdio.h" 2 3 4



extern struct _IO_FILE *stdin;
extern struct _IO_FILE *stdout;
extern struct _IO_FILE *stderr;







extern int remove (__const char *__filename) __attribute__ ((__nothrow__));

extern int rename (__const char *__old, __const char *__new) __attribute__ ((__nothrow__));









extern FILE *tmpfile (void);
# 178 "/usr/include/stdio.h" 3 4
extern char *tmpnam (char *__s) __attribute__ ((__nothrow__));





extern char *tmpnam_r (char *__s) __attribute__ ((__nothrow__));
# 196 "/usr/include/stdio.h" 3 4
extern char *tempnam (__const char *__dir, __const char *__pfx)
     __attribute__ ((__nothrow__)) __attribute__ ((__malloc__));








extern int fclose (FILE *__stream);




extern int fflush (FILE *__stream);

# 221 "/usr/include/stdio.h" 3 4
extern int fflush_unlocked (FILE *__stream);
# 235 "/usr/include/stdio.h" 3 4






extern FILE *fopen (__const char *__restrict __filename,
      __const char *__restrict __modes);




extern FILE *freopen (__const char *__restrict __filename,
        __const char *__restrict __modes,
        FILE *__restrict __stream);
# 262 "/usr/include/stdio.h" 3 4

# 273 "/usr/include/stdio.h" 3 4
extern FILE *fdopen (int __fd, __const char *__modes) __attribute__ ((__nothrow__));
# 294 "/usr/include/stdio.h" 3 4



extern void setbuf (FILE *__restrict __stream, char *__restrict __buf) __attribute__ ((__nothrow__));



extern int setvbuf (FILE *__restrict __stream, char *__restrict __buf,
      int __modes, size_t __n) __attribute__ ((__nothrow__));





extern void setbuffer (FILE *__restrict __stream, char *__restrict __buf,
         size_t __size) __attribute__ ((__nothrow__));


extern void setlinebuf (FILE *__stream) __attribute__ ((__nothrow__));








extern int fprintf (FILE *__restrict __stream,
      __const char *__restrict __format, ...);




extern int printf (__const char *__restrict __format, ...);

extern int sprintf (char *__restrict __s,
      __const char *__restrict __format, ...) __attribute__ ((__nothrow__));





extern int vfprintf (FILE *__restrict __s, __const char *__restrict __format,
       __gnuc_va_list __arg);




extern int vprintf (__const char *__restrict __format, __gnuc_va_list __arg);

extern int vsprintf (char *__restrict __s, __const char *__restrict __format,
       __gnuc_va_list __arg) __attribute__ ((__nothrow__));





extern int snprintf (char *__restrict __s, size_t __maxlen,
       __const char *__restrict __format, ...)
     __attribute__ ((__nothrow__)) __attribute__ ((__format__ (__printf__, 3, 4)));

extern int vsnprintf (char *__restrict __s, size_t __maxlen,
        __const char *__restrict __format, __gnuc_va_list __arg)
     __attribute__ ((__nothrow__)) __attribute__ ((__format__ (__printf__, 3, 0)));

# 388 "/usr/include/stdio.h" 3 4





extern int fscanf (FILE *__restrict __stream,
     __const char *__restrict __format, ...);




extern int scanf (__const char *__restrict __format, ...);

extern int sscanf (__const char *__restrict __s,
     __const char *__restrict __format, ...) __attribute__ ((__nothrow__));

# 430 "/usr/include/stdio.h" 3 4





extern int fgetc (FILE *__stream);
extern int getc (FILE *__stream);





extern int getchar (void);

# 454 "/usr/include/stdio.h" 3 4
extern int getc_unlocked (FILE *__stream);
extern int getchar_unlocked (void);
# 465 "/usr/include/stdio.h" 3 4
extern int fgetc_unlocked (FILE *__stream);











extern int fputc (int __c, FILE *__stream);
extern int putc (int __c, FILE *__stream);





extern int putchar (int __c);

# 498 "/usr/include/stdio.h" 3 4
extern int fputc_unlocked (int __c, FILE *__stream);







extern int putc_unlocked (int __c, FILE *__stream);
extern int putchar_unlocked (int __c);






extern int getw (FILE *__stream);


extern int putw (int __w, FILE *__stream);








extern char *fgets (char *__restrict __s, int __n, FILE *__restrict __stream);






extern char *gets (char *__s);

# 578 "/usr/include/stdio.h" 3 4





extern int fputs (__const char *__restrict __s, FILE *__restrict __stream);





extern int puts (__const char *__s);






extern int ungetc (int __c, FILE *__stream);






extern size_t fread (void *__restrict __ptr, size_t __size,
       size_t __n, FILE *__restrict __stream);




extern size_t fwrite (__const void *__restrict __ptr, size_t __size,
        size_t __n, FILE *__restrict __s);

# 631 "/usr/include/stdio.h" 3 4
extern size_t fread_unlocked (void *__restrict __ptr, size_t __size,
         size_t __n, FILE *__restrict __stream);
extern size_t fwrite_unlocked (__const void *__restrict __ptr, size_t __size,
          size_t __n, FILE *__restrict __stream);








extern int fseek (FILE *__stream, long int __off, int __whence);




extern long int ftell (FILE *__stream);




extern void rewind (FILE *__stream);

# 686 "/usr/include/stdio.h" 3 4






extern int fgetpos (FILE *__restrict __stream, fpos_t *__restrict __pos);




extern int fsetpos (FILE *__stream, __const fpos_t *__pos);
# 709 "/usr/include/stdio.h" 3 4

# 718 "/usr/include/stdio.h" 3 4


extern void clearerr (FILE *__stream) __attribute__ ((__nothrow__));

extern int feof (FILE *__stream) __attribute__ ((__nothrow__));

extern int ferror (FILE *__stream) __attribute__ ((__nothrow__));




extern void clearerr_unlocked (FILE *__stream) __attribute__ ((__nothrow__));
extern int feof_unlocked (FILE *__stream) __attribute__ ((__nothrow__));
extern int ferror_unlocked (FILE *__stream) __attribute__ ((__nothrow__));








extern void perror (__const char *__s);






# 1 "/usr/include/bits/sys_errlist.h" 1 3 4
# 27 "/usr/include/bits/sys_errlist.h" 3 4
extern int sys_nerr;
extern __const char *__const sys_errlist[];
# 748 "/usr/include/stdio.h" 2 3 4




extern int fileno (FILE *__stream) __attribute__ ((__nothrow__));




extern int fileno_unlocked (FILE *__stream) __attribute__ ((__nothrow__));
# 767 "/usr/include/stdio.h" 3 4
extern FILE *popen (__const char *__command, __const char *__modes);





extern int pclose (FILE *__stream);





extern char *ctermid (char *__s) __attribute__ ((__nothrow__));
# 807 "/usr/include/stdio.h" 3 4
extern void flockfile (FILE *__stream) __attribute__ ((__nothrow__));



extern int ftrylockfile (FILE *__stream) __attribute__ ((__nothrow__));


extern void funlockfile (FILE *__stream) __attribute__ ((__nothrow__));
# 828 "/usr/include/stdio.h" 3 4
# 1 "/usr/include/bits/stdio.h" 1 3 4
# 33 "/usr/include/bits/stdio.h" 3 4
extern __inline int
vprintf (__const char *__restrict __fmt, __gnuc_va_list __arg)
{
  return vfprintf (stdout, __fmt, __arg);
}


extern __inline int
getchar (void)
{
  return _IO_getc (stdin);
}




extern __inline int
getc_unlocked (FILE *__fp)
{
  return (__builtin_expect ((__fp)->_IO_read_ptr >= (__fp)->_IO_read_end, 0) ? __uflow (__fp) : *(unsigned char *) (__fp)->_IO_read_ptr++);
}


extern __inline int
getchar_unlocked (void)
{
  return (__builtin_expect ((stdin)->_IO_read_ptr >= (stdin)->_IO_read_end, 0) ? __uflow (stdin) : *(unsigned char *) (stdin)->_IO_read_ptr++);
}




extern __inline int
putchar (int __c)
{
  return _IO_putc (__c, stdout);
}




extern __inline int
fputc_unlocked (int __c, FILE *__stream)
{
  return (__builtin_expect ((__stream)->_IO_write_ptr >= (__stream)->_IO_write_end, 0) ? __overflow (__stream, (unsigned char) (__c)) : (unsigned char) (*(__stream)->_IO_write_ptr++ = (__c)));
}





extern __inline int
putc_unlocked (int __c, FILE *__stream)
{
  return (__builtin_expect ((__stream)->_IO_write_ptr >= (__stream)->_IO_write_end, 0) ? __overflow (__stream, (unsigned char) (__c)) : (unsigned char) (*(__stream)->_IO_write_ptr++ = (__c)));
}


extern __inline int
putchar_unlocked (int __c)
{
  return (__builtin_expect ((stdout)->_IO_write_ptr >= (stdout)->_IO_write_end, 0) ? __overflow (stdout, (unsigned char) (__c)) : (unsigned char) (*(stdout)->_IO_write_ptr++ = (__c)));
}
# 111 "/usr/include/bits/stdio.h" 3 4
extern __inline int
__attribute__ ((__nothrow__)) feof_unlocked (FILE *__stream)
{
  return (((__stream)->_flags & 0x10) != 0);
}


extern __inline int
__attribute__ ((__nothrow__)) ferror_unlocked (FILE *__stream)
{
  return (((__stream)->_flags & 0x20) != 0);
}
# 829 "/usr/include/stdio.h" 2 3 4






# 33 "tree234.c" 2
# 1 "/usr/include/stdlib.h" 1 3 4
# 33 "/usr/include/stdlib.h" 3 4
# 1 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 1 3 4
# 34 "/usr/include/stdlib.h" 2 3 4


# 96 "/usr/include/stdlib.h" 3 4


typedef struct
  {
    int quot;
    int rem;
  } div_t;



typedef struct
  {
    long int quot;
    long int rem;
  } ldiv_t;



# 140 "/usr/include/stdlib.h" 3 4
extern size_t __ctype_get_mb_cur_max (void) __attribute__ ((__nothrow__));




extern double atof (__const char *__nptr)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));

extern int atoi (__const char *__nptr)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));

extern long int atol (__const char *__nptr)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));





__extension__ extern long long int atoll (__const char *__nptr)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));





extern double strtod (__const char *__restrict __nptr,
        char **__restrict __endptr) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));

# 181 "/usr/include/stdlib.h" 3 4


extern long int strtol (__const char *__restrict __nptr,
   char **__restrict __endptr, int __base)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));

extern unsigned long int strtoul (__const char *__restrict __nptr,
      char **__restrict __endptr, int __base)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));




__extension__
extern long long int strtoq (__const char *__restrict __nptr,
        char **__restrict __endptr, int __base)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));

__extension__
extern unsigned long long int strtouq (__const char *__restrict __nptr,
           char **__restrict __endptr, int __base)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));





__extension__
extern long long int strtoll (__const char *__restrict __nptr,
         char **__restrict __endptr, int __base)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));

__extension__
extern unsigned long long int strtoull (__const char *__restrict __nptr,
     char **__restrict __endptr, int __base)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));

# 277 "/usr/include/stdlib.h" 3 4
extern double __strtod_internal (__const char *__restrict __nptr,
     char **__restrict __endptr, int __group)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));
extern float __strtof_internal (__const char *__restrict __nptr,
    char **__restrict __endptr, int __group)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));
extern long double __strtold_internal (__const char *__restrict __nptr,
           char **__restrict __endptr,
           int __group) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));

extern long int __strtol_internal (__const char *__restrict __nptr,
       char **__restrict __endptr,
       int __base, int __group)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));



extern unsigned long int __strtoul_internal (__const char *__restrict __nptr,
          char **__restrict __endptr,
          int __base, int __group)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));




__extension__
extern long long int __strtoll_internal (__const char *__restrict __nptr,
      char **__restrict __endptr,
      int __base, int __group)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));



__extension__
extern unsigned long long int __strtoull_internal (__const char *
         __restrict __nptr,
         char **__restrict __endptr,
         int __base, int __group)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));








extern __inline double
__attribute__ ((__nothrow__)) strtod (__const char *__restrict __nptr, char **__restrict __endptr)
{
  return __strtod_internal (__nptr, __endptr, 0);
}
extern __inline long int
__attribute__ ((__nothrow__)) strtol (__const char *__restrict __nptr, char **__restrict __endptr, int __base)

{
  return __strtol_internal (__nptr, __endptr, __base, 0);
}
extern __inline unsigned long int
__attribute__ ((__nothrow__)) strtoul (__const char *__restrict __nptr, char **__restrict __endptr, int __base)

{
  return __strtoul_internal (__nptr, __endptr, __base, 0);
}

# 359 "/usr/include/stdlib.h" 3 4
__extension__ extern __inline long long int
__attribute__ ((__nothrow__)) strtoq (__const char *__restrict __nptr, char **__restrict __endptr, int __base)

{
  return __strtoll_internal (__nptr, __endptr, __base, 0);
}
__extension__ extern __inline unsigned long long int
__attribute__ ((__nothrow__)) strtouq (__const char *__restrict __nptr, char **__restrict __endptr, int __base)

{
  return __strtoull_internal (__nptr, __endptr, __base, 0);
}




__extension__ extern __inline long long int
__attribute__ ((__nothrow__)) strtoll (__const char *__restrict __nptr, char **__restrict __endptr, int __base)

{
  return __strtoll_internal (__nptr, __endptr, __base, 0);
}
__extension__ extern __inline unsigned long long int
__attribute__ ((__nothrow__)) strtoull (__const char * __restrict __nptr, char **__restrict __endptr, int __base)

{
  return __strtoull_internal (__nptr, __endptr, __base, 0);
}




extern __inline double
__attribute__ ((__nothrow__)) atof (__const char *__nptr)
{
  return strtod (__nptr, (char **) ((void *)0));
}
extern __inline int
__attribute__ ((__nothrow__)) atoi (__const char *__nptr)
{
  return (int) strtol (__nptr, (char **) ((void *)0), 10);
}
extern __inline long int
__attribute__ ((__nothrow__)) atol (__const char *__nptr)
{
  return strtol (__nptr, (char **) ((void *)0), 10);
}




__extension__ extern __inline long long int
__attribute__ ((__nothrow__)) atoll (__const char *__nptr)
{
  return strtoll (__nptr, (char **) ((void *)0), 10);
}

# 424 "/usr/include/stdlib.h" 3 4
extern char *l64a (long int __n) __attribute__ ((__nothrow__));


extern long int a64l (__const char *__s)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));




# 1 "/usr/include/sys/types.h" 1 3 4
# 29 "/usr/include/sys/types.h" 3 4






typedef __u_char u_char;
typedef __u_short u_short;
typedef __u_int u_int;
typedef __u_long u_long;
typedef __quad_t quad_t;
typedef __u_quad_t u_quad_t;
typedef __fsid_t fsid_t;




typedef __loff_t loff_t;



typedef __ino_t ino_t;
# 62 "/usr/include/sys/types.h" 3 4
typedef __dev_t dev_t;




typedef __gid_t gid_t;




typedef __mode_t mode_t;




typedef __nlink_t nlink_t;




typedef __uid_t uid_t;





typedef __off_t off_t;
# 100 "/usr/include/sys/types.h" 3 4
typedef __pid_t pid_t;




typedef __id_t id_t;




typedef __ssize_t ssize_t;





typedef __daddr_t daddr_t;
typedef __caddr_t caddr_t;





typedef __key_t key_t;
# 133 "/usr/include/sys/types.h" 3 4
# 1 "/usr/include/time.h" 1 3 4
# 74 "/usr/include/time.h" 3 4


typedef __time_t time_t;



# 92 "/usr/include/time.h" 3 4
typedef __clockid_t clockid_t;
# 104 "/usr/include/time.h" 3 4
typedef __timer_t timer_t;
# 134 "/usr/include/sys/types.h" 2 3 4
# 147 "/usr/include/sys/types.h" 3 4
# 1 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 1 3 4
# 148 "/usr/include/sys/types.h" 2 3 4



typedef unsigned long int ulong;
typedef unsigned short int ushort;
typedef unsigned int uint;
# 191 "/usr/include/sys/types.h" 3 4
typedef int int8_t __attribute__ ((__mode__ (__QI__)));
typedef int int16_t __attribute__ ((__mode__ (__HI__)));
typedef int int32_t __attribute__ ((__mode__ (__SI__)));
typedef int int64_t __attribute__ ((__mode__ (__DI__)));


typedef unsigned int u_int8_t __attribute__ ((__mode__ (__QI__)));
typedef unsigned int u_int16_t __attribute__ ((__mode__ (__HI__)));
typedef unsigned int u_int32_t __attribute__ ((__mode__ (__SI__)));
typedef unsigned int u_int64_t __attribute__ ((__mode__ (__DI__)));

typedef int register_t __attribute__ ((__mode__ (__word__)));
# 213 "/usr/include/sys/types.h" 3 4
# 1 "/usr/include/endian.h" 1 3 4
# 37 "/usr/include/endian.h" 3 4
# 1 "/usr/include/bits/endian.h" 1 3 4
# 38 "/usr/include/endian.h" 2 3 4
# 214 "/usr/include/sys/types.h" 2 3 4


# 1 "/usr/include/sys/select.h" 1 3 4
# 31 "/usr/include/sys/select.h" 3 4
# 1 "/usr/include/bits/select.h" 1 3 4
# 32 "/usr/include/sys/select.h" 2 3 4


# 1 "/usr/include/bits/sigset.h" 1 3 4
# 23 "/usr/include/bits/sigset.h" 3 4
typedef int __sig_atomic_t;




typedef struct
  {
    unsigned long int __val[(1024 / (8 * sizeof (unsigned long int)))];
  } __sigset_t;
# 35 "/usr/include/sys/select.h" 2 3 4



typedef __sigset_t sigset_t;





# 1 "/usr/include/time.h" 1 3 4
# 118 "/usr/include/time.h" 3 4
struct timespec
  {
    __time_t tv_sec;
    long int tv_nsec;
  };
# 45 "/usr/include/sys/select.h" 2 3 4

# 1 "/usr/include/bits/time.h" 1 3 4
# 69 "/usr/include/bits/time.h" 3 4
struct timeval
  {
    __time_t tv_sec;
    __suseconds_t tv_usec;
  };
# 47 "/usr/include/sys/select.h" 2 3 4


typedef __suseconds_t suseconds_t;





typedef long int __fd_mask;
# 67 "/usr/include/sys/select.h" 3 4
typedef struct
  {






    __fd_mask __fds_bits[1024 / (8 * sizeof (__fd_mask))];


  } fd_set;






typedef __fd_mask fd_mask;
# 99 "/usr/include/sys/select.h" 3 4

# 109 "/usr/include/sys/select.h" 3 4
extern int select (int __nfds, fd_set *__restrict __readfds,
     fd_set *__restrict __writefds,
     fd_set *__restrict __exceptfds,
     struct timeval *__restrict __timeout);
# 128 "/usr/include/sys/select.h" 3 4

# 217 "/usr/include/sys/types.h" 2 3 4


# 1 "/usr/include/sys/sysmacros.h" 1 3 4
# 29 "/usr/include/sys/sysmacros.h" 3 4
__extension__
extern __inline unsigned int gnu_dev_major (unsigned long long int __dev)
     __attribute__ ((__nothrow__));
__extension__
extern __inline unsigned int gnu_dev_minor (unsigned long long int __dev)
     __attribute__ ((__nothrow__));
__extension__
extern __inline unsigned long long int gnu_dev_makedev (unsigned int __major,
       unsigned int __minor)
     __attribute__ ((__nothrow__));


__extension__ extern __inline unsigned int
__attribute__ ((__nothrow__)) gnu_dev_major (unsigned long long int __dev)
{
  return ((__dev >> 8) & 0xfff) | ((unsigned int) (__dev >> 32) & ~0xfff);
}

__extension__ extern __inline unsigned int
__attribute__ ((__nothrow__)) gnu_dev_minor (unsigned long long int __dev)
{
  return (__dev & 0xff) | ((unsigned int) (__dev >> 12) & ~0xff);
}

__extension__ extern __inline unsigned long long int
__attribute__ ((__nothrow__)) gnu_dev_makedev (unsigned int __major, unsigned int __minor)
{
  return ((__minor & 0xff) | ((__major & 0xfff) << 8)
   | (((unsigned long long int) (__minor & ~0xff)) << 12)
   | (((unsigned long long int) (__major & ~0xfff)) << 32));
}
# 220 "/usr/include/sys/types.h" 2 3 4
# 231 "/usr/include/sys/types.h" 3 4
typedef __blkcnt_t blkcnt_t;



typedef __fsblkcnt_t fsblkcnt_t;



typedef __fsfilcnt_t fsfilcnt_t;
# 266 "/usr/include/sys/types.h" 3 4
# 1 "/usr/include/bits/pthreadtypes.h" 1 3 4
# 23 "/usr/include/bits/pthreadtypes.h" 3 4
# 1 "/usr/include/bits/sched.h" 1 3 4
# 83 "/usr/include/bits/sched.h" 3 4
struct __sched_param
  {
    int __sched_priority;
  };
# 24 "/usr/include/bits/pthreadtypes.h" 2 3 4

typedef int __atomic_lock_t;


struct _pthread_fastlock
{
  long int __status;
  __atomic_lock_t __spinlock;

};



typedef struct _pthread_descr_struct *_pthread_descr;





typedef struct __pthread_attr_s
{
  int __detachstate;
  int __schedpolicy;
  struct __sched_param __schedparam;
  int __inheritsched;
  int __scope;
  size_t __guardsize;
  int __stackaddr_set;
  void *__stackaddr;
  size_t __stacksize;
} pthread_attr_t;





__extension__ typedef long long __pthread_cond_align_t;




typedef struct
{
  struct _pthread_fastlock __c_lock;
  _pthread_descr __c_waiting;
  char __padding[48 - sizeof (struct _pthread_fastlock)
   - sizeof (_pthread_descr) - sizeof (__pthread_cond_align_t)];
  __pthread_cond_align_t __align;
} pthread_cond_t;



typedef struct
{
  int __dummy;
} pthread_condattr_t;


typedef unsigned int pthread_key_t;





typedef struct
{
  int __m_reserved;
  int __m_count;
  _pthread_descr __m_owner;
  int __m_kind;
  struct _pthread_fastlock __m_lock;
} pthread_mutex_t;



typedef struct
{
  int __mutexkind;
} pthread_mutexattr_t;



typedef int pthread_once_t;
# 152 "/usr/include/bits/pthreadtypes.h" 3 4
typedef unsigned long int pthread_t;
# 267 "/usr/include/sys/types.h" 2 3 4



# 434 "/usr/include/stdlib.h" 2 3 4






extern long int random (void) __attribute__ ((__nothrow__));


extern void srandom (unsigned int __seed) __attribute__ ((__nothrow__));





extern char *initstate (unsigned int __seed, char *__statebuf,
   size_t __statelen) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2)));



extern char *setstate (char *__statebuf) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));







struct random_data
  {
    int32_t *fptr;
    int32_t *rptr;
    int32_t *state;
    int rand_type;
    int rand_deg;
    int rand_sep;
    int32_t *end_ptr;
  };

extern int random_r (struct random_data *__restrict __buf,
       int32_t *__restrict __result) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));

extern int srandom_r (unsigned int __seed, struct random_data *__buf)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2)));

extern int initstate_r (unsigned int __seed, char *__restrict __statebuf,
   size_t __statelen,
   struct random_data *__restrict __buf)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2, 4)));

extern int setstate_r (char *__restrict __statebuf,
         struct random_data *__restrict __buf)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));






extern int rand (void) __attribute__ ((__nothrow__));

extern void srand (unsigned int __seed) __attribute__ ((__nothrow__));




extern int rand_r (unsigned int *__seed) __attribute__ ((__nothrow__));







extern double drand48 (void) __attribute__ ((__nothrow__));
extern double erand48 (unsigned short int __xsubi[3]) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));


extern long int lrand48 (void) __attribute__ ((__nothrow__));
extern long int nrand48 (unsigned short int __xsubi[3])
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));


extern long int mrand48 (void) __attribute__ ((__nothrow__));
extern long int jrand48 (unsigned short int __xsubi[3])
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));


extern void srand48 (long int __seedval) __attribute__ ((__nothrow__));
extern unsigned short int *seed48 (unsigned short int __seed16v[3])
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));
extern void lcong48 (unsigned short int __param[7]) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));





struct drand48_data
  {
    unsigned short int __x[3];
    unsigned short int __old_x[3];
    unsigned short int __c;
    unsigned short int __init;
    unsigned long long int __a;
  };


extern int drand48_r (struct drand48_data *__restrict __buffer,
        double *__restrict __result) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));
extern int erand48_r (unsigned short int __xsubi[3],
        struct drand48_data *__restrict __buffer,
        double *__restrict __result) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));


extern int lrand48_r (struct drand48_data *__restrict __buffer,
        long int *__restrict __result)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));
extern int nrand48_r (unsigned short int __xsubi[3],
        struct drand48_data *__restrict __buffer,
        long int *__restrict __result)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));


extern int mrand48_r (struct drand48_data *__restrict __buffer,
        long int *__restrict __result)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));
extern int jrand48_r (unsigned short int __xsubi[3],
        struct drand48_data *__restrict __buffer,
        long int *__restrict __result)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));


extern int srand48_r (long int __seedval, struct drand48_data *__buffer)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2)));

extern int seed48_r (unsigned short int __seed16v[3],
       struct drand48_data *__buffer) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));

extern int lcong48_r (unsigned short int __param[7],
        struct drand48_data *__buffer)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));









extern void *malloc (size_t __size) __attribute__ ((__nothrow__)) __attribute__ ((__malloc__));

extern void *calloc (size_t __nmemb, size_t __size)
     __attribute__ ((__nothrow__)) __attribute__ ((__malloc__));







extern void *realloc (void *__ptr, size_t __size) __attribute__ ((__nothrow__)) __attribute__ ((__malloc__));

extern void free (void *__ptr) __attribute__ ((__nothrow__));




extern void cfree (void *__ptr) __attribute__ ((__nothrow__));



# 1 "/usr/include/alloca.h" 1 3 4
# 25 "/usr/include/alloca.h" 3 4
# 1 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 1 3 4
# 26 "/usr/include/alloca.h" 2 3 4







extern void *alloca (size_t __size) __attribute__ ((__nothrow__));






# 607 "/usr/include/stdlib.h" 2 3 4




extern void *valloc (size_t __size) __attribute__ ((__nothrow__)) __attribute__ ((__malloc__));
# 620 "/usr/include/stdlib.h" 3 4


extern void abort (void) __attribute__ ((__nothrow__)) __attribute__ ((__noreturn__));



extern int atexit (void (*__func) (void)) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));





extern int on_exit (void (*__func) (int __status, void *__arg), void *__arg)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));






extern void exit (int __status) __attribute__ ((__nothrow__)) __attribute__ ((__noreturn__));

# 652 "/usr/include/stdlib.h" 3 4


extern char *getenv (__const char *__name) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));




extern char *__secure_getenv (__const char *__name) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));





extern int putenv (char *__string) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));





extern int setenv (__const char *__name, __const char *__value, int __replace)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2)));


extern int unsetenv (__const char *__name) __attribute__ ((__nothrow__));






extern int clearenv (void) __attribute__ ((__nothrow__));
# 691 "/usr/include/stdlib.h" 3 4
extern char *mktemp (char *__template) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));
# 702 "/usr/include/stdlib.h" 3 4
extern int mkstemp (char *__template) __attribute__ ((__nonnull__ (1)));
# 721 "/usr/include/stdlib.h" 3 4
extern char *mkdtemp (char *__template) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));








extern int system (__const char *__command);

# 749 "/usr/include/stdlib.h" 3 4
extern char *realpath (__const char *__restrict __name,
         char *__restrict __resolved) __attribute__ ((__nothrow__));






typedef int (*__compar_fn_t) (__const void *, __const void *);









extern void *bsearch (__const void *__key, __const void *__base,
        size_t __nmemb, size_t __size, __compar_fn_t __compar)
     __attribute__ ((__nonnull__ (1, 2, 5)));



extern void qsort (void *__base, size_t __nmemb, size_t __size,
     __compar_fn_t __compar) __attribute__ ((__nonnull__ (1, 4)));



extern int abs (int __x) __attribute__ ((__nothrow__)) __attribute__ ((__const__));
extern long int labs (long int __x) __attribute__ ((__nothrow__)) __attribute__ ((__const__));












extern div_t div (int __numer, int __denom)
     __attribute__ ((__nothrow__)) __attribute__ ((__const__));
extern ldiv_t ldiv (long int __numer, long int __denom)
     __attribute__ ((__nothrow__)) __attribute__ ((__const__));

# 814 "/usr/include/stdlib.h" 3 4
extern char *ecvt (double __value, int __ndigit, int *__restrict __decpt,
     int *__restrict __sign) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4)));




extern char *fcvt (double __value, int __ndigit, int *__restrict __decpt,
     int *__restrict __sign) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4)));




extern char *gcvt (double __value, int __ndigit, char *__buf)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3)));




extern char *qecvt (long double __value, int __ndigit,
      int *__restrict __decpt, int *__restrict __sign)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4)));
extern char *qfcvt (long double __value, int __ndigit,
      int *__restrict __decpt, int *__restrict __sign)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4)));
extern char *qgcvt (long double __value, int __ndigit, char *__buf)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3)));




extern int ecvt_r (double __value, int __ndigit, int *__restrict __decpt,
     int *__restrict __sign, char *__restrict __buf,
     size_t __len) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4, 5)));
extern int fcvt_r (double __value, int __ndigit, int *__restrict __decpt,
     int *__restrict __sign, char *__restrict __buf,
     size_t __len) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4, 5)));

extern int qecvt_r (long double __value, int __ndigit,
      int *__restrict __decpt, int *__restrict __sign,
      char *__restrict __buf, size_t __len)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4, 5)));
extern int qfcvt_r (long double __value, int __ndigit,
      int *__restrict __decpt, int *__restrict __sign,
      char *__restrict __buf, size_t __len)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (3, 4, 5)));







extern int mblen (__const char *__s, size_t __n) __attribute__ ((__nothrow__));


extern int mbtowc (wchar_t *__restrict __pwc,
     __const char *__restrict __s, size_t __n) __attribute__ ((__nothrow__));


extern int wctomb (char *__s, wchar_t __wchar) __attribute__ ((__nothrow__));



extern size_t mbstowcs (wchar_t *__restrict __pwcs,
   __const char *__restrict __s, size_t __n) __attribute__ ((__nothrow__));

extern size_t wcstombs (char *__restrict __s,
   __const wchar_t *__restrict __pwcs, size_t __n)
     __attribute__ ((__nothrow__));








extern int rpmatch (__const char *__response) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));
# 954 "/usr/include/stdlib.h" 3 4
extern int getloadavg (double __loadavg[], int __nelem)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));






# 34 "tree234.c" 2
# 1 "/usr/include/assert.h" 1 3 4
# 67 "/usr/include/assert.h" 3 4



extern void __assert_fail (__const char *__assertion, __const char *__file,
      unsigned int __line, __const char *__function)
     __attribute__ ((__nothrow__)) __attribute__ ((__noreturn__));


extern void __assert_perror_fail (int __errnum, __const char *__file,
      unsigned int __line,
      __const char *__function)
     __attribute__ ((__nothrow__)) __attribute__ ((__noreturn__));




extern void __assert (const char *__assertion, const char *__file, int __line)
     __attribute__ ((__nothrow__)) __attribute__ ((__noreturn__));



# 35 "tree234.c" 2

# 1 "tree234.h" 1
# 38 "tree234.h"
typedef struct tree234_Tag tree234;

typedef int (*cmpfn234)(void *, void *);




typedef void (*freefn)(void *);






tree234 *newtree234(cmpfn234 cmp);




void freetree234(tree234 *t);




void free2tree234(tree234 *t, freefn fn);





void *add234(tree234 *t, void *e);
# 78 "tree234.h"
void *addpos234(tree234 *t, void *e, int index);
# 98 "tree234.h"
void *index234(tree234 *t, int index);
# 140 "tree234.h"
enum {
    REL234_EQ, REL234_LT, REL234_LE, REL234_GT, REL234_GE
};
void *find234(tree234 *t, void *e, cmpfn234 cmp);
void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation);
void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index);
void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp, int relation,
      int *index);
# 166 "tree234.h"
void *del234(tree234 *t, void *e);
void *delpos234(tree234 *t, int index);




int count234(tree234 *t);
# 37 "tree234.c" 2
# 1 "../../mem/shm_mem.h" 1
# 33 "../../mem/shm_mem.h"
# 1 "../../mem/../statistics.h" 1
# 32 "../../mem/../statistics.h"
# 1 "../../mem/../hash_func.h" 1
# 37 "../../mem/../hash_func.h"
# 1 "../../mem/../str.h" 1
# 28 "../../mem/../str.h"
struct _str{
 char* s;
 int len;
};

typedef struct _str str;
# 38 "../../mem/../hash_func.h" 2




static inline unsigned int core_hash( str *s1, str *s2, unsigned int size )
{
 char *p, *end;
 register unsigned v;
 register unsigned h;

 h=0;

 end=s1->s+s1->len;
 for ( p=s1->s ; p<=(end-4) ; p+=4 ){
  v=(*p<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
  h+=v^(v>>3);
 }
 v=0;
 for (; p<end ; p++){ v<<=8; v+=*p;}
 h+=v^(v>>3);

 if (s2) {
  end=s2->s+s2->len;
  for (p=s2->s; p<=(end-4); p+=4){
   v=(*p<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
   h+=v^(v>>3);
  }
  v=0;
  for (; p<end ; p++){ v<<=8; v+=*p;}
  h+=v^(v>>3);
 }
 h=((h)+(h>>11))+((h>>13)+(h>>23));
 return size?((h)&(size-1)):h;
}


static inline unsigned int core_case_hash( str *s1, str *s2, unsigned int size)
{
 char *p, *end;
 register unsigned v;
 register unsigned h;

 h=0;

 end=s1->s+s1->len;
 for ( p=s1->s ; p<=(end-4) ; p+=4 ){
  v=((((*p)>='A'&&(*p)<='Z')?((*p)|0x20):(*p))<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
  h+=v^(v>>3);
 }
 v=0;
 for (; p<end ; p++){ v<<=8; v+=(((*p)>='A'&&(*p)<='Z')?((*p)|0x20):(*p));}
 h+=v^(v>>3);

 if (s2) {
  end=s2->s+s2->len;
  for (p=s2->s; p<=(end-4); p+=4){
   v=((((*p)>='A'&&(*p)<='Z')?((*p)|0x20):(*p))<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
   h+=v^(v>>3);
  }
  v=0;
  for (; p<end ; p++){ v<<=8; v+=(((*p)>='A'&&(*p)<='Z')?((*p)|0x20):(*p));}
  h+=v^(v>>3);
 }
 h=((h)+(h>>11))+((h>>13)+(h>>23));
 return size?((h)&(size-1)):h;
}
# 33 "../../mem/../statistics.h" 2
# 1 "../../mem/../atomic.h" 1
# 34 "../../mem/../statistics.h" 2
# 45 "../../mem/../statistics.h"
typedef unsigned int stat_val;




typedef unsigned long (*stat_function)(void);

struct module_stats_;

typedef struct stat_var_{
 struct module_stats_ *module;
 str name;
 int flags;
 union{
  stat_val *val;
  stat_function f;
 }u;
 struct stat_var_ *hnext;
 struct stat_var_ *lnext;
} stat_var;

typedef struct module_stats_ {
 str name;
 int no;
 stat_var *head;
 stat_var *tail;
} module_stats;

typedef struct stats_collector_ {
 int stats_no;
 int mod_no;
 stat_var* hstats[(1<<(8))];
 module_stats *amodules;
}stats_collector;

typedef struct stat_export_ {
 char* name;
 int flags;
 stat_var** stat_pointer;

} stat_export_t;



int init_stats_collector();

void destroy_stats_collector();

int register_stat( char *module, char *name, stat_var **pvar, int flags);

int register_module_stats(char *module, stat_export_t *stats);

stat_var* get_stat( str *name );

unsigned int get_stat_val( stat_var *var );


# 1 "../../mem/../locking.h" 1
# 65 "../../mem/../locking.h"
# 1 "../../mem/../lock_ops.h" 1
# 68 "../../mem/../lock_ops.h"
# 1 "../../mem/../fastlock.h" 1
# 44 "../../mem/../fastlock.h"
# 1 "/usr/include/sched.h" 1 3 4
# 29 "/usr/include/sched.h" 3 4
# 1 "/usr/include/time.h" 1 3 4
# 30 "/usr/include/sched.h" 2 3 4


# 1 "/usr/include/bits/sched.h" 1 3 4
# 62 "/usr/include/bits/sched.h" 3 4
struct sched_param
  {
    int __sched_priority;
  };





extern int clone (int (*__fn) (void *__arg), void *__child_stack,
    int __flags, void *__arg) __attribute__ ((__nothrow__));



# 98 "/usr/include/bits/sched.h" 3 4
typedef unsigned long int __cpu_mask;






typedef struct
{
  __cpu_mask __bits[1024 / (8 * sizeof (__cpu_mask))];
} cpu_set_t;
# 33 "/usr/include/sched.h" 2 3 4







extern int sched_setparam (__pid_t __pid, __const struct sched_param *__param)
     __attribute__ ((__nothrow__));


extern int sched_getparam (__pid_t __pid, struct sched_param *__param) __attribute__ ((__nothrow__));


extern int sched_setscheduler (__pid_t __pid, int __policy,
          __const struct sched_param *__param) __attribute__ ((__nothrow__));


extern int sched_getscheduler (__pid_t __pid) __attribute__ ((__nothrow__));


extern int sched_yield (void) __attribute__ ((__nothrow__));


extern int sched_get_priority_max (int __algorithm) __attribute__ ((__nothrow__));


extern int sched_get_priority_min (int __algorithm) __attribute__ ((__nothrow__));


extern int sched_rr_get_interval (__pid_t __pid, struct timespec *__t) __attribute__ ((__nothrow__));
# 84 "/usr/include/sched.h" 3 4

# 45 "../../mem/../fastlock.h" 2







typedef volatile int fl_lock_t;
# 61 "../../mem/../fastlock.h"
inline static int tsl(fl_lock_t* lock)
{
 int val;
# 90 "../../mem/../fastlock.h"
 asm volatile(
   "# here \n\t"
   "swpb %0, %1, [%2] \n\t"
   : "=r" (val)
   : "r"(1), "r" (lock) : "memory"
 );
# 151 "../../mem/../fastlock.h"
 return val;
}



inline static void get_lock(fl_lock_t* lock)
{

 int i=1024;


 while(tsl(lock)){


  if (i>0) i--;
  else sched_yield();



 }
}



inline static void release_lock(fl_lock_t* lock)
{
# 195 "../../mem/../fastlock.h"
 asm volatile(
  " str %0, [%1] \n\r"
  :
  : "r"(0), "r"(lock)
  : "memory"
 );
# 231 "../../mem/../fastlock.h"
}
# 69 "../../mem/../lock_ops.h" 2

typedef fl_lock_t gen_lock_t;




inline static gen_lock_t* lock_init(gen_lock_t* lock)
{
 (*lock)=0;
 return lock;
}
# 224 "../../mem/../lock_ops.h"
struct gen_lock_set_t_ {
 long size;
 gen_lock_t* locks;
};
typedef struct gen_lock_set_t_ gen_lock_set_t;




inline static gen_lock_set_t* lock_set_init(gen_lock_set_t* s)
{
 int r;
 for (r=0; r<s->size; r++) if (lock_init(&s->locks[r])==0) return 0;
 return s;
}
# 66 "../../mem/../locking.h" 2
# 1 "../../mem/../lock_alloc.h" 1
# 50 "../../mem/../lock_alloc.h"
# 1 "../../mem/../mem/mem.h" 1
# 35 "../../mem/../mem/mem.h"
# 1 "../../mem/../mem/../config.h" 1
# 34 "../../mem/../mem/../config.h"
# 1 "../../mem/../mem/../types.h" 1
# 27 "../../mem/../mem/../types.h"
typedef unsigned int process_bm_t;
# 35 "../../mem/../mem/../config.h" 2
# 36 "../../mem/../mem/mem.h" 2
# 1 "../../mem/../mem/../dprint.h" 1
# 28 "../../mem/../mem/../dprint.h"
# 1 "/usr/include/syslog.h" 1 3 4
# 1 "/usr/include/sys/syslog.h" 1 3 4
# 37 "/usr/include/sys/syslog.h" 3 4
# 1 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stdarg.h" 1 3 4
# 38 "/usr/include/sys/syslog.h" 2 3 4


# 1 "/usr/include/bits/syslog-path.h" 1 3 4
# 41 "/usr/include/sys/syslog.h" 2 3 4
# 169 "/usr/include/sys/syslog.h" 3 4






extern void closelog (void);





extern void openlog (__const char *__ident, int __option, int __facility);


extern int setlogmask (int __mask) __attribute__ ((__nothrow__));





extern void syslog (int __pri, __const char *__fmt, ...)
     __attribute__ ((__format__(__printf__, 2, 3)));
# 200 "/usr/include/sys/syslog.h" 3 4
extern void vsyslog (int __pri, __const char *__fmt, __gnuc_va_list __ap)
     __attribute__ ((__format__(__printf__, 2, 0)));



# 1 "/usr/include/syslog.h" 2 3 4
# 29 "../../mem/../mem/../dprint.h" 2
# 41 "../../mem/../mem/../dprint.h"
extern int debug;
extern int log_stderr;
extern int log_facility;
extern char* log_name;







void dprint (char* format, ...);

int str2facility(char *s);
# 37 "../../mem/../mem/mem.h" 2
# 54 "../../mem/../mem/mem.h"
# 1 "../../mem/../mem/f_malloc.h" 1
# 40 "../../mem/../mem/f_malloc.h"
# 1 "../../mem/../mem/meminfo.h" 1
# 34 "../../mem/../mem/meminfo.h"
struct mem_info{
 unsigned long total_size;
 unsigned long free;
 unsigned long used;
 unsigned long real_used;
 unsigned long max_used;
 unsigned long min_frag;
 unsigned long total_frags;
};
# 41 "../../mem/../mem/f_malloc.h" 2
# 75 "../../mem/../mem/f_malloc.h"
struct fm_frag{
 unsigned long size;
 union{
  struct fm_frag* nxt_free;
  long reserved;
 }u;






};

struct fm_frag_lnk{
 struct fm_frag* first;
 unsigned long no;
};

struct fm_block{
 unsigned long size;

 unsigned long used;
 unsigned long real_used;
 unsigned long max_real_used;


 struct fm_frag* first_frag;
 struct fm_frag* last_frag;

 struct fm_frag_lnk free_hash[((1UL<<14UL)/8UL + (sizeof(long)*8-14UL)+1)];
};



struct fm_block* fm_malloc_init(char* address, unsigned long size);





void* fm_malloc(struct fm_block*, unsigned long size);






void fm_free(struct fm_block*, void* p);






void* fm_realloc(struct fm_block*, void* p, unsigned long size);


void fm_status(struct fm_block*);
void fm_info(struct fm_block*, struct mem_info*);



static inline unsigned long fm_get_size(struct fm_block* qm)
{
 return qm->size;
}
static inline unsigned long fm_get_used(struct fm_block* qm)
{
 return qm->used;
}
static inline unsigned long fm_get_free(struct fm_block* qm)
{
 return qm->size-qm->real_used;
}
static inline unsigned long fm_get_real_used(struct fm_block* qm)
{
 return qm->real_used;
}
static inline unsigned long fm_get_max_real_used(struct fm_block* qm)
{
 return qm->max_real_used;
}
static inline unsigned long fm_get_frags(struct fm_block* qm)
{
 unsigned long frags;
 int r;
 for(r=0,frags=0;r<((1UL<<14UL)/8UL + (sizeof(long)*8-14UL)+1); r++){
  frags+=qm->free_hash[r].no;
 }
 return frags;
}
# 55 "../../mem/../mem/mem.h" 2
  extern struct fm_block* mem_block;





 extern char mem_pool[1024*1024];
# 129 "../../mem/../mem/mem.h"
int init_pkg_mallocs();
int init_shm_mallocs();
# 51 "../../mem/../lock_alloc.h" 2

# 1 "../../mem/../mem/shm_mem.h" 1
# 33 "../../mem/../mem/shm_mem.h"
# 1 "../../mem/../mem/../statistics.h" 1
# 34 "../../mem/../mem/shm_mem.h" 2




# 1 "/usr/include/string.h" 1 3 4
# 28 "/usr/include/string.h" 3 4





# 1 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 1 3 4
# 34 "/usr/include/string.h" 2 3 4




extern void *memcpy (void *__restrict __dest,
       __const void *__restrict __src, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));


extern void *memmove (void *__dest, __const void *__src, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));






extern void *memccpy (void *__restrict __dest, __const void *__restrict __src,
        int __c, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));





extern void *memset (void *__s, int __c, size_t __n) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));


extern int memcmp (__const void *__s1, __const void *__s2, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));


extern void *memchr (__const void *__s, int __c, size_t __n)
      __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));

# 82 "/usr/include/string.h" 3 4


extern char *strcpy (char *__restrict __dest, __const char *__restrict __src)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));

extern char *strncpy (char *__restrict __dest,
        __const char *__restrict __src, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));


extern char *strcat (char *__restrict __dest, __const char *__restrict __src)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));

extern char *strncat (char *__restrict __dest, __const char *__restrict __src,
        size_t __n) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));


extern int strcmp (__const char *__s1, __const char *__s2)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));

extern int strncmp (__const char *__s1, __const char *__s2, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));


extern int strcoll (__const char *__s1, __const char *__s2)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));

extern size_t strxfrm (char *__restrict __dest,
         __const char *__restrict __src, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2)));

# 130 "/usr/include/string.h" 3 4
extern char *strdup (__const char *__s)
     __attribute__ ((__nothrow__)) __attribute__ ((__malloc__)) __attribute__ ((__nonnull__ (1)));
# 165 "/usr/include/string.h" 3 4


extern char *strchr (__const char *__s, int __c)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));

extern char *strrchr (__const char *__s, int __c)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));

# 181 "/usr/include/string.h" 3 4



extern size_t strcspn (__const char *__s, __const char *__reject)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));


extern size_t strspn (__const char *__s, __const char *__accept)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));

extern char *strpbrk (__const char *__s, __const char *__accept)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));

extern char *strstr (__const char *__haystack, __const char *__needle)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));



extern char *strtok (char *__restrict __s, __const char *__restrict __delim)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2)));




extern char *__strtok_r (char *__restrict __s,
    __const char *__restrict __delim,
    char **__restrict __save_ptr)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2, 3)));

extern char *strtok_r (char *__restrict __s, __const char *__restrict __delim,
         char **__restrict __save_ptr)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2, 3)));
# 240 "/usr/include/string.h" 3 4


extern size_t strlen (__const char *__s)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));

# 254 "/usr/include/string.h" 3 4


extern char *strerror (int __errnum) __attribute__ ((__nothrow__));

# 281 "/usr/include/string.h" 3 4
extern char *strerror_r (int __errnum, char *__buf, size_t __buflen)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (2)));





extern void __bzero (void *__s, size_t __n) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));



extern void bcopy (__const void *__src, void *__dest, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));


extern void bzero (void *__s, size_t __n) __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1)));


extern int bcmp (__const void *__s1, __const void *__s2, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));


extern char *index (__const char *__s, int __c)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));


extern char *rindex (__const char *__s, int __c)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));



extern int ffs (int __i) __attribute__ ((__nothrow__)) __attribute__ ((__const__));
# 325 "/usr/include/string.h" 3 4
extern int strcasecmp (__const char *__s1, __const char *__s2)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));


extern int strncasecmp (__const char *__s1, __const char *__s2, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
# 348 "/usr/include/string.h" 3 4
extern char *strsep (char **__restrict __stringp,
       __const char *__restrict __delim)
     __attribute__ ((__nothrow__)) __attribute__ ((__nonnull__ (1, 2)));
# 414 "/usr/include/string.h" 3 4
# 1 "/usr/include/bits/string.h" 1 3 4
# 415 "/usr/include/string.h" 2 3 4


# 1 "/usr/include/bits/string2.h" 1 3 4
# 80 "/usr/include/bits/string2.h" 3 4
typedef struct { unsigned char __arr[2]; } __attribute__ ((__packed__)) __STRING2_COPY_ARR2;
typedef struct { unsigned char __arr[3]; } __attribute__ ((__packed__)) __STRING2_COPY_ARR3;
typedef struct { unsigned char __arr[4]; } __attribute__ ((__packed__)) __STRING2_COPY_ARR4;
typedef struct { unsigned char __arr[5]; } __attribute__ ((__packed__)) __STRING2_COPY_ARR5;
typedef struct { unsigned char __arr[6]; } __attribute__ ((__packed__)) __STRING2_COPY_ARR6;
typedef struct { unsigned char __arr[7]; } __attribute__ ((__packed__)) __STRING2_COPY_ARR7;
typedef struct { unsigned char __arr[8]; } __attribute__ ((__packed__)) __STRING2_COPY_ARR8;
# 394 "/usr/include/bits/string2.h" 3 4
extern void *__rawmemchr (const void *__s, int __c);
# 969 "/usr/include/bits/string2.h" 3 4
extern __inline size_t __strcspn_c1 (__const char *__s, int __reject);
extern __inline size_t
__strcspn_c1 (__const char *__s, int __reject)
{
  register size_t __result = 0;
  while (__s[__result] != '\0' && __s[__result] != __reject)
    ++__result;
  return __result;
}

extern __inline size_t __strcspn_c2 (__const char *__s, int __reject1,
         int __reject2);
extern __inline size_t
__strcspn_c2 (__const char *__s, int __reject1, int __reject2)
{
  register size_t __result = 0;
  while (__s[__result] != '\0' && __s[__result] != __reject1
  && __s[__result] != __reject2)
    ++__result;
  return __result;
}

extern __inline size_t __strcspn_c3 (__const char *__s, int __reject1,
         int __reject2, int __reject3);
extern __inline size_t
__strcspn_c3 (__const char *__s, int __reject1, int __reject2,
       int __reject3)
{
  register size_t __result = 0;
  while (__s[__result] != '\0' && __s[__result] != __reject1
  && __s[__result] != __reject2 && __s[__result] != __reject3)
    ++__result;
  return __result;
}
# 1045 "/usr/include/bits/string2.h" 3 4
extern __inline size_t __strspn_c1 (__const char *__s, int __accept);
extern __inline size_t
__strspn_c1 (__const char *__s, int __accept)
{
  register size_t __result = 0;

  while (__s[__result] == __accept)
    ++__result;
  return __result;
}

extern __inline size_t __strspn_c2 (__const char *__s, int __accept1,
        int __accept2);
extern __inline size_t
__strspn_c2 (__const char *__s, int __accept1, int __accept2)
{
  register size_t __result = 0;

  while (__s[__result] == __accept1 || __s[__result] == __accept2)
    ++__result;
  return __result;
}

extern __inline size_t __strspn_c3 (__const char *__s, int __accept1,
        int __accept2, int __accept3);
extern __inline size_t
__strspn_c3 (__const char *__s, int __accept1, int __accept2, int __accept3)
{
  register size_t __result = 0;

  while (__s[__result] == __accept1 || __s[__result] == __accept2
  || __s[__result] == __accept3)
    ++__result;
  return __result;
}
# 1121 "/usr/include/bits/string2.h" 3 4
extern __inline char *__strpbrk_c2 (__const char *__s, int __accept1,
         int __accept2);
extern __inline char *
__strpbrk_c2 (__const char *__s, int __accept1, int __accept2)
{

  while (*__s != '\0' && *__s != __accept1 && *__s != __accept2)
    ++__s;
  return *__s == '\0' ? ((void *)0) : (char *) (size_t) __s;
}

extern __inline char *__strpbrk_c3 (__const char *__s, int __accept1,
         int __accept2, int __accept3);
extern __inline char *
__strpbrk_c3 (__const char *__s, int __accept1, int __accept2,
       int __accept3)
{

  while (*__s != '\0' && *__s != __accept1 && *__s != __accept2
  && *__s != __accept3)
    ++__s;
  return *__s == '\0' ? ((void *)0) : (char *) (size_t) __s;
}
# 1173 "/usr/include/bits/string2.h" 3 4
extern __inline char *__strtok_r_1c (char *__s, char __sep, char **__nextp);
extern __inline char *
__strtok_r_1c (char *__s, char __sep, char **__nextp)
{
  char *__result;
  if (__s == ((void *)0))
    __s = *__nextp;
  while (*__s == __sep)
    ++__s;
  __result = ((void *)0);
  if (*__s != '\0')
    {
      __result = __s++;
      while (*__s != '\0')
 if (*__s++ == __sep)
   {
     __s[-1] = '\0';
     break;
   }
      *__nextp = __s;
    }
  return __result;
}
# 1205 "/usr/include/bits/string2.h" 3 4
extern char *__strsep_g (char **__stringp, __const char *__delim);
# 1223 "/usr/include/bits/string2.h" 3 4
extern __inline char *__strsep_1c (char **__s, char __reject);
extern __inline char *
__strsep_1c (char **__s, char __reject)
{
  register char *__retval = *__s;
  if (__retval != ((void *)0) && (*__s = (__extension__ (__builtin_constant_p (__reject) && !__builtin_constant_p (__retval) && (__reject) == '\0' ? (char *) __rawmemchr (__retval, __reject) : __builtin_strchr (__retval, __reject)))) != ((void *)0))
    *(*__s)++ = '\0';
  return __retval;
}

extern __inline char *__strsep_2c (char **__s, char __reject1, char __reject2);
extern __inline char *
__strsep_2c (char **__s, char __reject1, char __reject2)
{
  register char *__retval = *__s;
  if (__retval != ((void *)0))
    {
      register char *__cp = __retval;
      while (1)
 {
   if (*__cp == '\0')
     {
       __cp = ((void *)0);
   break;
     }
   if (*__cp == __reject1 || *__cp == __reject2)
     {
       *__cp++ = '\0';
       break;
     }
   ++__cp;
 }
      *__s = __cp;
    }
  return __retval;
}

extern __inline char *__strsep_3c (char **__s, char __reject1, char __reject2,
       char __reject3);
extern __inline char *
__strsep_3c (char **__s, char __reject1, char __reject2, char __reject3)
{
  register char *__retval = *__s;
  if (__retval != ((void *)0))
    {
      register char *__cp = __retval;
      while (1)
 {
   if (*__cp == '\0')
     {
       __cp = ((void *)0);
   break;
     }
   if (*__cp == __reject1 || *__cp == __reject2 || *__cp == __reject3)
     {
       *__cp++ = '\0';
       break;
     }
   ++__cp;
 }
      *__s = __cp;
    }
  return __retval;
}
# 1304 "/usr/include/bits/string2.h" 3 4
extern char *__strdup (__const char *__string) __attribute__ ((__nothrow__)) __attribute__ ((__malloc__));
# 1323 "/usr/include/bits/string2.h" 3 4
extern char *__strndup (__const char *__string, size_t __n)
     __attribute__ ((__nothrow__)) __attribute__ ((__malloc__));
# 418 "/usr/include/string.h" 2 3 4
# 426 "/usr/include/string.h" 3 4

# 39 "../../mem/../mem/shm_mem.h" 2
# 1 "/usr/include/errno.h" 1 3 4
# 32 "/usr/include/errno.h" 3 4




# 1 "/usr/include/bits/errno.h" 1 3 4
# 25 "/usr/include/bits/errno.h" 3 4
# 1 "/usr/include/linux/errno.h" 1 3 4



# 1 "/usr/include/asm/errno.h" 1 3 4



# 1 "/usr/include/asm-generic/errno.h" 1 3 4



# 1 "/usr/include/asm-generic/errno-base.h" 1 3 4
# 5 "/usr/include/asm-generic/errno.h" 2 3 4
# 5 "/usr/include/asm/errno.h" 2 3 4
# 5 "/usr/include/linux/errno.h" 2 3 4
# 26 "/usr/include/bits/errno.h" 2 3 4
# 38 "/usr/include/bits/errno.h" 3 4
extern int *__errno_location (void) __attribute__ ((__nothrow__)) __attribute__ ((__const__));
# 37 "/usr/include/errno.h" 2 3 4
# 59 "/usr/include/errno.h" 3 4

# 40 "../../mem/../mem/shm_mem.h" 2

# 1 "/usr/include/sys/ipc.h" 1 3 4
# 29 "/usr/include/sys/ipc.h" 3 4
# 1 "/usr/include/bits/ipctypes.h" 1 3 4
# 31 "/usr/include/bits/ipctypes.h" 3 4
typedef unsigned short int __ipc_pid_t;
# 30 "/usr/include/sys/ipc.h" 2 3 4
# 1 "/usr/include/bits/ipc.h" 1 3 4
# 43 "/usr/include/bits/ipc.h" 3 4
struct ipc_perm
  {
    __key_t __key;
    __uid_t uid;
    __gid_t gid;
    __uid_t cuid;
    __gid_t cgid;
    unsigned short int mode;
    unsigned short int __pad1;
    unsigned short int __seq;
    unsigned short int __pad2;
    unsigned long int __unused1;
    unsigned long int __unused2;
  };
# 31 "/usr/include/sys/ipc.h" 2 3 4
# 52 "/usr/include/sys/ipc.h" 3 4



extern key_t ftok (__const char *__pathname, int __proj_id) __attribute__ ((__nothrow__));


# 42 "../../mem/../mem/shm_mem.h" 2







# 1 "/usr/include/sys/sem.h" 1 3 4
# 25 "/usr/include/sys/sem.h" 3 4
# 1 "/usr/lib/gcc/arm-linux-gnu/4.1.2/include/stddef.h" 1 3 4
# 26 "/usr/include/sys/sem.h" 2 3 4





# 1 "/usr/include/bits/sem.h" 1 3 4
# 39 "/usr/include/bits/sem.h" 3 4
struct semid_ds
{
  struct ipc_perm sem_perm;
  __time_t sem_otime;
  unsigned long int __unused1;
  __time_t sem_ctime;
  unsigned long int __unused2;
  unsigned long int sem_nsems;
  unsigned long int __unused3;
  unsigned long int __unused4;
};
# 73 "/usr/include/bits/sem.h" 3 4
struct seminfo
{
  int semmap;
  int semmni;
  int semmns;
  int semmnu;
  int semmsl;
  int semopm;
  int semume;
  int semusz;
  int semvmx;
  int semaem;
};
# 32 "/usr/include/sys/sem.h" 2 3 4
# 42 "/usr/include/sys/sem.h" 3 4
struct sembuf
{
  unsigned short int sem_num;
  short int sem_op;
  short int sem_flg;
};





extern int semctl (int __semid, int __semnum, int __cmd, ...) __attribute__ ((__nothrow__));


extern int semget (key_t __key, int __nsems, int __semflg) __attribute__ ((__nothrow__));


extern int semop (int __semid, struct sembuf *__sops, size_t __nsops) __attribute__ ((__nothrow__));








# 50 "../../mem/../mem/shm_mem.h" 2

# 1 "/usr/include/errno.h" 1 3 4
# 52 "../../mem/../mem/shm_mem.h" 2
# 68 "../../mem/../mem/shm_mem.h"
# 1 "../../mem/../mem/../lock_ops.h" 1
# 69 "../../mem/../mem/shm_mem.h" 2
# 79 "../../mem/../mem/shm_mem.h"
# 1 "../../mem/../mem/f_malloc.h" 1
# 80 "../../mem/../mem/shm_mem.h" 2
 extern struct fm_block* shm_block;
# 115 "../../mem/../mem/shm_mem.h"
 extern gen_lock_t* mem_lock;


int shm_mem_init();
int shm_getmem();
int shm_mem_init_mallocs(void* mempool, unsigned long size);


void shm_mem_destroy();
# 197 "../../mem/../mem/shm_mem.h"
inline static void* shm_malloc(unsigned int size)
{
 void *p;

 get_lock(mem_lock);
 p=fm_malloc(shm_block, (size));
 release_lock(mem_lock);
  return p;
}


inline static void* shm_realloc(void *ptr, unsigned int size)
{
 void *p;
 get_lock(mem_lock);
 p=fm_realloc(shm_block, ptr, size);
 release_lock(mem_lock);
 return p;
}
# 230 "../../mem/../mem/shm_mem.h"
void* _shm_resize(void* ptr, unsigned int size);
# 255 "../../mem/../mem/shm_mem.h"
extern stat_export_t shm_stats[];

inline static unsigned long shm_get_size() {
 return fm_get_size(shm_block);
}
inline static unsigned long shm_get_used() {
 return fm_get_used(shm_block);
}
inline static unsigned long shm_get_rused() {
 return fm_get_real_used(shm_block);
}
inline static unsigned long shm_get_mused() {
 return fm_get_max_real_used(shm_block);
}
inline static unsigned long shm_get_free() {
 return fm_get_free(shm_block);
}
inline static unsigned long shm_get_frags() {
 return fm_get_frags(shm_block);
}
# 53 "../../mem/../lock_alloc.h" 2
# 63 "../../mem/../lock_alloc.h"
inline static gen_lock_set_t* lock_set_alloc(int n)
{
 gen_lock_set_t* ls;
 ls=(gen_lock_set_t*)shm_malloc(sizeof(gen_lock_set_t)+n*sizeof(gen_lock_t));
 if (ls==0){
  do { if (debug>=(-2)){ if (log_stderr) dprint ("ERROR: lock_set_alloc (FL): could not allocate lock_set\n"); else { switch(-2){ case -2: syslog(2|log_facility, "ERROR: lock_set_alloc (FL): could not allocate lock_set\n"); break; case -3: syslog(1|log_facility, "ERROR: lock_set_alloc (FL): could not allocate lock_set\n"); break; case -1: syslog(3|log_facility, "ERROR: lock_set_alloc (FL): could not allocate lock_set\n"); break; case 1: syslog(4|log_facility, "ERROR: lock_set_alloc (FL): could not allocate lock_set\n"); break; case 2: syslog(5|log_facility, "ERROR: lock_set_alloc (FL): could not allocate lock_set\n"); break; case 3: syslog(6|log_facility, "ERROR: lock_set_alloc (FL): could not allocate lock_set\n"); break; case 4: syslog(7|log_facility, "ERROR: lock_set_alloc (FL): could not allocate lock_set\n"); break; } } } }while(0);
 }else{
  ls->locks=(gen_lock_t*)((char*)ls+sizeof(gen_lock_set_t));
  ls->size=n;
 }
 return ls;
}
# 67 "../../mem/../locking.h" 2
# 103 "../../mem/../statistics.h" 2
extern gen_lock_t *stat_lock;
# 34 "../../mem/shm_mem.h" 2
# 38 "tree234.c" 2
# 52 "tree234.c"
typedef struct node234_Tag node234;

struct tree234_Tag {
    node234 *root;
    cmpfn234 cmp;
};

struct node234_Tag {
    node234 *parent;
    node234 *kids[4];
    int counts[4];
    void *elems[3];
};




tree234 *newtree234(cmpfn234 cmp) {
    tree234 *ret = ( (tree234 *) shm_malloc (sizeof (tree234)) );
    ;
    ret->root = ((void *)0);
    ret->cmp = cmp;
    return ret;
}




static void freenode234(node234 *n) {
    if (!n)
 return;
    freenode234(n->kids[0]);
    freenode234(n->kids[1]);
    freenode234(n->kids[2]);
    freenode234(n->kids[3]);
    do { get_lock(mem_lock); fm_free(shm_block, (n)); release_lock(mem_lock); }while(0);
}
void freetree234(tree234 *t)
{
    if(t == ((void *)0))
     return;
    freenode234(t->root);
    do { get_lock(mem_lock); fm_free(shm_block, (t)); release_lock(mem_lock); }while(0);
}




static void free2node234(node234 *n, freefn fn )
{
    if (!n)
 return;
    free2node234(n->kids[0], fn);
    free2node234(n->kids[1], fn);
    free2node234(n->kids[2], fn);
    free2node234(n->kids[3], fn);
    fn(n->elems[0]);
    fn(n->elems[1]);
    fn(n->elems[2]);
    do { get_lock(mem_lock); fm_free(shm_block, (n)); release_lock(mem_lock); }while(0);
}
void free2tree234(tree234 *t, freefn fn)
{
    if(t == ((void *)0))
     return;
    free2node234(t->root, fn);
    do { get_lock(mem_lock); fm_free(shm_block, (t)); release_lock(mem_lock); }while(0);
}





static int countnode234(node234 *n) {
    int count = 0;
    int i;
    if (!n)
 return 0;
    for (i = 0; i < 4; i++)
 count += n->counts[i];
    for (i = 0; i < 3; i++)
 if (n->elems[i])
     count++;
    return count;
}




int count234(tree234 *t) {
    if (t->root)
 return countnode234(t->root);
    else
 return 0;
}





static void *add234_internal(tree234 *t, void *e, int index) {
    node234 *n, **np, *left, *right;
    void *orig_e = e;
    int c, lcount, rcount;

    ;
    if (t->root == ((void *)0)) {
 t->root = ( (node234 *) shm_malloc (sizeof (node234)) );
 t->root->elems[1] = t->root->elems[2] = ((void *)0);
 t->root->kids[0] = t->root->kids[1] = ((void *)0);
 t->root->kids[2] = t->root->kids[3] = ((void *)0);
 t->root->counts[0] = t->root->counts[1] = 0;
 t->root->counts[2] = t->root->counts[3] = 0;
 t->root->parent = ((void *)0);
 t->root->elems[0] = e;
 ;
 return orig_e;
 }

 np = &t->root;
 n = *np;

 while (*np) {
 int childnum;
 n = *np;
 ;





 if (index >= 0) {
     if (!n->kids[0]) {






  childnum = index;
     } else {





  do {
      if (index <= n->counts[0]) {
   childnum = 0;
   break;
      }
      index -= n->counts[0] + 1;
      if (index <= n->counts[1]) {
   childnum = 1;
   break;
      }
      index -= n->counts[1] + 1;
      if (index <= n->counts[2]) {
   childnum = 2;
   break;
      }
      index -= n->counts[2] + 1;
      if (index <= n->counts[3]) {
   childnum = 3;
   break;
      }
      return ((void *)0);
  } while (0);
     }
 } else {
     if ((c = t->cmp(e, n->elems[0])) < 0)
  childnum = 0;
     else if (c == 0)
  return n->elems[0];
     else if (n->elems[1] == ((void *)0) || (c = t->cmp(e, n->elems[1])) < 0)
  childnum = 1;
     else if (c == 0)
  return n->elems[1];
     else if (n->elems[2] == ((void *)0) || (c = t->cmp(e, n->elems[2])) < 0)
  childnum = 2;
     else if (c == 0)
  return n->elems[2];
     else
  childnum = 3;
 }
 np = &n->kids[childnum];
 ;
    }




    left = ((void *)0); lcount = 0;
    right = ((void *)0); rcount = 0;
    while (n) {
 ;





 ;

 if (n->elems[1] == ((void *)0)) {



     if (np == &n->kids[0]) {
  ;
  n->kids[2] = n->kids[1]; n->counts[2] = n->counts[1];
  n->elems[1] = n->elems[0];
  n->kids[1] = right; n->counts[1] = rcount;
  n->elems[0] = e;
  n->kids[0] = left; n->counts[0] = lcount;
     } else {
  ;
  n->kids[2] = right; n->counts[2] = rcount;
  n->elems[1] = e;
  n->kids[1] = left; n->counts[1] = lcount;
     }
     if (n->kids[0]) n->kids[0]->parent = n;
     if (n->kids[1]) n->kids[1]->parent = n;
     if (n->kids[2]) n->kids[2]->parent = n;
     ;
     break;
 } else if (n->elems[2] == ((void *)0)) {



     if (np == &n->kids[0]) {
  ;
  n->kids[3] = n->kids[2]; n->counts[3] = n->counts[2];
  n->elems[2] = n->elems[1];
  n->kids[2] = n->kids[1]; n->counts[2] = n->counts[1];
  n->elems[1] = n->elems[0];
  n->kids[1] = right; n->counts[1] = rcount;
  n->elems[0] = e;
  n->kids[0] = left; n->counts[0] = lcount;
     } else if (np == &n->kids[1]) {
  ;
  n->kids[3] = n->kids[2]; n->counts[3] = n->counts[2];
  n->elems[2] = n->elems[1];
  n->kids[2] = right; n->counts[2] = rcount;
  n->elems[1] = e;
  n->kids[1] = left; n->counts[1] = lcount;
     } else {
  ;
  n->kids[3] = right; n->counts[3] = rcount;
  n->elems[2] = e;
  n->kids[2] = left; n->counts[2] = lcount;
     }
     if (n->kids[0]) n->kids[0]->parent = n;
     if (n->kids[1]) n->kids[1]->parent = n;
     if (n->kids[2]) n->kids[2]->parent = n;
     if (n->kids[3]) n->kids[3]->parent = n;
     ;
     break;
 } else {
     node234 *m = ( (node234 *) shm_malloc (sizeof (node234)) );
     m->parent = n->parent;
     ;
# 321 "tree234.c"
     if (np == &n->kids[0]) {
  m->kids[0] = left; m->counts[0] = lcount;
  m->elems[0] = e;
  m->kids[1] = right; m->counts[1] = rcount;
  m->elems[1] = n->elems[0];
  m->kids[2] = n->kids[1]; m->counts[2] = n->counts[1];
  e = n->elems[1];
  n->kids[0] = n->kids[2]; n->counts[0] = n->counts[2];
  n->elems[0] = n->elems[2];
  n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
     } else if (np == &n->kids[1]) {
  m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
  m->elems[0] = n->elems[0];
  m->kids[1] = left; m->counts[1] = lcount;
  m->elems[1] = e;
  m->kids[2] = right; m->counts[2] = rcount;
  e = n->elems[1];
  n->kids[0] = n->kids[2]; n->counts[0] = n->counts[2];
  n->elems[0] = n->elems[2];
  n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
     } else if (np == &n->kids[2]) {
  m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
  m->elems[0] = n->elems[0];
  m->kids[1] = n->kids[1]; m->counts[1] = n->counts[1];
  m->elems[1] = n->elems[1];
  m->kids[2] = left; m->counts[2] = lcount;

  n->kids[0] = right; n->counts[0] = rcount;
  n->elems[0] = n->elems[2];
  n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
     } else {
  m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
  m->elems[0] = n->elems[0];
  m->kids[1] = n->kids[1]; m->counts[1] = n->counts[1];
  m->elems[1] = n->elems[1];
  m->kids[2] = n->kids[2]; m->counts[2] = n->counts[2];
  n->kids[0] = left; n->counts[0] = lcount;
  n->elems[0] = e;
  n->kids[1] = right; n->counts[1] = rcount;
  e = n->elems[2];
     }
     m->kids[3] = n->kids[3] = n->kids[2] = ((void *)0);
     m->counts[3] = n->counts[3] = n->counts[2] = 0;
     m->elems[2] = n->elems[2] = n->elems[1] = ((void *)0);
     if (m->kids[0]) m->kids[0]->parent = m;
     if (m->kids[1]) m->kids[1]->parent = m;
     if (m->kids[2]) m->kids[2]->parent = m;
     if (n->kids[0]) n->kids[0]->parent = n;
     if (n->kids[1]) n->kids[1]->parent = n;
     ;



     ;


     left = m; lcount = countnode234(left);
     right = n; rcount = countnode234(right);
 }
 if (n->parent)
     np = (n->parent->kids[0] == n ? &n->parent->kids[0] :
    n->parent->kids[1] == n ? &n->parent->kids[1] :
    n->parent->kids[2] == n ? &n->parent->kids[2] :
    &n->parent->kids[3]);
 n = n->parent;
    }







    if (n) {
 while (n->parent) {
     int count = countnode234(n);
     int childnum;
     childnum = (n->parent->kids[0] == n ? 0 :
   n->parent->kids[1] == n ? 1 :
   n->parent->kids[2] == n ? 2 : 3);
     n->parent->counts[childnum] = count;
     n = n->parent;
 }
    } else {
 ;
 t->root = ( (node234 *) shm_malloc (sizeof (node234)) );
 t->root->kids[0] = left; t->root->counts[0] = lcount;
 t->root->elems[0] = e;
 t->root->kids[1] = right; t->root->counts[1] = rcount;
 t->root->elems[1] = ((void *)0);
 t->root->kids[2] = ((void *)0); t->root->counts[2] = 0;
 t->root->elems[2] = ((void *)0);
 t->root->kids[3] = ((void *)0); t->root->counts[3] = 0;
 t->root->parent = ((void *)0);
 if (t->root->kids[0]) t->root->kids[0]->parent = t->root;
 if (t->root->kids[1]) t->root->kids[1]->parent = t->root;
 ;



    }

    return orig_e;
}

void *add234(tree234 *t, void *e) {
    if (!t->cmp)
 return ((void *)0);

    return add234_internal(t, e, -1);
}
void *addpos234(tree234 *t, void *e, int index) {
    if (index < 0 ||
 t->cmp)
 return ((void *)0);

    return add234_internal(t, e, index);
}





void *index234(tree234 *t, int index) {
    node234 *n;

    if (!t->root)
 return ((void *)0);

    if (index < 0 || index >= countnode234(t->root))
 return ((void *)0);

    n = t->root;

    while (n) {
 if (index < n->counts[0])
     n = n->kids[0];
 else if (index -= n->counts[0] + 1, index < 0)
     return n->elems[0];
 else if (index < n->counts[1])
     n = n->kids[1];
 else if (index -= n->counts[1] + 1, index < 0)
     return n->elems[1];
 else if (index < n->counts[2])
     n = n->kids[2];
 else if (index -= n->counts[2] + 1, index < 0)
     return n->elems[2];
 else
     n = n->kids[3];
    }


    return ((void *)0);
}
# 483 "tree234.c"
void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp,
      int relation, int *index) {
    node234 *n;
    void *ret;
    int c;
    int idx, ecount, kcount, cmpret;

    if (t->root == ((void *)0))
 return ((void *)0);

    if (cmp == ((void *)0))
 cmp = t->cmp;

    n = t->root;



    idx = 0;
    ecount = -1;



    cmpret = 0;
    if (e == ((void *)0)) {
 ((void) ((relation == REL234_LT || relation == REL234_GT) ? 0 : (__assert_fail ("relation == REL234_LT || relation == REL234_GT", "tree234.c", 507, __PRETTY_FUNCTION__), 0)));
 if (relation == REL234_LT)
     cmpret = +1;
 else if (relation == REL234_GT)
     cmpret = -1;
    }
    while (1) {
 for (kcount = 0; kcount < 4; kcount++) {
     if (kcount >= 3 || n->elems[kcount] == ((void *)0) ||
  (c = cmpret ? cmpret : cmp(e, n->elems[kcount])) < 0) {
  break;
     }
     if (n->kids[kcount]) idx += n->counts[kcount];
     if (c == 0) {
  ecount = kcount;
  break;
     }
     idx++;
 }
 if (ecount >= 0)
     break;
 if (n->kids[kcount])
     n = n->kids[kcount];
 else
     break;
    }

    if (ecount >= 0) {





 if (relation != REL234_LT && relation != REL234_GT) {
     if (index) *index = idx;
     return n->elems[ecount];
 }







 if (relation == REL234_LT)
     idx--;
 else
     idx++;
    } else {
# 565 "tree234.c"
 if (relation == REL234_EQ)
     return ((void *)0);






 if (relation == REL234_LT || relation == REL234_LE) {
     idx--;
 }
    }






    ret = index234(t, idx);
    if (ret && index) *index = idx;
    return ret;
}
void *find234(tree234 *t, void *e, cmpfn234 cmp) {
    return findrelpos234(t, e, cmp, REL234_EQ, ((void *)0));
}
void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation) {
    return findrelpos234(t, e, cmp, relation, ((void *)0));
}
void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index) {
    return findrelpos234(t, e, cmp, REL234_EQ, index);
}





static void *delpos234_internal(tree234 *t, int index) {
    node234 *n;
    void *retval;
    int ei = -1;

    retval = 0;

    n = t->root;
    ;
    while (1) {
 while (n) {
     int ki;
     node234 *sub;

     ;






     if (index < n->counts[0]) {
  ki = 0;
     } else if (index -= n->counts[0]+1, index < 0) {
  ei = 0; break;
     } else if (index < n->counts[1]) {
  ki = 1;
     } else if (index -= n->counts[1]+1, index < 0) {
  ei = 1; break;
     } else if (index < n->counts[2]) {
  ki = 2;
     } else if (index -= n->counts[2]+1, index < 0) {
  ei = 2; break;
     } else {
  ki = 3;
     }




     ;
     sub = n->kids[ki];
     if (!sub->elems[1]) {
  ;
  if (ki > 0 && n->kids[ki-1]->elems[1]) {
# 656 "tree234.c"
      node234 *sib = n->kids[ki-1];
      int lastelem = (sib->elems[2] ? 2 :
        sib->elems[1] ? 1 : 0);
      sub->kids[2] = sub->kids[1];
      sub->counts[2] = sub->counts[1];
      sub->elems[1] = sub->elems[0];
      sub->kids[1] = sub->kids[0];
      sub->counts[1] = sub->counts[0];
      sub->elems[0] = n->elems[ki-1];
      sub->kids[0] = sib->kids[lastelem+1];
      sub->counts[0] = sib->counts[lastelem+1];
      if (sub->kids[0]) sub->kids[0]->parent = sub;
      n->elems[ki-1] = sib->elems[lastelem];
      sib->kids[lastelem+1] = ((void *)0);
      sib->counts[lastelem+1] = 0;
      sib->elems[lastelem] = ((void *)0);
      n->counts[ki] = countnode234(sub);
      ;
      ;

      index += n->counts[ki-1];
      n->counts[ki-1] = countnode234(sib);
      index -= n->counts[ki-1];
      ;

  } else if (ki < 3 && n->kids[ki+1] &&
      n->kids[ki+1]->elems[1]) {
# 692 "tree234.c"
      node234 *sib = n->kids[ki+1];
      int j;
      sub->elems[1] = n->elems[ki];
      sub->kids[2] = sib->kids[0];
      sub->counts[2] = sib->counts[0];
      if (sub->kids[2]) sub->kids[2]->parent = sub;
      n->elems[ki] = sib->elems[0];
      sib->kids[0] = sib->kids[1];
      sib->counts[0] = sib->counts[1];
      for (j = 0; j < 2 && sib->elems[j+1]; j++) {
   sib->kids[j+1] = sib->kids[j+2];
   sib->counts[j+1] = sib->counts[j+2];
   sib->elems[j] = sib->elems[j+1];
      }
      sib->kids[j+1] = ((void *)0);
      sib->counts[j+1] = 0;
      sib->elems[j] = ((void *)0);
      n->counts[ki] = countnode234(sub);
      n->counts[ki+1] = countnode234(sib);
      ;
  } else {
# 732 "tree234.c"
      node234 *sib;
      int j;

      if (ki > 0) {
   ki--;
   index += n->counts[ki] + 1;
      }
      sib = n->kids[ki];
      sub = n->kids[ki+1];

      sub->kids[3] = sub->kids[1];
      sub->counts[3] = sub->counts[1];
      sub->elems[2] = sub->elems[0];
      sub->kids[2] = sub->kids[0];
      sub->counts[2] = sub->counts[0];
      sub->elems[1] = n->elems[ki];
      sub->kids[1] = sib->kids[1];
      sub->counts[1] = sib->counts[1];
      if (sub->kids[1]) sub->kids[1]->parent = sub;
      sub->elems[0] = sib->elems[0];
      sub->kids[0] = sib->kids[0];
      sub->counts[0] = sib->counts[0];
      if (sub->kids[0]) sub->kids[0]->parent = sub;

      n->counts[ki+1] = countnode234(sub);

      do { get_lock(mem_lock); fm_free(shm_block, (sib)); release_lock(mem_lock); }while(0);





      for (j = ki; j < 3 && n->kids[j+1]; j++) {
   n->kids[j] = n->kids[j+1];
   n->counts[j] = n->counts[j+1];
   n->elems[j] = j<2 ? n->elems[j+1] : ((void *)0);
      }
      n->kids[j] = ((void *)0);
      n->counts[j] = 0;
      if (j < 3) n->elems[j] = ((void *)0);
      ;

      if (!n->elems[0]) {




   ;
   t->root = sub;
   sub->parent = ((void *)0);
   do { get_lock(mem_lock); fm_free(shm_block, (n)); release_lock(mem_lock); }while(0);
      }
  }
     }
     n = sub;
 }
 if (!retval)
     retval = n->elems[ei];

 if (ei==-1)
     return ((void *)0);






 if (!n->parent && !n->elems[1] && !n->kids[0]) {
     ;
     do { get_lock(mem_lock); fm_free(shm_block, (n)); release_lock(mem_lock); }while(0);
     t->root = ((void *)0);
     return retval;
 }







 if (!n->kids[0] && n->elems[1]) {





     int i;
     ;
     for (i = ei; i < 2 && n->elems[i+1]; i++)
  n->elems[i] = n->elems[i+1];
     n->elems[i] = ((void *)0);




     while (n->parent) {
  int childnum;
  childnum = (n->parent->kids[0] == n ? 0 :
       n->parent->kids[1] == n ? 1 :
       n->parent->kids[2] == n ? 2 : 3);
  n->parent->counts[childnum]--;
  n = n->parent;
     }
     return retval;
 } else if (n->kids[ei]->elems[1]) {
# 845 "tree234.c"
     node234 *m = n->kids[ei];
     void *target;
     ;
     while (m->kids[0]) {
  m = (m->kids[3] ? m->kids[3] :
       m->kids[2] ? m->kids[2] :
       m->kids[1] ? m->kids[1] : m->kids[0]);
     }
     target = (m->elems[2] ? m->elems[2] :
        m->elems[1] ? m->elems[1] : m->elems[0]);
     n->elems[ei] = target;
     index = n->counts[ei]-1;
     n = n->kids[ei];
 } else if (n->kids[ei+1]->elems[1]) {




     node234 *m = n->kids[ei+1];
     void *target;
     ;
     while (m->kids[0]) {
  m = m->kids[0];
     }
     target = m->elems[0];
     n->elems[ei] = target;
     n = n->kids[ei+1];
     index = 0;
 } else {
# 882 "tree234.c"
     node234 *a = n->kids[ei], *b = n->kids[ei+1];
     int j;

     ;
     a->elems[1] = n->elems[ei];
     a->kids[2] = b->kids[0];
     a->counts[2] = b->counts[0];
     if (a->kids[2]) a->kids[2]->parent = a;
     a->elems[2] = b->elems[0];
     a->kids[3] = b->kids[1];
     a->counts[3] = b->counts[1];
     if (a->kids[3]) a->kids[3]->parent = a;
     do { get_lock(mem_lock); fm_free(shm_block, (b)); release_lock(mem_lock); }while(0);
     n->counts[ei] = countnode234(a);




     for (j = ei; j < 2 && n->elems[j+1]; j++) {
  n->elems[j] = n->elems[j+1];
  n->kids[j+1] = n->kids[j+2];
  n->counts[j+1] = n->counts[j+2];
     }
     n->elems[j] = ((void *)0);
     n->kids[j+1] = ((void *)0);
     n->counts[j+1] = 0;





            if (n->elems[0] == ((void *)0)) {
                ;
                t->root = a;
                a->parent = ((void *)0);
                do { get_lock(mem_lock); fm_free(shm_block, (n)); release_lock(mem_lock); }while(0);
            }




     n = a;
     index = a->counts[0] + a->counts[1] + 1;
 }
    }
}
void *delpos234(tree234 *t, int index) {
    if (index < 0 || index >= countnode234(t->root))
 return ((void *)0);
    return delpos234_internal(t, index);
}
void *del234(tree234 *t, void *e) {
    int index;
    if (!findrelpos234(t, e, ((void *)0), REL234_EQ, &index))
  return ((void *)0);
    return delpos234_internal(t, index);
}