FUSE - хэрэглэгчийн орон зайн файл систем

Сүүлийн үед үүл, тархай систем гэсэн нэр томьёонуудыг олонтаа сонсох боллоо. Сүлжээ ашиглан зарим файлуудыг өөр тооцоолуур дээр хадгалаж, өөрийн тооцоолуур дээр байгаа мэтээр хандах гэх мэт олон дэвшилтэт арга замууд бие болсон ба ийм технологи дээр суурилсан олон start-up компани бий болсон.

Энэ бичлэгтээ ийм технологи хийхэд маш их тус болдог FUSE (хэрэглэгчийн орон зайн файл систем) дээр жишээ хийж үзсэнээ хуваалцья гэж бодлоо. Юниксжуу үйлдлийн систем дээр байгаа файл системийг хүссэнээрээ харж хэрэглэхэд тус болдог цөмийн модуль юм.

За тэгэхээр нэг ийм жишээ бичье. Та өөрийгөө тагнуулч байна гэж бод. Тагнаж байгаа хүнийхээ гэрт орлоо. Хэрэглэгчийн тодорхой хугацаанд хандсан файлыг эсвэл хамгийн сүүлд хандсан файлыг олохыг хүслээ гэж бодьё. Энэ жишээн дээр бичих програм маань тодорхой хавтасыг хувьсагч болгож өгөөд ажиллуулахад тэр хавтасан дотор байгаа файлуудыг хамгийн сүүлд өөрчлөгдсөн жил, сар, өдөр, цагаар нь ангилладаг програм байх юм.

Жишээ нь, доорх шиг хавтасыг ангилья гэж бодьё:

Дээрх зурган дээр файлын нэрүүдийн өмнөх багана файлын хамгийн сүүлд өөрчлөгдсөн огноо болохыг анхаарна уу!

Тэгвэл програмыг ажиллуулсаны хүчинд доорх байдлаар харж болох юм.

Дээрх зурган дээр бид ангилсан хавтасуудын тусламжтайгаар 2010 оны 05 сарын 10-нь 01 цагт хамгийн сүүлд өөрчлөгдсөн файлыг харж байгаа юм.

За ингээд жишээний мааны код:

modiffs.c

#define FUSE_USE_VERSION 26

static const char * modiffsVersion = "2010.12.24";

#include <sys/types.h>
#include <sys/stat.h>
#include <sys/statvfs.h>
#include <stdio.h>
#include <strings.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <errno.h>
#include <fcntl.h>
#include <sys/xattr.h>
#include <dirent.h>
#include <unistd.h>
#include <fuse.h>
#include <time.h>

#define STACK_SIZE 250

typedef struct stack_s {
   char * items[STACK_SIZE];
   int size;
} stack;

int stack_exist(stack * s, char * elem) {
   int i = 0;
   for (i=0; i < s->size; i++) {
       if (strcmp(elem, s->items[i]) == 0) {
           return 1;
       }
   }
   return 0;
}

void stack_push(stack * s, char * elem) {
   s->items[s->size++] = elem;
}

int dir_depth(const char * path) {
   int depth = 0;
   char * temp = strchr(path, '/');
   while (temp != NULL) {
       depth++;
       temp = strchr(temp + 1, '/');
   }
   return depth;
}

char * full_path(char * upath, char * d_name) {
   char * ret = (char *) malloc(sizeof(char)*(strlen(upath) + strlen(d_name) + 1));
   strcpy(ret, upath);
   strcat(ret, d_name);
   return ret;
}

// Global to store our read-write path
char * rw_path;

// Translate an modiffs path into it's underlying filesystem path
static char * translate_path(const char * path) {

   char * rPath= malloc(sizeof(char)*(strlen(path)+strlen(rw_path)+1));

   strcpy(rPath, rw_path);
   if (rPath[strlen(rPath)-1]=='/') {
       rPath[strlen(rPath)-1]='\0';
   }
  
   int depth = dir_depth(path);
  
   if (strcmp("/", path) == 0) {
       strcat(rPath, "/");
   } else if (depth < 5) {
       strcat(rPath, "/");
   } else {
       int i = 0;
       char * temp = strchr(path, '/');
       while (i < (depth-1)) {
           i++;
           temp = strchr(temp + 1, '/');
       }
       strcat(rPath, "/");
       strcat(rPath, temp);
   }
  
   return rPath;
}

/*
* level:
* 0: year
* 1: month
* 2: day
* 3: hour
*/
char * last_attr(const char * path, int level) {   
   int depth = 0;
   char * cont = (char *) malloc(sizeof(char)*strlen(path));
   strcpy(cont, path);
   char * temp = strtok(cont, "/");
   while (depth < level && temp != NULL) {
       depth++;
       temp = strtok(NULL, "/");
   }
   return temp;
}

/******************************
*
* Callbacks for FUSE
*
******************************/

static int modiffs_getattr(const char * path, struct stat * stbuf) {
  
   int res = 0;
   int depth = dir_depth(path);
   memset(stbuf, 0, sizeof(struct stat));
  
   if (strcmp(path, "/") == 0) {
       stbuf->st_mode = S_IFDIR | 0755;
       stbuf->st_nlink = 1;
       stbuf->st_ctime = time(NULL);
       stbuf->st_atime = time(NULL);
       stbuf->st_mtime = time(NULL);
       stbuf->st_size = 4096;
   } else if (depth < 5) {       
       stbuf->st_mode = S_IFDIR | 0444;
       stbuf->st_nlink = 1;
       stbuf->st_ctime = time(NULL);
       stbuf->st_atime = time(NULL);
       stbuf->st_mtime = time(NULL);
       stbuf->st_size = 4096;
   } else {       
       char * upath = translate_path(path);
       res = lstat(upath, stbuf);
       free(upath);
       if(res == -1) {
           return -errno;
       }
   }

   return res;
}

static int modiffs_readlink(const char *path, char *buf, size_t size)
{
   int res;
   char * upath = translate_path(path);

   res = readlink(upath, buf, size - 1);
   free(upath);
   if(res == -1) {
       return -errno;
   }
   buf[res] = '\0';
   return 0;
}

static int modiffs_readdir(const char *path, void *buf, fuse_fill_dir_t filler, off_t offset, struct fuse_file_info *fi) {
  
   DIR * dp;
   struct dirent * de;
   int res;
  
   struct tm *ts;
  
   (void) offset;
   (void) fi;
  
   int depth;
  
   char * upath = translate_path(path);
  
   dp = opendir(upath);
  
   if(dp == NULL) {
       res = -errno;
       return res;
   }
  
   filler(buf, ".", NULL, 0);
   filler(buf, "..", NULL, 0);
  
   if (strcmp("/", path) == 0) {       
       stack years;
       years.size = 0;
       while((de = readdir(dp)) != NULL) {       
           struct stat st_modif;
           memset(&st_modif, 0, sizeof(st_modif));
           char * year = (char *) malloc(sizeof(char) * 5);           
           stat(full_path(upath, de->d_name), &st_modif);
           ts = localtime(&(st_modif.st_mtime));
           strftime(year, 255, "%Y", ts);
           if (stack_exist(&years, year) == 0) {
               stack_push(&years, year);
               filler(buf, year, NULL, 0);
           }
       }
   } else {
       depth = dir_depth(path);
       if (depth == 1) {
           stack months;
           months.size = 0;
           while((de = readdir(dp)) != NULL) {       
               struct stat st_modif;
               memset(&st_modif, 0, sizeof(st_modif));
               char * year = (char *) malloc(sizeof(char)*5);
               char * month = (char *) malloc(sizeof(char)*3);
               stat(full_path(upath, de->d_name), &st_modif);
               ts = localtime(&(st_modif.st_mtime));
               strftime(year, 255, "%Y", ts);
               strftime(month, 255, "%m", ts);
               if (strcmp(last_attr(path,0), year) == 0) {
                   if (stack_exist(&months, month) == 0) {
                       filler(buf, month, NULL, 0);
                       stack_push(&months, month);
                   }
               }
           }
       } else if (depth == 2) {
           stack days;
           days.size = 0;
           while((de = readdir(dp)) != NULL) {       
               struct stat st_modif;
               memset(&st_modif, 0, sizeof(st_modif));
               char * year = (char *) malloc(sizeof(char)*5);
               char * month = (char *) malloc(sizeof(char)*3);
               char * day = (char *) malloc(sizeof(char)*3);
               stat(full_path(upath, de->d_name), &st_modif);
               ts = localtime(&(st_modif.st_mtime));
               strftime(year, 255, "%Y", ts);
               strftime(month, 255, "%m", ts);
               strftime(day, 255, "%d", ts);
              
               if (strcmp(last_attr(path,0), year) == 0 &&
                   strcmp(last_attr(path,1), month) == 0) {
                   if (stack_exist(&days, day) == 0) {
                       stack_push(&days, day);
                       filler(buf, day, NULL, 0);
                   }
               }                           
           }
       } else if (depth == 3) {
           stack hours;
           hours.size = 0;
           while((de = readdir(dp)) != NULL) {       
               struct stat st_modif;
               memset(&st_modif, 0, sizeof(st_modif));
               char * year = (char *) malloc(sizeof(char)*5);
               char * month = (char *) malloc(sizeof(char)*3);
               char * day = (char *) malloc(sizeof(char)*3);
               char * hour = (char *) malloc(sizeof(char)*3);
               stat(full_path(upath, de->d_name), &st_modif);
               ts = localtime(&(st_modif.st_mtime));
               strftime(year, 255, "%Y", ts);
               strftime(month, 255, "%m", ts);
               strftime(day, 255, "%d", ts);
               strftime(hour, 255, "%H", ts);
              
               if (strcmp(last_attr(path,0), year) == 0 &&
                   strcmp(last_attr(path,1), month) == 0 &&
                   strcmp(last_attr(path,2), day) == 0) {
                   if (stack_exist(&hours, hour) == 0) {
                       stack_push(&hours, hour);
                       filler(buf, hour, NULL, 0);
                   }
               }                           
           }
       } else {
           while((de = readdir(dp)) != NULL) {
               if (strcmp(".", de->d_name) == 0 || strcmp("..", de->d_name) == 0) {
                   continue;
               }             
              
               struct stat st_modif;
               memset(&st_modif, 0, sizeof(st_modif));
               char * year = (char *) malloc(sizeof(char)*5);
               char * month = (char *) malloc(sizeof(char)*3);
               char * day = (char *) malloc(sizeof(char)*3);
               char * hour = (char *) malloc(sizeof(char)*3);
               stat(full_path(upath, de->d_name), &st_modif);
               ts = localtime(&(st_modif.st_mtime));
               strftime(year, 255, "%Y", ts);
               strftime(month, 255, "%m", ts);
               strftime(day, 255, "%d", ts);
               strftime(hour, 255, "%H", ts);
              
               if (strcmp(last_attr(path,0), year) == 0 &&
                   strcmp(last_attr(path,1), month) == 0 &&
                   strcmp(last_attr(path,2), day) == 0 &&
                   strcmp(last_attr(path,3), hour) == 0) {
                  
                   struct stat st;
                   memset(&st, 0, sizeof(st));
                   st.st_ino = de->d_ino;
                   st.st_mode = de->d_type << 12;

                   if (filler(buf, de->d_name, &st, 0)) {
                       break;
                   }
               }
           }
       }
   }
  
   free(upath);
   closedir(dp);
  
   return 0;
}

static int modiffs_mknod(const char *path, mode_t mode, dev_t rdev)
{
   (void)path;
   (void)mode;
   (void)rdev;
   return -EROFS;
}

static int modiffs_mkdir(const char *path, mode_t mode)
{
   (void)path;
   (void)mode;
   return -EROFS;
}

static int modiffs_unlink(const char *path)
{
   (void)path;
   return -EROFS;
}

static int modiffs_rmdir(const char *path)
{
   (void)path;
   return -EROFS;
}

static int modiffs_symlink(const char *from, const char *to)
{
   (void)from;
   (void)to;
   return -EROFS;
}

static int modiffs_rename(const char *from, const char *to)
{
   (void)from;
   (void)to;
   return -EROFS;
}

static int modiffs_link(const char *from, const char *to)
{
   (void)from;
   (void)to;
   return -EROFS;
}

static int modiffs_chmod(const char *path, mode_t mode)
{
   (void)path;
   (void)mode;
   return -EROFS;

}

static int modiffs_chown(const char *path, uid_t uid, gid_t gid)
{
   (void)path;
   (void)uid;
   (void)gid;
   return -EROFS;
}

static int modiffs_truncate(const char *path, off_t size)
{
   (void)path;
   (void)size;
   return -EROFS;
}

static int modiffs_utime(const char *path, struct utimbuf *buf)
{
   (void)path;
   (void)buf;
   return -EROFS;
}

static int modiffs_open(const char *path, struct fuse_file_info *finfo)
{
   int res;
  
   int flags = finfo->flags;

   if ((flags & O_WRONLY) || (flags & O_RDWR) || (flags & O_CREAT) || (flags & O_EXCL) || (flags & O_TRUNC) || (flags & O_APPEND)) {
       return -EROFS;
   }
  
   char * upath = translate_path(path);

   res = open(upath, flags);

   free(upath);
   if(res == -1) {
       return -errno;
   }
   close(res);
  
   return 0;
}

static int modiffs_read(const char *path, char *buf, size_t size, off_t offset, struct fuse_file_info *finfo)
{
   int fd;
   int res;
   (void)finfo;

   char * upath = translate_path(path);
   fd = open(upath, O_RDONLY);
   free(upath);
   if(fd == -1) {
       res = -errno;
       return res;
   }
   res = pread(fd, buf, size, offset);

   if(res == -1) {
       res = -errno;
   }
   close(fd);
   return 0;
  
}

static int modiffs_write(const char *path, const char *buf, size_t size, off_t offset, struct fuse_file_info *finfo)
{
   (void)path;
   (void)buf;
   (void)size;
   (void)offset;
   (void)finfo;
   return -EROFS;
}

static int modiffs_statfs(const char *path, struct statvfs *st_buf)
{
   int res;
   char * upath = translate_path(path);
   res = statvfs(upath, st_buf);
   free(upath);
   if (res == -1) {
       return -errno;
   }
   return 0;
}

static int modiffs_release(const char *path, struct fuse_file_info *finfo)
{
   (void) path;
   (void) finfo;
   return 0;
}

static int modiffs_fsync(const char *path, int crap, struct fuse_file_info *finfo)
{
   (void) path;
   (void) crap;
   (void) finfo;
   return 0;
}

static int modiffs_access(const char *path, int mode)
{
   int res;
   char *upath = translate_path(path);

   /* Don't pretend that we allow writing
    * Chris AtLee <chris@atlee.ca>
    */
   if (mode & W_OK)
       return -EROFS;

   res = access(upath, mode);
   free(upath);
   if (res == -1) {
       return -errno;
   }
   return res;
}

struct fuse_operations modiffs_oper = {
   .getattr     = modiffs_getattr,
   .readlink    = modiffs_readlink,
   .readdir     = modiffs_readdir,
   .mknod       = modiffs_mknod,
   .mkdir       = modiffs_mkdir,
   .symlink     = modiffs_symlink,
   .unlink      = modiffs_unlink,
   .rmdir       = modiffs_rmdir,
   .rename      = modiffs_rename,
   .link        = modiffs_link,
   .chmod       = modiffs_chmod,
   .chown       = modiffs_chown,
   .truncate    = modiffs_truncate,
   .utime       = modiffs_utime,
   .open        = modiffs_open,
   .read        = modiffs_read,
   .write       = modiffs_write,
   .statfs      = modiffs_statfs,
   .release     = modiffs_release,
   .fsync       = modiffs_fsync,
   .access      = modiffs_access
};
enum {
   KEY_HELP,
   KEY_VERSION,
};

static void usage(const char* progname)
{
   fprintf(stdout,
           "usage: %s readwritepath mountpoint [options]\n"
           "\n"
           "   Mounts readwritepath as a read-only mount at mountpoint\n"
           "\n"
           "general options:\n"
           "   -o opt,[opt...]     mount options\n"
           "   -h  --help          print help\n"
           "   -V  --version       print version\n"
           "\n", progname);
}

static int modiffs_parse_opt(void *data, const char *arg, int key,
                         struct fuse_args *outargs)
{
   (void) data;

   switch (key)
   {
   case FUSE_OPT_KEY_NONOPT:
       if (rw_path == 0)
       {
           rw_path = strdup(arg);
           return 0;
       }
       else
       {
           return 1;
       }
   case FUSE_OPT_KEY_OPT:
       return 1;
   case KEY_HELP:
       usage(outargs->argv[0]);
       exit(0);
   case KEY_VERSION:
       fprintf(stdout, "ROFS version %s\n", modiffsVersion);
       exit(0);
   default:
       fprintf(stderr, "see `%s -h' for usage\n", outargs->argv[0]);
       exit(1);
   }
   return 1;
}

static struct fuse_opt modiffs_opts[] = {
   FUSE_OPT_KEY("-h",          KEY_HELP),
   FUSE_OPT_KEY("--help",      KEY_HELP),
   FUSE_OPT_KEY("-V",          KEY_VERSION),
   FUSE_OPT_KEY("--version",   KEY_VERSION),
   FUSE_OPT_END
};

int main(int argc, char *argv[])
{
   struct fuse_args args = FUSE_ARGS_INIT(argc, argv);
   int res;

   res = fuse_opt_parse(&args, &rw_path, modiffs_opts, modiffs_parse_opt);
   if (res != 0)
   {
       fprintf(stderr, "Invalid arguments\n");
       fprintf(stderr, "see `%s -h' for usage\n", argv[0]);
       exit(1);
   }
   if (rw_path == 0)
   {
       fprintf(stderr, "Missing readwritepath\n");
       fprintf(stderr, "see `%s -h' for usage\n", argv[0]);
       exit(1);
   }

   fuse_main(args.argc, args.argv, &modiffs_oper, NULL);

   return 0;
}

Дээрх кодыг Убунту дээр ирдэг fuse-rofs багцын эх код дээр өөрчлөлт хийж бий болгосоныг анхаарна уу!

Эмхэтгэж ажиллуулахын тулд:

test.sh

gcc -o modiffs -Wall -ansi -W -std=c99 -g -ggdb -D_GNU_SOURCE -D_FILE_OFFSET_BITS=64 -lfuse modiffs.c fusermount -u /home/dagvadorj/Desktop/u sudo umount /home/dagvadorj/Desktop/u ./modiffs /home/dagvadorj/Desktop/untitled /home/dagvadorj/Desktop/u

General purpose linked list, stack and queue for C

Programmers refer to use modern programming languages like Java, Python or Ruby for their uses, because of their powerful built-in functions and flexibility. However, sooner or later, a programmer will have to face their old fella C someday.

For me, I had to use C when I decided to write an interpreter for a programming language I am developing. Of course, C lack of a bunch of stuff, which other modern languages have like hash table, and indexing of a list with a negative index (Python can do list[-2]), etc. But the first things I needed were stack, queue and linked list. We always write these ourselves when programming in C.

Here, I wrote a code for a linked list which can be used as stack and queue and supports negative indexing. Followings are the codes hosted on Google Code:

http://code.google.com/p/litelang/source/browse/trunk/litelang/slist.h (Includes description for methods)

http://code.google.com/p/litelang/source/browse/trunk/litelang/slist.c

Peace!

Image Processing буюу Зураг Боловсруулалт

Номын санд явж байсан манай сургуулийн нэг Камбуж залуу нэг даалгавар хараадхаа гэхээр нь очоод харсан сонирхолтой санагдаад хийж үзлээ.

ppm төрлийн зургийн файл нь ASCII форматаар илэрхийлэгддэг юм байна.

Жишээ нь доорх шиг ppm форматтай зургийг текст эдитор дээр нээвэл хажуудахь шиг харагдана.

Файлыг эндээс татаж авч болно.

ASCII кодыг тайлбарлавал:

P3 # форматын төрөл
150 150 # зургийн өргөн, урт
255 # хэрэглэгдсэн максимум өнгө
176 # эхний цэгийн RGB кодын Red
158 # эхний цэгийн RGB кодын Green
158 # эхний цэгийн RGB кодын Blue
172 # хоёр дахь цэгийн RGB кодын Red
152 # хоёр дахь цэгийн RGB кодын Green
153 # хоёр дахь цэгийн RGB кодын Blue

3 дахь мөрөөс хойш 150x150x3 мөр байна. Учир нь 3 тоо нэг цэгийн өнгийг илэрхийлж байна.

Тэгээд код бичиж үзлээ, энгийн мөртлөө их таалагдлаа. Програмыг ажиллуулахад доорх дөрвөн зураг ppm форматаар үүсэх юм.

Хүний арьсны өнгийг аватарын арьсны өнгөтэй төстэй болгодог болохоор ингэж нэрлэлээ :) Зургийн RGB кодны улаан, цэнхэр хоёр утгыг нь солиход гарна	Зургийн нэгатив	Зургийн хэмжээг 2 дахин багасгасан байдал	Толинд харсан байдал

За ингээд эцэст нь кодоо хавсаргая:

#include 

#include 



int main() {

        FILE * input;
        FILE * avatar;

        FILE * negative;

        FILE * small;
        FILE * mirror;

        int i, m;

        int width, height, max;

        char fname[20];
        

        printf("Enter the name of the file: ");

        scanf("%20s", &fname);
        

        input = fopen(fname, "r");
        avatar = fopen("avatar.ppm", "w");

        negative = fopen("negative.ppm", "w");

        small = fopen("small.ppm", "w");
        mirror = fopen("mirror.ppm", "w");

        
        if (input == NULL) {

           printf("ERROR: The file can not be found!\n");

           return -1;

        }
        

        fscanf(input, "P3\n%d %d\n%d", &width, &height, &max);
        fprintf(avatar, "P3\n%d %d\n%d\n", width, height, max);

        fprintf(negative, "P3\n%d %d\n%d\n", width, height, max);

        fprintf(small, "P3\n%d %d\n%d\n", width/2, height/2, max);
        fprintf(mirror, "P3\n%d %d\n%d\n", width, height, max);

        
        int dim = width*height;

        int temp[dim][3];

        
        for (i=0;i < dim;i++) {

            fscanf(input, "%d %d %d ", &temp[i][0], &temp[i][1], &temp[i][2]);

            fprintf(avatar, "%d %d %d ", 

                temp[i][2], 

                temp[i][1], 

                temp[i][0]);
            fprintf(negative, "%d %d %d ", 

                max-temp[i][0], 

                max-temp[i][1], 

                max-temp[i][2]);

            if ((i/width)%2==0) {

                if (i%2==0)

                   fprintf(small, "%d %d %d ", 

                       temp[i][0], 

                       temp[i][1], 

                       temp[i][2]);

            }

        }
    
        for (i=0;i < dim;i++) {
        m = (i/width)*width+width-i%width-1;
        fprintf(mirror, "%d %d %d ", temp[m][0], temp[m][1], temp[m][2]);
        }
        

        fclose(input);
        fclose(avatar);

        fclose(negative);

        fclose(small);
        fclose(mirror);

        return 0;

}

Дажгүй цэгцтэй код боллоо. Зураг том бол RAM-д их зай эзлэх нь дээ. :(

Counting sort буюу Тоолж жагсаах алгоритм

Энэ адилтгах програмыг харж байгаад Тоолж жагсаах алгоритмыг бичлээ.

#include 

using namespace std;

void countingsort(int *from, int *to, int size) {

    int bound;

    //calculate the bound
    bound = from[0];
    for(int i=1; i < size; i++) {
        if(bound < from[i]) bound = from[i];
    }
    bound = bound+1;

    // counting elements to temporary array
    // of bound length
    int *tmp = new int[bound];
    for (int i=0; i < bound; i++) {
        tmp[i] = 0;
    }
    for (int i=0; i < size; i++) {
        tmp[from[i]]++;
    }

    // processing temporary array
    for (int i=1; i < bound; i++) {
        tmp[i] += tmp[i-1];
    }

    // moving elements to final array
    for (int i=0; i < size; i++) {
        tmp[from[i]]--;
        to[tmp[from[i]]] = from[i];
    }

    delete tmp;
}

int main() {
    int from[8] = {0,4,5,0,3,4,9,4};
    int to[8] = {0};

    cout << "The initial array is: " << endl;
    for(int i=0; i < 8; i++) {
        cout << from[i] << " ";
    }
    cout << endl;

    countingsort(from, to, 8);

    cout << "The final array is: " << endl;
    for(int i=0; i < 8; i++) {
        cout << to[i] << " ";
    }
    cout << endl;

    system("PAUSE");
    return 0;
}

Обьект хандлагат програмчлал

#include 
#include 

using namespace std;

class Fraction {
 unsigned int num;
 unsigned int denom;
 public:
  Fraction() { }
  Fraction(unsigned int , unsigned int );
  Fraction(const Fraction & );
  bool operator==(const Fraction & z) {
   return (z.num == num && z.denom == denom);
  }
  bool operator<(const Fraction & z) const {
   if ((float)num/denom < (float)z.num/z.denom)
    return true;
   else
    return false;
  }
  void setDenom(int new_denom) {
   denom = new_denom;
  }
  unsigned int getNum() const {
   return num;
  }
  unsigned int getDenom() const {
   return denom;
  }
};

Fraction::Fraction(unsigned int new_num, unsigned int new_denom) {
 num = new_num;
 denom = new_denom;
}

Fraction::Fraction(const Fraction & z) {
 num = z.num;
 denom = z.denom;
}

template
class MyArray {
 int mysize;
    Type * content;
    public:
        MyArray(int);
  MyArray(const MyArray & z) {
   mysize = z.mysize;
   content = z.content;
  }
  Type & operator[](int i)  {
   if (i < 0) throw string("index out of bounds");
   else if (i > mysize) throw string("index out of bounds");
   return content[i];
  }
  const Type & operator[](int i) const {
   if (i < 0) throw string("index out of bounds");
   else if (i > mysize) throw string("index out of bounds");
   return content[i];
  }
  bool contains(Type elem) const {
   int i;
   for (i=0; i < mysize; i++) {
    if(content[i] == elem) return true;
   }
   return false;
  }
  const Type & operator!() const {
   int i=0;
   for (int j=1 ; j <= mysize; j++)
    if (content[i] < content[j]) i=j;
   return content[i];
  }
};

template
MyArray::MyArray(int size) {
 mysize = size;
    content = new Type[size];
}

ostream& operator <<(ostream& out, const Fraction& z)  // Overloading <<
{
 out << "( " << z.getNum() << "/" << z.getDenom() << " )";
 return out;
};

int main(int argc, int ** argv) {
    int i;
 MyArray m1(5); // creates an empty 5-element-integer array inside the object m1;
 MyArray m2(3); // creates an empty 3-element-integer array inside the object m2;
 for (int i = 0; i <= 5; i++ ){
  try{
   m1[i] = i;
  }
  catch(const string & err_msg){ // exception handler
   cout << err_msg << endl; //writes "index out of bounds"
  }
 }

 MyArray m3 = m2 = m1;

 for (i = 0; i <= 5; i++ ){
  try{
   cout << m3[i] << " ";
  }
  catch(const string & err_msg){ // exception handler
   cout << err_msg << endl; //writes "index out of bounds"
  }
 }

 if (m1.contains(3))
  cout << "Element 3 is contained in the array" << endl;
 else
  cout << "Element 3 is not contained in the array" << endl;

 cout << "The largest element in the array: " << !m1 << endl ;

 MyArray m4(3); // An array with two empty spaces

 Fraction cObj1(3, 5); // A Fraction object with an unsigned numerator and unsigned denominator
 Fraction cObj2 = cObj1;
 Fraction cObj3 (3,4);
 cObj2.setDenom(7); // sets the denomenator of the Fraction object as 7

 try {
  m4[0] = cObj1;
  m4[1] = cObj2;
  m4[2] = cObj3;
 }
 catch(const string & err_msg){ // exception handler
  cout << err_msg << endl; //writes "index out of bounds"
 }

 for (i = 0; i < 3; i++ ){ // NOTE: burada yanlislikla i<=3 yazildigini sanip degistirdim
  try{
   cout << m4[i] << " ";
  }
  catch(const string & err_msg){ // exception handler
   cout << err_msg << endl; //writes "index out of bounds"
  }
 }
 if (m4.contains(Fraction(3,7)))
  cout << "The element is contained in the array" << endl;
 else
  cout << "The element is not contained in the array" << endl;

 cout << "The largest element in the array: " << !m4 << endl ;

    return 0;
}

Процесс хоорондын харилцаа буюу IPC

#include < stdio.h >
#include < stdlib.h >
#include < string.h >
#include < sys/sem.h >
#include < sys/shm.h >
#include < sys/types.h >
#include < sys/ipc.h >
#include < time.h >

#define SEMKEY (1492)
#define SHMKEY (1493)
#define SHMKEY2 (1494)

int obid() {
 int shmid2;
 int * bestbid;
 if ((shmid2 = shmget(SHMKEY2, sizeof(int), 0666)) < 0) {
  exit(-1);
 }
 if ((bestbid = shmat(shmid2, NULL, 0)) == (int *) -1) {
  exit(-1);
 }
 if (*bestbid == -1)
                printf("Үнэ хаялтын шийдвэр хүлээгдэж байна.n");
 while (*bestbid == -1)
                sleep(1);
 return 0;
}

int main(int argc, char **argv){
 int n;
 int semid;
 int shmid, shmid2;
 pid_t pid;
 int retval;
 int i; // for iteration i.e., C99 standard
 struct sembuf operations[1];
 int * bids, * bestbid;
 int semval;
 int rndnum;
 int min;
 int processid;

 if (argc < 2) {
  printf("Алдаа: Ажиллуулмаар байгаа процессийн тоо хэмжээг оруулаагүй байна.n");
  exit(-1);
 }
 n = atoi(argv[1]);

 /* Semaphore */

 semid = semget(SEMKEY, 1, 0666 | IPC_CREAT);
 if(semid < 0)
 {
  exit(-1);
 }

 union semun {
  int val;
  struct semid_ds *buf;
  ushort * array;
 } argument;
 argument.val = n;

 if( semctl(semid, 0, SETVAL, argument) < 0) {
                printf("Алдаа: Сэмафорын утгыг өгч чадсангүй.\n");
                exit(-1);
        }

 /* Shared memory for bids */

 if ((shmid = shmget(SHMKEY, n*sizeof(int), IPC_CREAT | 0666)) < 0) {
  exit(-1);
 }

 if ((bids = shmat(shmid, NULL, 0)) == (int *) -1) {
  exit(-1);
 }

 /* Shared memory for the minimum bid */

 if ((shmid2 = shmget(SHMKEY2, sizeof(int), IPC_CREAT | 0666)) < 0) {
  exit(-1);
 }

 if ((bestbid = shmat(shmid2, NULL, 0)) == (int *) -1) {
  exit(-1);
 }

 *bestbid = -1;

 for (i=0; i < n; i++) {
  pid = fork();
  if (pid < 0) {
   printf("Алдаа: Хүүхэд процесс үүсгэхэд алдаа гарлаа.\n");
  } else if (pid == 0) { //child process
   processid = i;
   semval = semctl(semid, 0, GETVAL, argument);

   rndnum = (abs((getpid() * rand())) % 1000) + 10;

   *(bids+semval) = rndnum;

   printf("Процесс #%d: %d MNT Үнэ санал болголоо. ", i, rndnum);

   operations[0].sem_num = 0;
   operations[0].sem_op = -1;
   operations[0].sem_flg = 0;

   if (semval == 1) {
    printf("Шийдвэр хүлээгдэж байна.\n");
                min = *(bids+i);
    for(i=1; i <= n; i++) {
     if (min > *(bids+i+1) & i+1 <= n) {
      min = *(bids+i+1);
     }
    }
    *bestbid= min;
    printf("Хамгийн бага үнийн санал: %d MNT. obid функцд хүлээгдэж байсан процессууд ажилна.\n", *bestbid);
   }

   retval = semop(semid, operations, 1);

   if(retval == 0)
   {
    if (obid() == 0) {
                    printf("Процесс #%d: obid функцээс буцлаа. \n", processid);
                }
    exit(0);
   }

  } else { //parent process
   if (semctl(semid, 0, GETVAL, argument) == 0) {
    semctl(semid,0,IPC_RMID,0);
                shmctl(shmid,IPC_RMID,0);
                shmctl(shmid2,IPC_RMID,0);
                exit(0);
   }
  }
 }

 printf("n");
 return 0;
}

Insertion Sort Algorithm буюу Нэмж Жагсаах Алгоритм

void insertionsort(int * input, int n) {
     int j;
     int i;
     int key;
     for(j=1; j < n; j++) {
        key = input[j];
        i = j-1;
        while(i >= 0 && input[i] > key) {
            input[i+1] = input[i];
            i--;
        }
        input[i+1] = key;
     }
}

int main() {
    int i;
    int array[] = {9,8,7,6,4,2};

    insertionsort(&array, 6);
    for (i=0; i<6; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    system("PAUSE");
    return 0;
}

Дээрх алгоритм нь массивт байгаа тоонуудыг хоёр дахиас нь эхлэн тоо тус бүрийг өмнөх тоонуудтай нь харицуулан өмнөх тооноосоо бага бол байрыг нь сольж үргэлжлүүлэн итерацаар ажилна.

Хамгийн муугаар бодож байж алгоритмын үнэ цэнийг олж авна. Жишээ нь дээрх “нэмж жагсаах” алгоритмийн хувьд массив дахь тоонууд эсрэгээрээ (ихээсээ багаруу) жагсаагдсан байрлалтай бол n2 үйлдлийн дараа алгоритм ажилаа хийж дуусан байна. Өөрөө хэлбэл O(n2).

Шугаман хайлт буюу lsearch

C хэлний санамжийг яаж ашигладагийг анзаарахын тулд шугаман хайлт буюу lsearch алгоритмыг авч үзье! Энэ алгоритм нь “генерик” буюу буюу бүхий л өгөгдлийн төрөл дээр ажиллана. (Жишээ нь: int, char, short гэх мэт)

void * lsearch(void * key, void * base, int n, int elemSize,
                int (* cmpfn)(void *, void *))
{
    int i;
    for(i=0; i < n; i++) {
        void * elemAddr = (char *)base + i*elemSize;
        if(cmpfn(key, elemAddr) == 0)
            return elemAddr;
    }
    return NULL;
}

Дээрх функц нь доорх 5 параметрийг авч байна:

• key – хайх түлхүүр
• base – санамжинд хайж эхлэх хаяг
• n – санамжин дахь хайх урт
• elemSize – элементийн хэмжээ
• cmpfn – тэнцүү эсэхийг шалгах функцийн прототип

Зарчмын хувьд энэхүү алгоритм нь компьютерийн санамж буюу RAM дээрх нэгэн байршилаас (void * base) эхлэн тус бүр өгөгдсөн ижил урттай (int elemSize) тодорхой тооны (int n) элемент дунд нэг обьект (void * key) байгаа эсэхийг шалгана. 6-р мөрөнд void * elemAddr=(char *)base + i*elemSize; гэж зааснаар base-ийн зааж буй нэг byte мэдээллээс хойш i*elemSize алхам хойно гэсэн утга заажээ.

Харин өгөгдсөн элементүүдийн төрөлөөс шалтгаалан тэнцүү эсэхийг шалгах функц нь өөр өөр байж болох учир функцийн прототипийг зааж өгсөн (int (* cmpfn)(void *, void *)) байгаа ба алгоритмийг хэрэглэгч өөрөө тэр функцыг тодорхойлох хэрэгтэй. Жишээ нь өгөгдсөн массив дотор тодорхой нэгэн тоо байгаа эсэхийг шалгах програм бичье.

int IntCmp(void * elem1, void * elem2) { 
    int *ip1 = elem1; 
    int *ip2 = elem2; 
    return *ip1-*ip2; 
} 

int main(int argc, char * argv[]) { 
    int array[] = {4,2,3,7,11,6}; 
    int size = 6; 
    int number = 7; 

    void * found = lsearch(&number, array, size, sizeof(int), IntCmp); 

    if (found == NULL) 
        printf("Not found!\n"); 
    else
        printf("Found.\n"); 

    system("PAUSE"); 
    return 0; 
}