add prioq abstract data type

git-svn-id: file:///home/lennart/svn/public/avahi/trunk@5 941a03a8-eaeb-0310-b9a0-b1bbd8fe43fe

13 files changed, 660 insertions, 46 deletions

diff --git a/Makefile b/Makefile
index f5af624..dc3a033 100644
--- a/Makefile
+++ b/Makefile
@@ -1,9 +1,16 @@
 CFLAGS=-g -O0 -Wall -W -pipe $(shell pkg-config --cflags glib-2.0)
 LIBS=$(shell pkg-config --libs glib-2.0)
 
-flexmdns: main.o iface.o netlink.o server.o address.o util.o local.o
+#flexmdns: main.o iface.o netlink.o server.o address.o util.o local.o
+#	$(CC) -o $@ $^ $(LIBS)
+
+#test-llist: test-llist.o
+#	$(CC) -o $@ $^ $(LIBS)
+
+prioq-test: prioq-test.o prioq.o
 	$(CC) -o $@ $^ $(LIBS)
 
+
 *.o: *.h
 
 clean:
diff --git a/address.c b/address.c
index 9099ad9..a6a7a52 100644
--- a/address.c
+++ b/address.c
@@ -23,7 +23,7 @@ gint flx_address_cmp(const flxAddress *a, const flxAddress *b) {
     if (a->family != b->family)
         return -1;
 
-    return memcmp(a, b, flx_address_get_size(a));
+    return memcmp(a->data, b->data, flx_address_get_size(a));
 }
 
 gchar *flx_address_snprint(char *s, guint length, const flxAddress *a) {
@@ -86,7 +86,7 @@ gchar *flx_reverse_lookup_name_ipv6_int(const flxIPv6Address *a) {
     return reverse_lookup_name_ipv6(a, "ip6.int");
 }
 
-flxAddress *flx_address_parse(const char *s, int family, flxAddress *ret_addr) {
+flxAddress *flx_address_parse(const char *s, guchar family, flxAddress *ret_addr) {
     g_assert(ret_addr);
     g_assert(s);
 
diff --git a/address.h b/address.h
index 33dcc27..193a2d1 100644
--- a/address.h
+++ b/address.h
@@ -12,7 +12,7 @@ typedef struct {
 } flxIPv6Address;
 
 typedef struct {
-    guint family;
+    guchar family;
 
     union {
         flxIPv6Address ipv6;
@@ -26,7 +26,7 @@ gint flx_address_cmp(const flxAddress *a, const flxAddress *b);
 
 gchar *flx_address_snprint(char *ret_s, guint length, const flxAddress *a);
 
-flxAddress *flx_address_parse(const char *s, int family, flxAddress *ret_addr);
+flxAddress *flx_address_parse(const char *s, guchar family, flxAddress *ret_addr);
 
 gchar* flx_reverse_lookup_name_ipv4(const flxIPv4Address *a);
 gchar* flx_reverse_lookup_name_ipv6_arpa(const flxIPv6Address *a);
diff --git a/flx.h b/flx.h
index b7a5ae9..419ab86 100644
--- a/flx.h
+++ b/flx.h
@@ -29,9 +29,9 @@ void flx_server_free(flxServer* s);
 
 gint flx_server_get_next_id(flxServer *s);
 
-void flx_server_add_rr(flxServer *s, gint id, gint interface, const flxRecord *rr);
-void flx_server_add(flxServer *s, gint id, gint interface, const gchar *name, guint16 type, gconstpointer data, guint size);
-void flx_server_add_address(flxServer *s, gint id, gint interface, const gchar *name, flxAddress *a);
+void flx_server_add_rr(flxServer *s, gint id, gint interface, guchar protocol, const flxRecord *rr);
+void flx_server_add(flxServer *s, gint id, gint interface, guchar protocol, const gchar *name, guint16 type, gconstpointer data, guint size);
+void flx_server_add_address(flxServer *s, gint id, gint interface, guchar protocol, const gchar *name, flxAddress *a);
 
 void flx_server_remove(flxServer *s, gint id);
 
@@ -47,17 +47,21 @@ typedef struct _flxLocalAddrSource flxLocalAddrSource;
 flxLocalAddrSource *flx_local_addr_source_new(flxServer *s);
 void flx_local_addr_source_free(flxLocalAddrSource *l);
 
-#define FLX_DNS_TYPE_A 0x01
-#define FLX_DNS_TYPE_AAAA 0x1C
-#define FLX_DNS_TYPE_PTR 0x0C
-#define FLX_DNS_TYPE_HINFO 0x0D
-#define FLX_DNS_TYPE_CNAME 0x05
-#define FLX_DNS_TYPE_NS 0x02
-#define FLX_DNS_TYPE_SOA 0x06
-#define FLX_DNS_TYPE_MX 0x0F
-#define FLX_DNS_TYPE_TXT 0x10
-
-#define FLX_DNS_CLASS_IN 0x01
+enum {
+    FLX_DNS_TYPE_A = 0x01,
+    FLX_DNS_TYPE_NS = 0x02,
+    FLX_DNS_TYPE_CNAME = 0x05,
+    FLX_DNS_TYPE_SOA = 0x06,
+    FLX_DNS_TYPE_PTR = 0x0C,
+    FLX_DNS_TYPE_HINFO = 0x0D,
+    FLX_DNS_TYPE_MX = 0x0F,
+    FLX_DNS_TYPE_TXT = 0x10,
+    FLX_DNS_TYPE_AAAA = 0x1C,
+};
+
+enum {
+    FLX_DNS_CLASS_IN = 0x01
+};
 
 #define FLX_DEFAULT_TTL (120*60)
 
diff --git a/iface.c b/iface.c
index 01f0637..61d7b51 100644
--- a/iface.c
+++ b/iface.c
@@ -57,6 +57,11 @@ static void free_address(flxInterfaceMonitor *m, flxInterfaceAddress *a) {
     g_assert(a);
     g_assert(a->interface);
 
+    if (a->address.family == AF_INET)
+        a->interface->n_ipv4_addrs --;
+    else if (a->address.family == AF_INET6)
+        a->interface->n_ipv6_addrs --;
+ 
     if (a->prev)
         a->prev->next = a->next;
     else
@@ -75,6 +80,9 @@ static void free_interface(flxInterfaceMonitor *m, flxInterface *i) {
     while (i->addresses)
         free_address(m, i->addresses);
 
+    g_assert(i->n_ipv6_addrs == 0);
+    g_assert(i->n_ipv4_addrs == 0);
+
     if (i->prev)
         i->prev->next = i->next;
     else
@@ -143,9 +151,11 @@ static void callback(flxNetlink *nl, struct nlmsghdr *n, gpointer userdata) {
         if ((i = (flxInterface*) flx_interface_monitor_get_interface(m, ifinfomsg->ifi_index)))
             changed = 1;
         else {
-            i = g_new0(flxInterface, 1);
+            i = g_new(flxInterface, 1);
+            i->name = NULL;
             i->index = ifinfomsg->ifi_index;
             i->addresses = NULL;
+            i->n_ipv4_addrs = i->n_ipv6_addrs = 0;
             if ((i->next = m->interfaces))
                 i->next->prev = i;
             m->interfaces = i;
@@ -223,6 +233,7 @@ static void callback(flxNetlink *nl, struct nlmsghdr *n, gpointer userdata) {
 
                     memcpy(raddr.data, RTA_DATA(a), RTA_PAYLOAD(a));
                     raddr_valid = 1;
+
                     break;
                     
                 default:
@@ -232,6 +243,7 @@ static void callback(flxNetlink *nl, struct nlmsghdr *n, gpointer userdata) {
             a = RTA_NEXT(a, l);
         }
 
+
         if (!raddr_valid)
             return;
 
@@ -241,8 +253,14 @@ static void callback(flxNetlink *nl, struct nlmsghdr *n, gpointer userdata) {
             if ((addr = get_address(m, i, &raddr)))
                 changed = 1;
             else {
-                addr = g_new0(flxInterfaceAddress, 1);
+                addr = g_new(flxInterfaceAddress, 1);
                 addr->address = raddr;
+
+                if (raddr.family == AF_INET)
+                    i->n_ipv4_addrs++;
+                else if (raddr.family == AF_INET6)
+                    i->n_ipv6_addrs++;
+                
                 addr->interface = i;
                 if ((addr->next = i->addresses))
                     addr->next->prev = addr;
diff --git a/iface.h b/iface.h
index 3476645..49bcf20 100644
--- a/iface.h
+++ b/iface.h
@@ -19,6 +19,8 @@ struct _flxInterface {
     gint index;
     guint flags;
 
+    guint n_ipv6_addrs, n_ipv4_addrs;
+    
     flxInterfaceAddress *addresses;
     flxInterface *next, *prev;
 };
diff --git a/local.c b/local.c
index 7204ca8..6c61fac 100644
--- a/local.c
+++ b/local.c
@@ -42,14 +42,18 @@ static guint hash(gconstpointer v, guint l) {
 static guint addr_hash(gconstpointer v) {
     const flxAddress *a = v;
 
-    return hash(a, sizeof(a->family) + flx_address_get_size(a));
+    return hash(a->data, flx_address_get_size(a));
 }
 
 static void remove_addr(flxLocalAddrSource *l, const flxInterfaceAddress *a) {
+    flxAddress foo;
     g_assert(l);
     g_assert(a);
-    
-    g_hash_table_remove(l->hash_table, &a->address);
+
+    memset(&foo, 0, sizeof(foo));
+    foo.family = AF_INET;
+
+    g_hash_table_remove(l->hash_table, &foo); 
 }
 
 static void add_addr(flxLocalAddrSource *l, const flxInterfaceAddress *a) {
@@ -59,14 +63,14 @@ static void add_addr(flxLocalAddrSource *l, const flxInterfaceAddress *a) {
 
     if (g_hash_table_lookup(l->hash_table, &a->address))
         return; /* Entry already existant */
-    
+
     ai = g_new(addr_info, 1);
     ai->server = l->server;
     ai->address = a->address;
     
     ai->id = flx_server_get_next_id(l->server);
 
-    flx_server_add_address(l->server, ai->id, a->interface->index, l->hostname, &ai->address);
+    flx_server_add_address(l->server, ai->id, a->interface->index, AF_UNSPEC, l->hostname, &ai->address);
 
     g_hash_table_replace(l->hash_table, &ai->address, ai);
 }
@@ -152,9 +156,8 @@ flxLocalAddrSource *flx_local_addr_source_new(flxServer *s) {
     uname(&utsname);
     c = g_strdup_printf("%s%c%s%n", g_strup(utsname.machine), 0, g_strup(utsname.sysname), &length);
     
-    flx_server_add(l->server, l->hinfo_id, 0, l->hostname,
-                   FLX_DNS_TYPE_HINFO,
-                   c, length+1);
+    flx_server_add(l->server, l->hinfo_id, 0, AF_UNSPEC,
+                   l->hostname, FLX_DNS_TYPE_HINFO, c, length+1);
     g_free(c);
     
     return l;
diff --git a/main.c b/main.c
index da4b338..0dcfa70 100644
--- a/main.c
+++ b/main.c
@@ -22,10 +22,10 @@ int main(int argc, char *argv[]) {
     l = flx_local_addr_source_new(flx);
 
     flx_address_parse("127.0.0.1", AF_INET, &a);
-    flx_server_add_address(flx, 0, 0, "localhost", &a);
+    flx_server_add_address(flx, 0, 0, AF_UNSPEC, "localhost", &a);
 
     flx_address_parse("::1", AF_INET6, &a);
-    flx_server_add_address(flx, 0, 0, "ip6-localhost", &a);
+    flx_server_add_address(flx, 0, 0, AF_UNSPEC, "ip6-localhost", &a);
 
     g_timeout_add(1000, timeout, NULL);
     
diff --git a/prioq-test.c b/prioq-test.c
new file mode 100644
index 0000000..56cfbc1
--- /dev/null
+++ b/prioq-test.c
@@ -0,0 +1,55 @@
+#include <time.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "prioq.h"
+
+static gint compare(gpointer a, gpointer b) {
+    gint i = GPOINTER_TO_INT(a), j = GPOINTER_TO_INT(b);
+
+    return i < j ? -1 : (i > j ? 1 : 0);
+}
+
+static void rec(flxPrioQueueNode *n) {
+    if (!n)
+        return;
+
+    if (n->parent) {
+        int a = GPOINTER_TO_INT(n->parent->data), b = GPOINTER_TO_INT(n->data);
+        if (a > b) {
+            printf("%i <= %i: NO\n", a, b);
+            abort();
+        }
+    }
+
+    rec(n->left);
+    rec(n->right);
+}
+
+int main(int argc, char *argv[]) {
+    flxPrioQueue *q;
+    gint i, prev;
+
+    q = flx_prio_queue_new(compare);
+
+    srand(time(NULL));
+
+    flx_prio_queue_put(q, GINT_TO_POINTER(255)); 
+    flx_prio_queue_put(q, GINT_TO_POINTER(255)); 
+    
+    for (i = 0; i < 10000; i++) 
+        flx_prio_queue_put(q, GINT_TO_POINTER(random() & 0xFFFF)); 
+
+    prev = 0;
+    while (q->root) {
+        gint v = GPOINTER_TO_INT(q->root->data);
+        rec(q->root);
+        printf("%i\n", v);
+        flx_prio_queue_remove(q, q->root);
+        g_assert(v >= prev);
+        prev = v;
+    }
+
+    flx_prio_queue_free(q);
+    return 0;
+}
diff --git a/prioq.c b/prioq.c
new file mode 100644
index 0000000..4360497
--- /dev/null
+++ b/prioq.c
@@ -0,0 +1,341 @@
+#include "prioq.h"
+
+flxPrioQueue* flx_prio_queue_new(gint (*compare) (gpointer a, gpointer b)) {
+    flxPrioQueue *q;
+    g_assert(compare);
+
+    q = g_new(flxPrioQueue, 1);
+    q->root = q->last = NULL;
+    q->n_nodes = 0;
+    q->compare = compare;
+    return q;
+}
+
+void flx_prio_queue_free(flxPrioQueue *q) {
+    g_assert(q);
+
+    while (q->last)
+        flx_prio_queue_remove(q, q->last);
+
+    g_assert(!q->n_nodes);
+    g_free(q);
+}
+
+static flxPrioQueueNode* get_node_at_xy(flxPrioQueue *q, guint x, guint y) {
+    guint r;
+    flxPrioQueueNode *n;
+    g_assert(q);
+
+    n = q->root;
+    g_assert(n);
+
+    for (r = 0; r < y; r++) {
+        g_assert(n);
+        
+        if ((x >> (y-r-1)) & 1)
+            n = n->right;
+        else
+            n = n->left;
+    }
+
+    g_assert(n->x == x);
+    g_assert(n->y == y);
+
+    return n;
+}
+
+static void exchange_nodes(flxPrioQueue *q, flxPrioQueueNode *a, flxPrioQueueNode *b) {
+    flxPrioQueueNode *l, *r, *p, *ap, *an, *bp, *bn;
+    gint t;
+    g_assert(q);
+    g_assert(a);
+    g_assert(b);
+    g_assert(a != b);
+
+    /* Swap positions */
+    t = a->x; a->x = b->x; b->x = t;
+    t = a->y; a->y = b->y; b->y = t;
+
+    if (a->parent == b) {
+        /* B is parent of A */
+        
+        p = b->parent;
+        b->parent = a;
+
+        if ((a->parent = p)) {
+            if (a->parent->left == b)
+                a->parent->left = a;
+            else
+                a->parent->right = a;
+        } else
+            q->root = a;
+
+        if (b->left == a) {
+            if ((b->left = a->left))
+                b->left->parent = b;
+            a->left = b;
+
+            r = a->right;
+            if ((a->right = b->right))
+                a->right->parent = a;
+            if ((b->right = r))
+                b->right->parent = b;
+            
+        } else {
+            if ((b->right = a->right))
+                b->right->parent = b;
+            a->right = b;
+
+            l = a->left;
+            if ((a->left = b->left))
+                a->left->parent = a;
+            if ((b->left = l))
+                b->left->parent = b;
+        }
+    } else if (b->parent == a) {
+        /* A ist parent of B */
+        
+        p = a->parent;
+        a->parent = b;
+
+        if ((b->parent = p)) {
+            if (b->parent->left == a)
+                b->parent->left = b;
+            else
+                b->parent->right = b;
+        } else
+            q->root = b;
+
+        if (a->left == b) {
+            if ((a->left = b->left))
+                a->left->parent = a;
+            b->left = a;
+
+            r = a->right;
+            if ((a->right = b->right))
+                a->right->parent = a;
+            if ((b->right = r))
+                b->right->parent = b;
+        } else {
+            if ((a->right = b->right))
+                a->right->parent = a;
+            b->right = a;
+
+            l = a->left;
+            if ((a->left = b->left))
+                a->left->parent = a;
+            if ((b->left = l))
+                b->left->parent = b;
+        }
+    } else {
+        /* Swap parents */
+        p = a->parent;
+        
+        if ((a->parent = b->parent)) {
+            if (a->parent->left == b)
+                a->parent->left = a;
+            else
+                a->parent->right = a;
+        } else
+            q->root = a;
+                
+        if ((b->parent = p)) {
+            if (b->parent->left == a)
+                b->parent->left = b;
+            else
+                b->parent->right = b;
+        } else
+            q->root = b;
+
+        /* Swap children */
+        l = a->left; 
+        r = a->right; 
+
+        if ((a->left = b->left))
+            a->left->parent = a;
+
+        if ((b->left = l))
+            b->left->parent = b;
+
+        if ((a->right = b->right))
+            a->right->parent = a;
+
+        if ((b->right = r))
+            b->right->parent = b;
+    }
+    
+    /* Swap siblings */
+    ap = a->prev; an = a->next;
+    bp = b->prev; bn = b->next;
+
+    if (a->next == b) {
+        /* A is predecessor of B */
+        a->prev = b;
+        b->next = a;
+
+        if ((a->next = bn))
+            a->next->prev = a;
+        else
+            q->last = a;
+
+        if ((b->prev = ap))
+            b->prev->next = b;
+        
+    } else if (b->next == a) {
+        /* B is predecessor of A */
+        a->next = b;
+        b->prev = a;
+
+        if ((a->prev = bp))
+            a->prev->next = a;
+
+        if ((b->next = an))
+            b->next->prev = b;
+        else
+            q->last = b;
+
+    } else {
+        /* A is no neighbour of B */
+
+        if ((a->prev = bp))
+            a->prev->next = a;
+        
+        if ((a->next = bn))
+            a->next->prev = a;
+        else
+            q->last = a;
+        
+        if ((b->prev = ap))
+            b->prev->next = b;
+        
+        if ((b->next = an))
+            b->next->prev = b;
+        else
+            q->last = b;
+    }
+}
+
+/* Move a node to the correct position */
+static void shuffle_node(flxPrioQueue *q, flxPrioQueueNode *n) {
+    g_assert(q);
+    g_assert(n);
+
+    /* Move up until the position is OK */
+    while (n->parent && q->compare(n->parent->data, n->data) > 0)
+        exchange_nodes(q, n, n->parent);
+
+    /* Move down until the position is OK */
+    for (;;) {
+        flxPrioQueueNode *min;
+
+        if (!(min = n->left)) {
+            /* No children */
+            g_assert(!n->right);
+            break;
+        }
+
+        if (n->right && q->compare(n->right->data, min->data) < 0)
+            min = n->right;
+
+        /* min now contains the smaller one of our two children */
+
+        if (q->compare(n->data, min->data) <= 0)
+            /* Order OK */
+            break;
+
+        exchange_nodes(q, n, min);
+    }
+}
+
+flxPrioQueueNode* flx_prio_queue_put(flxPrioQueue *q, gpointer data) {
+    flxPrioQueueNode *n;
+    g_assert(q);
+
+    n = g_new(flxPrioQueueNode, 1);
+    n->queue = q;
+    n->data = data;
+
+    if (q->last) {
+        g_assert(q->root);
+        g_assert(q->n_nodes);
+        
+        n->y = q->last->y;
+        n->x = q->last->x+1;
+
+        if (n->x >= ((guint) 1 << n->y)) {
+            n->x = 0;
+            n->y++;
+        }
+
+        q->last->next = n;
+        n->prev = q->last;
+        
+        g_assert(n->y > 0);
+        n->parent = get_node_at_xy(q, n->x/2, n->y-1);
+
+        if (n->x & 1)
+            n->parent->right = n;
+        else
+            n->parent->left = n;
+    } else {
+        g_assert(!q->root);
+        g_assert(!q->n_nodes);
+        
+        n->y = n->x = 0;
+        q->root = n;
+        n->prev = n->parent = NULL;
+    }
+
+    n->next = n->left = n->right = NULL;
+    q->last = n;
+    q->n_nodes++;
+
+    shuffle_node(q, n);
+
+    return n;
+}
+
+void flx_prio_queue_remove(flxPrioQueue *q, flxPrioQueueNode *n) {
+    g_assert(q);
+    g_assert(n);
+
+    if (n != q->last) {
+        flxPrioQueueNode *replacement = q->last;
+        exchange_nodes(q, replacement, n);
+        flx_prio_queue_remove(q, q->last);
+        shuffle_node(q, replacement);
+        return;
+    }
+
+    g_assert(n == q->last);
+    g_assert(!n->next);
+    g_assert(!n->left);
+    g_assert(!n->right);
+
+    q->last = n->prev;
+    
+    if (n->prev)
+        n->prev->next = NULL;
+    else
+        g_assert(!n->parent);
+
+    if (n->parent) {
+        g_assert(n->prev);
+        if (n->parent->left == n) {
+            g_assert(n->parent->right == NULL);
+            n->parent->left = NULL;
+        } else {
+            g_assert(n->parent->right == n);
+            g_assert(n->parent->left != NULL);
+            n->parent->right = NULL;
+        }
+    } else {
+        g_assert(q->root == n);
+        g_assert(!n->prev);
+        q->root = NULL;
+    }
+
+    q->n_nodes--;
+    
+    g_free(n);
+}
diff --git a/prioq.h b/prioq.h
new file mode 100644
index 0000000..e1b8796
--- /dev/null
+++ b/prioq.h
@@ -0,0 +1,33 @@
+#ifndef fooprioqhfoo
+#define fooprioqhfoo
+
+#include <glib.h>
+
+struct _flxPrioQueue;
+typedef struct _flxPrioQueue flxPrioQueue;
+
+struct _flxPrioQueueNode;
+typedef struct _flxPrioQueueNode flxPrioQueueNode;
+
+struct _flxPrioQueue {
+    flxPrioQueueNode *root, *last;
+    
+    guint n_nodes;
+    gint (*compare) (gpointer a, gpointer b);
+};
+
+struct _flxPrioQueueNode {
+    flxPrioQueue *queue;
+    gpointer data;
+    guint x, y;
+
+    flxPrioQueueNode *left, *right, *parent, *next, *prev;
+};
+
+flxPrioQueue* flx_prio_queue_new(gint (*compare) (gpointer a, gpointer b));
+void flx_prio_queue_free(flxPrioQueue *q);
+
+flxPrioQueueNode* flx_prio_queue_put(flxPrioQueue *q, gpointer data);
+void flx_prio_queue_remove(flxPrioQueue *q, flxPrioQueueNode *n);
+
+#endif
diff --git a/server.c b/server.c
index 2fa1275..35dbe3a 100644
--- a/server.c
+++ b/server.c
@@ -19,6 +19,9 @@ flxServer *flx_server_new(GMainContext *c) {
     s->rrset_by_name = g_hash_table_new(g_str_hash, g_str_equal);
     s->entries = NULL;
 
+    s->first_response_job = s->last_response_job = NULL;
+    s->first_query_jobs = s->last_query_job = NULL;
+    
     s->monitor = flx_interface_monitor_new(s->context);
     
     return s;
@@ -43,7 +46,7 @@ gint flx_server_get_next_id(flxServer *s) {
     return s->current_id++;
 }
 
-void flx_server_add_rr(flxServer *s, gint id, gint interface, const flxRecord *rr) {
+void flx_server_add_rr(flxServer *s, gint id, gint interface, guchar protocol, const flxRecord *rr) {
     flxEntry *e;
     g_assert(s);
     g_assert(rr);
@@ -55,6 +58,7 @@ void flx_server_add_rr(flxServer *s, gint id, gint interface, const flxRecord *r
     flx_record_copy_normalize(&e->rr, rr);
     e->id = id;
     e->interface = interface;
+    e->protocol = protocol;
 
     /* Insert into linked list */
     e->prev = NULL;
@@ -75,7 +79,7 @@ void flx_server_add_rr(flxServer *s, gint id, gint interface, const flxRecord *r
     g_hash_table_replace(s->rrset_by_name, e->rr.name, e);
 }
 
-void flx_server_add(flxServer *s, gint id, gint interface, const gchar *name, guint16 type, gconstpointer data, guint size) {
+void flx_server_add(flxServer *s, gint id, gint interface, guchar protocol, const gchar *name, guint16 type, gconstpointer data, guint size) {
     flxRecord rr;
     g_assert(s);
     g_assert(name);
@@ -88,7 +92,7 @@ void flx_server_add(flxServer *s, gint id, gint interface, const gchar *name, gu
     rr.data = (gpointer) data;
     rr.size = size;
     rr.ttl = FLX_DEFAULT_TTL;
-    flx_server_add_rr(s, id, interface, &rr);
+    flx_server_add_rr(s, id, interface, protocol, &rr);
 }
 
 const flxRecord *flx_server_iterate(flxServer *s, gint id, void **state) {
@@ -202,7 +206,7 @@ void flx_server_dump(flxServer *s, FILE *f) {
 
     for (e = s->entries; e; e = e->next) {
         char t[256];
-        fprintf(f, "%i: %-40s %-8s %-8s ", e->interface, e->rr.name, dns_class_to_string(e->rr.class), dns_type_to_string(e->rr.type));
+        fprintf(f, "%i.%u: %-40s %-8s %-8s ", e->interface, e->protocol, e->rr.name, dns_class_to_string(e->rr.class), dns_type_to_string(e->rr.type));
 
         t[0] = 0;
         
@@ -229,7 +233,7 @@ void flx_server_dump(flxServer *s, FILE *f) {
     }
 }
 
-void flx_server_add_address(flxServer *s, gint id, gint interface, const gchar *name, flxAddress *a) {
+void flx_server_add_address(flxServer *s, gint id, gint interface, guchar protocol, const gchar *name, flxAddress *a) {
     gchar *n;
     g_assert(s);
     g_assert(name);
@@ -240,28 +244,131 @@ void flx_server_add_address(flxServer *s, gint id, gint interface, const gchar *
     if (a->family == AF_INET) {
         gchar *r;
         
-        flx_server_add(s, id, interface, n, FLX_DNS_TYPE_A, &a->ipv4, sizeof(a->ipv4));
+        flx_server_add(s, id, interface, protocol, n, FLX_DNS_TYPE_A, &a->ipv4, sizeof(a->ipv4));
 
         r = flx_reverse_lookup_name_ipv4(&a->ipv4);
         g_assert(r);
-        flx_server_add(s, id, interface, r, FLX_DNS_TYPE_PTR, n, strlen(n)+1);
+        flx_server_add(s, id, interface, protocol, r, FLX_DNS_TYPE_PTR, n, strlen(n)+1);
         g_free(r);
         
     } else {
         gchar *r;
             
-        flx_server_add(s, id, interface, n, FLX_DNS_TYPE_AAAA, &a->ipv6, sizeof(a->ipv6));
+        flx_server_add(s, id, interface, protocol, n, FLX_DNS_TYPE_AAAA, &a->ipv6, sizeof(a->ipv6));
 
         r = flx_reverse_lookup_name_ipv6_arpa(&a->ipv6);
         g_assert(r);
-        flx_server_add(s, id, interface, r, FLX_DNS_TYPE_PTR, n, strlen(n)+1);
+        flx_server_add(s, id, interface, protocol, r, FLX_DNS_TYPE_PTR, n, strlen(n)+1);
         g_free(r);
     
         r = flx_reverse_lookup_name_ipv6_int(&a->ipv6);
         g_assert(r);
-        flx_server_add(s, id, interface, r, FLX_DNS_TYPE_PTR, n, strlen(n)+1);
+        flx_server_add(s, id, interface, protocol, r, FLX_DNS_TYPE_PTR, n, strlen(n)+1);
         g_free(r);
     }
     
     g_free(n);
 }
+
+flxQueryJob* flx_query_job_new(void) {
+    flxQueryJob *job = g_new(flxQueryJob);
+    job->query.name = NULL;
+    job->query.class = 0;
+    job->query.type = 0;
+    job->ref = 1;
+    return job;
+}
+
+flxQueryJob* flx_query_job_ref(flxQueryJob *job) {
+    g_assert(job);
+    g_assert(job->ref >= 1);
+    job->ref++;
+    return job;
+}
+
+void flx_query_job_unref(flxQueryJob *job) {
+    g_assert(job);
+    g_assert(job->ref >= 1);
+    if (!(--job->ref))
+        g_free(job);
+}
+
+static void post_query_job(flxServer *s, gint interface, guchar protocol, flxQueryJob *job) {
+    flxQueryJobInstance *i;
+    g_assert(s);
+    g_assert(job);
+
+    if (interface <= 0) {
+        flxInterface *i;
+        
+        for (i = s->monitor->interfaces; i; i = i->next)
+            post_query_job(s, i->index, protocol, job);
+    } else if (protocol == AF_UNSPEC) {
+        post_query_job(s, index, AF_INET, job);
+        post_query_job(s, index, AF_INET6, job);
+    } else {
+
+        if (query_job_exists(s, interface, protocol, &job->query))
+            return;
+        
+        i = g_new(flxQueryJobInstance, 1);
+        i->job = flx_query_job_ref(job);
+        i->interface = interface;
+        i->protocol = protocol;
+        if (i->prev = s->last_query_job)
+            i->prev->next = i;
+        else
+            s->first_query_job = i;
+        i->next = NULL;
+        s->last_query_job = i;
+    }
+}
+
+void flx_server_post_query_job(flxServer *s, gint interface, guchar protocol, const flxQuery *q) {
+    flxQueryJob *job;
+    g_assert(s);
+    g_assert(q);
+
+    job = flx_query_job_new();
+    job->query.name = g_strdup(q->name);
+    job->query.class = q->class;
+    job->query.type = q->type;
+    post_query_job(s, interface, protocol, job);
+}
+
+void flx_server_drop_query_job(flxServer *s, gint interface, guchar protocol, const flxQuery *q) {
+    flxQueryJobInstance *i, *next;
+    g_assert(s);
+    g_assert(interface > 0);
+    g_assert(protocol != AF_UNSPEC);
+    g_assert(q);
+
+    for (i = s->first_query_job; i; i = next) {
+        next = i->next;
+    
+        if (flx_query_equal(i->query, q))
+            flx_server_remove_query_job_instance(s, i);
+    }
+}
+
+gboolean flx_query_equal(const flxQuery *a, const flxQuery *b) {
+    return strcmp(a->name, b->name) == 0 && a->type == b->type && a->class == b->class;
+}
+
+void flx_server_remove_query_job_instance(flxServer *s, flxQueryJobInstance *i) {
+    g_assert(s);
+    g_assert(i);
+
+    if (i->prev)
+        i->prev = i->next;
+    else
+        s->first_query_job = i->next;
+
+    if (i->next)
+        i->next = i->prev;
+    else
+        s->last_query_job = i->prev;
+
+    flx_query_job_unref(i->job);
+    g_free(i);
+}
diff --git a/server.h b/server.h
index 7c96e78..f1a15fc 100644
--- a/server.h
+++ b/server.h
@@ -4,19 +4,48 @@
 #include "flx.h"
 #include "iface.h"
 
+struct _flxEntry;
+typedef struct _flxEntry flxEntry;
 struct _flxEntry {
     flxRecord rr;
     gint id;
     gint interface;
+    guchar protocol;
 
-    int unique;
+    gboolean unique;
 
-    struct _flxEntry *next, *prev;
-    struct _flxEntry *next_by_name, *prev_by_name;
-    struct _flxEntry *next_by_id, *prev_by_id;
+    flxEntry *next, *prev;
+    flxEntry *next_by_name, *prev_by_name;
+    flxEntry *next_by_id, *prev_by_id;
 };
 
-typedef struct _flxEntry flxEntry;
+typedef struct _flxQueryJob {
+    gint ref;
+    flxQuery query;
+} flxQueryJob;
+
+struct _flxQueryJobInstance;
+typedef struct _flxQueryJobInstance flxQueryJobInstance;
+struct _flxQueryJobInstance {
+    flxQueryJob *job;
+    gint interface;
+    guchar protocol;
+    flxQueryJobInstance *next, *prev;
+};
+
+typedef struct _flxResponseJob {
+    gint ref;
+    flxRecord response;
+} flxResponseJob;
+
+struct _flxResponseJobInstance;
+typedef struct _flxResponseJobInstance flxResponseJobInstance;
+struct _flxResponseJobInstance {
+    flxResponseJob *job;
+    gint interface;
+    guchar protocol;
+    flxResponseJob *next, *prev;
+};
 
 struct _flxServer {
     GMainContext *context;
@@ -28,6 +57,21 @@ struct _flxServer {
     GHashTable *rrset_by_name;
 
     flxEntry *entries;
+
+    flxResponseJobInstance *first_response_job, *last_response_job;
+    flxQueryJobInstance *first_query_job, *last_query_job;
 };
 
+flxQueryJob* flx_query_job_new(void);
+flxQueryJob* flx_query_job_ref(flxQueryJob *job);
+void flx_query_job_unref(flxQueryJob *job);
+
+void flx_server_post_query_job(flxServer *s, gint interface, guchar protocol, const flxQuery *q);
+void flx_server_drop_query_job(flxServer *s, gint interface, guchar protocol, const flxQuery *q);
+
+void flx_server_remove_query_job_instance(flxServer *s, flxQueryJobInstance *i);
+
+gboolean flx_query_equal(const flxQuery *a, const flxQuery *b);
+
+
 #endif