util/dict.c

/* 
 *
 * Thread-safe Dictionary Using String Identifiers
 * Copyright 1998-2000 Scott Shambarger (scott@shambarger.net)
 *
 * This software is open source. Permission to use, copy, modify, and
 * distribute this software for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies.  No
 * warranty of any kind is expressed or implied.  Use at your own risk.
 *
 */

#include "cs_config.h"

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#include "neo_misc.h"
#include "neo_err.h"
#include "dict.h"
#include "skiplist.h"
#include "ulocks.h"


typedef struct dictValue {

  void *value;                                        /* value to set/update */
  dictNewValueCB new;                  /* new value callback (value is NULL) */
  dictUpdateValueCB update;         /* update value callback (value is NULL) */
  void *rock;                                   /* rock to pass to callbacks */

} *dictValuePtr;

typedef struct dictItem {

  struct dictItem *next;                            /* pointer to next value */
  char *id;                                                     /* string id */
  void *value;                                                      /* value */

} *dictItemPtr;

typedef struct dictEntry {

  dictItemPtr first;                                  /* first item in entry */
  BOOL deleted;               /* TRUE if entry has been passed to skipDelete */

} *dictEntryPtr;

typedef UINT32 (*dictHashFunc)(const char *str);
typedef int (*dictCompFunc)(const char *s1, const char *s2);

struct _dictCtx {

  pthread_mutex_t mList;                                /* list update mutex */
  skipList list;                                                /* skip list */

  dictHashFunc hash;                                        /* hash function */
  dictCompFunc comp;                                  /* id compare function */
  BOOL useCase;

  BOOL threaded;                                         /* TRUE if threaded */
  dictFreeValueFunc freeValue;                        /* free value callback */
  void *freeRock;                                   /* context for freeValue */
};

#undef DO_DEBUG

#ifdef DO_DEBUG
#include <sched.h>
#define DICT_LOCK(dict) \
  do { if((dict)->threaded) { sched_yield(); \
   mLock(&(dict)->mList); } } while(0)
#define DICT_HASH_BITS 16
#else
#define DICT_LOCK(dict) \
  if((dict)->threaded) mLock(&(dict)->mList)
#define DICT_HASH_BITS 65536
#endif
#define DICT_UNLOCK(dict) \
  if((dict)->threaded) mUnlock(&(dict)->mList)

/* entry is locked, so item may be added */
static NEOERR *dictNewItem(dictCtx dict, dictEntryPtr entry,
    const char *id, dictValuePtr newval, dictItemPtr *item) 
{
  dictItemPtr my_item;

  if (item != NULL)
    *item = NULL;

  /* check if we can set a new value */
  if(! (newval->value || newval->new))
    return nerr_raise(NERR_ASSERT, "value or new are NULL");

  if(! (my_item = calloc(1, sizeof(struct dictItem))))
    return nerr_raise(NERR_NOMEM, "Unable to allocate new dictItem");

  if(! (my_item->id = strdup(id))) {
    free(my_item);
    return nerr_raise(NERR_NOMEM, "Unable to allocate new id for dictItem");
  }

  /* set new value */
  if(newval->value) {
    my_item->value = newval->value;
  }
  else {
    NEOERR *err = STATUS_OK;

    err = newval->new(id, newval->rock, &(my_item->value));
    if (err != STATUS_OK)
    {
      /* new item callback failed, cleanup */
      free(my_item->id);
      free(my_item);

      return nerr_pass(err);
    }
  }

  my_item->next = entry->first;
  entry->first = my_item;
  if (item != NULL)
    *item = my_item;

  return STATUS_OK;
}

static void dictFreeItem(dictCtx dict, dictItemPtr item) {

  if(dict->freeValue)
    dict->freeValue(item->value, dict->freeRock);
  free(item->id);
  free(item);

  return;
}

/* list locked, so safe to walk entry */
static dictItemPtr dictFindItem(dictCtx dict, dictEntryPtr entry, 
                                const char *id, BOOL unlink) {

  dictItemPtr *prev, item;

  prev = &entry->first;

  for(item = entry->first; item; item = item->next) {

    if(! dict->comp(item->id, id)) {

      if(unlink)
        *prev = item->next;

      return item;
    }

    prev = &item->next;
  }

  return NULL;
}

static NEOERR *dictUpdate(dictCtx dict, dictEntryPtr entry, const char *id, 
                       dictValuePtr newval, void *lock) {

  NEOERR *err = STATUS_OK;
  dictItemPtr item = NULL;
  void *newValue;

  /* check for entry (maybe not found...) */
  if(! entry)
    return nerr_raise(NERR_NOT_FOUND, "Entry is NULL");

  /* only use entry if not deleted */
  if(! entry->deleted) {

    /* find item */
    if((item = dictFindItem(dict, entry, id, FALSE))) {
      
      if(newval->value) {

        if(dict->freeValue)
          dict->freeValue(item->value, dict->freeRock);
        
        item->value = newval->value;
      }
      else if(newval->update) {

        /* track error (if update fails) */
	err = newval->update(id, item->value, newval->rock);
      }
      else if((err = newval->new(id, newval->rock, &newValue)) == STATUS_OK) {

        if(dict->freeValue)
          dict->freeValue(item->value, dict->freeRock);
        
        item->value = newValue;
      }
      else {
        /* new item failed (don't remove old), indicate that update failed */
        item = NULL;
      }
    }
    else {
      
      /* add new item to entry */
      err = dictNewItem(dict, entry, id, newval, &item);
    }
  }

  /* release entry lock */
  skipRelease(dict->list, lock);

  return nerr_pass(err);
}

static NEOERR *dictInsert(dictCtx dict, UINT32 hash, const char *id, 
                          dictValuePtr newval) {

  dictEntryPtr entry;
  void *lock;
  NEOERR *err = STATUS_OK;

  /* create new item and insert entry */
  entry = calloc(1, sizeof(struct dictEntry));
  if (entry == NULL)
    return nerr_raise(NERR_NOMEM, "Unable to allocate memory for dictEntry");
    
  /* create/insert item (or cleanup) */
  err = dictNewItem(dict, entry, id, newval, NULL);
  if (err != STATUS_OK) return nerr_pass(err);

  /* if we insert, we're done */
  if((err = skipInsert(dict->list, hash, entry, FALSE)) == STATUS_OK)
    return STATUS_OK;

  /* failed to insert, cleanup */
  if(dict->freeValue && ! newval->value)
    dict->freeValue(entry->first->value, dict->freeRock);
  free(entry->first->id);
  free(entry->first);
  free(entry);

  /* check err */
  if (!nerr_handle(&err, NERR_DUPLICATE))
    return nerr_pass(err);
  
  /* cool, someone already inserted the entry before we got the lock */
  entry = skipSearch(dict->list, hash, &lock);

  /* update entry as normal (handles entry not found) */
  return nerr_pass(dictUpdate(dict, entry, id, newval, lock));
}

static UINT32 dictHash(dictCtx dict, const char *id) {

  UINT32 hash;

  hash = dict->hash(id) % DICT_HASH_BITS;

  /* ensure hash is valid for skiplist (modify consistently if not) */
  if(! (hash && (hash != (UINT32)-1)))
    hash = 1;

  return hash;
}

static NEOERR *dictModify(dictCtx dict, const char *id, dictValuePtr newval) 
{
  NEOERR *err;
  UINT32 hash;
  dictEntryPtr entry;
  void *lock = NULL;

  hash = dictHash(dict, id);

  /* find entry in list */
  entry = skipSearch(dict->list, hash, &lock);
    
  DICT_LOCK(dict);

  if((err = dictUpdate(dict, entry, id, newval, lock)) != STATUS_OK) 
  {
    /* insert new entry */
    nerr_ignore(&err);
    err = dictInsert(dict, hash, id, newval);
  }

  DICT_UNLOCK(dict);
  
  return nerr_pass(err);
}

NEOERR *dictSetValue(dictCtx dict, const char *id, void *value) {

  struct dictValue newval;

  assert(value);

  newval.value = value;

  return dictModify(dict, id, &newval);
}

NEOERR *dictModifyValue(dictCtx dict, const char *id, dictNewValueCB new, 
                     dictUpdateValueCB update, void *rock) {

  struct dictValue newval;

  if(! (new || update))
    return FALSE;

  newval.value = NULL;
  newval.new = new;
  newval.update = update;
  newval.rock = rock;

  return dictModify(dict, id, &newval);
}

void dictReleaseLock(dictCtx dict, void *lock) {

  /* release entry */
  DICT_UNLOCK(dict);

  /* release skip entry */
  skipRelease(dict->list, lock);

  return;
}

void dictCleanup(dictCtx dict, dictCleanupFunc cleanup, void *rock) {

  dictItemPtr *prev, item, next;
  dictEntryPtr entry;
  UINT32 key = 0;
  void *lock;

  while((entry = skipNext(dict->list, &key, &lock))) {

    DICT_LOCK(dict);

    prev = &entry->first;
    
    for(item = entry->first; item; item = next) {
      
      next = item->next;
      
      if(cleanup(item->id, item->value, rock)) {
        
        /* remove item */
        *prev = item->next;
        dictFreeItem(dict, item);
      }
      else {
        /* update reference pointer */
        prev = &item->next;
      }
    }

    /* delete entry if last item removed */
    if(! entry->first) {

      entry->deleted = TRUE;

      skipDelete(dict->list, key);
    }
    
    dictReleaseLock(dict, lock);
  }

  return;
}

void *dictSearch(dictCtx dict, const char *id, void **plock) {

  dictEntryPtr entry;
  dictItemPtr item;
  UINT32 hash;
  void *lock;
  void *value;

  hash = dictHash(dict, id);

  /* find entry in list */
  if(! (entry = skipSearch(dict->list, hash, &lock)))
    return NULL;

  /* lock entry */
  DICT_LOCK(dict);

  /* find item */
  if((item = dictFindItem(dict, entry, id, FALSE))) {

    value = item->value;

    if(plock)
      *plock = lock;
    else
      dictReleaseLock(dict, lock);

    return value;
  }

  dictReleaseLock(dict, lock);

  return NULL;
}

void *dictNext (dictCtx dict, char **id, void **plock)
{
  dictEntryPtr entry;
  dictItemPtr item;
  UINT32 hash;
  void *lock;
  void *value;

  /* Handle the first one special case */
  if (*id == NULL)
  {
    hash = 0;
    /* find entry in list */
    if(! (entry = skipNext (dict->list, &hash, &lock)))
      return NULL;

    /* lock entry */
    DICT_LOCK(dict);

    /* Take first item in list */
    item = entry->first;

    if (item != NULL)
    {
      value = item->value;
      *id = item->id;

      if(plock)
	*plock = lock;
      else
	dictReleaseLock(dict, lock);

      return value;
    }

    dictReleaseLock(dict, lock);

    return NULL;
  }
  else
  {
    hash = dictHash(dict, *id);

    /* find entry in list */
    entry = skipSearch (dict->list, hash, &lock);

    if (entry == NULL)
    {
      entry = skipNext (dict->list, &hash, &lock);
      /* Not found, we're at the end of the dict */
      if (entry == NULL)
	return NULL;
    }

    /* lock entry */
    DICT_LOCK(dict);

    item = dictFindItem(dict, entry, *id, FALSE);
    if (item != NULL)
    {
      if (item->next != NULL)
      {
	item = item->next;
      }
      else
      {
	/* we have to move to the next skip entry */
	entry = skipNext (dict->list, &hash, &lock);
	/* Not found, we're at the end of the dict */
        item = entry?entry->first:NULL;
        
	if(! item) {
          dictReleaseLock(dict, lock);
	  return NULL;
        }

      }
      value = item->value;
      *id = item->id;

      if(plock)
	*plock = lock;
      else
	dictReleaseLock(dict, lock);

      return value;
    }

    dictReleaseLock(dict, lock);
  }

  return NULL;
}

BOOL dictRemove(dictCtx dict, const char *id) {

  dictEntryPtr entry;
  dictItemPtr item;
  UINT32 hash;
  void *lock;

  hash = dictHash(dict, id);

  /* find entry in list */
  if(! (entry = skipSearch(dict->list, hash, &lock)))
    return FALSE;

  /* lock entry */
  DICT_LOCK(dict);

  /* find/unlink/free item */
  if((item = dictFindItem(dict, entry, id, TRUE)))
    dictFreeItem(dict, item);

  dictReleaseLock(dict, lock);

  return item ? TRUE : FALSE;
}

/* called by skipList when safe to destroy entry */
static void dictDestroyEntry(void *value, void *ctx) {

  dictItemPtr item, next;
  dictEntryPtr entry;

  entry = value;

  for(item = entry->first; item; item = next) {

    next = item->next;
    dictFreeItem(ctx, item);
    item = next;
  }

  free(value);

  return;
}

NEOERR *dictCreate(dictCtx *rdict, BOOL threaded, UINT32 root, UINT32 maxLevel, 
    UINT32 flushLimit, BOOL useCase, dictFreeValueFunc freeValue, void *freeRock) 
{
  NEOERR *err;
  dictCtx dict;

  *rdict = NULL;

  do {

    if(! (dict = calloc(1, sizeof(struct _dictCtx))))
      return nerr_raise (NERR_NOMEM, "Unable to allocate memory for dictCtx");

    dict->useCase = useCase;
    dict->hash = python_string_hash;
    if(useCase) {
      dict->comp = strcmp;
    }
    else {
      /* dict->hash = uhashUpper; */
      dict->comp = strcasecmp;
    }

    dict->threaded = threaded;
    dict->freeValue = freeValue;
    dict->freeRock = freeRock;

    err = skipNewList(&(dict->list), threaded, root, maxLevel, 
	    flushLimit, dictDestroyEntry, dict);
    if (err != STATUS_OK) break;

    if (threaded)
    {
      err = mCreate(&(dict->mList));
      if (err != STATUS_OK) break;
    }

    *rdict = dict;
    return STATUS_OK;

  } while(FALSE);

  dictDestroy(dict);

  return nerr_pass(err);
}

void dictDestroy(dictCtx dict) {

  if(! dict)
    return;

  skipFreeList(dict->list);

  mDestroy(&dict->mList);

  free(dict);

  return;
}