nsresult
nsHostRecord::Create(const nsHostKey *key, nsHostRecord **result)
{
    size_t hostLen = strlen(key->host) + 1;
    size_t size = hostLen + sizeof(nsHostRecord);

    nsHostRecord *rec = (nsHostRecord*) ::operator new(size);
    if (!rec)
        return NS_ERROR_OUT_OF_MEMORY;

    rec->host = ((char *) rec) + sizeof(nsHostRecord);
    rec->flags = RES_KEY_FLAGS(key->flags);
    rec->af = key->af;

    rec->_refc = 1; // addref
    rec->addr_info = nsnull;
    rec->addr = nsnull;
    rec->expiration = NowInMinutes();
    rec->resolving = PR_FALSE;
    PR_INIT_CLIST(rec);
    PR_INIT_CLIST(&rec->callbacks);
    memcpy((char *) rec->host, key->host, hostLen);

    *result = rec;
    return NS_OK;
}

PRStatus _PR_InitLock(PRLock *lock)
{
    if (_PR_MD_NEW_LOCK(&lock->ilock) != PR_SUCCESS) {
        return PR_FAILURE;
    }
    PR_INIT_CLIST(&lock->links);
    PR_INIT_CLIST(&lock->waitQ);
    return PR_SUCCESS;
}

PR_IMPLEMENT(PRAlarmID*) PR_SetAlarm(
    PRAlarm *alarm, PRIntervalTime period, PRUint32 rate,
    PRPeriodicAlarmFn function, void *clientData)
{
    /*
     * Create a new periodic alarm an existing current structure.
     * Set up the context and compute the first notify time (immediate).
     * Link the new ID into the head of the list (since it's notifying
     * immediately).
     */

    PRAlarmID *id = PR_NEWZAP(PRAlarmID);

    if (!id)
        return NULL;

    id->alarm = alarm;
    PR_INIT_CLIST(&id->list);
    id->function = function;
    id->clientData = clientData;
    id->period = period;
    id->rate = rate;
    id->epoch = id->nextNotify = PR_IntervalNow();
    (void)pr_PredictNextNotifyTime(id);

    PR_Lock(alarm->lock);
    PR_INSERT_BEFORE(&id->list, &alarm->timers);
    PR_NotifyCondVar(alarm->cond);
    PR_Unlock(alarm->lock);

    return id;
}  /* PR_SetAlarm */

/* Initialize the extension data block. */
void
ssl3_InitExtensionData(TLSExtensionData *xtnData, const sslSocket *ss)
{
    unsigned int advertisedMax;
    PRCList *cursor;

    /* Set things up to the right starting state. */
    PORT_Memset(xtnData, 0, sizeof(*xtnData));
    xtnData->peerSupportsFfdheGroups = PR_FALSE;
    PR_INIT_CLIST(&xtnData->remoteKeyShares);

    /* Allocate enough to allow for native extensions, plus any custom ones. */
    if (ss->sec.isServer) {
        advertisedMax = PR_MAX(PR_ARRAY_SIZE(certificateRequestHandlers),
                               PR_ARRAY_SIZE(tls13_cert_req_senders));
    } else {
        advertisedMax = PR_MAX(PR_ARRAY_SIZE(clientHelloHandlers),
                               PR_ARRAY_SIZE(clientHelloSendersTLS));
        ++advertisedMax; /* For the RI SCSV, which we also track. */
    }
    for (cursor = PR_NEXT_LINK(&ss->extensionHooks);
         cursor != &ss->extensionHooks;
         cursor = PR_NEXT_LINK(cursor)) {
        ++advertisedMax;
    }
    xtnData->advertised = PORT_ZNewArray(PRUint16, advertisedMax);
}

PRBool
nsSocketTransportService::ServiceEventQ()
{
    PRBool keepGoing;

    // grab the event queue
    PRCList eq;
    PR_INIT_CLIST(&eq);
    {
        nsAutoLock lock(mEventQLock);

        MoveCList(mEventQ, eq);

        // check to see if we're supposed to shutdown
        keepGoing = mInitialized;
    }
    // service the event queue
    PLEvent *event;
    while (!PR_CLIST_IS_EMPTY(&eq)) {
        event = PLEVENT_FROM_LINK(PR_LIST_HEAD(&eq));
        PR_REMOVE_AND_INIT_LINK(&event->link);

        PL_HandleEvent(event);
    }
    return keepGoing;
}

// static
nsresult
nsSHistory::Startup()
{
  nsCOMPtr<nsIPrefService> prefs = do_GetService(NS_PREFSERVICE_CONTRACTID);
  if (prefs) {
    nsCOMPtr<nsIPrefBranch> sesHBranch;
    prefs->GetBranch(nsnull, getter_AddRefs(sesHBranch));
    if (sesHBranch) {
      sesHBranch->GetIntPref(PREF_SHISTORY_SIZE, &gHistoryMaxSize);
    }

    // The goal of this is to unbreak users who have inadvertently set their
    // session history size to less than the default value.
    PRInt32  defaultHistoryMaxSize = 50;
    nsCOMPtr<nsIPrefBranch> defaultBranch;
    prefs->GetDefaultBranch(nsnull, getter_AddRefs(defaultBranch));
    if (defaultBranch) {
      defaultBranch->GetIntPref(PREF_SHISTORY_SIZE, &defaultHistoryMaxSize);
    }

    if (gHistoryMaxSize < defaultHistoryMaxSize) {
      gHistoryMaxSize = defaultHistoryMaxSize;
    }
    
    // Allow the user to override the max total number of cached viewers,
    // but keep the per SHistory cached viewer limit constant
    nsCOMPtr<nsIPrefBranch2> branch = do_QueryInterface(prefs);
    if (branch) {
      branch->GetIntPref(PREF_SHISTORY_MAX_TOTAL_VIEWERS,
                         &sHistoryMaxTotalViewers);
      nsSHistoryObserver* obs = new nsSHistoryObserver();
      if (!obs) {
        return NS_ERROR_OUT_OF_MEMORY;
      }
      branch->AddObserver(PREF_SHISTORY_MAX_TOTAL_VIEWERS,
                          obs, PR_FALSE);

      nsCOMPtr<nsIObserverService> obsSvc =
        do_GetService("@mozilla.org/observer-service;1");
      if (obsSvc) {
        // Observe empty-cache notifications so tahat clearing the disk/memory
        // cache will also evict all content viewers.
        obsSvc->AddObserver(obs,
                            NS_CACHESERVICE_EMPTYCACHE_TOPIC_ID, PR_FALSE);

        // Same for memory-pressure notifications
        obsSvc->AddObserver(obs, "memory-pressure", PR_FALSE);
      }
    }
  }
  // If the pref is negative, that means we calculate how many viewers
  // we think we should cache, based on total memory
  if (sHistoryMaxTotalViewers < 0) {
    sHistoryMaxTotalViewers = CalcMaxTotalViewers();
  }

  // Initialize the global list of all SHistory objects
  PR_INIT_CLIST(&gSHistoryList);
  return NS_OK;
}

nsresult
nsIOThreadPool::Init()
{
#if defined(PR_LOGGING)
    if (!gIOThreadPoolLog)
        gIOThreadPoolLog = PR_NewLogModule("nsIOThreadPool");
#endif

    mNumThreads = 0;
    mNumIdleThreads = 0;
    mShutdown = PR_FALSE;

    mLock = PR_NewLock();
    if (!mLock)
        return NS_ERROR_OUT_OF_MEMORY;

    mIdleThreadCV = PR_NewCondVar(mLock);
    if (!mIdleThreadCV)
        return NS_ERROR_OUT_OF_MEMORY;

    mExitThreadCV = PR_NewCondVar(mLock);
    if (!mExitThreadCV)
        return NS_ERROR_OUT_OF_MEMORY;

    PR_INIT_CLIST(&mEventQ);

    // We want to shutdown the i/o thread pool at xpcom-shutdown-threads time.
    nsCOMPtr<nsIObserverService> os = mozilla::services::GetObserverService();
    if (os)
        os->AddObserver(this, "xpcom-shutdown-threads", PR_FALSE);
    return NS_OK;
}

static SECStatus
init_blinding_params(RSABlindingParams *rsabp, RSAPrivateKey *key,
                     mp_int *n, unsigned int modLen)
{
    blindingParams * bp = rsabp->array;
    int i = 0;

    /* Initialize the list pointer for the element */
    PR_INIT_CLIST(&rsabp->link);
    for (i = 0; i < RSA_BLINDING_PARAMS_MAX_CACHE_SIZE; ++i, ++bp) {
    	bp->next = bp + 1;
	MP_DIGITS(&bp->f) = 0;
	MP_DIGITS(&bp->g) = 0;
	bp->counter = 0;
    }
    /* The last bp->next value was initialized with out
     * of rsabp->array pointer and must be set to NULL 
     */ 
    rsabp->array[RSA_BLINDING_PARAMS_MAX_CACHE_SIZE - 1].next = NULL;
    
    bp          = rsabp->array;
    rsabp->bp   = NULL;
    rsabp->free = bp;

    /* List elements are keyed using the modulus */
    SECITEM_CopyItem(NULL, &rsabp->modulus, &key->modulus);

    return SECSuccess;
}

void JavaDOMGlobals::TakeOutGarbage()
{
    nsAutoLock lock(garbageLock);

    PRUint32 count = 0;
    nsISupports* domo = NULL;

    PRCList* chain = NULL;
    PRCList* elem = NULL;
    for (chain = PR_LIST_HEAD(&garbage);
            chain != &garbage;
            chain = PR_NEXT_LINK(chain)) {

        delete elem;
        elem = chain;
        domo = ((jniDOMGarbage*) elem)->domObject;
        PR_LOG(log, PR_LOG_DEBUG,
               ("JavaDOMGlobals::TakeOutGarbage: Releasing %x\n", domo));
        domo->Release();
        domo = NULL;

        count++;
    }
    delete elem;
    PR_INIT_CLIST(&garbage);

    if (count)
        PR_LOG(log, PR_LOG_DEBUG,
               ("JavaDOMGlobals::TakeOutGarbage: Released %d objects\n", count));
}

/*
** Create a new condition variable.
** 	"lock" is the lock to use with the condition variable.
**
** Condition variables are synchronization objects that threads can use
** to wait for some condition to occur.
**
** This may fail if memory is tight or if some operating system resource
** is low.
*/
PR_IMPLEMENT(PRCondVar*) PR_NewCondVar(PRLock *lock)
{
    PRCondVar *cvar;

    PR_ASSERT(lock != NULL);

    cvar = PR_NEWZAP(PRCondVar);
    if (cvar) {
#ifdef _PR_GLOBAL_THREADS_ONLY
	if(_PR_MD_NEW_CV(&cvar->md)) {
		PR_DELETE(cvar);
		PR_SetError(PR_INSUFFICIENT_RESOURCES_ERROR, 0);
		return NULL;
	}
#endif
        if (_PR_MD_NEW_LOCK(&(cvar->ilock)) == PR_FAILURE) {
		PR_DELETE(cvar);
		PR_SetError(PR_INSUFFICIENT_RESOURCES_ERROR, 0);
		return NULL;
	}
    cvar->lock = lock;
	PR_INIT_CLIST(&cvar->condQ);

    } else {
        PR_SetError(PR_OUT_OF_MEMORY_ERROR, 0);
    }
    return cvar;
}

nsPACMan::nsPACMan()
  : mLoadPending(false)
  , mShutdown(false)
  , mScheduledReload(LL_MAXINT)
  , mLoadFailureCount(0)
{
  PR_INIT_CLIST(&mPendingQ);
}

PR_IMPLEMENT(PRLock*) PR_NewLock(void)
{
    PRLock *lock;

    if (!_pr_initialized) _PR_ImplicitInitialization();

    lock = PR_NEWZAP(PRLock);
    if (lock) {
        if (_PR_MD_NEW_LOCK(&lock->ilock) == PR_FAILURE) {
		PR_DELETE(lock);
		return(NULL);
	}
        PR_INIT_CLIST(&lock->links);
        PR_INIT_CLIST(&lock->waitQ);
    }
    return lock;
}

nsCacheEntryDescriptor::nsCacheEntryDescriptor(nsCacheEntry * entry,
                                               nsCacheAccessMode accessGranted)
    : mCacheEntry(entry),
      mAccessGranted(accessGranted)
{
    PR_INIT_CLIST(this);
    NS_ADDREF(nsCacheService::GlobalInstance());  // ensure it lives for the lifetime of the descriptor
}

/* Initialize the extension data block. */
void
ssl3_InitExtensionData(TLSExtensionData *xtnData)
{
    /* Set things up to the right starting state. */
    PORT_Memset(xtnData, 0, sizeof(*xtnData));
    xtnData->peerSupportsFfdheGroups = PR_FALSE;
    PR_INIT_CLIST(&xtnData->remoteKeyShares);
}

SECStatus
setupJobs(int maxJobs)
{
    int i;

    jobTable = (JOB *)PR_Calloc(maxJobs, sizeof(JOB));
    if (!jobTable)
        return SECFailure;

    PR_INIT_CLIST(&jobQ);
    PR_INIT_CLIST(&freeJobs);

    for (i = 0; i < maxJobs; ++i) {
        JOB *pJob = jobTable + i;
        PR_APPEND_LINK(&pJob->link, &freeJobs);
    }
    return SECSuccess;
}

void
nsGenConList::Insert(nsGenConNode* aNode)
{
  if (mFirstNode) {
    // Check for append.
    if (NodeAfter(aNode, Prev(mFirstNode))) {
      PR_INSERT_BEFORE(aNode, mFirstNode);
    }
    else {
      // Binary search.

      // the range of indices at which |aNode| could end up.
      // (We already know it can't be at index mSize.)
      PRUint32 first = 0, last = mSize - 1;

      // A cursor to avoid walking more than the length of the list.
      nsGenConNode *curNode = Prev(mFirstNode);
      PRUint32 curIndex = mSize - 1;

      while (first != last) {
        PRUint32 test = (first + last) / 2;
        if (last == curIndex) {
          for ( ; curIndex != test; --curIndex)
            curNode = Prev(curNode);
        } else {
          for ( ; curIndex != test; ++curIndex)
            curNode = Next(curNode);
        }

        if (NodeAfter(aNode, curNode)) {
          first = test + 1;
          // if we exit the loop, we need curNode to be right
          ++curIndex;
          curNode = Next(curNode);
        } else {
          last = test;
        }
      }
      PR_INSERT_BEFORE(aNode, curNode);
      if (curNode == mFirstNode) {
        mFirstNode = aNode;
      }
    }
  }
  else {
    // initialize list with first node
    PR_INIT_CLIST(aNode);
    mFirstNode = aNode;
  }
  ++mSize;

  NS_ASSERTION(aNode == mFirstNode || NodeAfter(aNode, Prev(aNode)),
               "sorting error");
  NS_ASSERTION(IsLast(aNode) || NodeAfter(Next(aNode), aNode),
               "sorting error");
}

  NS_DECL_ISUPPORTS
  NS_DECL_NSIDNSLISTENER

  PendingPACQuery(nsPACMan *pacMan, nsIURI *uri, nsPACManCallback *callback)
    : mPACMan(pacMan)
    , mURI(uri)
    , mCallback(callback)
  {
    PR_INIT_CLIST(this);
  }

/**
 * returns a string containing all the parameters in the ConfigStore hash set in the 
 * format key1=value1&&key2=value2&& ...
 * The list will be lexically ordered by parameter key values.
 * The string needs to be freed by the caller.
 **/
TPS_PUBLIC const char* ConfigStore::GetOrderedList()
{
    char *outstr = NULL;
    char *new_string = NULL;
    PRCList order_list;
    PR_INIT_CLIST(&order_list);

    PR_Lock(m_lock);
    PL_HashTableEnumerateEntries(m_root->getSet(), &OrderLoop, &order_list);
    PR_Unlock(m_lock);

    PRCList *current = PR_LIST_HEAD(&order_list);
    PRCList *next;

    outstr = (char*) PR_Malloc(128);
    int allocated = 128;
    int needed = 0;
    PR_snprintf(outstr, 128, "");

    while (current != &order_list) {
        OrderedEntry_t *entry = (OrderedEntry_t *) current;
        const char *value = GetConfigAsString(entry->key, "");

        if ((entry != NULL) && (entry->key != NULL)) {
            needed = PL_strlen(outstr) + PL_strlen(entry->key) + PL_strlen(value) + 4;
            if (allocated <= needed) {
                while (allocated <= needed) {
                    allocated = allocated * 2;
                }
                new_string = (char *)PR_Malloc(allocated);
                PR_snprintf(new_string, allocated, "%s", outstr);
                PR_Free(outstr);
                outstr = new_string;
            } 
                
            PL_strcat(outstr, entry->key);
            PL_strcat(outstr, "=");
            PL_strcat(outstr, value);

            // free the memory for the Ordered Entry
            PL_strfree(entry->key);
        }

        next = PR_NEXT_LINK(current);
        PR_REMOVE_AND_INIT_LINK(current);
        if (current != NULL) {
            PR_Free(current);
        }
        current = next;

        if (current != &order_list) PL_strcat(outstr, "&&");
    }
    return outstr;
}

nsDiskCacheBinding::nsDiskCacheBinding(nsCacheEntry* entry, nsDiskCacheRecord * record)
    :   mCacheEntry(entry)
    ,   mStreamIO(nsnull)
    ,   mDeactivateEvent(nsnull)
{
    NS_ASSERTION(record->ValidRecord(), "bad record");
    PR_INIT_CLIST(this);
    mRecord     = *record;
    mDoomed     = entry->IsDoomed();
    mGeneration = record->Generation();    // 0 == uninitialized, or data & meta using block files
}

static inline void
MoveCList(PRCList &from, PRCList &to)
{
    if (!PR_CLIST_IS_EMPTY(&from)) {
        to.next = from.next;
        to.prev = from.prev;
        to.next->prev = &to;
        to.prev->next = &to;
        PR_INIT_CLIST(&from);
    }             
}