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