common/tr_comm.c

   1 /*
   2  * Copyright (c) 2012-2018, JANET(UK)
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  *
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * 3. Neither the name of JANET(UK) nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  24  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
  25  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  26  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  27  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  29  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  30  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  31  * OF THE POSSIBILITY OF SUCH DAMAGE.
  32  *
  33  */
  34
  35 #include <stdio.h>
  36 #include <jansson.h>
  37 #include <talloc.h>
  38 #include <sys/time.h>
  39
  40 #include <tr_rp.h>
  41 #include <tr_idp.h>
  42 #include <tr_name_internal.h>
  43 #include <trp_internal.h>
  44 #include <tr_comm.h>
  45 #include <tr_debug.h>
  46 #include <tr_util.h>
  47
  48 static int tr_comm_destructor(void *obj)
  49 {
  50   TR_COMM *comm=talloc_get_type_abort(obj, TR_COMM);
  51   if (comm->id!=NULL)
  52     tr_free_name(comm->id);
  53   if (comm->owner_realm!=NULL)
  54     tr_free_name(comm->owner_realm);
  55   if (comm->owner_contact!=NULL)
  56     tr_free_name(comm->owner_contact);
  57   return 0;
  58 }
  59
  60 TR_COMM *tr_comm_new(TALLOC_CTX *mem_ctx)
  61 {
  62   TR_COMM *comm=talloc(mem_ctx, TR_COMM);
  63   if (comm!=NULL) {
  64     comm->next=NULL;
  65     comm->id=NULL;
  66     comm->type=TR_COMM_UNKNOWN;
  67     comm->apcs=NULL;
  68     comm->owner_realm=NULL;
  69     comm->owner_contact=NULL;
  70     comm->expiration_interval=0;
  71     comm->refcount=0;
  72     talloc_set_destructor((void *)comm, tr_comm_destructor);
  73   }
  74   return comm;
  75 }
  76
  77 void tr_comm_free(TR_COMM *comm)
  78 {
  79   talloc_free(comm);
  80 }
  81
  82 void tr_comm_set_id(TR_COMM *comm, TR_NAME *id)
  83 {
  84   if (comm->id != NULL)
  85     tr_free_name(comm->id);
  86   comm->id=id;
  87 }
  88
  89 void tr_comm_incref(TR_COMM *comm)
  90 {
  91   comm->refcount++;
  92 }
  93
  94 void tr_comm_decref(TR_COMM *comm)
  95 {
  96   if (comm->refcount>0)
  97     comm->refcount--;
  98 }
  99
 100 void tr_comm_set_apcs(TR_COMM *comm, TR_APC *apc)
 101 {
 102   if (comm->apcs!=NULL)
 103     tr_apc_free(comm->apcs);
 104   comm->apcs=apc;
 105   talloc_steal(comm, apc);
 106 }
 107
 108 TR_APC *tr_comm_get_apcs(TR_COMM *comm)
 109 {
 110   return comm->apcs;
 111 }
 112
 113 TR_NAME *tr_comm_get_id(TR_COMM *comm)
 114 {
 115   return comm->id;
 116 }
 117
 118 TR_NAME *tr_comm_dup_id(TR_COMM *comm)
 119 {
 120   return tr_dup_name(comm->id);
 121 }
 122
 123 void tr_comm_set_type(TR_COMM *comm, TR_COMM_TYPE type)
 124 {
 125   comm->type=type;
 126 }
 127
 128 TR_COMM_TYPE tr_comm_get_type(TR_COMM *comm)
 129 {
 130   return comm->type;
 131 }
 132
 133 void tr_comm_set_owner_realm(TR_COMM *comm, TR_NAME *realm)
 134 {
 135   if (comm->owner_realm!=NULL)
 136     tr_free_name(comm->owner_realm);
 137   comm->owner_realm=realm;
 138 }
 139
 140 TR_NAME *tr_comm_get_owner_realm(TR_COMM *comm)
 141 {
 142   return comm->owner_realm;
 143 }
 144
 145 TR_NAME *tr_comm_dup_owner_realm(TR_COMM *comm)
 146 {
 147   return tr_dup_name(comm->owner_realm);
 148 }
 149
 150 void tr_comm_set_owner_contact(TR_COMM *comm, TR_NAME *contact)
 151 {
 152   if (comm->owner_contact != NULL)
 153     tr_free_name(comm->owner_contact);
 154   comm->owner_contact=contact;
 155 }
 156
 157 TR_NAME *tr_comm_get_owner_contact(TR_COMM *comm)
 158 {
 159   return comm->owner_contact;
 160 }
 161
 162 TR_NAME *tr_comm_dup_owner_contact(TR_COMM *comm)
 163 {
 164   return tr_dup_name(comm->owner_contact);
 165 }
 166
 167 unsigned int tr_comm_get_refcount(TR_COMM *comm)
 168 {
 169   return comm->refcount;
 170 }
 171
 172 /* 0 if equivalent, nonzero if different, only considers
 173  * nhops last hops (nhops==0 means consider all, nhops==1
 174  * only considers last hop) */
 175 static int tr_comm_memb_provenance_cmp(TR_COMM_MEMB *m1, TR_COMM_MEMB *m2, int nhops)
 176 {
 177   size_t ii;
 178
 179   if ((m1->provenance==NULL) || (m2->provenance==NULL))
 180     return m1->provenance!=m2->provenance; /* return 0 if both null, 1 if only one null */
 181
 182   if (json_array_size(m1->provenance)!=json_array_size(m2->provenance))
 183     return 1;
 184
 185   if (nhops==0)
 186     nhops=json_array_size(m1->provenance); /* same as size(m2->provenance) */
 187
 188   for (ii=0; ii<json_array_size(m1->provenance); ii++) {
 189     if (0==strcmp(json_string_value(json_array_get(m1->provenance, ii)),
 190                   json_string_value(json_array_get(m2->provenance, ii)))) {
 191       return 0;
 192     }
 193   }
 194   return 1;
 195 }
 196
 197 /* Accepts an update that either came from the same peer as the previous
 198  * origin, has a shorter provenance list, or can replace an expired
 199  * membership. Otherwise keeps the existing one.
 200  * On replacement, frees the old member and moves new member to ctab's
 201  * context. Caller should not free newmemb except by freeing its original
 202  * context. */
 203 static void tr_comm_add_if_shorter(TR_COMM_TABLE *ctab, TR_COMM_MEMB *existing, TR_COMM_MEMB *newmemb)
 204 {
 205   int accept=0;
 206
 207   if (existing==NULL) {
 208     /* not in the table */
 209     tr_comm_table_add_memb(ctab, newmemb);
 210   } else {
 211     if (0==tr_comm_memb_provenance_cmp(existing, newmemb, 1))
 212       accept=1; /* always accept a replacement from the same peer */
 213     else if (tr_comm_memb_provenance_len(newmemb) < tr_comm_memb_provenance_len(existing))
 214       accept=1; /* accept a shorter provenance */
 215     else if (existing->times_expired>0)
 216       accept=1;
 217     else
 218       accept=0;
 219
 220     if (accept) {
 221       tr_comm_table_remove_memb(ctab, existing);
 222       tr_comm_memb_free(existing);
 223       tr_comm_table_add_memb(ctab, newmemb);
 224     }
 225   }
 226 }
 227
 228 /* does not take responsibility for freeing IDP realm */
 229 void tr_comm_add_idp_realm(TR_COMM_TABLE *ctab,
 230                            TR_COMM *comm,
 231                            TR_IDP_REALM *realm,
 232                            unsigned int interval,
 233                            json_t *provenance,
 234                            struct timespec *expiry)
 235 {
 236   TALLOC_CTX *tmp_ctx=talloc_new(NULL);
 237   TR_COMM_MEMB *newmemb=tr_comm_memb_new(tmp_ctx);
 238   TR_COMM_MEMB *existing=NULL;
 239
 240   if (newmemb==NULL) {
 241     tr_err("tr_comm_add_idp_realm: unable to allocate new membership record.");
 242     talloc_free(tmp_ctx);
 243     return;
 244   }
 245
 246   tr_comm_memb_set_idp_realm(newmemb, realm);
 247   tr_comm_memb_set_comm(newmemb, comm);
 248   tr_comm_memb_set_interval(newmemb, interval);
 249   tr_comm_memb_set_provenance(newmemb, provenance);
 250   tr_comm_memb_set_expiry(newmemb, expiry);
 251
 252   existing=tr_comm_table_find_idp_memb_origin(ctab,
 253                                               tr_idp_realm_get_id(realm),
 254                                               tr_comm_get_id(comm),
 255                                               tr_comm_memb_get_origin(newmemb));
 256   tr_comm_add_if_shorter(ctab, existing, newmemb); /* takes newmemb out of tmp_ctx if needed */
 257
 258   talloc_free(tmp_ctx);
 259 }
 260
 261 /* does not take responsibility for freeing RP realm */
 262 void tr_comm_add_rp_realm(TR_COMM_TABLE *ctab,
 263                           TR_COMM *comm,
 264                           TR_RP_REALM *realm,
 265                           unsigned int interval,
 266                           json_t *provenance,
 267                           struct timespec *expiry)
 268 {
 269   TALLOC_CTX *tmp_ctx=talloc_new(NULL);
 270   TR_COMM_MEMB *newmemb=tr_comm_memb_new(tmp_ctx);
 271   TR_COMM_MEMB *existing=NULL;
 272
 273   if (newmemb==NULL) {
 274     tr_err("tr_comm_add_idp_realm: unable to allocate new membership record.");
 275     talloc_free(tmp_ctx);
 276     return;
 277   }
 278
 279   tr_comm_memb_set_rp_realm(newmemb, realm);
 280   tr_comm_memb_set_comm(newmemb, comm);
 281   tr_comm_memb_set_interval(newmemb, interval);
 282   tr_comm_memb_set_provenance(newmemb, provenance);
 283   tr_comm_memb_set_expiry(newmemb, expiry);
 284
 285   existing=tr_comm_table_find_rp_memb_origin(ctab,
 286                                              tr_rp_realm_get_id(realm),
 287                                              tr_comm_get_id(comm),
 288                                              tr_comm_memb_get_origin(newmemb));
 289   tr_comm_add_if_shorter(ctab, existing, newmemb); /* takes newmemb out of tmp_ctx if needed */
 290   talloc_free(tmp_ctx);
 291 }
 292
 293 static TR_COMM *tr_comm_tail(TR_COMM *comm)
 294 {
 295   if (comm==NULL)
 296     return comm;
 297
 298   while (comm->next!=NULL)
 299     comm=comm->next;
 300   return comm;
 301 }
 302
 303 /* All list members are in the talloc context of the head.
 304  * This will require careful thought if entries are ever removed
 305  * Call like comms=tr_comm_add_func(comms, new_comm);
 306  * or just use the tr_comm_add(comms, new) macro. */
 307 #define tr_comm_add(comms, new) ((comms)=tr_comm_add_func((comms), (new)))
 308 static TR_COMM *tr_comm_add_func(TR_COMM *comms, TR_COMM *new)
 309 {
 310   if (comms==NULL)
 311     comms=new;
 312   else {
 313     tr_comm_tail(comms)->next=new;
 314     while(new!=NULL) {
 315       talloc_steal(comms, new);
 316       new=new->next;
 317     }
 318   }
 319   return comms;
 320 }
 321
 322 /* Guarantees comm is not in the list, not an error if it was't there.
 323  * Does not free the removed element, nor change its talloc context. */
 324 #define tr_comm_remove(comms, c) ((comms)=tr_comm_remove_func((comms), (c)))
 325 static TR_COMM *tr_comm_remove_func(TR_COMM *comms, TR_COMM *remove)
 326 {
 327   TALLOC_CTX *list_ctx=talloc_parent(comms); /* in case we need to remove the head */
 328   TR_COMM *this=NULL;
 329
 330   if (comms==NULL)
 331     return NULL;
 332
 333   if (comms==remove) {
 334     /* if we're removing the head, put the next element (if present) into the context
 335      * the list head was in. */
 336     comms=comms->next;
 337     if (comms!=NULL) {
 338       talloc_steal(list_ctx, comms);
 339       /* now put all the other elements in the context of the list head */
 340       for (this=comms->next; this!=NULL; this=this->next)
 341         talloc_steal(comms, this);
 342     }
 343   } else {
 344     /* not removing the head; no need to play with contexts */
 345     for (this=comms; this->next!=NULL; this=this->next) {
 346       if (this->next==remove) {
 347         this->next=remove->next;
 348         break;
 349       }
 350     }
 351   }
 352   return comms;
 353 }
 354
 355 /* remove any with zero refcount
 356  * Call via macro. */
 357 #define tr_comm_sweep(head) ((head)=tr_comm_sweep_func((head)))
 358 static TR_COMM *tr_comm_sweep_func(TR_COMM *head)
 359 {
 360   TR_COMM *comm=NULL;
 361   TR_COMM *old_next=NULL;
 362
 363   if (head==NULL)
 364     return NULL;
 365
 366   while ((head!=NULL) && (head->refcount==0)) {
 367     comm=head; /* keep a pointer so we can remove it */
 368     tr_comm_remove(head, comm); /* use this to get talloc contexts right */
 369     tr_comm_free(comm);
 370   }
 371
 372   if (head==NULL)
 373     return NULL;
 374
 375   /* will not remove the head here, that has already been done */
 376   for (comm=head; (comm!=NULL) && (comm->next!=NULL); comm=comm->next) {
 377     if (comm->next->refcount==0) {
 378       old_next=comm->next;
 379       tr_comm_remove(head, comm->next); /* changes comm->next, may make it null */
 380       tr_comm_free(old_next);
 381     }
 382   }
 383
 384   return head;
 385 }
 386
 387 TR_IDP_REALM *tr_comm_find_idp(TR_COMM_TABLE *ctab, TR_COMM *comm, TR_NAME *idp_realm)
 388 {
 389   TALLOC_CTX *tmp_ctx=talloc_new(NULL);
 390   TR_COMM_ITER *iter=NULL;
 391   TR_IDP_REALM *this_idp=NULL;
 392
 393   if ((NULL==ctab) || (NULL==comm) || (NULL==idp_realm)) {
 394     talloc_free(tmp_ctx);
 395     return NULL;
 396   }
 397
 398   iter=tr_comm_iter_new(tmp_ctx);
 399   for (this_idp=tr_idp_realm_iter_first(iter, ctab, tr_comm_get_id(comm));
 400        this_idp!=NULL;
 401        this_idp=tr_idp_realm_iter_next(iter)) {
 402     if (0==tr_name_cmp(idp_realm, tr_idp_realm_get_id(this_idp))) {
 403       tr_debug("tr_comm_find_idp: Found IdP %s in community %s.", idp_realm->buf, tr_comm_get_id(comm)->buf);
 404       talloc_free(tmp_ctx);
 405       return this_idp;
 406     }
 407   }
 408   tr_debug("tr_comm_find_idp: Unable to find IdP %s in community %s.", idp_realm->buf, tr_comm_get_id(comm)->buf);
 409   talloc_free(tmp_ctx);
 410   return NULL;
 411 }
 412
 413 TR_RP_REALM *tr_comm_find_rp (TR_COMM_TABLE *ctab, TR_COMM *comm, TR_NAME *rp_realm)
 414 {
 415   TALLOC_CTX *tmp_ctx=talloc_new(NULL);
 416   TR_COMM_ITER *iter=NULL;
 417   TR_RP_REALM *this_rp=NULL;
 418
 419   if ((NULL==ctab) || (NULL==comm) || (NULL==rp_realm)) {
 420     talloc_free(tmp_ctx);
 421     return NULL;
 422   }
 423
 424   iter=tr_comm_iter_new(tmp_ctx);
 425   for (this_rp=tr_rp_realm_iter_first(iter, ctab, tr_comm_get_id(comm));
 426        this_rp!=NULL;
 427        this_rp=tr_rp_realm_iter_next(iter)) {
 428     if (0==tr_name_cmp(rp_realm, tr_rp_realm_get_id(this_rp))) {
 429       tr_debug("tr_comm_find_rp: Found RP %s in community %s.", rp_realm->buf, tr_comm_get_id(comm)->buf);
 430       talloc_free(tmp_ctx);
 431       return this_rp;
 432     }
 433   }
 434   tr_debug("tr_comm_find_rp: Unable to find RP %s in community %s.", rp_realm->buf, tr_comm_get_id(comm)->buf);
 435   talloc_free(tmp_ctx);
 436   return NULL;
 437 }
 438
 439 static TR_COMM *tr_comm_lookup(TR_COMM *comms, TR_NAME *comm_name)
 440 {
 441   TR_COMM *cfg_comm = NULL;
 442
 443   for (cfg_comm = comms; NULL != cfg_comm; cfg_comm = cfg_comm->next) {
 444     if (0==tr_name_cmp(cfg_comm->id, comm_name))
 445       return cfg_comm;
 446   }
 447   return NULL;
 448 }
 449
 450 TR_COMM_ITER *tr_comm_iter_new(TALLOC_CTX *mem_ctx)
 451 {
 452   TR_COMM_ITER *iter=talloc(mem_ctx, TR_COMM_ITER);
 453   if (iter!=NULL) {
 454     iter->cur_comm=NULL;
 455     iter->cur_memb=NULL;
 456     iter->cur_orig_head=NULL;
 457     iter->match=NULL;
 458     iter->realm=NULL;
 459   }
 460   return iter;
 461 }
 462
 463 void tr_comm_iter_free(TR_COMM_ITER *iter)
 464 {
 465   talloc_free(iter);
 466 }
 467
 468
 469 TR_COMM *tr_comm_iter_first(TR_COMM_ITER *iter, TR_COMM_TABLE *ctab, TR_NAME *realm)
 470 {
 471   iter->match=realm;
 472
 473   /* find memberships for this realm */
 474   for (iter->cur_memb=ctab->memberships;
 475        iter->cur_memb!=NULL;
 476        iter->cur_memb=iter->cur_memb->next) {
 477     if (0==tr_name_cmp(iter->match, tr_comm_memb_get_realm_id(iter->cur_memb)))
 478       return tr_comm_memb_get_comm(iter->cur_memb);
 479   }
 480   return NULL;
 481 }
 482
 483 TR_COMM *tr_comm_iter_next(TR_COMM_ITER *iter)
 484 {
 485   for (iter->cur_memb=iter->cur_memb->next;
 486        iter->cur_memb!=NULL;
 487        iter->cur_memb=iter->cur_memb->next) {
 488     if (0==tr_name_cmp(iter->match, tr_comm_memb_get_realm_id(iter->cur_memb)))
 489       return tr_comm_memb_get_comm(iter->cur_memb);
 490   }
 491   return NULL;
 492 }
 493
 494 /* iterate only over RPs */
 495 TR_COMM *tr_comm_iter_first_rp(TR_COMM_ITER *iter, TR_COMM_TABLE *ctab, TR_NAME *realm)
 496 {
 497   iter->match=realm;
 498
 499   /* find memberships for this realm */
 500   for (iter->cur_memb=ctab->memberships;
 501        iter->cur_memb!=NULL;
 502        iter->cur_memb=iter->cur_memb->next) {
 503     if ((tr_comm_memb_get_rp_realm(iter->cur_memb)!=NULL) &&
 504         (0==tr_name_cmp(iter->match, tr_comm_memb_get_realm_id(iter->cur_memb))))
 505       return tr_comm_memb_get_comm(iter->cur_memb);
 506   }
 507   return NULL;
 508 }
 509
 510 TR_COMM *tr_comm_iter_next_rp(TR_COMM_ITER *iter)
 511 {
 512   for (iter->cur_memb=iter->cur_memb->next;
 513        iter->cur_memb!=NULL;
 514        iter->cur_memb=iter->cur_memb->next) {
 515     if ((tr_comm_memb_get_rp_realm(iter->cur_memb)!=NULL) &&
 516         (0==tr_name_cmp(iter->match, tr_comm_memb_get_realm_id(iter->cur_memb))))
 517       return tr_comm_memb_get_comm(iter->cur_memb);
 518   }
 519   return NULL;
 520 }
 521
 522 /* iterate only over IDPs */
 523 TR_COMM *tr_comm_iter_first_idp(TR_COMM_ITER *iter, TR_COMM_TABLE *ctab, TR_NAME *realm)
 524 {
 525   iter->match=realm;
 526
 527   /* find memberships for this realm */
 528   for (iter->cur_memb=ctab->memberships;
 529        iter->cur_memb!=NULL;
 530        iter->cur_memb=iter->cur_memb->next) {
 531     if ((tr_comm_memb_get_idp_realm(iter->cur_memb)!=NULL) &&
 532         (0==tr_name_cmp(iter->match, tr_comm_memb_get_realm_id(iter->cur_memb))))
 533       return tr_comm_memb_get_comm(iter->cur_memb);
 534   }
 535   return NULL;
 536 }
 537
 538 TR_COMM *tr_comm_iter_next_idp(TR_COMM_ITER *iter)
 539 {
 540   for (iter->cur_memb=iter->cur_memb->next;
 541        iter->cur_memb!=NULL;
 542        iter->cur_memb=iter->cur_memb->next) {
 543     if ((tr_comm_memb_get_idp_realm(iter->cur_memb)!=NULL) &&
 544         (0==tr_name_cmp(iter->match, tr_comm_memb_get_realm_id(iter->cur_memb))))
 545       return tr_comm_memb_get_comm(iter->cur_memb);
 546   }
 547   return NULL;
 548 }
 549
 550 static TR_REALM *tr_realm_new(TALLOC_CTX *mem_ctx)
 551 {
 552   TR_REALM *realm=talloc(mem_ctx, TR_REALM);
 553   if (realm!=NULL) {
 554     realm->role=TR_ROLE_UNKNOWN;
 555     realm->rp=NULL;
 556     realm->idp=NULL;
 557   }
 558   return realm;
 559 }
 560
 561 static void tr_realm_free(TR_REALM *realm)
 562 {
 563   talloc_free(realm);
 564 }
 565
 566 static void tr_realm_set_rp(TR_REALM *realm, TR_RP_REALM *rp)
 567 {
 568   if (realm->idp!=NULL)
 569     realm->idp=NULL;
 570   realm->role=TR_ROLE_RP;
 571   realm->rp=rp;
 572 }
 573
 574 static void tr_realm_set_idp(TR_REALM *realm, TR_IDP_REALM *idp)
 575 {
 576   if (realm->rp!=NULL)
 577     realm->rp=NULL;
 578   realm->role=TR_ROLE_IDP;
 579   realm->idp=idp;
 580 }
 581
 582 TR_NAME *tr_realm_get_id(TR_REALM *realm)
 583 {
 584   switch (realm->role) {
 585   case TR_ROLE_RP:
 586     return tr_rp_realm_get_id(realm->rp);
 587   case TR_ROLE_IDP:
 588     return tr_idp_realm_get_id(realm->idp);
 589   default:
 590     break;
 591   }
 592   return NULL;
 593 }
 594
 595 TR_NAME *tr_realm_dup_id(TR_REALM *realm)
 596 {
 597   return tr_dup_name(tr_realm_get_id(realm));
 598 }
 599
 600 /* Iterate over either sort of realm. Do not free the TR_REALM returned. It becomes
 601  * undefined/invalid after the next operation affecting the iterator. */
 602 TR_REALM *tr_realm_iter_first(TR_COMM_ITER *iter, TR_COMM_TABLE *ctab, TR_NAME *comm)
 603 {
 604   iter->match=comm;
 605   if (iter->realm==NULL)
 606     iter->realm=tr_realm_new(iter);
 607   if (iter->realm==NULL)
 608     return NULL;
 609
 610   /* find memberships for this comm */
 611   for (iter->cur_memb=ctab->memberships;
 612        iter->cur_memb!=NULL;
 613        iter->cur_memb=iter->cur_memb->next) {
 614     if (0==tr_name_cmp(iter->match,
 615                        tr_comm_get_id(tr_comm_memb_get_comm(iter->cur_memb)))) {
 616       /* found a match, determine whether it's an rp realm or an idp realm */
 617       if (tr_comm_memb_get_rp_realm(iter->cur_memb)!=NULL)
 618         tr_realm_set_rp(iter->realm, tr_comm_memb_get_rp_realm(iter->cur_memb));
 619       else if (tr_comm_memb_get_idp_realm(iter->cur_memb)!=NULL)
 620         tr_realm_set_idp(iter->realm, tr_comm_memb_get_idp_realm(iter->cur_memb));
 621       else {
 622         if (iter->realm!=NULL)
 623           tr_realm_free(iter->realm);
 624         iter->realm=NULL;
 625       }
 626       return iter->realm;
 627     }
 628   }
 629   if (iter->realm!=NULL)
 630     tr_realm_free(iter->realm);
 631   iter->realm=NULL;
 632   return NULL;
 633 }
 634
 635 TR_REALM *tr_realm_iter_next(TR_COMM_ITER *iter)
 636 {
 637   if (iter->realm==NULL)
 638     return NULL;
 639
 640   /* find memberships for this comm */
 641   for (iter->cur_memb=iter->cur_memb->next;
 642        iter->cur_memb!=NULL;
 643        iter->cur_memb=iter->cur_memb->next) {
 644     if (0==tr_name_cmp(iter->match,
 645                        tr_comm_get_id(tr_comm_memb_get_comm(iter->cur_memb)))) {
 646       /* found a match, determine whether it's an rp realm or an idp realm */
 647       if (tr_comm_memb_get_rp_realm(iter->cur_memb)!=NULL)
 648         tr_realm_set_rp(iter->realm, tr_comm_memb_get_rp_realm(iter->cur_memb));
 649       else if (tr_comm_memb_get_idp_realm(iter->cur_memb)!=NULL)
 650         tr_realm_set_idp(iter->realm, tr_comm_memb_get_idp_realm(iter->cur_memb));
 651       else {
 652         if (iter->realm!=NULL)
 653           tr_realm_free(iter->realm);
 654         iter->realm=NULL;
 655       }
 656       return iter->realm;
 657     }
 658   }
 659   if (iter->realm!=NULL)
 660     tr_realm_free(iter->realm);
 661   iter->realm=NULL;
 662   return NULL;
 663 }
 664
 665 TR_RP_REALM *tr_rp_realm_iter_first(TR_COMM_ITER *iter, TR_COMM_TABLE *ctab, TR_NAME *comm)
 666 {
 667   iter->match=comm;
 668
 669   /* find memberships for this comm */
 670   for (iter->cur_memb=ctab->memberships;
 671        iter->cur_memb!=NULL;
 672        iter->cur_memb=iter->cur_memb->next) {
 673     if ((tr_comm_memb_get_rp_realm(iter->cur_memb)!=NULL) &&
 674         (0==tr_name_cmp(iter->match, tr_comm_get_id(tr_comm_memb_get_comm(iter->cur_memb)))))
 675       return tr_comm_memb_get_rp_realm(iter->cur_memb);
 676   }
 677   return NULL;
 678 }
 679
 680 TR_RP_REALM *tr_rp_realm_iter_next(TR_COMM_ITER *iter)
 681 {
 682   for (iter->cur_memb=iter->cur_memb->next;
 683        iter->cur_memb!=NULL;
 684        iter->cur_memb=iter->cur_memb->next) {
 685     if ((tr_comm_memb_get_rp_realm(iter->cur_memb)!=NULL) &&
 686         (0==tr_name_cmp(iter->match, tr_comm_get_id(tr_comm_memb_get_comm(iter->cur_memb)))))
 687       return tr_comm_memb_get_rp_realm(iter->cur_memb);
 688   }
 689   return NULL;
 690 }
 691
 692 TR_IDP_REALM *tr_idp_realm_iter_first(TR_COMM_ITER *iter, TR_COMM_TABLE *ctab, TR_NAME *comm)
 693 {
 694   iter->match=comm;
 695
 696   /* find memberships for this comm */
 697   for (iter->cur_memb=ctab->memberships;
 698        iter->cur_memb!=NULL;
 699        iter->cur_memb=iter->cur_memb->next) {
 700     if ((tr_comm_memb_get_idp_realm(iter->cur_memb)!=NULL) &&
 701         (0==tr_name_cmp(iter->match, tr_comm_get_id(tr_comm_memb_get_comm(iter->cur_memb)))))
 702       return tr_comm_memb_get_idp_realm(iter->cur_memb);
 703   }
 704   return NULL;
 705 }
 706
 707 TR_IDP_REALM *tr_idp_realm_iter_next(TR_COMM_ITER *iter)
 708 {
 709   for (iter->cur_memb=iter->cur_memb->next;
 710        iter->cur_memb!=NULL;
 711        iter->cur_memb=iter->cur_memb->next) {
 712     if ((tr_comm_memb_get_idp_realm(iter->cur_memb)!=NULL) &&
 713         (0==tr_name_cmp(iter->match, tr_comm_get_id(tr_comm_memb_get_comm(iter->cur_memb)))))
 714       return tr_comm_memb_get_idp_realm(iter->cur_memb);
 715   }
 716   return NULL;
 717 }
 718
 719 /* iterators for all communities in a table */
 720 TR_COMM *tr_comm_table_iter_first(TR_COMM_ITER *iter, TR_COMM_TABLE *ctab)
 721 {
 722   iter->cur_comm=ctab->comms;
 723   return iter->cur_comm;
 724 }
 725
 726 TR_COMM *tr_comm_table_iter_next(TR_COMM_ITER *iter)
 727 {
 728   return iter->cur_comm=iter->cur_comm->next;
 729 }
 730
 731 const char *tr_comm_type_to_str(TR_COMM_TYPE type)
 732 {
 733   const char *s=NULL;
 734   switch(type) {
 735   case TR_COMM_UNKNOWN:
 736     s="unknown";
 737     break;
 738   case TR_COMM_APC:
 739     s="apc";
 740     break;
 741   case TR_COMM_COI:
 742     s="coi";
 743     break;
 744   default:
 745     s="invalid";
 746   }
 747   return s;
 748 }
 749
 750 /* iterate along the origin list for this member */
 751 TR_COMM_MEMB *tr_comm_memb_iter_first(TR_COMM_ITER *iter, TR_COMM_MEMB *memb)
 752 {
 753   iter->cur_memb=memb;
 754   return iter->cur_memb;
 755 }
 756
 757 TR_COMM_MEMB *tr_comm_memb_iter_next(TR_COMM_ITER *iter)
 758 {
 759   if (iter->cur_memb!=NULL)
 760     iter->cur_memb=iter->cur_memb->origin_next;
 761   return iter->cur_memb;
 762 }
 763
 764
 765 /* iterate over all memberships in the table
 766  *
 767  * The table is structured as a vertical list of memberships, each for a
 768  * different community/realm. Each element in this list has a horizontal "origin list,"
 769  * each for the same community/realm but with a different origin for the membership.
 770  * Only the first element in the origin list has a vertical link ("next" pointer).
 771  * Any element may have a horizontal link ("origin_next" pointer).
 772  *
 773  *  (A) - (B) - (C) - X
 774  *   |
 775  *  (D) - (E) - X
 776  *   |
 777  *  (F) - X
 778  *   |
 779  *  (G) - (H) - X
 780  *   |
 781  *   X
 782  *
 783  *  A, B, and C are all community/realm pair membership 1, with different origins
 784  *  D, E are a second community/realm pair, with different origins
 785  *  F is a third...
 786  *  G, H are a fourth pair, with different origins
 787  *
 788  * This iterator will return every element in the grid.
 789  *
 790  * Algorithm:
 791  *   The iterator struct stores the current member (cur_memb) and the origin head (cur_orig_head).
 792  *   The latter is a pointer to the head of the current origin list (i.e., first element in a row).
 793  *   The former can point to any element in the list. Both start at the root of the list (A in the
 794  *   diagram above).
 795  *
 796  *   After each call to _first() or _next(), cur_memb points to the element just returned.
 797  *
 798  *   0. _first() just returns the first element. The rest of the steps are in _next()
 799  *
 800  *   1. If cur_memb has an origin_next element, walk the origin list. Move cur_memb to
 801  *      the origin_list element (next one in this row) and return it.
 802  *   2. If cur_memb does not have an origin_next element, we've finished the current origin
 803  *      list. Move cur_memb to cur_orig_head's next element (the start of the next column),
 804  *      move cur_orig_head to that same place, and return it.
 805  *   3. If neither cur_memb has an origin_next element nor cur_orig_head has a next element,
 806  *      then we have already reached the end of the list and there's nothing more to do.
 807  *      Return NULL.
 808  */
 809 TR_COMM_MEMB *tr_comm_memb_iter_all_first(TR_COMM_ITER *iter, TR_COMM_TABLE *ctab)
 810 {
 811   /* step 0: return the root of the list */
 812   iter->cur_memb=ctab->memberships;
 813   iter->cur_orig_head=ctab->memberships;
 814   return iter->cur_memb;
 815 }
 816
 817 TR_COMM_MEMB *tr_comm_memb_iter_all_next(TR_COMM_ITER *iter)
 818 {
 819   if (iter->cur_memb->origin_next) {
 820     /* step 1: return the next element in the current origin list */
 821     iter->cur_memb = iter->cur_memb->origin_next;
 822   } else if (iter->cur_orig_head->next) {
 823     /* step 2: move to the start of the next row and return the first element */
 824     iter->cur_orig_head = iter->cur_memb = iter->cur_orig_head->next;
 825   } else {
 826     /* step 3: both cur_memb->origin_next and cur_orig_head->next are null */
 827     iter->cur_orig_head = iter->cur_memb = NULL;
 828   }
 829   return iter->cur_memb;
 830 }
 831
 832
 833 TR_COMM_TYPE tr_comm_type_from_str(const char *s)
 834 {
 835   if (strcmp(s, "apc")==0)
 836     return TR_COMM_APC;
 837   if (strcmp(s,"coi")==0)
 838     return TR_COMM_COI;
 839   return TR_COMM_UNKNOWN;
 840 }
 841
 842
 843 static int tr_comm_memb_destructor(void *obj)
 844 {
 845   TR_COMM_MEMB *memb=talloc_get_type_abort(obj, TR_COMM_MEMB);
 846   if (memb->origin!=NULL)
 847     tr_free_name(memb->origin);
 848
 849   if (memb->rp!=NULL)
 850     tr_rp_realm_decref(memb->rp);
 851   if (memb->idp!=NULL)
 852     tr_idp_realm_decref(memb->idp);
 853   if (memb->comm!=NULL)
 854     tr_comm_decref(memb->comm);
 855   if (memb->provenance!=NULL)
 856     json_decref(memb->provenance);
 857   return 0;
 858 }
 859
 860 TR_COMM_MEMB *tr_comm_memb_new(TALLOC_CTX *mem_ctx)
 861 {
 862   TR_COMM_MEMB *memb=talloc(mem_ctx, TR_COMM_MEMB);
 863   if (memb!=NULL) {
 864     memb->next=NULL;
 865     memb->origin_next=NULL;
 866     memb->idp=NULL;
 867     memb->rp=NULL;
 868     memb->comm=NULL;
 869     memb->origin=NULL;
 870     memb->provenance=NULL;
 871     memb->interval=0;
 872     memb->triggered=0;
 873     memb->times_expired=0;
 874     memb->expiry=talloc(memb, struct timespec);
 875     if (memb->expiry==NULL) {
 876       talloc_free(memb);
 877       return NULL;
 878     }
 879     *(memb->expiry)=(struct timespec){0,0};
 880     talloc_set_destructor((void *)memb, tr_comm_memb_destructor);
 881   }
 882   return memb;
 883 }
 884
 885 void tr_comm_memb_free(TR_COMM_MEMB *memb)
 886 {
 887   talloc_free(memb);
 888 }
 889
 890 /* Returns 0 if they are the same, nonzero if they differ.
 891  * Ignores expiry, triggered, and times_expired, next pointers */
 892 int tr_comm_memb_cmp(TR_COMM_MEMB *m1, TR_COMM_MEMB *m2)
 893 {
 894   if ((m1->idp==m2->idp) &&
 895       (m1->rp==m2->rp) &&
 896       (m1->comm==m2->comm) &&
 897       (tr_comm_memb_provenance_cmp(m1, m2, 0)==0) &&
 898       (m1->interval==m2->interval))
 899     return 0;
 900   return 1;
 901 }
 902
 903 TR_REALM_ROLE tr_comm_memb_get_role(TR_COMM_MEMB *memb)
 904 {
 905   if (memb->rp!=NULL)
 906     return TR_ROLE_RP;
 907   if (memb->idp!=NULL)
 908     return TR_ROLE_IDP;
 909   return TR_ROLE_UNKNOWN;
 910 }
 911
 912 void tr_comm_memb_set_rp_realm(TR_COMM_MEMB *memb, TR_RP_REALM *realm)
 913 {
 914   if (memb->idp!=NULL) {
 915     tr_idp_realm_decref(memb->idp);
 916     memb->idp=NULL;
 917   }
 918   if (memb->rp!=NULL)
 919     tr_rp_realm_decref(memb->rp);
 920
 921
 922   memb->rp=realm;
 923   tr_rp_realm_incref(realm);
 924 }
 925
 926 TR_RP_REALM *tr_comm_memb_get_rp_realm(TR_COMM_MEMB *memb)
 927 {
 928   return memb->rp;
 929 }
 930
 931 void tr_comm_memb_set_idp_realm(TR_COMM_MEMB *memb, TR_IDP_REALM *realm)
 932 {
 933   if (memb->rp!=NULL) {
 934     tr_rp_realm_decref(memb->rp);
 935     memb->rp=NULL;
 936   }
 937   if (memb->idp!=NULL)
 938     tr_idp_realm_decref(memb->idp);
 939
 940   memb->idp=realm;
 941   tr_idp_realm_incref(realm);
 942 }
 943
 944 TR_IDP_REALM *tr_comm_memb_get_idp_realm(TR_COMM_MEMB *memb)
 945 {
 946   return memb->idp;
 947 }
 948
 949 void tr_comm_memb_set_comm(TR_COMM_MEMB *memb, TR_COMM *comm)
 950 {
 951   if (memb->comm!=NULL)
 952     tr_comm_decref(memb->comm);
 953   memb->comm=comm;
 954   tr_comm_incref(comm);
 955 }
 956
 957 TR_COMM *tr_comm_memb_get_comm(TR_COMM_MEMB *memb)
 958 {
 959   return memb->comm;
 960 }
 961
 962 static void tr_comm_memb_set_origin(TR_COMM_MEMB *memb, TR_NAME *origin)
 963 {
 964   if (memb->origin!=NULL)
 965     tr_free_name(memb->origin);
 966   memb->origin=origin;
 967 }
 968
 969 TR_NAME *tr_comm_memb_get_origin(TR_COMM_MEMB *memb)
 970 {
 971   return memb->origin;
 972 }
 973
 974 TR_NAME *tr_comm_memb_dup_origin(TR_COMM_MEMB *memb)
 975 {
 976   if (memb->origin!=NULL)
 977     return tr_dup_name(memb->origin);
 978   return NULL;
 979 }
 980
 981 json_t *tr_comm_memb_get_provenance(TR_COMM_MEMB *memb)
 982 {
 983   if (memb!=NULL)
 984     return memb->provenance;
 985   return NULL;
 986 }
 987
 988 void tr_comm_memb_set_provenance(TR_COMM_MEMB *memb, json_t *prov)
 989 {
 990   const char *s=NULL;
 991
 992   if (memb->provenance)
 993     json_decref(memb->provenance);
 994
 995   memb->provenance=prov;
 996   if (prov!=NULL) {
 997     json_incref(prov);
 998
 999     /* next line sets origin to NULL if provenance is empty because jansson
1000      * routines return NULL on error */
1001     s=json_string_value(json_array_get(prov, 0));
1002     if (s==NULL)
1003       tr_comm_memb_set_origin(memb, NULL);
1004     else
1005       memb->origin=tr_new_name(s);
1006   } else {
1007     tr_comm_memb_set_origin(memb, NULL);
1008   }
1009 }
1010
1011 void tr_comm_memb_add_to_provenance(TR_COMM_MEMB *memb, TR_NAME *hop)
1012 {
1013   if (memb->provenance==NULL) {
1014     memb->provenance=json_array();
1015     if (memb->provenance==NULL) {
1016       tr_err("tr_comm_memb_add_to_provenance: unable to allocate provenance list.");
1017       return;
1018     }
1019     /* this is the first entry in the provenance, so it is the origin */
1020     tr_comm_memb_set_origin(memb,tr_dup_name(hop));
1021     if (memb->origin==NULL) {
1022       tr_err("tr_comm_memb_add_to_provenance: unable to allocate origin.");
1023       json_decref(memb->provenance);
1024       memb->provenance=NULL;
1025       return;
1026     }
1027   }
1028   if (0!=json_array_append_new(memb->provenance, tr_name_to_json_string(hop)))
1029     tr_err("tr_comm_memb_add_to_provenance: unable to extend provenance list.");
1030 }
1031
1032 size_t tr_comm_memb_provenance_len(TR_COMM_MEMB *memb)
1033 {
1034   if (memb->provenance==NULL)
1035     return 0;
1036   return json_array_size(memb->provenance);
1037 }
1038
1039 void tr_comm_memb_set_interval(TR_COMM_MEMB *memb, unsigned int interval)
1040 {
1041   memb->interval=interval;
1042 }
1043
1044 unsigned int tr_comm_memb_get_interval(TR_COMM_MEMB *memb)
1045 {
1046   return memb->interval;
1047 }
1048
1049 void tr_comm_memb_set_expiry(TR_COMM_MEMB *memb, struct timespec *time)
1050 {
1051   if (time==NULL)
1052     *(memb->expiry)=(struct timespec){0,0};
1053   else {
1054     memb->expiry->tv_sec=time->tv_sec;
1055     memb->expiry->tv_nsec=time->tv_nsec;
1056   }
1057 }
1058
1059 struct timespec *tr_comm_memb_get_expiry(TR_COMM_MEMB *memb)
1060 {
1061   return memb->expiry;
1062 }
1063
1064 /**
1065  * Get the expiration according to the realtime clock
1066  *
1067  * @param memb
1068  * @param result space to store the result
1069  * @return pointer to the result, or null on error
1070  */
1071 struct timespec *tr_comm_memb_get_expiry_realtime(TR_COMM_MEMB *memb, struct timespec *result)
1072 {
1073   return tr_clock_convert(TRP_CLOCK, memb->expiry, CLOCK_REALTIME, result);
1074 }
1075
1076 int tr_comm_memb_is_expired(TR_COMM_MEMB *memb, struct timespec *curtime)
1077 {
1078   tr_debug("tr_comm_memb_is_expired: (cur->tv_sec>memb->expiry->tv_sec)=(%u > %u)=%s",
1079            curtime->tv_sec,
1080            memb->expiry->tv_sec,
1081            (curtime->tv_sec > memb->expiry->tv_sec)?"true":"false");
1082
1083   return ((curtime->tv_sec > memb->expiry->tv_sec)
1084          || ((curtime->tv_sec == memb->expiry->tv_sec)
1085             &&(curtime->tv_nsec >= memb->expiry->tv_nsec)));
1086 }
1087
1088 void tr_comm_memb_set_triggered(TR_COMM_MEMB *memb, int trig)
1089 {
1090   memb->triggered=trig;
1091 }
1092
1093 int tr_comm_memb_is_triggered(TR_COMM_MEMB *memb)
1094 {
1095   return memb->triggered;
1096 }
1097
1098 void tr_comm_memb_reset_times_expired(TR_COMM_MEMB *memb)
1099 {
1100   memb->times_expired=0;
1101 }
1102
1103 /* bumps the expiration count */
1104 void tr_comm_memb_expire(TR_COMM_MEMB *memb)
1105 {
1106   /* avoid overflow */
1107   if (memb->times_expired+1>memb->times_expired)
1108     memb->times_expired++;
1109 }
1110
1111 unsigned int tr_comm_memb_get_times_expired(TR_COMM_MEMB *memb)
1112 {
1113   return memb->times_expired;
1114 }
1115
1116 TR_COMM_TABLE *tr_comm_table_new(TALLOC_CTX *mem_ctx)
1117 {
1118   TR_COMM_TABLE *ctab=talloc(mem_ctx, TR_COMM_TABLE);
1119   if (ctab!=NULL) {
1120     ctab->comms=NULL;
1121     ctab->memberships=NULL;
1122     ctab->idp_realms=NULL;
1123     ctab->rp_realms=NULL;
1124   }
1125   return ctab;
1126 }
1127
1128 void tr_comm_table_free(TR_COMM_TABLE *ctab)
1129 {
1130   talloc_free(ctab);
1131 }
1132
1133 static TR_REALM_ROLE tr_comm_memb_role(TR_COMM_MEMB *memb)
1134 {
1135   if (memb->rp!=NULL)
1136     return TR_ROLE_RP;
1137   if (memb->idp!=NULL)
1138     return TR_ROLE_IDP;
1139
1140   return TR_ROLE_UNKNOWN;
1141 }
1142
1143 void tr_comm_table_add_memb(TR_COMM_TABLE *ctab, TR_COMM_MEMB *new)
1144 {
1145   TR_COMM_MEMB *cur=NULL;
1146
1147   /* TODO: further validate the member (must have valid comm and realm) */
1148   if ((new->next!=NULL) || (new->origin_next!=NULL)) {
1149     tr_debug("tr_comm_table_add_memb: attempting to add member already in a list.");
1150   }
1151
1152   /* handle the empty list case */
1153   if (ctab->memberships==NULL) {
1154     ctab->memberships=new;
1155     talloc_steal(ctab, new);
1156     return;
1157   }
1158
1159   /* The list was not empty. See if we already have a membership for this realm/comm/role */
1160   switch (tr_comm_memb_role(new)) {
1161   case TR_ROLE_RP:
1162     cur=tr_comm_table_find_rp_memb(ctab,
1163                                    tr_rp_realm_get_id(tr_comm_memb_get_rp_realm(new)),
1164                                    tr_comm_get_id(tr_comm_memb_get_comm(new)));
1165     break;
1166   case TR_ROLE_IDP:
1167     cur=tr_comm_table_find_idp_memb(ctab,
1168                                     tr_idp_realm_get_id(tr_comm_memb_get_idp_realm(new)),
1169                                     tr_comm_get_id(tr_comm_memb_get_comm(new)));
1170     break;
1171   case TR_ROLE_UNKNOWN:
1172   default:
1173     tr_err("tr_comm_table_add_memb: realm with unknown role added.");
1174     cur=NULL;
1175   }
1176
1177   if (cur==NULL) {
1178     /* no entry for this realm/comm/role, tack it on the end */
1179     for (cur=ctab->memberships; cur->next!=NULL; cur=cur->next) { }
1180     cur->next=new;
1181   } else {
1182     /* Found an entry. Add to the end of its same-origin list. */
1183     while (cur->origin_next!=NULL) {
1184       cur=cur->origin_next;
1185     }
1186     cur->origin_next=new;
1187   }
1188
1189   talloc_steal(ctab, new);
1190 }
1191
1192 /* Remove memb from ctab. Do not free anything. Do nothing if memb not in ctab. */
1193 void tr_comm_table_remove_memb(TR_COMM_TABLE *ctab, TR_COMM_MEMB *memb)
1194 {
1195   TR_COMM_MEMB *cur=NULL; /* for walking the main list */
1196   TR_COMM_MEMB *orig_cur=NULL; /* for walking the origin list */
1197
1198   if ((memb==NULL) || (ctab->memberships==NULL))
1199     return;
1200
1201   /* see if it's the first member */
1202   if (ctab->memberships==memb) {
1203     if (memb->origin_next!=NULL) {
1204       memb->origin_next->next=memb->next;
1205       ctab->memberships=memb->origin_next;
1206     } else
1207       ctab->memberships=memb->next;
1208
1209     return;
1210   }
1211
1212   /* see if it's in first member's origin list */
1213   for (orig_cur=ctab->memberships;
1214        orig_cur->origin_next!=NULL;
1215        orig_cur=orig_cur->origin_next) {
1216     if (orig_cur->origin_next==memb) {
1217       orig_cur->origin_next=memb->origin_next;
1218       return;
1219     }
1220   }
1221
1222   /* now we have to walk the rest of the tree */
1223   for (cur=ctab->memberships; cur->next!=NULL; cur=cur->next) {
1224     if (cur->next==memb) {
1225       /* it matched an entry on the main list */
1226       if (memb->origin_next==NULL)
1227         cur->next=memb->next; /* no origin list, just drop memb */
1228       else {
1229         /* replace the entry in the main list with the next element on the origin list */
1230         memb->origin_next->next=memb->next;
1231         cur->next=memb->origin_next;
1232       }
1233       return;
1234     } else {
1235       /* it was not on the main list, walk the origin list */
1236       for (orig_cur=cur; orig_cur->origin_next!=NULL; orig_cur=orig_cur->origin_next) {
1237         if (orig_cur->origin_next==memb) {
1238           orig_cur->origin_next=memb->origin_next;
1239           return; /* just drop the element from the origin list */
1240         }
1241       }
1242     }
1243   }
1244   /* if we got here, cur->next was null. Still have to check the origin_next list */
1245   for (orig_cur=cur; orig_cur->origin_next!=NULL; orig_cur=orig_cur->origin_next) {
1246     if (orig_cur->origin_next==memb) {
1247       orig_cur->origin_next=memb->origin_next;
1248       return; /* just drop the element from the origin list */
1249     }
1250   }
1251 }
1252
1253 TR_NAME *tr_comm_memb_get_realm_id(TR_COMM_MEMB *memb)
1254 {
1255   if (memb->rp!=NULL)
1256     return tr_rp_realm_get_id(memb->rp);
1257   else
1258     return tr_idp_realm_get_id(memb->idp);
1259 }
1260
1261 /* find a membership from any origin */
1262 TR_COMM_MEMB *tr_comm_table_find_memb(TR_COMM_TABLE *ctab, TR_NAME *realm, TR_NAME *comm)
1263 {
1264   TR_COMM_MEMB *cur=NULL;
1265   TR_NAME *cur_realm_name=NULL;
1266
1267   for (cur=ctab->memberships; cur!=NULL; cur=cur->next) {
1268     cur_realm_name=tr_comm_memb_get_realm_id(cur);
1269     if (cur_realm_name==NULL) {
1270       tr_warning("tr_comm_table_find: encountered realm with no name.");
1271       continue;
1272     }
1273     if ((0==tr_name_cmp(realm, cur_realm_name)) &&
1274         (0==tr_name_cmp(comm, tr_comm_get_id(tr_comm_memb_get_comm(cur))))) {
1275       return cur;
1276     }
1277   }
1278   return NULL;
1279 }
1280
1281 /* find a membership from a particular origin */
1282 TR_COMM_MEMB *tr_comm_table_find_memb_origin(TR_COMM_TABLE *ctab, TR_NAME *realm, TR_NAME *comm, TR_NAME *origin)
1283 {
1284   TR_NAME *cur_orig=NULL;
1285   TR_COMM_MEMB *cur=tr_comm_table_find_memb(ctab, realm, comm);
1286   if (cur==NULL)
1287     return NULL; /* no match */
1288
1289   /* had a match for comm/realm; find origin match */
1290   while (cur!=NULL) {
1291     if (((origin==NULL) && (cur_orig==NULL)) ||
1292         ((origin!=NULL) && (cur_orig!=NULL) && (0==tr_name_cmp(origin, cur_orig))))
1293       return cur; /* found a match */
1294     cur=cur->origin_next;
1295   }
1296   return NULL; /* no match */
1297 }
1298
1299
1300 /* find an idp membership regardless of its origin */
1301 TR_COMM_MEMB *tr_comm_table_find_idp_memb(TR_COMM_TABLE *ctab, TR_NAME *realm, TR_NAME *comm)
1302 {
1303   TR_COMM_MEMB *cur=NULL;
1304   TR_IDP_REALM *idp_realm=NULL;
1305
1306   for (cur=ctab->memberships; cur!=NULL; cur=cur->next) {
1307     idp_realm=tr_comm_memb_get_idp_realm(cur);
1308     if (idp_realm==NULL)
1309       continue; /* was not an idp */
1310
1311     if ((0==tr_name_cmp(realm, idp_realm->realm_id)) &&
1312         (0==tr_name_cmp(comm, tr_comm_get_id(tr_comm_memb_get_comm(cur))))) {
1313       return cur;
1314     }
1315   }
1316   return NULL;
1317 }
1318
1319 /* find an idp membership from a particular origin */
1320 TR_COMM_MEMB *tr_comm_table_find_idp_memb_origin(TR_COMM_TABLE *ctab, TR_NAME *realm, TR_NAME *comm, TR_NAME *origin)
1321 {
1322   TR_NAME *cur_orig=NULL;
1323   TR_COMM_MEMB *cur=tr_comm_table_find_idp_memb(ctab, realm, comm);
1324   if (cur==NULL)
1325     return NULL; /* no match */
1326
1327   /* had a match for comm/realm; find origin match */
1328   while (cur!=NULL) {
1329     cur_orig=tr_comm_memb_get_origin(cur);
1330     if (((origin==NULL) && (cur_orig==NULL)) ||
1331         ((origin!=NULL) && (cur_orig!=NULL) && (0==tr_name_cmp(origin, cur_orig))))
1332       return cur; /* found a match */
1333     cur=cur->origin_next;
1334   }
1335   return NULL; /* no match */
1336 }
1337
1338 /* find an rp membership from any origin */
1339 TR_COMM_MEMB *tr_comm_table_find_rp_memb(TR_COMM_TABLE *ctab, TR_NAME *realm, TR_NAME *comm)
1340 {
1341   TR_COMM_MEMB *cur=NULL;
1342   TR_RP_REALM *rp_realm=NULL;
1343
1344   for (cur=ctab->memberships; cur!=NULL; cur=cur->next) {
1345     rp_realm=tr_comm_memb_get_rp_realm(cur);
1346     if (rp_realm==NULL)
1347       continue; /* was not an rp */
1348
1349     if ((0==tr_name_cmp(realm, tr_rp_realm_get_id(rp_realm))) &&
1350         (0==tr_name_cmp(comm, tr_comm_get_id(tr_comm_memb_get_comm(cur))))) {
1351       return cur;
1352     }
1353   }
1354   return NULL;
1355 }
1356
1357 /* find an rp membership from a particular origin */
1358 TR_COMM_MEMB *tr_comm_table_find_rp_memb_origin(TR_COMM_TABLE *ctab, TR_NAME *realm, TR_NAME *comm, TR_NAME *origin)
1359 {
1360   TR_NAME *cur_orig=NULL;
1361   TR_COMM_MEMB *cur=tr_comm_table_find_rp_memb(ctab, realm, comm);
1362   if (cur==NULL)
1363     return NULL; /* no match */
1364
1365   /* had a match for comm/realm; find origin match */
1366   while (cur!=NULL) {
1367     cur_orig=tr_comm_memb_get_origin(cur);
1368     if (((origin==NULL) && (cur_orig==NULL)) ||
1369         ((origin!=NULL) && (cur_orig!=NULL) && (0==tr_name_cmp(origin, cur_orig))))
1370       return cur; /* found a match */
1371     cur=cur->origin_next;
1372   }
1373   return NULL; /* no match */
1374 }
1375
1376 TR_COMM *tr_comm_table_find_comm(TR_COMM_TABLE *ctab, TR_NAME *comm_id)
1377 {
1378   return tr_comm_lookup(ctab->comms, comm_id);
1379 }
1380
1381 /**
1382  * Add a community to the table.
1383  *
1384  * Does not allow duplicate community ids.
1385  *
1386  * @param ctab
1387  * @param new
1388  * @return 0 on success, -1 on failure
1389  */
1390 int tr_comm_table_add_comm(TR_COMM_TABLE *ctab, TR_COMM *new)
1391 {
1392   if (tr_comm_table_find_comm(ctab, tr_comm_get_id(new)) != NULL)
1393     return -1;
1394
1395   tr_comm_add(ctab->comms, new);
1396   if (ctab->comms!=NULL)
1397     talloc_steal(ctab, ctab->comms); /* make sure it's in the right context */
1398   return 0;
1399 }
1400
1401 void tr_comm_table_remove_comm(TR_COMM_TABLE *ctab, TR_COMM *comm)
1402 {
1403   tr_comm_remove(ctab->comms, comm);
1404 }
1405
1406 TR_RP_REALM *tr_comm_table_find_rp_realm(TR_COMM_TABLE *ctab, TR_NAME *realm_id)
1407 {
1408   return tr_rp_realm_lookup(ctab->rp_realms, realm_id);
1409 }
1410
1411 void tr_comm_table_add_rp_realm(TR_COMM_TABLE *ctab, TR_RP_REALM *new)
1412 {
1413   tr_rp_realm_add(ctab->rp_realms, new);
1414   if (ctab->rp_realms!=NULL)
1415     talloc_steal(ctab, ctab->rp_realms); /* make sure it's in the right context */
1416 }
1417
1418 void tr_comm_table_remove_rp_realm(TR_COMM_TABLE *ctab, TR_RP_REALM *realm)
1419 {
1420   tr_rp_realm_remove(ctab->rp_realms, realm);
1421 }
1422
1423 TR_IDP_REALM *tr_comm_table_find_idp_realm(TR_COMM_TABLE *ctab, TR_NAME *realm_id)
1424 {
1425   return tr_idp_realm_lookup(ctab->idp_realms, realm_id);
1426 }
1427
1428 void tr_comm_table_add_idp_realm(TR_COMM_TABLE *ctab, TR_IDP_REALM *new)
1429 {
1430   tr_idp_realm_add(ctab->idp_realms, new);
1431   if (ctab->idp_realms!=NULL)
1432     talloc_steal(ctab, ctab->idp_realms); /* make sure it's in the right context */
1433 }
1434
1435 void tr_comm_table_remove_idp_realm(TR_COMM_TABLE *ctab, TR_IDP_REALM *realm)
1436 {
1437   tr_idp_realm_remove(ctab->idp_realms, realm);
1438 }
1439
1440
1441 /* how many communities in the table? */
1442 size_t tr_comm_table_size(TR_COMM_TABLE *ctab)
1443 {
1444   size_t count=0;
1445   TR_COMM *this=ctab->comms;
1446   while(this!=NULL) {
1447     this=this->next;
1448     count++;
1449   }
1450   return count;
1451 }
1452
1453 /* clean up unreferenced realms, etc */
1454 void tr_comm_table_sweep(TR_COMM_TABLE *ctab)
1455 {
1456   tr_rp_realm_sweep(ctab->rp_realms);
1457   tr_idp_realm_sweep(ctab->idp_realms);
1458   tr_comm_sweep(ctab->comms);
1459 }
1460
1461
1462 const char *tr_realm_role_to_str(TR_REALM_ROLE role)
1463 {
1464   switch(role) {
1465   case TR_ROLE_IDP:
1466     return "idp";
1467   case TR_ROLE_RP:
1468     return "rp";
1469   default:
1470     return NULL;
1471   }
1472 }
1473
1474 TR_REALM_ROLE tr_realm_role_from_str(const char *s)
1475 {
1476   if (strcmp(s, "idp")==0)
1477     return TR_ROLE_IDP;
1478   if (strcmp(s, "rp")==0)
1479     return TR_ROLE_RP;
1480   return TR_ROLE_UNKNOWN;
1481 }
1482
1483 static char *tr_comm_table_append_provenance(char *ctable_s, json_t *prov)
1484 {
1485   const char *s=NULL;
1486   char *tmp=NULL;
1487   size_t ii=0;
1488
1489   for (ii=0; ii<json_array_size(prov); ii++) {
1490     s=json_string_value(json_array_get(prov, ii));
1491     if (s!=NULL) {
1492       tmp=talloc_asprintf_append(ctable_s, "%s%s", s, ((ii + 1) == json_array_size(prov)) ? "" : ", ");
1493       if (tmp==NULL)
1494         return NULL;
1495       ctable_s=tmp;
1496     }
1497   }
1498   return ctable_s;
1499 }
1500
1501 char *tr_comm_table_to_str(TALLOC_CTX *mem_ctx, TR_COMM_TABLE *ctab)
1502 {
1503   TALLOC_CTX *tmp_ctx=talloc_new(NULL);
1504   char *ctable_s=NULL;
1505   char *tmp=NULL;
1506 #define append_on_success_helper(tab,tmp,expr) if(NULL==((tmp)=(expr))){(tab)=NULL;goto cleanup;}(tab)=(tmp)
1507
1508   TR_COMM_MEMB *p1=NULL; /* for walking the main list */
1509   TR_COMM_MEMB *p2=NULL; /* for walking the same-origin lists */
1510
1511   ctable_s=talloc_asprintf(tmp_ctx, ">> Membership table start <<\n");
1512   if (ctable_s==NULL)
1513     goto cleanup;
1514
1515   for (p1=ctab->memberships; p1!=NULL; p1=p1->next) {
1516     append_on_success_helper(
1517         ctable_s, tmp,
1518         talloc_asprintf_append(ctable_s, "* %s %s/%s\n  %s (%p) - prov: ",
1519                                tr_realm_role_to_str(tr_comm_memb_get_role(p1)),
1520                                tr_comm_memb_get_realm_id(p1)->buf,
1521                                tr_comm_get_id(tr_comm_memb_get_comm(p1))->buf,
1522                                (tr_comm_memb_get_origin(p1)==NULL)?"null origin":(tr_comm_memb_get_origin(p1)->buf),
1523                                p1));
1524
1525     append_on_success_helper(ctable_s, tmp, tr_comm_table_append_provenance(ctable_s, p1->provenance));
1526
1527     append_on_success_helper(ctable_s, tmp, talloc_strdup_append_buffer(ctable_s, "\n"));
1528
1529     for (p2=p1->origin_next; p2!=NULL; p2=p2->origin_next) {
1530       append_on_success_helper(
1531           ctable_s, tmp,
1532           talloc_asprintf_append(ctable_s, "  %s (%p) - prov: ",
1533           (tr_comm_memb_get_origin(p2)==NULL)?"null origin":(tr_comm_memb_get_origin(p2)->buf),
1534               p2));
1535       append_on_success_helper(ctable_s, tmp, tr_comm_table_append_provenance(ctable_s, p2->provenance));
1536       append_on_success_helper(ctable_s, tmp, talloc_strdup_append_buffer(ctable_s, "\n"));
1537     }
1538     append_on_success_helper(ctable_s, tmp, talloc_strdup_append_buffer(ctable_s, "\n"));
1539   }
1540
1541 cleanup:
1542   if (ctable_s!=NULL)
1543     talloc_steal(mem_ctx, ctable_s);
1544
1545   talloc_free(tmp_ctx);
1546   return ctable_s;
1547 }
1548
1549 void tr_comm_table_print(FILE *f, TR_COMM_TABLE *ctab)
1550 {
1551   char *s=tr_comm_table_to_str(NULL, ctab);
1552   if (s!=NULL) {
1553     tr_debug("%s", s);
1554     talloc_free(s);
1555   }
1556 }