Register a SA Forums Account here!
JOINING THE SA FORUMS WILL REMOVE THIS BIG AD, THE ANNOYING UNDERLINED ADS, AND STUPID INTERSTITIAL ADS!!!

You can: log in, read the tech support FAQ, or request your lost password. This dumb message (and those ads) will appear on every screen until you register! Get rid of this crap by registering your own SA Forums Account and joining roughly 150,000 Goons, for the one-time price of $9.95! We charge money because it costs us money per month for bills, and since we don't believe in showing ads to our users, we try to make the money back through forum registrations.
The Something Awful Forums > Main > Post Your Favorite: Carefully Curated > PYF List (LISTS ONLY)
 
  • Post
  • Reply
Hyperlynx
Sep 13, 2015

 I'm a big fan of
code:
std::list
edit: Actually, I'm also still pretty proud of the type-safe list I wrote in C, while I was in uni:

code:
#ifndef LINKLIST_H
#define LINKLIST_H

#include <string.h>
  /*memcpy()*/

/**********************\
|declaration generators|
\**********************/
#define GEN_LLIST_H(datatype)\
/*prerequisites: none*/\
typedef struct _LLIST_NODE##datatype\
{\
  datatype data;\
  struct _LLIST_NODE##datatype* next;\
  struct _LLIST_NODE##datatype* prev;\
}LLIST_NODE_##datatype;\
typedef struct\
{\
  LLIST_NODE_##datatype *first;\
  LLIST_NODE_##datatype *last;\
  int size;\
}LLIST_##datatype;\
void LLIST_InitList_##datatype(LLIST_##datatype *list);\
LLIST_NODE_##datatype* LLIST_PopFront_##datatype(LLIST_##datatype *list);\
void LLIST_ClearList_##datatype(LLIST_##datatype *list,\
  void (*destructor)(datatype*));\
LLIST_NODE_##datatype *LLIST_PushFront_##datatype(LLIST_##datatype *list,\
   datatype* data);\
LLIST_NODE_##datatype *LLIST_PushBack_##datatype(LLIST_##datatype *list,\
   datatype* data);\
LLIST_NODE_##datatype *LLIST_PopBack_##datatype(LLIST_##datatype* list);\
void LLIST_PopLink_##datatype(LLIST_##datatype* list, LLIST_NODE_##datatype*\
   link);

#define GEN_LLIST_BASICSEARCH_H(datatype)\
/*prerequisites: GEN_LLIST_H*/\
\
LLIST_NODE_##datatype* LLIST_Search_##datatype(LLIST_##datatype *list,\
                       datatype value, datatype tolerance, int forwards);\
LLIST_NODE_##datatype* LLIST_SearchNext_##datatype(LLIST_##datatype *list,\
                       datatype value,\
                       datatype tolerance, \
                       LLIST_NODE_##datatype *start,\
                       int forwards);

#define GEN_LLIST_ADVSEARCH_H(datatype)\
/*prerequisites: GEN_LLIST_H*/\
LLIST_NODE_##datatype* LLIST_Search_##datatype(LLIST_##datatype *list,\
                     datatype* value,\
                     int (*compareFunc)(datatype*,datatype*),\
                     int forwards);\
LLIST_NODE_##datatype* LLIST_SearchNext_##datatype(LLIST_##datatype *list,\
                       datatype* value,\
                       int (*compareFunc)(datatype*,datatype*),\
                       LLIST_NODE_##datatype *start,\
                       int forwards);

/***************\
|code generators|
\***************/
#define GEN_LLIST(datatype)\
\
void LLIST_InitList_##datatype(LLIST_##datatype *list)\
{\
  list->first = NULL;\
  list->last = NULL;\
  list->size = 0;\
}\
\
LLIST_NODE_##datatype* LLIST_PopFront_##datatype(LLIST_##datatype *list)\
{\
  if(list->first == NULL)\
    return NULL;\
\
  LLIST_NODE_##datatype *temp;\
  temp = list->first;\
\
  if(list->first == list->last) /*the list has just one link*/\
  {\
    list->first = NULL;\
    list->last = NULL;\
  }\
  else\
  {\
    list->first = temp->next;\
    list->first->prev = NULL;\
  }\
  --list->size;\
\
  return temp;\
}\
\
void LLIST_ClearList_##datatype(LLIST_##datatype *list,\
  void (*destructor)(datatype*))\
{\
  LLIST_NODE_##datatype *link;\
  link = LLIST_PopFront_##datatype(list);\
  while(link)\
  {\
    if(destructor)\
      destructor(&link->data);\
    free(link);\
    link = LLIST_PopFront_##datatype(list);\
  }\
}\
\
LLIST_NODE_##datatype *LLIST_PushFront_##datatype(LLIST_##datatype *list,\
                                      datatype* data)\
{\
  /*NTS: put in error checking*/\
  LLIST_NODE_##datatype *link;\
\
  link = (LLIST_NODE_##datatype *) malloc(sizeof(LLIST_NODE_##datatype));\
  memcpy(&link->data, data, sizeof(datatype));\
\
  link->prev = NULL;\
\
  if(list->last == NULL) /*the list is empty*/\
  {\
    list->last = link;\
    list->first = link;\
    link->next = NULL;\
  }\
  else\
  {\
    LLIST_NODE_##datatype* temp = list->first;\
    list->first = link;\
    link->next = temp;\
    temp->prev = link;\
  }\
  ++list->size;\
\
  return link;\
}\
\
LLIST_NODE_##datatype *LLIST_PushBack_##datatype(LLIST_##datatype *list,\
                                     datatype* data)\
{\
  /*NTS: put in error checking*/\
  LLIST_NODE_##datatype *link;\
\
  link = (LLIST_NODE_##datatype *) malloc(sizeof(LLIST_NODE_##datatype));\
  memcpy(&link->data, data, sizeof(datatype));\
\
  link->next = NULL;\
\
  if(list->first == NULL) /*the list is empty*/\
  {\
    list->last = link;\
    list->first = link;\
    link->prev = NULL;\
  }\
  else\
  {\
    LLIST_NODE_##datatype *temp = list->last;\
    list->last = link;\
    link->prev = temp;\
    temp->next = link;\
  }\
  ++list->size;\
\
  return link;\
}\
\
LLIST_NODE_##datatype *LLIST_PopBack_##datatype(LLIST_##datatype* list)\
{\
  if(list->last == NULL)\
    return NULL;\
\
  LLIST_NODE_##datatype *temp;\
  temp = list->last;\
\
  if(list->first == list->last) /*the list has just one link*/\
  {\
    list->first = NULL;\
    list->last = NULL;\
  }\
  else\
  {\
    list->last = temp->prev;\
    list->last->next = NULL;\
  }\
  --list->size;\
\
  return temp;\
}\
\
void LLIST_PopLink_##datatype(LLIST_##datatype* list, LLIST_NODE_##datatype* link)\
{\
  if(link == list->first)\
    link = LLIST_PopFront_##datatype(list);\
  else if(link == list->last)\
    link = LLIST_PopBack_##datatype(list);\
  else\
  {\
    link->next->prev = link->prev;\
    link->prev->next = link->next;\
    /*note: link->next or link->prev can only be NULL if there are only two
    links in the list, in which case it's already been handled by PopFront or
    PopBack.*/\
    --list->size;\
  }\
}

/*if the linked list is a list of primatives, we can generate a search function.
  We can't if it's a linked list of structures, because you can't compare
  structures with simple arithmetic operators (unless you're using C++, in which
  case you don't need these macros!)
  
  Anyway, use this macro to generate the search functions if your datatype is
  compatible with them. If you try it with structs you will get compile errors.
  
  Note that it won't work with a linked list of pointers.*/

#define GEN_LLIST_BASICSEARCH(datatype)\
\
LLIST_NODE_##datatype* LLIST_Search_##datatype(LLIST_##datatype *list,\
                       datatype value, datatype tolerance, int forwards)\
{\
\
  LLIST_NODE_##datatype* result;\
  datatype abs;\
  if(forwards)\
  {\
    result = list->first;\
    while(result!=NULL\
    && ( ((abs = result->data - value)<0)?-abs:abs > tolerance) )\
    {\
      result = result->next;\
    }\
  }\
  else\
  {\
    result = list->last;\
    while(result!=NULL\
    && ( ((abs = result->data - value)<0)?-abs:abs > tolerance) )\
    {\
      result = result->prev;\
    }\
  }\
  return result;\
}\
\
LLIST_NODE_##datatype* LLIST_SearchNext_##datatype(LLIST_##datatype *list,\
                       datatype value,\
                       datatype tolerance, LLIST_NODE_##datatype *start,\
                       int forwards)\
{\
  int abs;\
  if(forwards)\
  {\
    do\
    {\
      start = start->next;\
    }while(start!=NULL &&\
     ( ((abs = start->data - value)<0)?-abs:abs > tolerance) );\
  }\
  else\
  {\
    do\
    {\
      start = start->prev;\
    }while(start!=NULL &&\
     ( ((abs = start->data - value)<0)?-abs:abs > tolerance) );\
  }\
  return start;\
}
 
#define GEN_LLIST_ADVSEARCH(datatype)\
LLIST_NODE_##datatype* LLIST_Search_##datatype(LLIST_##datatype *list,\
                     datatype* criteria, int (*compareFunc)(datatype*,datatype*),\
                     int forwards)\
{\
  LLIST_NODE_##datatype* result;\
  if(forwards)\
  {\
    result = list->first;\
    while(result!=NULL && !compareFunc(&result->data, criteria))\
    {\
      result = result->next;\
    }\
  }\
  else\
  {\
    result = list->last;\
    while(result!=NULL && !compareFunc(&result->data, criteria))\
    {\
      result = result->prev;\
    }\
  }\
  return result;\
}\
\
LLIST_NODE_##datatype* LLIST_SearchNext_##datatype(LLIST_##datatype *list,\
                       datatype* criteria,\
                       int (*compareFunc)(datatype*,datatype*),\
                       LLIST_NODE_##datatype *start,\
                       int forwards)\
{\
  if(forwards)\
  {\
    do\
    {\
      start = start->next;\
    }while(start!=NULL && !compareFunc(&start->data, criteria));\
  }\
  else\
  {\
    do\
    {\
      start = start->prev;\
    }while(start!=NULL && !compareFunc(&start->data, criteria));\
  }\
  return start;\
}

#endif

Hyperlynx has a new favorite as of 13:02 on Jul 9, 2021

* # ¿ Jul 9, 2021 09:12
  • Quote
Adbot
ADBOT LOVES YOU

# ¿ Apr 26, 2024 17:43
  • Quote
  • 1
  • 2
  • 3
  • 4
  • 5
  • Post
  • Reply
The Something Awful Forums > Main > Post Your Favorite: Carefully Curated > PYF List (LISTS ONLY)