/*******************************************************************
 *
 * Description:     Delete a key in the hash table.
 *
 * Modified args:   None
 *
 * Return value:    0 if deleted, negative if not found.
 *
 *******************************************************************/
int
hash_delete(HASH_TABLE *ptbl, char *key)
{
    HASH_DATUM key_datum;
    struct hash_table_datum *entry;
    struct hash_table_datum *prev_entry = NULL;
    int index;

    key_datum.size = strlen(key) + 1;
    key_datum.data = key;
    
    index = HASH(&key_datum);
    entry = ((struct hash_table_datum **)ptbl)[index];

    while (entry != NULL && (key_datum.size != entry->key.size || (memcmp(key_datum.data, entry->key.data, key_datum.size) != 0)))
    {
        prev_entry = entry;      /* Keep the previous entry, we need it when unlinking */
        entry = entry->next;
    }

    if (entry != NULL)
    {
        /* Unlink the old entry, and free memory */
        if (prev_entry != NULL)
        {
            prev_entry->next = entry->next;
        }
        else
        {
            /* Old entry was the first in the list */
            ((struct hash_table_datum **)ptbl)[index] = entry->next;
        }
        HASH_FREE(entry);

        return 0;
    }
    
    return -1;  /* Not found */
}

/* allocate the object, creating the object */
struct Data *data_alloc( void ) {
  struct Data *data;
  int index;

  if ( (data = malloc( sizeof( struct Data ) )) != NULL ) {
    data->count = 1;
    if ( pthread_mutex_init( &data->lock, NULL ) != 0 ) {
      free( data );
      return NULL;
    }
    index = HASH( data );
    pthread_mutex_lock( &tablelock );
    data->next = table[ index ];
    /* I think it should be = data; */
    table[ index ] = data->next;
    pthread_mutex_lock( &data->lock );
    pthread_mutex_unlock( &tablelock );
    data->number = -9999;
    pthread_mutex_unlock( data->lock );
  }
  return data;
}

/*
**	A channel is uniquely identified by a socket.
**	Note that we don't create the input and output stream - they are 
**	created later.
**
**	We only keep a hash on sockfd's as we don't have to look for channels
**	for ANSI file descriptors.
*/
PUBLIC HTChannel * HTChannel_new (SOCKET sockfd, FILE * fp, BOOL active)
{
    HTList * list = NULL;
    HTChannel * ch = NULL;
    int hash = sockfd < 0 ? 0 : HASH(sockfd);
    HTTRACE(PROT_TRACE, "Channel..... Hash value is %d\n" _ hash);
    if (!channels) {
	if (!(channels = (HTList **) HT_CALLOC(HT_M_HASH_SIZE,sizeof(HTList*))))
	    HT_OUTOFMEM("HTChannel_new");
    }
    if (!channels[hash]) channels[hash] = HTList_new();
    list = channels[hash];
    if ((ch = (HTChannel *) HT_CALLOC(1, sizeof(HTChannel))) == NULL)
	HT_OUTOFMEM("HTChannel_new");	    
    ch->sockfd = sockfd;
    ch->fp = fp;
    ch->active = active;
    ch->semaphore = 1;
    ch->channelIStream.isa = &ChannelIStreamIsa;
    ch->channelOStream.isa = &ChannelOStreamIsa;
    ch->channelIStream.channel = ch;
    ch->channelOStream.channel = ch;
    HTList_addObject(list, (void *) ch);

#ifdef HT_MUX
	    /*
	    **  Create a MUX channel and do a connect on this channel with a
	    **  new session.
	    */
	    {
		HTProtocol * protocol = HTNet_protocol(net);
		HTMuxChannel * muxch = HTMuxChannel_new(me);
		net->session = HTMuxSession_connect(muxch, net, HTProtocol_id(protocol));
	    }
#endif /* HT_MUX */

    HTTRACE(PROT_TRACE, "Channel..... Added %p to list %p\n" _ ch _ list);
    return ch;
}

/* Note that even the slow path doesn't lock.	*/
void *  PREFIXED(slow_getspecific) (tsd * key, unsigned long qtid,
				    tse * volatile * cache_ptr) {
    pthread_t self = pthread_self();
    unsigned hash_val = HASH(self);
    tse *entry = key -> hash[hash_val];

    GC_ASSERT(qtid != INVALID_QTID);
    while (entry != NULL && entry -> thread != self) {
	entry = entry -> next;
    } 
    if (entry == NULL) return NULL;
    /* Set cache_entry.		*/
        entry -> qtid = qtid;
		/* It's safe to do this asynchronously.  Either value 	*/
		/* is safe, though may produce spurious misses.		*/
		/* We're replacing one qtid with another one for the	*/
		/* same thread.						*/
	*cache_ptr = entry;
		/* Again this is safe since pointer assignments are 	*/
		/* presumed atomic, and either pointer is valid.	*/
    return entry -> value;
}

// ------------------------------------------------------------------
size_t __checked_pointer_table::getSize(const void* address)
{
	int index = HASH_UNCHECKED(address);
	__node* node = uncheckedTable[index];

	while((node != 0) && (node->address != address))
		node = node->next;

	if(node != 0)
		return node->size;

	index = HASH(address);
	node = table[index];

	while((node != 0) && (node->address != address))
		node = node->next;

	if(node != 0)		
		return node->size;

	return (size_t)-1;
}

/*
 - initialize - hand-craft a cache entry for startup, otherwise get ready
 ^ static struct sset *initialize(struct vars *, struct dfa *, chr *);
 */
static struct sset *
initialize(
    struct vars *v,		/* used only for debug flags */
    struct dfa *d,
    chr *start)
{
    struct sset *ss;
    int i;

    /*
     * Is previous one still there?
     */

    if (d->nssused > 0 && (d->ssets[0].flags&STARTER)) {
	ss = &d->ssets[0];
    } else {			/* no, must (re)build it */
	ss = getvacant(v, d, start, start);
	for (i = 0; i < d->wordsper; i++) {
	    ss->states[i] = 0;
	}
	BSET(ss->states, d->cnfa->pre);
	ss->hash = HASH(ss->states, d->wordsper);
	assert(d->cnfa->pre != d->cnfa->post);
	ss->flags = STARTER|LOCKED|NOPROGRESS;

	/*
	 * lastseen dealt with below
	 */
    }

    for (i = 0; i < d->nssused; i++) {
	d->ssets[i].lastseen = NULL;
    }
    ss->lastseen = start;	/* maybe untrue, but harmless */
    d->lastpost = NULL;
    d->lastnopr = NULL;
    return ss;
}

struct foo *
foo_alloc(void) /* allocate the object */
{
	struct foo	*fp;
	int			idx;

	if ((fp = malloc(sizeof(struct foo))) != NULL) {
		fp->f_count = 1;
		if (pthread_mutex_init(&fp->f_lock, NULL) != 0) {
			free(fp);
			return(NULL);
		}
		idx = HASH(fp);
		pthread_mutex_lock(&hashlock);
		fp->f_next = fh[idx];
		fh[idx] = fp->f_next;
		pthread_mutex_lock(&fp->f_lock);
		pthread_mutex_unlock(&hashlock);
		/* ... continue initialization ... */
		pthread_mutex_unlock(&fp->f_lock);
	}
	return(fp);
}

void fooRele(struct Foo *fp){
    struct Foo *tfp;
    int idx;
    
    pthread_mutex_lock(&hashLock);
    if(-- fp -> fCount == 0){
        idx = HASH(fp -> fId);
        tfp = fh[idx];
        if(tfp == fp){
            fh[idx] = fp -> fNext;
        }else{
            while(tfp -> fNext != fp){
                tfp = tfp -> fNext;
            }
            tfp -> fNext = fp -> fNext;
        }
        pthread_mutex_unlock(&hashLock);
        pthread_mutex_destroy(&fp -> fLock);
        free(fp);
    }else{
        pthread_mutex_unlock(&hashLock);
    }
}

void __pspgl_hash_insert (struct hashtable *h, unsigned long key, void *value)
{
	unsigned long b = HASH(key);
	struct hashentry *ent;

	if (key <= h->maxkey) {
		for (ent=h->buckets[b]; ent!=NULL; ent=ent->next) {
			if (ent->key == key) {
				ent->data = value;
				return;
			}
		}
	}

	if ((ent = malloc(sizeof(*ent)))) {
		ent->key = key;
		ent->data = value;
		ent->next = h->buckets[b];
		h->buckets[b] = ent;
		if (key > h->maxkey)
			h->maxkey = key;
	}
}

/*
 * returned value is not dup-ed
 */
extern char *
kvs_get(char *key)
{
	kvs_bucket_t *bucket;
	char *val = NULL;
	int i;

	debug3("mpi/pmi2: in kvs_get, key=%s", key);

	bucket = &kvs_hash[HASH(key)];
	if (bucket->count > 0) {
		for(i = 0; i < bucket->count; i ++) {
			if (! xstrcmp(key, bucket->pairs[KEY_INDEX(i)])) {
				val = bucket->pairs[VAL_INDEX(i)];
				break;
			}
		}
	}

	debug3("mpi/pmi2: out kvs_get, val=%s", val);

	return val;
}

int
hash_insert (
    void       *el,
    hashtab    *htab)
{
    int         i;
    hashnode   *hnode;

    ++htab->cardinal;
    if (htab->cardinal > htab->size * 10)
    {
        restructure (htab);
    }
    hnode = new hashnode[sizeof (*hnode)];
    if (hnode == NULL)
        return 1;

    i = HASH (htab, el);
    hnode->next = htab->vec[i];
    hnode->el = el;
    htab->vec[i] = hnode;
    return 0;
}

//-----------------------------------------------------------------
//
// Function:   SearchStructure
//
// Purpose:    Searches the profiler data struture for the function
//             name.
//
// Input:      Profile  -  pointer to profiler data structure
//             Symbol   -  pointer to name to search  for
//
// Output:     SProfileRecord  -  pointer to the entry that contains
//                                the name, Symbol, if found.  Otherwise
//                                NULL is returned.
//
//------------------------------------------------------------------
SProfileRecord * SearchStructure (SProfile *Profile, UCHAR *Symbol)
{
   unsigned long cHashNumber;
   unsigned long iBucket;
   SProfileRecord *pProfileRecord;

   // Hash on the first + last letters of the symbol
   cHashNumber = (unsigned long)Symbol[0] + (unsigned long)Symbol[strlen(Symbol)-1];
   iBucket = HASH(cHashNumber);

   // Search the bucket for the corresponding entry
   pProfileRecord = Profile->Buckets[iBucket];

   while (pProfileRecord != NULL)
   {
      if (!strcmp(pProfileRecord->Symbol, Symbol))
         break;
      else
         pProfileRecord = pProfileRecord->pNext;
   }

   return (pProfileRecord);
}

/**
 * Find request by the id we used when relaying it and remove it from
 * id hash and timeout list.  Called from pxdns_pmgr_pump() when reply
 * comes.
 */
static struct request *
pxdns_request_find(struct pxdns *pxdns, u16_t id)
{
    struct request *req = NULL;

    sys_mutex_lock(&pxdns->lock);

    /* find request in the id->req hash */
    for (req = pxdns->request_hash[HASH(id)]; req != NULL; req = req->next_hash) {
        if (req->id == id) {
            break;
        }
    }

    if (req != NULL) {
        pxdns_hash_del(pxdns, req);
        pxdns_timeout_del(pxdns, req);
        --pxdns->active_queries;
    }

    sys_mutex_unlock(&pxdns->lock);
    return req;
}

struct Foo *fooAlloc(int id){
    struct Foo *fp;
    int idx;

    if((fp = (Foo *)malloc(sizeof(struct Foo))) != NULL){
        fp -> fCount = 1;
        fp -> fId = id;
        if(pthread_mutex_init(&fp -> fLock, NULL) != 0){
            free(fp);
            return NULL;
        }

        idx = HASH(id);
        pthread_mutex_lock(&hashLock);
        fp -> fNext = fh[idx];
        fh[idx] = fp;
        pthread_mutex_lock(&fp -> fLock);
        pthread_mutex_unlock(&hashLock);
        pthread_mutex_unlock(&fp -> fLock);
    }

    return fp;
}

    ///----------------------------------------------------------------------------//
    ///--------------------- UPDATE SECTION ---------------------------------------//
    ///----------------------------------------------------------------------------//
    Scene::Enum update(float dt) override {
        Entity animLogo = e(HASH("logo/logo_anim", 0xed78c546));

        if (timeAccum > 0.8 + 0.05 + 0.25 + 0.05) {
            RENDERING(animLogo)->show = false;
            return Scene::Menu;
        } else if (timeAccum > 0.8 + 0.05 + 0.25) {
            RENDERING(animLogo)->texture = theRenderingSystem.loadTextureFile("soupe_logo2_365_331");
        }
        else if (timeAccum > 0.8 + 0.05) {
            if (!soundPlayed) {
                SOUND(animLogo)->sound = theSoundSystem.loadSoundFile("sounds/logo_blink.ogg");
                soundPlayed = true;
            }
            RENDERING(animLogo)->texture = theRenderingSystem.loadTextureFile("soupe_logo3_365_331");
        }
        else if (timeAccum > 0.8) {
            RENDERING(animLogo)->show = true;
        }

        timeAccum += dt;
        return Scene::Logo;
    }

/* thread exit.                                                         */
GC_INNER void GC_remove_specific(tsd * key)
{
    pthread_t self = pthread_self();
    unsigned hash_val = HASH(self);
    tse *entry;
    tse **link = &key->hash[hash_val].p;

    pthread_mutex_lock(&(key -> lock));
    entry = *link;
    while (entry != NULL && entry -> thread != self) {
      link = &(entry -> next);
      entry = *link;
    }
    /* Invalidate qtid field, since qtids may be reused, and a later    */
    /* cache lookup could otherwise find this entry.                    */
    if (entry != NULL) {
      entry -> qtid = INVALID_QTID;
      *link = entry -> next;
      /* Atomic! concurrent accesses still work.        */
      /* They must, since readers don't lock.           */
      /* We shouldn't need a volatile access here,      */
      /* since both this and the preceding write        */
      /* should become visible no later than            */
      /* the pthread_mutex_unlock() call.               */
    }
    /* If we wanted to deallocate the entry, we'd first have to clear   */
    /* any cache entries pointing to it.  That probably requires        */
    /* additional synchronization, since we can't prevent a concurrent  */
    /* cache lookup, which should still be examining deallocated memory.*/
    /* This can only happen if the concurrent access is from another    */
    /* thread, and hence has missed the cache, but still...             */

    /* With GC, we're done, since the pointers from the cache will      */
    /* be overwritten, all local pointers to the entries will be        */
    /* dropped, and the entry will then be reclaimed.                   */
    pthread_mutex_unlock(&(key -> lock));
}

Token
idf_hashed(const char *str) {
	int32 h = 0;

	/* let's be careful about ranges; if done wrong it's hard to debug */
	while (*str) {
		int ch = *str++ & 0377;

		/* ignore spaces in spaced words */
		if (ch == ' ') continue;

		/* -1 <= h <= 2^31-1 */
		h = HASH(h, ch);
		/* -2^31 <= h <= 2^31-1 */
		if (h < 0) {
			/* -2^31 <= h <= -1 */
			h += 2147483647;	/* 2^31-1 */
			/* -1 <= h <= 2^31-2 */
		}
		else {
			/* 0 <= h <= 2^31-1 */
		}
		/* -1 <= h <= 2^31-1 */
	}
	/* -1 <= h <= 2^31-1 */
	if (h < 0) {
		/* h = -1 */
		h = 0;
	}
	/* 0 <= h <= 2^31-1 */
	h %= (N_TOKENS - N_REGULAR_TOKENS - 1);
	/* 0 <= h < N_TOKENS - N_REGULAR_TOKENS - 1 */
	h += N_REGULAR_TOKENS;
	/* N_REGULAR_TOKENS <= h < N_TOKENS - 1 */
	return int2Token(h);
	/* this avoids the regular tokens and End_Of_Line */
}

/* release a reference to the object */
void data_release( struct Data *data ) {
  struct Data *tmp;
  int index;

  pthread_mutex_lock( &data->lock );
  if ( data->count == 1 ) {
    /* it is the last reference */
    pthread_mutex_unlock( &data->lock );
    pthread_mutex_lock( &tablelock );
    pthread_mutex_lock( &data->lock );
    /* need to recheck the condition */
    if ( data->count != 1 ) {
      data->count--;
      pthread_mutex_unlock( &data->lock );
      pthread_mutex_unlock( &tablelock );
      return;
    }
    /* remove it from list */
    index = HASH( data );
    tmp = table[ index ];
    if ( tmp == data ) {
      table[ index ] = data->next;
    } else {
      while ( tmp->next != data ) {
	tmp = data->next;
      }
      tmp->next = data->next;
    }
    pthread_mutex_unlock( &tablelock );
    pthread_mutex_unlock( &data->lock );
    pthread_mutex_destroy( &data->lock );
    free( data );
  } else {
    data->count--;
    pthread_mutex_unlock( &data->lock );
  }
}

int hashset_add(hashset_p set, const void *item, size_t bytes)
{
	slot_p slot = NULL, new_slot = NULL;

	slotlist_p slotlist = &set->slotlists[HASH(set, item, bytes) % set->slotlists_n];
	slot_p *pslot = &slotlist->list;

	int is_new = !(slot = *pslot);

	while (slot) {
		if (!CMP(set, &slot->data, item, bytes)) {
			return -1;
		}
		pslot = &slot->next;
		slot = *pslot;
	}

	*pslot = new_slot = (slot_p) malloc(bytes + sizeof(slot_p));
	if (!new_slot) {
		return -2;
	}
	new_slot->next = NULL;

	memcpy(&new_slot->data, item, bytes);

	if (!set->non_null) {
		set->non_null = slotlist;
	} else if (is_new) {
		set->non_null->pre = slotlist;
		slotlist->next = set->non_null;
		set->non_null = slotlist;
	}

	++set->size;

	return 0;
}

void
foo_rele(struct foo *fp) /* release a reference to the object */
{
	struct foo	*tfp;
	int			idx;

	pthread_mutex_lock(&fp->f_lock);
	if (fp->f_count == 1) { /* last reference */
		pthread_mutex_unlock(&fp->f_lock);
		pthread_mutex_lock(&hashlock);
		pthread_mutex_lock(&fp->f_lock);
		/* need to recheck the condition */
		if (fp->f_count != 1) {
			fp->f_count--;
			pthread_mutex_unlock(&fp->f_lock);
			pthread_mutex_unlock(&hashlock);
			return;
		}
		/* remove from list */
		idx = HASH(fp);
		tfp = fh[idx];
		if (tfp == fp) {
			fh[idx] = fp->f_next;
		} else {
			while (tfp->f_next != fp)
			tfp = tfp->f_next;
			tfp->f_next = fp->f_next;
		}
		pthread_mutex_unlock(&hashlock);
		pthread_mutex_unlock(&fp->f_lock);
		pthread_mutex_destroy(&fp->f_lock);
		free(fp);
		} else {
			fp->f_count--;
			pthread_mutex_unlock(&fp->f_lock);
		}
}