Самые популярные сериалы Swatcher_Bot на конец 2018 года

Собрал подборку самых отслеживаемых сериалов в 2016 году, по результатам работы Swatcher_bot.

Игра престолов2554
Ходячие мертвецы1218
Теория большого взрыва1155
Сверхъестественное904
Викинги784
Люцифер736
Мир Дикого Запада665
Бесстыдники (USA)643
Мистер Робот628
Рик и Морти597

Обход блокировок используя VPN и роутер Mikrotik

 

Недавно я приобрел новый роутер Mikrotik hAP ac lite и услышал что можно настроить бесшовный обход блокировок с автоматической загрузкой заблокированных IP адресов. Т.е. обычный трафик идет как всегда, а вот в случае если мы обращаемся к заблокированному ресурсу, роутер это понимает и направляет трафик через VPN.

 

VPN

Я решил настроить pptp или openvpn на своем сервере, но не вышло, там у меня отключен tun/tap и nat. Потому пришлось обратиться к платным VPN-провайдерам. Первым делом я пошел к TunnelBear которым уже пользовался, но из-за настроек их VPN-сервером, мне не удалось к ним подключиться. К сожалению роутер не поддерживате lzo и SHA256. Пришлось искать другой и я нашел StrongVPN, у них даже есть инструкция как настроить VPN на роутерах Mikrotik. Здесь важно снять или не ставить галочку напротив default route потому что мы будем использовать VPN как запасной канал.

После настройки необходимо добавить правила для роутера, идем IP — Firewall — Mangle — Add

  • General: Src. Address меняем на свой, у меня он был такой 192.168.88.10-192.168.88.254
  • Advanced: Dst. Address List на rkn
  • Action: Action — mark routing, New Routing Mark — rkn_mark, и ставим галочку Passthrough

Теперь когда мы пометили пакеты, нужно создать для них правило, идем IP — Routes — ADD и на вкладке General настраиваем:

  • Dst.Address — 0.0.0.0/0
  • Gateway — <Ваш VPN>
  • Type — unicast
  • Routing Mark — rkn_mark <— та метка что мы раньше создали

И теперь добавляем маскарадинг IP — Firewall — NAT — Add :

  • General: Out. Interface <Ваш VPN>
  • Action: Action — masquerade

Теперь единственное что осталось сделать это импортировать Address List.

 

Импорт Address List

Тут для простоты я опишу как скачивать уже готовый список с моего github, для тех кто не доверяет мне или же по другим причинам хочет сам его генерировать я сделаю отдельный пост.

Итак, я создал репозиторий в который автоматически выгружается самый свежий список заблокированных ресурсов в виде скрипта для импортирования, с ним мы и будем работать. Идем в System — Scripts — Add

{
/tool fetch url="https://raw.githubusercontent.com/Driim/mikrotik_rkn/master/subnets.rsc" mode=https
}

Обзываем этот скрипт DownloadSubnets и сохраняем, этот скрипт просто скачивает subnets.rsc, следующий скрипт немного сложней, создаем новый скрипт:

:if ([:len [/file find name=subnets.rsc]] > 0) do={
/ip firewall address-list remove [/ip firewall address-list find list="rkn"]
import file=subnets.rsc
/file remove subnets.rsc
}

Этот скрипт, проверяет наличие файла subnets.rsc, если файл есть, то он удаляет все старые записи списка rkn и импортирует новые, после чего удаляет файл. Обзываем скрипт SetSubnets и сохраняем.

Остался последний шаг, нам нужно что бы эти скрипты раз в день вызывались. Идем в System — Scheduler и создаем два правила.

 

Теперь каждую ночь будет автоматически подгружаться список заблокированных IP-адресов, трафик к которым роутер будет направлять через VPN и необходимые вам ресурсы снова станут доступны.

Многопоточное архивирование в Linux при помощи tar

Обратил я тут внимание на то что архивирование в Linux через tar занимает только одно ядро и решил поискать как это можно исправить и утилизировать все 4 ядра своего процессора.

В мануале по tar я нашел такую опцию:

-I, –use-compress-program PROG
filter through PROG (must accept -d)

А поиск по интернету выдал мне многопоточные архиваторы:

  • gz:   pigz
  • bz2: pbzip2
  • xz:   pxz

Установить все три можно в Ubuntu командой:

sudo apt-get install pxz pigz pbzip2

Команды для архивации:

  • gz:   tar -czf tarball.tar.gz files
  • bz2: tar -cjf tarball.tar.bz2 files
  • xz:   tar -cJf tarball.tar.xz files

Команды для разархивации:

  • gz: tar -xzf tarball.tar.gz
  • bz2: tar -xjf tarball.tar.bz2
  • xz: tar -xJf tarball.tar.xz

А теперь параллельная версия архивации:

  • gz:   tar -I pigz -cf tarball.tar.gz files
  • bz2: tar -I pbzip2 -cf tarball.tar.bz2 files
  • xz:   tar -I pxz -cf tarball.tar.xz files

И разархивации:

  • gz:   tar -I pigz -xf tarball.tar.gz
  • bz2: tar -I pbzip2 -xf tarball.tar.bz2
  • xz:   tar -I pxz -xf tarball.tar.xz

Воспользуюсь исходниками ядра Linux версии 4.15 буду архивировать и разархивировать на M.2 SSD диске используя CPU Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz 4 cores, 4 threads, 8Gb RAM

Время архивации(больше проверять не вижу смысла):

.                                    gzip           bzip2                 xz
Однопоточное          26.409s    1m23.939s    6m43.628s
Многопоточное        10.048s      34.784s       2m45.230s

How to build Sailfish OS for Samsung Galaxy S7

 

This manual based on HADK 2.0.1.

4.1 Setting up required environment variables

cat <<'EOF' > $HOME/.hadk.env
export PLATFORM_SDK_ROOT="/srv/mer"
export ANDROID_ROOT="$HOME/hadk"
export VENDOR="samsung"
export DEVICE="herolte"
# ARCH conflicts with kernel build?
export PORT_ARCH="armv7hl"
EOF
cat <<'EOF' >> $HOME/.mersdkubu.profile
function hadk() { source $HOME/.hadk.env; echo "Env setup for $DEVICE"; }
export PS1="HABUILD_SDK [\${DEVICE}] $PS1"
hadk
EOF
cat <<'EOF' >> $HOME/.mersdk.profile
function hadk() { source $HOME/.hadk.env; echo "Env setup for $DEVICE"; }
export PS1="PlatformSDK [\${DEVICE}] $PS1"
[ -d /etc/bash_completion.d ] && for i in /etc/bash_completion.d/*;do . $i;done
hadk

4.2 Setup the Platform SDK

export PLATFORM_SDK_ROOT="/srv/mer"
curl -k -O http://releases.sailfishos.org/sdk/installers/latest/Jolla-latest-SailfishOS_Platform_SDK_Chroot-i486.tar.bz2 ;
sudo mkdir -p $PLATFORM_SDK_ROOT/sdks/sfossdk ;
sudo tar --numeric-owner -p -xjf Jolla-latest-SailfishOS_Platform_SDK_Chroot-i486.tar.bz2 -C $PLATFORM_SDK_ROOT/sdks/sfossdk ;
echo "export PLATFORM_SDK_ROOT=$PLATFORM_SDK_ROOT" >> ~/.bashrc
echo 'alias sfossdk=$PLATFORM_SDK_ROOT/sdks/sfossdk/mer-sdk-chroot' >> ~/.bashrc ; exec bash ;
sfossdk

4.3 Preparing the Platform SDK

PLATFORM_SDK $
sudo zypper in android-tools createrepo zip

4.4 Setting up an Android Build Environment

4.4.1 Downloading and Unpacking Ubuntu Chroot

PLATFORM_SDK $
TARBALL=ubuntu-trusty-android-rootfs.tar.bz2
curl -O http://img.merproject.org/images/mer-hybris/ubu/$TARBALL
UBUNTU_CHROOT=$PLATFORM_SDK_ROOT/sdks/ubuntu
sudo mkdir -p $UBUNTU_CHROOT
sudo tar --numeric-owner -xjf $TARBALL -C $UBUNTU_CHROOT

4.4.2 Entering Ubuntu Chroot

PLATFORM_SDK $

ubu-chroot -r $PLATFORM_SDK_ROOT/sdks/ubuntu
# FIXME: Hostname resolution might fail. This error can be ignored.

# Can be fixed manually by adding the hostname to /etc/hosts
sudo apt-get update
sudo apt-get install bsdmainutils rsync vim unzip imagemagick software-properties-common python-software-properties
sudo add-apt-repository ppa:openjdk-r/ppa
sudo apt-get update
sudo apt-get install openjdk-8-jdk
sudo update-alternatives --config java
sudo update-java-alternatives -s java-1.8.0-openjdk-amd64
# choose openjdk-8-jdk

5.1 Checking out CyanogenMod Source

Configure git:

git config --global user.name "Your Name"

git config --global user.email "you@example.com"
HABUILD_SDK $
sudo mkdir -p $ANDROID_ROOT
sudo chown -R $USER $ANDROID_ROOT
cd $ANDROID_ROOT
repo init -u git://github.com/mer-hybris/android.git -b hybris-14.1

5.2 Device repos

HABUILD_SDK $
cd $ANDROID_ROOT/.repo
git clone https://github.com/Driim/local_manifests
cd ../

repo sync --fetch-submodules

5.3 Configure Mountpoint Information

Nothing to do here

5.4 Building Relevant Bits of CyanogenMod

HABUILD_SDK $
source build/envsetup.sh
export USE_CCACHE=1
breakfast $DEVICE
make -j<XX> hybris-hal libcameraservice_32 libdroidmedia_32 minimediaservice minisfservice libaudioflingerglue_32 miniafservice

<XX> - number of cores

Next we are going to build droid-hal-device

7.2.1 Building the droid-hal-device packages
 

PLATFORM_SDK $

cd $ANDROID_ROOT

sdk-assistant create SailfishOS-latest http://releases.sailfishos.org/sdk/latest/Jolla-latest-Sailfish_SDK_Tooling-i486.tar.bz2
sdk-assistant create $VENDOR-$DEVICE-$PORT_ARCH http://releases.sailfishos.org/sdk/latest/Jolla-latest-Sailfish_SDK_Target-armv7hl.tar.bz2
sdk-assistant create SailfishOS-latest-i486 http://releases.sailfishos.org/sdk/latest/Jolla-latest-Sailfish_SDK_Target-i486.tar.bz2

sb2 -t $VENDOR-$DEVICE-$PORT_ARCH -m sdk-install -R zypper rm ngfd-plugin-native-vibrator
rpm/dhd/helpers/build_packages.sh --mw=ngfd-plugin-droid-vibrator --spec=rpm/ngfd-plugin-droid-vibrator.spec

sb2 -t $VENDOR-$DEVICE-$PORT_ARCH -m sdk-install -R zypper rm qt5-feedback-haptics-native-vibrator
rpm/dhd/helpers/build_packages.sh --mw=qt5-feedback-haptics-droid-vibrator --spec=rpm/qt5-feedback-haptics-droid-vibrator.spec

# build droidmedia
DROIDMEDIA_VERSION=$(git --git-dir external/droidmedia/.git describe --tags | sed \
-r "s/\-/\+/g")
rpm/dhd/helpers/pack_source_droidmedia-localbuild.sh $DROIDMEDIA_VERSION
mkdir -p hybris/mw/droidmedia-localbuild/rpm
cp rpm/dhd/helpers/droidmedia-localbuild.spec \
hybris/mw/droidmedia-localbuild/rpm/droidmedia.spec
sed -ie "s/0.0.0/$DROIDMEDIA_VERSION/" \
hybris/mw/droidmedia-localbuild/rpm/droidmedia.spec
mv hybris/mw/droidmedia-$DROIDMEDIA_VERSION.tgz hybris/mw/droidmedia-localbuild
rpm/dhd/helpers/build_packages.sh --build=hybris/mw/droidmedia-localbuild
rpm/dhd/helpers/build_packages.sh --droid-hal --mw=https://github.com/sailfishos/gst-droid.git

# build audioflingerglue
rpm/dhd/helpers/pack_source_audioflingerglue-localbuild.sh
mkdir -p hybris/mw/audioflingerglue-localbuild/rpm
cp rpm/dhd/helpers/audioflingerglue-localbuild.spec \
hybris/mw/audioflingerglue-localbuild/rpm/audioflingerglue.spec
mv hybris/mw/audioflingerglue-0.0.1.tgz hybris/mw/audioflingerglue-localbuild
rpm/dhd/helpers/build_packages.sh --build=hybris/mw/audioflingerglue-localbuild
rpm/dhd/helpers/build_packages.sh --droid-hal \
--mw=https://github.com/mer-hybris/pulseaudio-modules-droid-glue.git

# build libgrillio
rpm/dhd/helpers/build_packages.sh --mw=https://git.merproject.org/mer-core/libgrilio.git

# build ofono
rpm/dhd/helpers/build_packages.sh --mw=https://git.merproject.org/mer-core/ofono.git

I had problems with ngfd-plugin-droid-vibrator and qt5-feedback-haptics-droid-vibrator packages, os we build then before everything else. Also audio package builded from different source. So When we start build another packages we need to choose Y for every packet(not all) and wait then builded, but for the ngfd-plugin-droid-vibrator, qt5-feedback-haptics-droid-vibrator, pulseaudio-modules-droid choose n.

rpm/dhd/helpers/build_packages.sh

8.3 Creating and Configuring the Kickstart File

PLATFORM_SDK $

HA_REPO="repo --name=adaptation-community-common-$DEVICE-@RELEASE@"
HA_DEV="repo --name=adaptation-community-$DEVICE-@RELEASE@"
KS="Jolla-@RELEASE@-$DEVICE-@ARCH@.ks"
sed "/$HA_REPO/i$HA_DEV --baseurl=file:\/\/$ANDROID_ROOT\/droid-local-repo\/$DEVICE" $ANDROID_ROOT/hybris/droid-configs/installroot/usr/share/kickstarts/$KS > $KS

8.5 Building the Image with MIC

PLATFORM_SDK $

RELEASE=2.1.3.7
EXTRA_NAME=-s7

hybris/droid-configs/droid-configs-device/helpers/process_patterns.sh
#Command fail, but that's ok
sudo mic create fs --arch=$PORT_ARCH --tokenmap=ARCH:$PORT_ARCH,RELEASE:$RELEASE,EXTRA_NAME:$EXTRA_NAME --record-pkgs=name,url --outdir=sfe-$DEVICE-$RELEASE$EXTRA_NAME --pack-to=sfe-$DEVICE-$RELEASE$EXTRA_NAME.tar.bz2 $ANDROID_ROOT/Jolla-@RELEASE@-$DEVICE-@ARCH@.ks

Folder sfe-herolte-2.1.3.7-s7 has zip-file ready to install from TWRP

Audio begin to work if comment tms and playback_record in /system/etc/audio_policy.conf but it sound terribly.

Как получить доступ к UART телефонов Galaxy S7

Так уж вышло, что мне потребовалось получить доступ к UART на Galaxy S7. И, естественно, я обратился к гуглу с  этим вопросом. На XDA было несколько топиков, посвященных этому вопросу, но все они были старыми (2012-2013 год), с информацией о старом загрузчике. Кроме того, информацией о использовании UART с загрузчиком все и ограничивалось. А мне же нужно было получить доступ к Android. Здесь я постараюсь структурировать всю полученную мной информацию.

Начать стоит с того, что между USB-коннектором и USB-контроллером стоит мультиплексор (MUIC), который определяем сопротивление между ножкой ID и землей (GND), и в зависимости от этого сопротивления выставляет режим работы USB-контроллера. Это не новость: так, например, работает USB OTG. Но есть и другие режимы работы, которые являются скрытыми. Этими режимами работы пользуется специальное устройство, используемое инженерами Samsung. Такое устройство можно заказать на eBay, но я не вижу смысла. Исходные коды ядра, используемого в телефоне, доступны для скачивания, и там есть драйвер этого мультиплексора.

Этот MUIC на S7 оказался MAX77854, документацию на который найти не удалось, но у нас есть драйвер. Драйвер этого MUIC-устройства можно посмотреть здесь: drivers/muic/max77854-muic.c Полазив по исходникам, я нашел актуальную таблицу сопротивлений и режимов работы для этого устройства:

  • OTG = GND
  • MHL = 1K
  • VZW_ACC = 28.7K
  • VZW_INCOMPATIBLE = 34K
  • RDU_TA = 40.2K
  • HMT = 49.9K
  • AUDIODOCK = 64.9K
  • USB_LANHUB = 80.07K
  • CHARGING_CABLE = 102K
  • GAMEPAD = 121K
  • TYPE1_CHG = 200K
  • JIG_USB_OFF = 255K
  • JIG_USB_ON = 301K
  • DESKDOCK = 365K
  • TYPE2_CHG = 442K
  • JIG_UART_OFF = 523K
  • JIG_UART_ON = 619K
  • TA = OPEN
  • USB = OPEN
  • CDP = OPEN
  • UNDEFINED_CHARGING = UNDEFINED
  • ATTACHED_DEV_NUM = NUM

Я понятия не имею, что значит большинство этих режимов, но есть очень интересный режим JIG_UART_ON, который был уже немного изучен и который позволял через переходник USB-UART подключиться к устройству и видеть лог загрузки SBOOT. Мне очень помогла вот эта статья про SBOOT, в которой человек изучал возможность взлома загрузчика и сумел понять, как получить возможность менять параметры загрузчика, в том числе и параметры загрузки ядра.

В первую очередь необходимо собрать переходник JIG(UART)-переходник. Для этого нам потребуется любой USB-UART переходник (я использовал вот такой на FT232)  и резистор на 619КОм (в близжайшек к моему дому магазине я купил на 620K) и собрать это все в вот такую схемку:

Собранный переходник подключаем к компьютеру, в моей системе он появился как /dev/ttyUSB0, подключаемся к нему терминалом (я использовал minicom):

sudo minicom -D /dev/ttyUSB0

Я не знаю, какие будут у вас настройки по умолчанию для вашей программы, потому настоятельно рекомендую зайти в настройки порта и выключить аппаратное управление потоком. Дальше необходимо подключить к этому переходнику сам телефон и включить его комбинацией клавиш: Vol-(Volume Down) + Power

Как только на экран начнут появляться символы, нужно начать спамить клавишу Enter (если кого интересует более точное значение, то нужно нажать минимум 3 раза) до момента появления приглашения к вводу. Мы оказались в консоли SBOOT. В консоли выполняем команду:

setenv CMDLINE console=ttySAC4,115200 loglevel=4
saveenv

После этого зажимаем Vol-(Volume Down) (если эта клавиша не нажата, то SBOOT не будет ничего печатать в консоль) и вводим в консоль SBOOT команду:

reset

Устройство перезагрузится, и мы увидим лог загрузки SBOOT и часть лога загрузки ядра. Почему только часть? Потому что в исходниках ядра я нашел одну маленькую нелогичность, патч исправляющий эту нелогичность ниже:

 

diff --git a/drivers/muic/universal/muic_apis.c b/drivers/muic/universal/muic_apis.c
index 342bc51..5af193c 100755
--- a/drivers/muic/universal/muic_apis.c
+++ b/drivers/muic/universal/muic_apis.c
@@ -796,7 +796,7 @@ int detach_jig_uart_boot_off(muic_data_t *pmuic)
*/
int attach_jig_uart_boot_on(muic_data_t *pmuic, muic_attached_dev_t new_dev)
{
- int com_index = COM_OPEN;
+ int com_index = COM_UART_AP;
int ret = 0;

pr_info("%s:%s JIG UART BOOT-ON(0x%x)\n",

 

После его применения можно будет увидеть весь лог загрузки ядра, правда мы сломаем GSM-часть телефона. Этот UART-порт используется системой для общения с GSM-модемом (получается, что нелогичность все таки имела логику). В принципе на данном этапе уже можно использовать все это для отладки ядра, но мы  добивались не этого, попробуем получить консоль системы, не через adb, а через UART, используя полученные ранее данные.

Для этого потребуется установить на свой телефон TWRP, и, используя его, рутануть телефон. Потом поставить вот этот пакет с busybox, который отличается от стандартного тем, что там есть getty. Теперь загружаемся, устанавливаем эмулятор терминала и переводим телефон в авиарежим. Открываем эмулятор и вводим следующие команды:

su
echo 1 > /sys/devices/virtual/sec/switch/uart_en
echo AP > /sys/devices/virtual/sec/switch/uart_sel #на этом этапе должен появиться лог ядра 
su root -c "getty -n -L -l /system/bin/sh 115200 ttySAC4 vt102"

Полезные материалы:

Поиск и замена используя регулярные выражения в Sublime Text 3

Я продолжаю изучать Javascript и Node JS, а так как теорию я люблю закреплять практикой, то практикую все новое в 3 версии своего Swatcher_Bot. Я решил все переписать практически с нуля и одним из главных требований к 3 версии было покрытие кода юнит-тестами. Я учусь и развиваюсь, и первоначально я тестировал код используя банальные assets. Но когда я дошел до этапа более сложных проверок, меня перестал устраивать assets и я решил переехать на Chai. Для этого большое количество тестов вида:

assert.equal(serial_info.season[0].starts, 2017);

нужно было переделать в тесты вида:

expect(serial_info.season[0].starts).to.equal(2017);

Можно было бы сделать это вручную и потерять кучу времени и я задумался о том что можно легко трансформировать этот код использую регулярные выражения. И мне не хотелось использовать для этого сторонние утилиты, потому я пошел изучать возможности Sublime Text. И оказалось что «Replace» из текстового редактора поддерживает такую возможность.

 

Для этого необходимо вызвать меню замены(Ctrl+H) и включить регулярные выражения(Alt+R) после чего в поле поиска вставить такое выражение:

assert.equal\((.+), (\d+)\)

а в поле замены вставить это:

expect($1).to.equal($2)

В регулярном выражение извлекаются первый и второй аргумент функции, а в поле замены они($1 и $2) используются в подставляемом выражении.

Реализация «легкого» spinlock на атомарных операциях

Решил я тут разобраться с атомарными командами, что это такое, какими они бывают и что делают. В целом если объяснять на пальцах, то атомарные или неделимые операции, как следуют из названия, неделимые. Т.е. команда либо еще не выполнена, либо уже выполнена, мы не сможем застать эту операцию в середине процесса. Естественно это реализуется за счет аппаратной поддержке. И у разных архитектур эти команды могут и отличаются, но что бы с вами не зарывались в спецификациях разработчики компиляторов унифицировали работу с этими операциями, описание всех команд можно найти в документации к компилятору(например gcc).

Читая эту документацию и разбираясь с тем как все это работает, мне пришла в голову идея легкого spinlock’a на атомарных функциях. В чем же легкость этого spinlock’a относительного того же mutex’a?! Легкость заключается в том что эта блокировка не приводит к системному вызову, как например блокировка mutex’a.

Итак для создание легкого spinlock’a в userspace нам потребуются 2 функции:

  • bool __atomic_test_and_set (void *ptr, int memorder)
  • void __atomic_clear (bool *ptr, int memorder)

__atomic_test_and_set — устанавливает байт *ptr в некое предопределенное значение ‘set’. Функция вернет true только в том случае если байт *ptr до этого уже находился в состояние ‘set’, иначе функция вернет false. Функцию стоит использовать только с типами char и bool, иначе *ptr будем модифицировано только частично.

__atomic_clear — функция сбрасывает байт *ptr в 0.

int memorder переменная обозначающая используемый способ упорядочения памяти. Это отдельная, довольно обширная тема барьеров памяти разбирать которую в рамках этой статьи я не буду, нам вполне значение по умолчанию __ATOMIC_SEQ_CST, самый строгий ordering. Хотя, если я правильно понял принципы memory ordering’a, то можно использовать более оптимальный Acquire/Release memory ordering.

Теперь сами функции:

 

void spinlock_lock(bool *lock)
{
    /*
     * Крутимся в цикле(spinlock же) пока функция не вернет false,
     * что будет означать что мы захватили блокировку
     */
    while(__atomic_test_and_set(lock, __ATOMIC_SEQ_CST) != false);
}

void spinlock_unlock(bool * lock)
{
    __atomic_clear(lock, __ATOMIC_SEQ_CST);
}

 

Ничего сложного. Не требует подключения дополнительных заголовочных файлов.

Быстрая сортировка на С

Продолжаю записи про язык программирования С, точней про различные структуры и простейшие алгоритмы. Следующей в очереди идет быстрая сортировка, вот что о ней пишут в википедии:

Быстрая сортировка, сортировка Хоара (англ.quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n\log n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

Как указано в википедии это сортировка входит в стандартную библиотеку языка С и о том как ей пользоваться можно почитать в документации.  Но меня же больше интересует реализация, для понимания и сохранения на случай экзаменов, задач и т.п. где пользоваться стандартной библиотекой нельзя.

 

Вот собственно вся функция сортировки массива целых чисел(int):

void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void quick_sort(int *s_arr, int first, int last)
{
	int i = first, j = last, x = s_arr[(first + last)/2];

	do {
		while(s_arr[i] < x) i++; while(s_arr[j] > x) j--;

		if(i <= j) { if(s_arr[i] > s_arr[j])
				swap(&s_arr[i], &s_arr[j]);
			i++;
			j--;
		}
	} while(i <= j);

	if(i < last)
		quick_sort(s_arr, i, last);
	if(first < j)
		quick_sort(s_arr, first, j);
}

Самые популярные сериалы в 2016 году

Собрал подборку самых отслеживаемых сериалов в 2016 году, по результатам работы Swatcher_bot. Из событий этого года можно ознаменовать только внезапный переезд к другому VPS-провайдеру в связи с кончиной старого. А так же попадание бота в различные подборки ботов(от лайфхакера, например) что крайне положительно повлияло на количество пользователей.

На этот год у меня запланировано несколько нововведений, о которых я буду рассказывать по мере их внедрения.

 

Игра престолов
710
Теория большого взрыва
403
Мистер Робот
333
Ходячие мертвецы
320
Флэш
242
Мир Дикого запада
228
Форс-мажоры
217
Сверхъестественное
181
Шерлок
180
Кремниевая долина
171
Викинги
162
Проповедник
161
Бесстыдники (USA)
147
Люцифер
135
Стрела
123
Готэм
121
Элементарно
120
Черное зеркало
116
Южный Парк
113
Лучше звоните Солу
111
Американская история ужасов
108
Изгоняющий дьявола
102
Карточный домик
96
Сотня
82
Симпсоны
81
Очень странные дела
76
Гримм
75
Дневники вампира
71
Последний человек на Земле
67
Бруклин 9-9
66
Рик и Морти
65
Щ.И.Т.
65
Бойтесь ходячих мертвецов
62
Мажор
61
Гриффины
58
Доктор Кто
56
Области тьмы
55
Однажды ночью
55
Штамм
55
Настоящий детектив
52
Нарки
50

 

Всего в топе 5752 добавления. За год бот обзавелся 3 012 новыми пользователями, что по мне так крайне хороший результат, учитывая что на его рекламу я не тратил ни денег, ни времени.

Поиск в ширину на С

Следующим за поиском в глубину идет поиск в ширину или BFS. Так как и в случае поиска в глубину, реализация будет итеративной, с использованием реализованной ранее очереди.

Немного инфы из вики:

поиск в ширину

Поиск в ширину (англ. breadth-first search, BFS) — метод обхода графа и поиска пути в графе. Поиск в ширину является одним из неинформированных алгоритмов поиска[1].

 

Будем использовать структуру данных из прошлого поста:

typedef struct tree_node {
    /* указатель на левую вершину */
    struct tree_node * left;
    /* указатель на правую вершину */
    struct tree_node * rigth;
    /* указатель на хранимые в вершине данные */
    void *data;
    /* необходимая при обходе пометка */
    int mark;
} tree_node_t;

Так же нужно определить указатель на функцию которая быдет вызывается для обработки данных находящихся в обрабатываемой вершине.

typedef void (*visit_node_f)(tree_node_t *node, void *visit_data);

Т.е. нам нужно определить функцию которая будет проводить некоторые манипуляции с данными хранимыми в вершине tree_node_t *node, а void * data будет расшариваться между всеми вызовами, например в нем можно сохранить счетчик или еще что-нибудь что может пригодиться при обработке данных.

 

А теперь сам алгоритм:

 

void bfs(tree_node_t * root, visit_node_f node_function, void *visit_data)
{
    list_t *st = create_list();

    list_push_back(st, root);

    /* Посещаем корневую вершину */
    (*node_function)(root, visit_data);
    root->mark = 1;

    while(st->size != 0) {
        tree_node_t * node = (tree_node_t *)list_pop(st);

        if(node->left != NULL && !node->left->mark){
            list_push_back(st, node->left);
            /* посещаем левую вершину */
            (*node_function)(node->left, visit_data);
            node->left->mark = 1;

        }

        if(node->rigth != NULL && !node->rigth->mark){
            list_push_back(st, node->rigth);
            /* посещаем правую вершину вершину */
            (*node_function)(node->rigth, visit_data);
            node->rigth->mark = 1;
        }
    }
}

Вот и все.