Backend-Entwicklung
PHP-Tutorial
Nginx-Datenstruktur 2 – Schreiben Sie den rot-schwarzen Baum selbst neu
Nginx-Datenstruktur 2 – Schreiben Sie den rot-schwarzen Baum selbst neu
Lassen Sie uns ohne weitere Umschweife den Code neu schreiben. Dieses Mal werde ich die auf Englisch verfassten Kommentare als Überprüfung des Englischen verwenden.
rbtree.h:
/*
* Copyright (C) Bipedal Bit
* Verson 1.0.0.1
*/
#ifndef _RBTREE_H_INCLUDED_
#define _RBTREE_H_INCLUDED_
/* the node structure of the red-black tree */
typedef struct rbtree_node_s rbtree_node_t;
/* Using type int means its range is -0x7fffffff-1~0x7fffffff. */
typedef int rbtree_key_t;
/* Abstract type is complicated to achieve with C so I use char* instead. */
typedef char* rbtree_data_t;
struct rbtree_node_s
{
/* key of the node */
rbtree_key_t key;
/* pointer of the parent of the node */
rbtree_node_t* parent;
/* pointer of the left kid of the node */
rbtree_node_t* left;
/* pointer of the right kid of the node */
rbtree_node_t* right;
/* color of the node */
unsigned char color;
/* pointer of the value of the node corresponding to the key */
rbtree_data_t value;
};
/* the tree object stucture of the red-black tree */
typedef struct rbtree_s rbtree_t;
/* foundational insert function pointer*/
typedef void (*rbtree_insert_p) (rbtree_t* root, rbtree_node_t* node);
struct rbtree_s
{
/* the pointer of the root node of the tree */
rbtree_node_t* root;
/* black leaf nodes as sentinel */
rbtree_node_t* sentinel;
/* the polymorphic insert function pointer */
rbtree_insert_p insert;
};
/* macros */
#define rbtree_init(tree, s, i) \
rbtree_sentinel_init(s); \
(tree)->root = s; \
(tree)->sentinel = s; \
(tree)->insert = i
#define rbtree_red(node) ((node)->color = 1)
#define rbtree_black(node) ((node)->color = 0)
#define rbtree_is_red(node) ((node)->color)
#define rbtree_is_black(node) (!rbtree_is_red(node))
/* copy n2's color to n1 */
#define rbtree_copy_color(n1, n2) (n1->color = n2->color)
/* sentinel must be black cuz it's leaf node */
#define rbtree_sentinel_init(node) rbtree_black(node)
/* statements of public methods */
void rbtree_insert_value(rbtree_t* tree, rbtree_node_t* node);
void rbtree_insert(rbtree_t* tree, rbtree_node_t* node);
void rbtree_delete(rbtree_t* tree, rbtree_node_t* node);
rbtree_node_t* rbtree_find(rbtree_t* tree, rbtree_key_t key);
#endif /* _RBTREE_H_INCLUDED_ */Wer den Nginx-Quellcode gelesen hat, wird feststellen, dass sich meine Header-Datei im Vergleich zu ngx_rbree.h nicht wesentlich geändert hat, sie ist sehr ähnlich .
Der Schlüssel rbtree.c:
/*
* Copyright (C) Bipedal Bit
* Verson 1.0.0.1
*/
#include <stddef.h>
#include "rbtree.h"
/* inline methods */
/* get the node with the minimum key in a subtree of the red-black tree */
static inline rbtree_node_t*
rbtree_subtree_min(rbtree_node_t* node, rbtree_node_t* sentinel)
{
while(node->left != sentinel)
{
node = node->left;
}
return node;
}
/* replace the node "node" in the tree with node "tmp" */
static inline void rbtree_replace(rbtree_t* tree,
rbtree_node_t* node, rbtree_node_t* tmp)
{
/* upward: p[node] <- p[tmp] */
    tmp->parent = node->parent;
if (node == tree->root)
{
tree->root = tmp;
}
else if (node == node->parent->left)
{
/* downward: left[p[node]] <- tmp */
        node->parent->left = tmp;
}
else
{
/* downward: right[p[node]] <- tmp */
        node->parent->right = tmp;
}
node->parent = tmp;
}
/* change the topologic structure of the tree keeping the order of the nodes */
static inline void rbtree_left_rotate(rbtree_t* tree, rbtree_node_t* node)
{
/* node as the var x in CLRS while tmp as the var y */
rbtree_node_t* tmp = node->right;
/* replace y with left[y] */
/* downward: right[x] <- left[y] */
    node->right = tmp->left;
/* if left[[y] is not NIL it has a parent */
if (tmp->left != tree->sentinel)
{
/* upward: p[left[y]] <- x */
        tmp->left->parent = node;
}
/* replace x with y */
rbtree_replace(tree, node, tmp);
tmp->left = node;
}
static inline void rbtree_right_rotate(rbtree_t* tree, rbtree_node_t* node)
{
rbtree_node_t* tmp = node->left;
/* replace y with right[y] */
node->left = tmp->right;
if (tmp->right != tree->sentinel)
{
tmp->right->parent = node;
}
/* replace x with y */
rbtree_replace(tree, node, tmp);
tmp->right = node;
}
/* static methods */
/* fix the red-black tree after the new node inserted */
static void rbtree_insert_fixup(rbtree_t* tree, rbtree_node_t* node)
{
while(rbtree_is_red(node->parent))
{
if (node->parent == node->parent->parent->left)
{
/* case 1: node's uncle is red */
if (rbtree_is_red(node->parent->parent->right))
{
rbtree_black(node->parent);
rbtree_black(node->parent->parent->right);
rbtree_red(node->parent->parent);
node = node->parent->parent;
/* Then we can consider the whole subtree */
/* which is represented by the new "node" as the "node" before */
/* and keep looping till "node" become the root. */
}
/* case 2: node's uncle is black */
else
{
/* ensure node is the left kid of its parent */
if (node == node->parent->right)
{
node = node->parent;
rbtree_left_rotate(tree, node);
}
/* case 2 -> case 1 */
rbtree_black(node->parent);
rbtree_red(node->parent->parent);
rbtree_right_rotate(tree, node->parent->parent);
}
}
/* same as the "if" clause before with "left" and "right" exchanged */
else
{
if (rbtree_is_red(node->parent->parent->left))
{
rbtree_black(node->parent);
rbtree_black(node->parent->parent->left);
rbtree_red(node->parent->parent);
node = node->parent->parent;
}
else
{
if (node == node->parent->left)
{
node = node->parent;
rbtree_right_rotate(tree, node);
}
rbtree_black(node->parent);
rbtree_red(node->parent->parent);
rbtree_left_rotate(tree, node->parent->parent);
}
}
}
/* ensure the root node being black */
rbtree_black(tree->root);
}
static void rbtree_delete_fixup(rbtree_t* tree, rbtree_node_t* node)
{
rbtree_node_t* brother = NULL;
while(node != tree->root && rbtree_is_black(node))
{
if (node == node->parent->left)
{
brother = node->parent->right;
if (rbtree_is_red(brother))
{
rbtree_black(brother);
rbtree_red(node->parent);
rbtree_left_rotate(tree, node->parent);
/* update brother after topologic change of the tree */
brother = node->parent->right;
}
if (rbtree_is_black(brother->left) && rbtree_is_black(brother->right))
{
rbtree_red(brother);
/* go upward and keep on fixing color */
node = node->parent;
}
else
{
if (rbtree_is_black(brother->right))
{
rbtree_black(brother->left);
rbtree_red(brother);
rbtree_right_rotate(tree, brother);
/* update brother after topologic change of the tree */
brother = node->parent->right;
}
rbtree_copy_color(brother, node->parent);
rbtree_black(node->parent);
rbtree_black(brother->right);
rbtree_left_rotate(tree, node->parent);
/* end the loop and ensure root is black */
node = tree->root;
}
}
/* same as the "if" clause before with "left" and "right" exchanged */
else
{
brother = node->parent->left;
if (rbtree_is_red(brother))
{
rbtree_black(brother);
rbtree_red(node->parent);
rbtree_left_rotate(tree, node->parent);
brother = node->parent->left;
}
if (rbtree_is_black(brother->left) && rbtree_is_black(brother->right))
{
rbtree_red(brother);
node = node->parent;
}
else
{
if (rbtree_is_black(brother->left))
{
rbtree_black(brother->right);
rbtree_red(brother);
rbtree_right_rotate(tree, brother);
brother = node->parent->left;
}
rbtree_copy_color(brother, node->parent);
rbtree_black(node->parent);
rbtree_black(brother->left);
rbtree_left_rotate(tree, node->parent);
node = tree->root;
}
}
}
rbtree_black(node);
}
/* public methods */
void rbtree_insert_value(rbtree_t* tree, rbtree_node_t* node)
{
/* Using ** to know wether the new node will be a left kid */
/* or a right kid of its parent node. */
rbtree_node_t** tmp = &tree->root;
rbtree_node_t* parent;
while(*tmp != tree->sentinel)
{
parent = *tmp;
tmp = (node->key < parent->key) ? &parent->left : &parent->right;
}
/* The pointer knows wether the node should be on the left side */
/* or on the right one. */
*tmp = node;
node->parent = parent;
node->left = tree->sentinel;
node->right = tree->sentinel;
rbtree_red(node);
}
void rbtree_insert(rbtree_t* tree, rbtree_node_t* node)
{
rbtree_node_t* sentinel = tree->sentinel;
/* if the tree is empty */
if (tree->root == sentinel)
{
tree->root = node;
node->parent = sentinel;
node->left = sentinel;
node->right = sentinel;
rbtree_black(node);
return;
}
/* generally */
tree->insert(tree, node);
rbtree_insert_fixup(tree, node);
}
void rbtree_delete(rbtree_t* tree, rbtree_node_t* node)
{
rbtree_node_t* sentinel = tree->sentinel;
/* wether "node" is on the left side or the right one */
rbtree_node_t** ptr_to_node = NULL;
/* "cover" is the node which is going to cover "node" */
rbtree_node_t* cover = NULL;
/* wether we lossing a red node on the edge of the tree */
int loss_red = rbtree_is_red(node);
int is_root = (node == tree->root);
/* get "cover" & "loss_red" */
/* sentinel in "node"'s kids */
if (node->left == sentinel)
{
cover = node->right;
}
else if (node->right == sentinel)
{
cover = node->left;
}
/* "node"'s kids are both non-sentinel */
else
{
/* update "node" & "loss_red" & "is_root" & "cover" */
cover = rbtree_subtree_min(node->right, sentinel);
node->key = cover->key;
node->value = cover->value;
node = cover;
loss_red = rbtree_is_red(node);
is_root = 0;
/* move "cover"'s kids */
/* "cover" can only be a left kid */
/* and can only have a right non-sentinel kid */
/* because of function "rbtree_subtree_min" */
cover = node->right;
}
if (is_root)
{
/* update root */
tree->root = cover;
}
else
{
/* downward link */
if (node == node->parent->left)
{
node->parent->left = cover;
}
else
{
node->parent->right = cover;
}
}
/* upward link */
cover->parent = node->parent;
/* "cover" may be a sentinel */
if (cover != sentinel)
{
/* set "cover" */
cover->left = node->left;
cover->right = node->right;
rbtree_copy_color(cover, node);
}
/* clear "node" since it's useless */
node->key = -1;
node->parent = NULL;
node->left = NULL;
node->right = NULL;
node->value = NULL;
if (loss_red)
{
return;
}
/* When lossing a black node on edge */
/* the fifth rule of red-black tree will be broke. */
/* So the tree need to be fixed. */
rbtree_delete_fixup(tree, cover);
}
/* find the node in the tree corresponding to the given key value */
rbtree_node_t* rbtree_find(rbtree_t* tree, rbtree_key_t key)
{
rbtree_node_t* tmp = tree->root;
int step_cnt = 0;
/* search the binary tree */
while(tmp != tree->sentinel)
{
/* next line is just fot test */
// step_cnt++;
if(key == tmp->key)
{
/* next line is just for test */
// printf("step count: %d, color: %s, ", step_cnt, rbtree_is_red(tmp) ? "red" : "black");
return tmp;
}
tmp = (key < tmp->key) ? tmp->left : tmp->right;
}
return NULL;
}
Obwohl ich verstehe, dass der lange Funktionskörper von mehr als 100 Zeilen im Nginx-Quellcode auch eine Optimierung ist, um zu viele Funktionen zu vermeiden Aufrufe, die den Zeit- und Platzaufwand erhöhen, klassifiziere und unterteile ich dennoch alle Funktionen in weniger als 100 Zeilen. Die Lesbarkeit zu erhöhen ist eine Sache, kann aber auch ein wenig zwanghaft sein. Später werden mehrere statistische Methoden wie Max, Min und Mid sowie eine Traversalmethode erweitert.
Das Folgende ist der Aufruftest test.c:
#include <stdio.h>
#include "rbtree.h"
int main(int argc, char const *argv[])
{
rbtree_t t = {};
rbtree_node_t s = {};
rbtree_init(&t, &s, rbtree_insert_value);
const int cnt = 10;
const int max_len = 15;
#define TEST_VALUES {"apple", "banana", "cherry", "grape", "lemon", "mango", "pear", "pineapple", "strawberry", "watermelon"}
/* for gcc */
char* v[] = TEST_VALUES;
/* for g++ */
// char v[][max_len] = TEST_VALUES;
rbtree_node_t n[cnt];
int i;
for (i = 0; i < cnt; i++)
    {
        n[i].key = i+1;
        n[i].value = v[i];
        rbtree_insert(&t, &n[i]);
    }
    rbtree_node_t* p[cnt];
    for (i = 1; i <= cnt; i++)
    {
        printf("key: %d\n", i);
        p[i] = rbtree_find(&t, i);
        printf("value: %s\n", (p[i] != NULL) ? p[i]->value : "?");
}
rbtree_delete(&t, &n[5]);
printf("\nafter delete 6->mango:\n\n");
for (i = 1; i <= cnt; i++)
    {
        printf("key: %d\n", i);
        p[i] = rbtree_find(&t, i);
        printf("value: %s\n", (p[i] != NULL) ? p[i]->value : "?");
}
return 0;
}
Entsperren Sie den Testzeilenkommentar in der rbtree_find-Methode und führen Sie ihn reibungslos aus:
key: 1 step count: 3, color: black, value: apple key: 2 step count: 2, color: black, value: banana key: 3 step count: 3, color: black, value: cherry key: 4 step count: 1, color: black, value: grape key: 5 step count: 3, color: black, value: lemon key: 6 step count: 2, color: black, value: mango key: 7 step count: 4, color: black, value: pear key: 8 step count: 3, color: red, value: pineapple key: 9 step count: 4, color: black, value: strawberry key: 10 step count: 5, color: red, value: watermelon after delete 6->mango: key: 1 step count: 3, color: black, value: apple key: 2 step count: 2, color: black, value: banana key: 3 step count: 3, color: black, value: cherry key: 4 step count: 1, color: black, value: grape key: 5 step count: 3, color: black, value: lemon key: 6 value: ? key: 7 step count: 2, color: black, value: pear key: 8 step count: 4, color: black, value: pineapple key: 9 step count: 3, color: red, value: strawberry key: 10 step count: 4, color: black, value: watermelon
Machen wir es unten. Ein Stresstest mit einer großen Datenmenge. Achten Sie darauf, die Testzeile in der rbtree_find-Methode auszukommentieren, sonst können die Konsequenzen beängstigend sein:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "rbtree.h"
int main(int argc, char const *argv[])
{
double duration;
double room;
rbtree_t t = {};
rbtree_node_t s = {};
rbtree_init(&t, &s, rbtree_insert_value);
const int cnt = 1<<20;
const int max_len = 15;
#define TEST_VALUES {"apple", "banana", "cherry", "grape", "lemon", "mango", "pear", "pineapple", "strawberry", "watermelon"}
/* for gcc */
char* v[] = TEST_VALUES;
/* for g++ */
// char v[][max_len] = TEST_VALUES;
/* Default stack size in Ubuntu Kylin 14.04 is 8MB. */
/* It's not enough. So I use memory in heap which offers a lot larger room. */
rbtree_node_t* n = (rbtree_node_t*)calloc(cnt, sizeof(rbtree_node_t));
int i;
long time1 = clock();
for (i = 0; i < cnt; i++)
{
n[i].key = i+1;
n[i].value = v[i%10];
rbtree_insert(&t, &n[i]);
}
long time2 = clock();
room = 48.0*cnt/(1<<20);
duration = (double)(time2 - time1) / CLOCKS_PER_SEC;
printf("Inserting %d nodes costs %.2fMB and spends %f seconds.\n", cnt, room, duration);
const int search_cnt = 1<<10;
srand( (unsigned int)time(0) );
for( i = 0 ; i < search_cnt ; i++ )
{
rbtree_find(&t, (rand()%cnt)+1);
}
long time3 = clock();
duration = (double)(time3 - time2) / CLOCKS_PER_SEC;
printf("Searching %d nodes among %d spends %f seconds.\n", search_cnt, cnt, duration);
const int delete_cnt = 1<<10;
int nums[delete_cnt];
int num;
/* Let's hash! */
char* mark = (char*)calloc(cnt, sizeof(char));
memset(mark, 0, cnt*sizeof(char));
for(i = 0; i < delete_cnt; i++)
{
for(;;)
{
num = rand()%cnt;
if (mark[num] == 0)
{
mark[num] = 1;
nums[i] = num;
break;
}
}
}
long time4 = clock();
duration = (double)(time4 - time3) / CLOCKS_PER_SEC;
printf("Hash %d times spends %f seconds.\n", delete_cnt, duration);
for(i = 0; i < delete_cnt; i++)
{
rbtree_delete(&t, &n[nums[i]]);
}
long time5 = clock();
duration = (double)(time5 - time4) / CLOCKS_PER_SEC;
printf("Deleting %d nodes among %d spends %f seconds.\n", delete_cnt, cnt, duration);
free(mark);
free(n);
return 0;
}Werfen wir einen Blick auf die Ergebnisse:
Inserting 1048576 nodes costs 48.00MB and spends 0.425416 seconds. Searching 1024 nodes among 1048576 spends 0.001140 seconds. Hash 1024 times spends 0.000334 seconds. Deleting 1024 nodes among 1048576 spends 0.000783 seconds.
Ich werde Statistiken und Traversierungsmethoden schreiben.
Urheberrechtserklärung: Dieser Artikel ist ein Originalartikel des Bloggers und darf nicht ohne die Erlaubnis des Bloggers reproduziert werden.
Das Obige stellt die Nginx-Datenstruktur 2 vor. Ich hoffe, dass es für Freunde, die sich für PHP-Tutorials interessieren, hilfreich sein wird.
Heiße KI -Werkzeuge
Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos
AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.
Undress AI Tool
Ausziehbilder kostenlos
Clothoff.io
KI-Kleiderentferner
AI Hentai Generator
Erstellen Sie kostenlos Ai Hentai.
Heißer Artikel
Heiße Werkzeuge
Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor
SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen
Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung
Dreamweaver CS6
Visuelle Webentwicklungstools
SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)
Heiße Themen
1369
52
So löschen Sie einen Knoten in NVM
Dec 29, 2022 am 10:07 AM
So löschen Sie einen Knoten mit nvm: 1. Laden Sie „nvm-setup.zip“ herunter und installieren Sie es auf dem Laufwerk C. 2. Konfigurieren Sie Umgebungsvariablen und überprüfen Sie die Versionsnummer mit dem Befehl „nvm -v“. install“-Befehl Knoten installieren; 4. Löschen Sie den installierten Knoten über den Befehl „nvm uninstall“.
So verwenden Sie Express für den Datei-Upload im Knotenprojekt
Mar 28, 2023 pm 07:28 PM
Wie gehe ich mit dem Datei-Upload um? Der folgende Artikel stellt Ihnen vor, wie Sie Express zum Hochladen von Dateien im Knotenprojekt verwenden. Ich hoffe, er ist hilfreich für Sie!
Wie führt man eine Docker-Spiegelung des Node-Dienstes durch? Detaillierte Erläuterung der ultimativen Optimierung
Oct 19, 2022 pm 07:38 PM
Während dieser Zeit habe ich einen dynamischen HTML-Dienst entwickelt, der allen Kategorien von Tencent-Dokumenten gemeinsam ist. Um die Generierung und Bereitstellung des Zugriffs auf verschiedene Kategorien zu erleichtern und dem Trend der Cloud-Migration zu folgen, habe ich über die Verwendung von Docker nachgedacht Serviceinhalte verwalten und Produktversionen einheitlich verwalten. In diesem Artikel werden die Optimierungserfahrungen, die ich bei der Bereitstellung von Docker gesammelt habe, als Referenz weitergegeben.
Eine ausführliche Analyse des Prozessmanagement-Tools „pm2' von Node
Apr 03, 2023 pm 06:02 PM
In diesem Artikel stellen wir Ihnen das Prozessmanagement-Tool „pm2“ von Node vor und sprechen darüber, warum PM2 benötigt wird und wie Sie PM2 installieren und verwenden. Ich hoffe, dass es für alle hilfreich ist!
PI -Knotenunterricht: Was ist ein PI -Knoten? Wie installiere und richte ich einen PI -Knoten ein?
Mar 05, 2025 pm 05:57 PM
Detaillierte Erläuterungs- und Installationshandbuch für Pinetwork -Knoten In diesem Artikel wird das Pinetwork -Ökosystem im Detail vorgestellt - PI -Knoten, eine Schlüsselrolle im Pinetwork -Ökosystem und vollständige Schritte für die Installation und Konfiguration. Nach dem Start des Pinetwork -Blockchain -Testnetzes sind PI -Knoten zu einem wichtigen Bestandteil vieler Pioniere geworden, die aktiv an den Tests teilnehmen und sich auf die bevorstehende Hauptnetzwerkveröffentlichung vorbereiten. Wenn Sie Pinetwork noch nicht kennen, wenden Sie sich bitte an was Picoin ist? Was ist der Preis für die Auflistung? PI -Nutzung, Bergbau und Sicherheitsanalyse. Was ist Pinetwork? Das Pinetwork -Projekt begann 2019 und besitzt seine exklusive Kryptowährung PI -Münze. Das Projekt zielt darauf ab, eine zu erstellen, an der jeder teilnehmen kann
Lassen Sie uns darüber sprechen, wie Sie mit pkg Node.js-Projekte in ausführbare Dateien packen.
Dec 02, 2022 pm 09:06 PM
Wie packe ich die ausführbare Datei von nodejs mit pkg? Im folgenden Artikel erfahren Sie, wie Sie mit pkg ein Node-Projekt in eine ausführbare Datei packen. Ich hoffe, dass er Ihnen weiterhilft!
Was tun, wenn npm node gyp ausfällt?
Dec 29, 2022 pm 02:42 PM
npm node gyp schlägt fehl, weil „node-gyp.js“ nicht mit der Version von „Node.js“ übereinstimmt. Die Lösung ist: 1. Löschen Sie den Knotencache über „npm cache clean -f“ 2. Über „npm install -“ g n“ Installieren Sie das n-Modul. 3. Installieren Sie die Version „node v12.21.0“ über den Befehl „n v12.21.0“.
Tokenbasierte Authentifizierung mit Angular und Node
Sep 01, 2023 pm 02:01 PM
Die Authentifizierung ist einer der wichtigsten Teile jeder Webanwendung. In diesem Tutorial werden tokenbasierte Authentifizierungssysteme und ihre Unterschiede zu herkömmlichen Anmeldesystemen erläutert. Am Ende dieses Tutorials sehen Sie eine voll funktionsfähige Demo, die in Angular und Node.js geschrieben wurde. Traditionelle Authentifizierungssysteme Bevor wir zu tokenbasierten Authentifizierungssystemen übergehen, werfen wir einen Blick auf traditionelle Authentifizierungssysteme. Der Benutzer gibt seinen Benutzernamen und sein Passwort im Anmeldeformular ein und klickt auf „Anmelden“. Nachdem Sie die Anfrage gestellt haben, authentifizieren Sie den Benutzer im Backend, indem Sie die Datenbank abfragen. Wenn die Anfrage gültig ist, wird eine Sitzung mit den aus der Datenbank erhaltenen Benutzerinformationen erstellt und die Sitzungsinformationen werden im Antwortheader zurückgegeben, sodass die Sitzungs-ID im Browser gespeichert wird. Bietet Zugriff auf Anwendungen, die unterliegen
